Make 'list::sort' quick by using natural mergesort

jiribenes commented 1 week ago

Please see issue #710 for context and analysis. (Resolves #710)

It would be nice if somebody benchmarked this properly: the old quicksort, this new quicksort on JS and LLVM + with JS native sort, but I can notice the improvement as this version can suddenly quickly sort huge random lists.

As far as I can tell when trying to use it, it's about 2-3x slower than a JS native sort -- I blame the optimiser 😇

Other considerations:

we could do some hybrid sort for smaller lists (and it would probably speed it up!), but I don't want the mental overhead of two different sorting algorithms
I'm pretty limited here by Effekt not allowing mutually recursive subfunctions -- this means that I need to pass compare everywhere manually.
not stacksafe (but works fine for ~5M random elements, so it's good enough for me!)
- EDIT: I still want to be able to sort a, let's say, ~10M list without getting a OOM :(
technically this breaks the previous interface: now the function wants a >= instead of a >
it uses a lot of mutual recursion, but I'm willing to optimise stuff a bit more
doesn't seem to work well in LLVM

jiribenes commented 1 week ago

It seems that this change makes Valgrind very unhappy with the LLVM backend :)

https://github.com/effekt-lang/effekt/actions/runs/11990743350/job/33428584571#step:11:164

jiribenes commented 6 days ago

I tried improving both the performance and the stack safety here by making certain parts (mergeAll) more imperative, but it didn't really work (actually made it measurably slower!)

jiribenes commented 15 hours ago

In a "real" application (and by that I mean AoC), this change saves 25-50% of the run time:

Before
✓ 1: JS [6.44ms]
✓ 2: JS [103.46ms]
✓ 1: LLVM [0.27ms]
✓ 2: LLVM [17.80ms]

After
✓ 1: JS [5.66ms]
✓ 2: JS [80.25ms]
✓ 1: LLVM [0.12ms]
✓ 2: LLVM [8.72ms]

effekt-lang / effekt

Make 'list::sort' quick by using natural mergesort #711