4 ms·

> The QuadTree and every general-purpose tree data structure are insanely slow. Trees are not an informed representation of your data. > Any time you’re using

> The QuadTree and every general-purpose tree data structure are insanely slow. Trees are not an informed representation of your data. > Any time you’re using a tree you’re ignoring an O(~1) hash algorithm for a more complicated O(log(N)) algorithm This is incredibly misguided. The hashing approach is fine if your points are evenly distributed and you only really want to query an area relatively close to the fixed subdivisions you've chosen, otherwise your 0(1) is going to degenerate to O(n). Trees are an informed representation when you don't know how your data is distributed. Similar story for randomized algorithms. What happens when your search space is many trillions of items or possibilities? Or there are no heuristics to be had? If you can't brute force it and you can't use a clever algorithm then randomized algorithms are a savior. Maybe these aren't needed for this specific application, but best to not make sweeping statements.

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!)
phkahler 2y ago
For 3D I found octtrees very effective and fast. In my implementation you can even move items around without having to regenerate the tree. I have yet to find a satisfactory way to store points (in 2d or 3d) and be able to query nearby points. a kD tree is nice, but I want to add points as I go, not build a structure around a fixed set.
- o11c 2y ago
  I suspect that thinking in trie terms is the way to go, where each node chooses its preferred representation. The top level should usually use a grid, though uniform-density children can also use one. The grid scale should be chosen to maximize low-density children while minimizing empty children. For low-density children, just store an unsorted bunch of items, or maybe sort them on just one axis (preferably the outermost axis used for rendering). If your outer level is actually uniform, all of its children will be this (or empty). For high-density children, use a quadtree/octree ... or just treat them as opaque objects to be handled recursively. These still suck for all the memory-walking they do, but since you've handled the outer part using the grid, the overhead is smaller. These can do "nearby" queries if your implementation is good, but many implementations suck. Making them mutable just means you need to either implement rebalancing or just stick to fixed planes.

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!)

phkahler 2y ago

For 3D I found octtrees very effective and fast. In my implementation you can even move items around without having to regenerate the tree. I have yet to find a satisfactory way to store points (in 2d or 3d) and be able to query nearby points. a kD tree is nice, but I want to add points as I go, not build a structure around a fixed set.

o11c 2y ago
I suspect that thinking in trie terms is the way to go, where each node chooses its preferred representation. The top level should usually use a grid, though uniform-density children can also use one. The grid scale should be chosen to maximize low-density children while minimizing empty children. For low-density children, just store an unsorted bunch of items, or maybe sort them on just one axis (preferably the outermost axis used for rendering). If your outer level is actually uniform, all of its children will be this (or empty). For high-density children, use a quadtree/octree ... or just treat them as opaque objects to be handled recursively. These still suck for all the memory-walking they do, but since you've handled the outer part using the grid, the overhead is smaller. These can do "nearby" queries if your implementation is good, but many implementations suck. Making them mutable just means you need to either implement rebalancing or just stick to fixed planes.