5 ms·

Which costs more, doubling the number of runLength comparisons or allocating more memory? Without knowing that answer it's hard to say which is the better solu

Which costs more, doubling the number of runLength comparisons or allocating more memory? Without knowing that answer it's hard to say which is the better solution (assuming more memory actually fixes the bug).

marcosdumay 12y ago
Exchanging memory usage for equality comparations is an almost universal no brainer. The number of comparations must increase hundreds of times for compensating doubling the memory usage... and that's just for performance, for energy savings you'll need more.
- stingraycharles 12y ago
  Where do you base these numbers on? If it still fits inside the L1 cache, I assume that increasing the comparisons will have a relatively bigger impact?
  - marcosdumay 12y ago
    Yes, that's right. The thing is that nearly all of the times you want to order arrays that fit inside the L1 cache, neither execution time nor allocation size are a problem.
- tedunangst 12y ago
  Sounds like the amount of memory involved is quite small. Below a certain threshold, doubling is practically free. And IIUC even over-allocating memory doesn't necessarily mean it uses all of the memory, only for the the inputs that cause the bug. The extra comparison however would be performed for all inputs.
  - rozim 12y ago
    Below what threshold though? L1 cache size? O(64 bytes), no?
    - nostrademons 12y ago
      Depends upon the operation of the rest of the program. 64 bytes is the size of a cache line, the actual L1 cache (on recent Intel processors) is 1024 of those cache lines. If the extra memory just means that you pull an extra line into cache for a bookkeeping array, the effect is negligible. If it means that you thrash the cache and have to evict some of your sorted data, the effect could be orders of magnitude. I'd really hope that the JDK maintainers benchmarked against real-world programs before deciding which fix to use. My intuition is that the set of programs where increasing the memory usage matters is tiny, but the effect is large for them - it's the set of programs where the working set is greater than the L1 cache size. Equality comparisons aren't free either, they can often cause branch mispredicts. But the point is that performance tuning on real-world programs is very counterintuitive, and so the best way to do it is to run some actual numbers on actual programs.
      - vardump 12y ago
        All Intel CPUs worth mentioning in last 10 years have 512 L1 data cache entries, not 1024. Including Haswell and Sandy Bridge. I do agree with your analysis otherwise.
  - caf 12y ago
    The extra comparison ought to return the same value on all but the inputs that cause the bug too, so it should be perfectly predicted.
- maxerickson 12y ago
  Memory isn't being doubled though, some bookkeeping that is a fraction of the total memory being used is being increased by less than 2x.
- pron 12y ago
  They've added 36 bytes for input sizes > 120K elements. That's not even one cache line. This, instead of a few more branches that would need to run every iteration, no matter the input size. I haven't run a benchmark (they probably did), but my gut says they've made the right choice.

marcosdumay 12y ago

Exchanging memory usage for equality comparations is an almost universal no brainer. The number of comparations must increase hundreds of times for compensating doubling the memory usage... and that's just for performance, for energy savings you'll need more.

stingraycharles 12y ago
Where do you base these numbers on? If it still fits inside the L1 cache, I assume that increasing the comparisons will have a relatively bigger impact?
- marcosdumay 12y ago
  Yes, that's right. The thing is that nearly all of the times you want to order arrays that fit inside the L1 cache, neither execution time nor allocation size are a problem.
tedunangst 12y ago
Sounds like the amount of memory involved is quite small. Below a certain threshold, doubling is practically free. And IIUC even over-allocating memory doesn't necessarily mean it uses all of the memory, only for the the inputs that cause the bug. The extra comparison however would be performed for all inputs.
- rozim 12y ago
  Below what threshold though? L1 cache size? O(64 bytes), no?
  - nostrademons 12y ago
    Depends upon the operation of the rest of the program. 64 bytes is the size of a cache line, the actual L1 cache (on recent Intel processors) is 1024 of those cache lines. If the extra memory just means that you pull an extra line into cache for a bookkeeping array, the effect is negligible. If it means that you thrash the cache and have to evict some of your sorted data, the effect could be orders of magnitude. I'd really hope that the JDK maintainers benchmarked against real-world programs before deciding which fix to use. My intuition is that the set of programs where increasing the memory usage matters is tiny, but the effect is large for them - it's the set of programs where the working set is greater than the L1 cache size. Equality comparisons aren't free either, they can often cause branch mispredicts. But the point is that performance tuning on real-world programs is very counterintuitive, and so the best way to do it is to run some actual numbers on actual programs.
    - vardump 12y ago
      All Intel CPUs worth mentioning in last 10 years have 512 L1 data cache entries, not 1024. Including Haswell and Sandy Bridge. I do agree with your analysis otherwise.
- caf 12y ago
  The extra comparison ought to return the same value on all but the inputs that cause the bug too, so it should be perfectly predicted.
maxerickson 12y ago
Memory isn't being doubled though, some bookkeeping that is a fraction of the total memory being used is being increased by less than 2x.
pron 12y ago
They've added 36 bytes for input sizes > 120K elements. That's not even one cache line. This, instead of a few more branches that would need to run every iteration, no matter the input size. I haven't run a benchmark (they probably did), but my gut says they've made the right choice.