mourner
Switch to non recursive quicksort
Fixes #69
I have now switched to a non recursive implementation in order to solve this once and for all. There is a minor performance penalty for the indexing part (215ms -> 255ms) which I still think is worth it. Even with an optimized recursive implementation there can be datasets that fail or that require random numbers in the algorithm which would also slow it down. @mourner What do you think?
215 to 255 is a 19% increase, which is quite significant — I'd love to see if we can fix this without a big regression for all cases. In theory, the non-recursive version shouldn't be slower — I'll see if there are any microoptimizations available here...
I guess microoptimizations are possible however it being slower very much depends on the JS engine as well the hardware. A function call stack is handled differently from a custom stack. Anyhow there are also other options to get faster, i.e. by using insertion sort once the partition is small enough.
Apart from that how do you want me to get rid of current typing errors that show up due to pop() indicate possible undefined?
@muendlein for type checking, we can add ignores similar to the existing ones in places where it's hard to type soundly: https://github.com/mourner/flatbush/blob/main/index.js#L304
@mourner I have added some performance improvements which now brings the performance to the same speed.
Followed up in https://github.com/mourner/flatbush/commit/5dedc6880cb8856b5bd79913a4d769daae91063c to make the code a bit shorter and simpler.