Hacker News Reader

Comment by JeffJenkins | Hacker News Reader

Non-strict comparator with the STL. Nearly impossible to identify when it's happening. It's happened once to me and once or twice to a coworker over the last couple years, and takes 3-5 days to debug every time.

Example:

  struct FooSort {
    bool operator()(Foo const& a, Foo const& b)  const {
  -    return not a < b ;
  +    return b < a;
     }
  };

View on HN

Try a worse version of this - comparing the results of a floating-point function call where the left operand gets moved into the 80bit fp unit during computation, and the right operand stays in register.

Obviously there is a precision difference between the two numbers, enough to make a < b and b < a return true in a surprising number of cases. The way I ended up fixing it was by putting the result of the function call in a member variable in every struct, pre-computing all of the results, and comparing based on that value.

I hit this, too. Regression tests were failing when I changed code that obviously shouldn't change the output of the program at all. This happened on a regular basis when we changed numeric code, because of the normal limitations of floating-point arithmetic; we just made sure the numerical results were accurate and updated the regression tests. (The regression tests were quite handy for finding logic errors; they weren't really used to test numerical accuracy.)

But in this case I was just adding some error checks, which weren't even being triggered. Clearly this shouldn't affect the results of our numerical calculations. Since my code shouldn't affect the calculations, I was convinced that our existing numerical code had a subtle memory or timing bug. (I knew that floating-point code was tricky, but clearly I was doing exactly the same operations on exactly the same values.) I spent days staring at code, and then my boss told me to stop working on it since the results were clearly correct in both versions, even if they weren't identical.

A few weeks later I read about how values change when they're copied out of the x87 stack into registers. And I thought, naw, we couldn't possibly be using x87 arithmetic. But we were. Which was horrifying, since floating-point calculations could be a bottleneck under some workloads. But we had been running that way since before I started working on it, so at least it wasn't my fault. I added a compiler option to request sse2 floating point instead of x87 floating point. Voila, predictable floating-point results, plus measurably faster performance on a few tests.

This has happened to me several times. Especially in combination with the fact that C++ does not guarantee floating point operations happen the same every time... Argh. So it is unwise to do things like

  bool operator()(Foo const& a, Foo const& b) const {
    return a.some_float_func() < b.some_float_func();
  }

if some_float_func does floating point operations rather than just returning a stored value.

> C++ does not guarantee floating point operations happen the same every time...

Can you elaborate more on this? Are you implying that two identical calculations will return different results?

For example, a function might be inlined at some call sites and not inlined at others. Inlined versions might carry 80 bits through the result, but non-inlined version are truncated to 64. So in:

  double foo(double x) { return x*3.3; }
  double bar1(double x) { return foo(x); }
  double bar2(double x) { return foo(x); }
  void t_bar(double x) { assert(bar1(x) == bar2(x)); }

t_bar can fail depending on how bar1 and bar2 are compiled.

I'm not sure how the example could make the assertion fail; I think that the point is that if 3.3 is treated as a long double by the compiler, then the result of x*3.3 will be a long double, which is more precise than the double returned by foo; but, regardless of how bar1 and bar2 are compiled, they both make a call to foo() which returns a double. Is it the case then that the behavior depends on how foo is compiled? I don't see how else the 80-bit result could propagate to the test for equality.

returning a double can be optimized into returning an 80-bit result in a register. If this happens with bar1 but not bar2, then you get different results.

There are situations where the order of evaluation is not guaranteed. The big one that I've seen is evaluation of expressions as arguments in a function call, but there are others. It is easy to create floating point expressions where because of rounding, the results will differ depending on the order of evaluation. I'm not aware of situations where the order of operation differs from one execution to the next. However, I could see a compiler generating different code for the same expression when it appears in more than one place in the source code because of optimization.

I'm glad I'm not the only one who has trouble when I hit this.

I really, really wish the STL had a mode you could compile it in which boiled down to, "Double check everything no matter how slow it makes things." Maybe it has it and I don't know it. But that was my top irritation with the little bit of C++ I've done.

I have no idea how a non-strict comparator can lead to memory corruption rather than just indeterminate sort order, but it is no fun tracking that down.

Reply on news.ycombinator.com