3 ms·

Measure measure measure measure. Each case is different. But more seriously I think tree based algos tend to be overhyped, and people get a bit absorbed into t

by rtpg 2y ago

Measure measure measure measure. Each case is different. But more seriously I think tree based algos tend to be overhyped, and people get a bit absorbed into thinking about big-O behavior when the constant factors are super important even when you’re looking at hundreds of thousands of elements. Not to mention stuff like data locality. Like sometimes your computer will be faster at just looking in a seq scan rather than dealing with the bookkeeping of a fancier structure. Sometimes. I think a nicer argument overall is to build a tiny wrapper around your operations, build out what is easy, and then figure it out through measurements. Worst case you end up entirely rewriting your program to accommodate a different structure to try for better perf but in my experience rewriting entire files from scratch tends to get you a good number of improvements for free.

dkjaudyeqooe 2y ago
Sequential scans are terribly underrated given today's architectures. If the datum is small and it's like 1000 elements max it's going to be hard to beat a simple scan of an array for speed and memory efficiency. But trees et al also make a lot of sense as a default. If you need the performance to scale in a roughly linear manner you need to be smart about it. This is what sinks a lot of software, usability wise.
- seveibar 2y ago
  Author here. This was almost worth a mention in the article. Every once in a while I'd have a friend take a look at a piece of my algorithm and they'd suggest swapping out a sort() function for a priority queue etc. (without looking at the performance data) and find no change or sometimes even a slightly worse result! This is why having performance data is so critical, the performance of a complex algorithm can be counter-intuitive and most performance "gotchas" are just straight up mistakes or recalculations rather than fundamental algorithm issues (remember the GTA5 bug that caused the loading screen to take an extra 5 seconds, and was simple enough for a random dev to patch? that is the most common type of performance issue in development!)

by rtpg 2y ago

dkjaudyeqooe 2y ago

Sequential scans are terribly underrated given today's architectures. If the datum is small and it's like 1000 elements max it's going to be hard to beat a simple scan of an array for speed and memory efficiency. But trees et al also make a lot of sense as a default. If you need the performance to scale in a roughly linear manner you need to be smart about it. This is what sinks a lot of software, usability wise.

seveibar 2y ago
Author here. This was almost worth a mention in the article. Every once in a while I'd have a friend take a look at a piece of my algorithm and they'd suggest swapping out a sort() function for a priority queue etc. (without looking at the performance data) and find no change or sometimes even a slightly worse result! This is why having performance data is so critical, the performance of a complex algorithm can be counter-intuitive and most performance "gotchas" are just straight up mistakes or recalculations rather than fundamental algorithm issues (remember the GTA5 bug that caused the loading screen to take an extra 5 seconds, and was simple enough for a random dev to patch? that is the most common type of performance issue in development!)