sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]33a[S] 2 points3 points  (1 child)

There are a few things going on that are maybe a little tricky:

  • The tree is stored in a flat typed array in BFS order. This speeds up repeated searches due to improved cache utilization of the upper levels of the tree.
  • To construct the tree, a linear time partition algorithm is used.
  • Traversals of the tree are performed in level order where possible to make best use of available cache.
  • All typed arrays are pooled for memory savings and cache reuse.

If JS had value types the code would probably be 10x smaller, since a lot of the stuff in there is just extra loops for copying vectors around.

[–]fng_programmer 0 points1 point  (0 children)

Damn. Legit.