3 ms·
> Just the other day I found a case someone had rolled their own priority queue with a sorted array instead of a heap. I feel like this story needs an ending?
by Arelius 6y ago
> Just the other day I found a case someone had rolled their own priority queue with a sorted array instead of a heap.
I feel like this story needs an ending? Did somebody re-implement it using a heap and found significant performance wins? Or was the sorted array used on purpose to take advantage of some specific cache constraints and actually end up being a huge win?
- WJW 6y agoThe story ends (so far) with me filing a GH issue and offering a PR, my own benchmarking getting an average 3x speedup over a wide range of inputs. I happen to know that the maintainer has been on vacation for the last week and only got back a few days ago so no further discussion has been had yet.
- vlovich123 6y agoA serious HW perf improvement will, generally improve everything, including shitty algorithms. There’s a reason that through the 90s and 2000s serious developers routinely ignored spending significant time optimizing code because the hardware doubled the speed of ALL code every ~12-18 months. So even though there are low-hanging fruit for software optimization, such low-hanging fruit can be missing from already heavily optimized code (eg games, scientific computations etc) and is orders of magnitude more expensive than “run this on newer HW for faster perf”. If you can do this “transparently” (max some OS/compiler integration and you can use the new Hw for perf wins), then the cost economics are powerful. If it’s a special-purpose piece of HW then it gets trickier and will be relegated to accelerating certain memory-heavy programs (like GPUs accelerate certain kinds of mass-data algorithms).