3 ms·

It turns into a serious problem if the floats are of different magnitude. Consider [1e50, -1e50, 1e3, 1e3]. Evaluating it as (((1e50 + -1e50) + 1e3) + 1e3) give

by crote 2y ago

It turns into a serious problem if the floats are of different magnitude. Consider [1e50, -1e50, 1e3, 1e3]. Evaluating it as (((1e50 + -1e50) + 1e3) + 1e3) gives 2e3, evaluating it as ((1e50 + 1e3) + (-1e50 + 1e3)) gives 0. You get similar issues if you're trying to add a large number of small-magnitude numbers to a single larger-magnitude number. (((1e3 + 1e3) + 1e3) ... + 1e50) is substantially different from (((1e50 + 1e3) + 1e3) ... + 1e3).

jandrese 2y ago
Adding and subtracting numbers of wildly different magnitudes is always cursed. If you're doing this I'd say the majority of the time you are making an error. Your equation ends up being like "We calculated the diameter of the observable universe, but what if we added the Empire State Building to one side, how does that affect the result?"
- skybrian 2y ago
  It’s also what we do when incrementing a counter, if it’s a very big counter. Operations like that don’t have a physical meaning, but can happen in things like random number generators where it’s a way of mixing the bits. Or maybe allocating unique ids, if you started from a random number.
  - bee_rider 2y ago
    Of course it is just an example so we shouldn’t nitpick you too much, but that sounds more like a job for an integer.
    - skybrian 2y ago
      Yes, absolutely. Though in JavaScript we often make do with the safe integer range. (I don’t know how fast BigInt is for 64 bit integers.)
      - bee_rider 2y ago
        I don’t know JavaScript so I’m sure to shoot my own foot here, but surely a BigInt who’s value can fit in 64 bits is just a normal 64 bit int (from hardware) with some extra bookkeeping around it on most platforms, right?
        IainIreland 2y ago
        I can't speak for any other engines, but in SpiderMonkey a BigInt is a GC-managed object with a one-word header containing the sign bit, the length, and some GC bookkeeping bits, along with a second word that is either a single inline 64-bit digit, or a pointer to an array of 64-bit digits. So the memory overhead of a BigInt that fits in 64 bits is "only" 2x, but doing math with BigInt requires more work than a native integer because it needs to handle larger numbers, manually manage sign bits, and so on. (https://searchfox.org/mozilla-central/source/js/src/vm/BigIntType.h#49-464 https://searchfox.org/mozilla-central/source/js/src/vm/BigIn...)
    - aardvark179 2y ago
      If all you’ve got is JS then every problem looks like a double.
- colomon 2y ago
  I don't remember the exact numbers, but I remember seeing a CAD file that was not working well a few years ago, and it turned out the coordinate system set up for the part was roughly equivalent to building a part the size of a man's fist but measuring it from the center of the Earth (in meters) while putting the part in Earth orbit.
mywittyname 2y ago
But you haven't demonstrated that the SIMD approach produces a meaningfully different and more accurate approach than the naive method. Just like processor magic made the theoretically more performant code perform worse, it's possible that the processor has facilities for bucketing the data such that results from such a dataset are the same or more accurate than the naive approach. This is absolutely a situation that requires empirical testing.
- scaredginger 2y ago
  Yeah, no. If I know what my data look like, I can choose an order of summation that reduces the error. I wouldn't want the compiler by default to assume associativity and introduce bugs. There's a reason this reordering is disabled by default
  - Sesse__ 2y ago
    Not the least that you should get the same result from your code every time, even if you compile it with a different compiler. Doesn't matter if that result is somehow better or worse or “difference is so small that it doesn't matter”; it needs to be exactly the same, every time.
    - bee_rider 2y ago
      I think there’s often a disconnect in these discussions between people that work on libraries and people that work on the application code. If you have written a library, the user will provide some inputs. While the rounding behavior of floating point operations is well defined, for arbitrary user input, you can’t usually guarantee that it’ll go either way. Therefore, you need to do the numerical analysis given users inputs from some range, if you want to be at all rigorous. This will give results with error bounds, not exact bit patterns. If you want exact matches for your tests, maybe identify the bits that are essentially meaningless and write them to some arbitrary value. Edit: that said I don’t think anybody particularly owns rigor on this front, given that most libraries don’t actually do the analysis, lol.
