Problem finding key in STL map with gcc 4.1.0

[graham.macpherson]

I have 2 Suse Linux PCs which I compile my code on. Until recently
they both had gcc 4.0.X on them, but I upgraded one of them to gcc
4.1.0. I have come across a very strange problem in the following code
which uses an STL map:

void Distribution::AddToDistribution (double& valueToAddToDistribution)
{
int n;
n = static_cast<int>(valueToAddToDistribution/itsBinWidth);

float keyToAddTo;
keyToAddTo = (n + 0.5)*itsBinWidth;

// std::cout << "n: " << n << ", keyToAddTo: " << keyToAddTo <<
std::endl;

std::map<float, int>::iterator addToDistributionIterator;

addToDistributionIterator = itsDistributionValues.find(keyToAddTo);

if (addToDistributionIterator == itsDistributionValues.end()) // Key
not found in map
{
itsDistributionValues[keyToAddTo] = 1;
}

else // Key present in map
{
addToDistributionIterator->second++;
}
}

On one machine with gcc version 4.0.2 20050901 (prerelease) (SUSE
Linux) (AMD 64bit) this works fine and the code goes into the "else //
Key present in map" part of the code as required. However, on the
machine with gcc version 4.1.0 (intel P4) it doesn't - the map key
isn't found - it worked fine with 4.0.X however! The strange thing is
that, if i uncomment the line:

"std::cout << "n: " << n << ", keyToAddTo: " << keyToAddTo <<
std::endl;"

to print the key value to the screen (used as a quick debug/test line),
then the code works fine and enters the "else // Key present in map"
as required.

Do you think that this is a compiler bug, or a bug in my code that the
compiler wasn't sensitive to before?

Any help gratefully received,

Graham

 

[Pete C]

I have 2 Suse Linux PCs which I compile my code on. Until recently
they both had gcc 4.0.X on them, but I upgraded one of them to gcc
4.1.0. I have come across a very strange problem in the following code
which uses an STL map:

// std::cout << "n: " << n << ", keyToAddTo: " << keyToAddTo <<
std::endl;

std::map<float, int>::iterator addToDistributionIterator;

Have you heard the rule of thumb that it's usually a bad idea to
compare two floating point values for equality? Well using a map keyed
on float values is the same thing. You often get surprised by the way
things are rounded, and the behaviour may vary from compiler to
compiler (or even the order of the mathematical operations you use to
calculate the value).

I would guess that by outputing keyToAddTo via cout, you have taken a
reference to it and thus forced it into memory whereas without that
line it would have remained in a floating point register. Registers
will often have a different precision than the memory location used to
store them, and I think your problems are due to the rounding that
follows.

The ideal solution would be to key the map on an integer type (I'm sure
you can find a way). Failing that, supply a comparator to the map that
will compare floats using a predefined tolerance rather than ==.

 

[Bernd Strieder]

Hello,

std::map<float, int>::iterator addToDistributionIterator;

You should learn a fair deal about floating point arithmetics, there are
some papers in the net, and there are books. Use a search engine, and
read, well invested time.

You probably have got trapped in the most simple pitfall, you cannot
rely directly on equality or < or > to compare floating point values
calculated from different source values. Different compilers create
different code, and different values, e.g. if the hardware has excess
precision and intermediate results don't get rounded due to
optimization.

You as a programmer have to decide what ranges of floating point values
are to be treated as one value each, that's the key. Consider the
precision of the input values.

isn't found - it worked fine with 4.0.X however! The strange thing is
that, if i uncomment the line:

then the code works fine and enters the "else // Key present in map"
as required.

This is a clear sign for an optimization issue. Printing a value changes
a lot in compilation. Usually a lot of optimization possibilities are
killed, because printing cannot be inlined, i.e. a real function is
called with all its natural overhead and different optimization
opportunities. Compilers are allowed to produce different floating
point results depending on optimization, if the precision is above a
specified minimum. A great deal of the recent changes to gcc, the
compiler in question here, is due to better optimization.

Do you think that this is a compiler bug, or a bug in my code that the
compiler wasn't sensitive to before?

It's the last choice, clearly. It's a bug to rely on maximum precision
of floating point values up to equality. Usually, the input data has
remarkably less precision, anyway.

Bernd

 

[Michiel.Salters]

Have you heard the rule of thumb that it's usually a bad idea to
compare two floating point values for equality? Well using a map keyed
on float values is the same thing. You often get surprised by the way
things are rounded, and the behaviour may vary from compiler to
compiler (or even the order of the mathematical operations you use to
calculate the value).

The ideal solution would be to key the map on an integer type (I'm sure
you can find a way). Failing that, supply a comparator to the map that
will compare floats using a predefined tolerance rather than ==.

In general, that's a good advice. However, map requires operator< or a
similar weak ordering. For floats, it's all too easy to define a
BrokenLess(float,float) such that

BrokenLess(a,b)==false && BrokenLess(b,a)==false &&
BrokenLess(a,c)==false && BrokenLess(c,a)==false &&
BrokenLess(b,c) == true; // BAD!

If a and b are equivalent, and a and c also, then b and c must be
equivalent
as well. Now, with the normal epsilon trick, imagine what happens if
b == a+eps and c == a-eps.

Floats are basically not suited very well, if at all, for maps.

HTH,
Michiel Salters

 

[graham.macpherson]

Thanks very much - I can redesign the class so that the key is an
integer, and I'll bear your advice in mind in future.

Graham

 

[Pete C]

In general, that's a good advice. However, map requires operator< or a
similar weak ordering. For floats, it's all too easy to define a
BrokenLess(float,float) such that

BrokenLess(a,b)==false && BrokenLess(b,a)==false &&
BrokenLess(a,c)==false && BrokenLess(c,a)==false &&
BrokenLess(b,c) == true; // BAD!

I'd imagine it's inevitable (rather than merely 'easy'), is it not?
Similarly to how any normal epsilon-based comparison can appear to
yield:

a == b && b == c && a != c

That's just the nature of the game, and why it's so important to choose
the right epsilon for your application (and why it's even more
important to not put yourself in that position in the first place).

Floats are basically not suited very well, if at all, for maps.

agreed...

 

[Pete Becker]

I'd imagine it's inevitable (rather than merely 'easy'), is it not?
Similarly to how any normal epsilon-based comparison can appear to
yield:

a == b && b == c && a != c

That's just the nature of the game, and why it's so important to choose
the right epsilon for your application (and why it's even more
important to not put yourself in that position in the first place).

The point is that a comparator like this does not meet the requirements
for use in a map (unless epsilon is 0). Typically you'll get runtime
crashes, which only start showing up the night before your product is
supposed to ship.