Make 'list::sort' quick by using natural mergesort #711
Conversation
See issue #710 for context and analysis
|
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 |
libraries/common/list.effekt
Outdated
| /// When in an ascending sequence, try to add `current` to `run` (if possible) | ||
| def ascending[A](current: A, rest: List[A]) { runDiff: List[A] => List[A] } { compare: (A, A) => Bool }: List[List[A]] = rest match { | ||
| case Cons(next, tail) and compare(current, next) => | ||
| ascending(next, tail) { diffRest => runDiff(Cons(current, diffRest)) } {compare} | ||
| case _ => Cons(runDiff([current]), sequences(rest) {compare}) | ||
| } |
There was a problem hiding this comment.
This function usually uses a difference list (we need to append to the end)
It would probably be interesting to compare it (perf-wise) with:
- prepending and then
.reverse-ing - some
yieldeffect
What would be the most idiomatic solution here?
There was a problem hiding this comment.
I still really want to have Daan-style contexts. That would help here, right?
|
I tried improving both the performance and the stack safety here by making certain parts ( |
|
In a "real" application (and by that I mean AoC), this change saves 25-50% of the run time: |
|
|
||
| /// Check if a list is sorted according to the given comparison function. | ||
| /// Check if a list is sorted according to the given comparison function (less-or-equal). | ||
| /// | ||
| /// O(N) | ||
| def isSortedBy[A](list: List[A]) { compare: (A, A) => Bool }: Bool = { |
There was a problem hiding this comment.
TODO: Consider changing the names of comparison functions from compare to something like lteq or lessThanOrEqual even, just to express properly what we expect of them...
|
Blocked on resolving the leak on the LLVM backend. ^ |
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.
Other considerations:
compareeverywhere manually.>=instead of a>