- 2y ago
bee_rider 2y ago
Whether you care about the order or not depends on the intent of the programmer. I think the intent is usually to sum up the array for this sort of code. So, at first glance your first example looks more like a result of something like 0 +- 1e35 in double to me (added one to the exponent to avoid having to do math). The intent of the programmer always has to be interpreted by the language. I’m saying the default interpretation should be one that doesn’t impose an ordering unless specifically requested. This is much more sympathetic to modern deeply parallel machines.
- FreakLegion 2y ago
  Very often there's no particular intent, other than to be consistent. You haven't lived until you've traced discrepancies in an ML model deployed across a bunch of platforms back to which SIMD instructions each happens to support (usually squirreled away in some dependency).

by crote 2y ago

jandrese 2y ago

Adding and subtracting numbers of wildly different magnitudes is always cursed. If you're doing this I'd say the majority of the time you are making an error. Your equation ends up being like "We calculated the diameter of the observable universe, but what if we added the Empire State Building to one side, how does that affect the result?"

skybrian 2y ago
It’s also what we do when incrementing a counter, if it’s a very big counter. Operations like that don’t have a physical meaning, but can happen in things like random number generators where it’s a way of mixing the bits. Or maybe allocating unique ids, if you started from a random number.
- bee_rider 2y ago
  Of course it is just an example so we shouldn’t nitpick you too much, but that sounds more like a job for an integer.
  - skybrian 2y ago
    Yes, absolutely. Though in JavaScript we often make do with the safe integer range. (I don’t know how fast BigInt is for 64 bit integers.)
    - bee_rider 2y ago
      I don’t know JavaScript so I’m sure to shoot my own foot here, but surely a BigInt who’s value can fit in 64 bits is just a normal 64 bit int (from hardware) with some extra bookkeeping around it on most platforms, right?
      - IainIreland 2y ago
        I can't speak for any other engines, but in SpiderMonkey a BigInt is a GC-managed object with a one-word header containing the sign bit, the length, and some GC bookkeeping bits, along with a second word that is either a single inline 64-bit digit, or a pointer to an array of 64-bit digits. So the memory overhead of a BigInt that fits in 64 bits is "only" 2x, but doing math with BigInt requires more work than a native integer because it needs to handle larger numbers, manually manage sign bits, and so on. (https://searchfox.org/mozilla-central/source/js/src/vm/BigIntType.h#49-464 https://searchfox.org/mozilla-central/source/js/src/vm/BigIn...)
  - aardvark179 2y ago
    If all you’ve got is JS then every problem looks like a double.
colomon 2y ago
I don't remember the exact numbers, but I remember seeing a CAD file that was not working well a few years ago, and it turned out the coordinate system set up for the part was roughly equivalent to building a part the size of a man's fist but measuring it from the center of the Earth (in meters) while putting the part in Earth orbit.

mywittyname 2y ago

But you haven't demonstrated that the SIMD approach produces a meaningfully different and more accurate approach than the naive method. Just like processor magic made the theoretically more performant code perform worse, it's possible that the processor has facilities for bucketing the data such that results from such a dataset are the same or more accurate than the naive approach. This is absolutely a situation that requires empirical testing.

scaredginger 2y ago
Yeah, no. If I know what my data look like, I can choose an order of summation that reduces the error. I wouldn't want the compiler by default to assume associativity and introduce bugs. There's a reason this reordering is disabled by default
- Sesse__ 2y ago
  Not the least that you should get the same result from your code every time, even if you compile it with a different compiler. Doesn't matter if that result is somehow better or worse or “difference is so small that it doesn't matter”; it needs to be exactly the same, every time.
  - bee_rider 2y ago
    I think there’s often a disconnect in these discussions between people that work on libraries and people that work on the application code. If you have written a library, the user will provide some inputs. While the rounding behavior of floating point operations is well defined, for arbitrary user input, you can’t usually guarantee that it’ll go either way. Therefore, you need to do the numerical analysis given users inputs from some range, if you want to be at all rigorous. This will give results with error bounds, not exact bit patterns. If you want exact matches for your tests, maybe identify the bits that are essentially meaningless and write them to some arbitrary value. Edit: that said I don’t think anybody particularly owns rigor on this front, given that most libraries don’t actually do the analysis, lol.
2y ago

bee_rider 2y ago

Whether you care about the order or not depends on the intent of the programmer. I think the intent is usually to sum up the array for this sort of code. So, at first glance your first example looks more like a result of something like 0 +- 1e35 in double to me (added one to the exponent to avoid having to do math). The intent of the programmer always has to be interpreted by the language. I’m saying the default interpretation should be one that doesn’t impose an ordering unless specifically requested. This is much more sympathetic to modern deeply parallel machines.

FreakLegion 2y ago
Very often there's no particular intent, other than to be consistent. You haven't lived until you've traced discrepancies in an ML model deployed across a bunch of platforms back to which SIMD instructions each happens to support (usually squirreled away in some dependency).