roc: `List.sortWith` is notably slower than sorting in other non-systems languages
system
- Roc version
github:roc-lang/roc/dc37b7a31d4fa2014ec159eda1d51c27832ddca6 - run on macOS 13.4.1 arm64 (M1 macbook air)
setup
main.roc
# references
# - https://github.com/roc-lang/examples/tree/main/examples/CommandLineArgs
app "main"
packages {
pf: "https://github.com/roc-lang/basic-cli/releases/download/0.7.0/bkGby8jb0tmZYsy2hg1E_B2QrCgcSTxdUlHtETwm5m4.tar.br",
}
imports [pf.Stdout, pf.Task]
provides [main] to pf
main : Task.Task {} I32
main =
Stdout.line "w/e"
expect
n = 86896
list = List.range { start: At n, end: Before 0 }
List.sortWith list Num.compare == List.range { start: At 1, end: At n }
problem
Running roc test --optimize terminates after ~20 seconds with the following correct test output:
$ roc test --optimize
0 failed and 1 passed in 20094 ms.
expected behavior
The given code should run faster relative to other languages, as described on the Roc website.
Specifically, I consider the above code to be roughly equivalent to the following Python code:
n = 10000000 # a much larger value!
l = list(reversed(range(n)))
l.sort()
l == list(range(n))
Timing this code via the *nix time command produces the following output:
$ time python3 -c "n = 10000000; l = list(reversed(range(n))); l.sort(); l == list(range(n))"
python3 -c 0.36s user 0.10s system 96% cpu 0.475 total
Note that the above results are for a data input ~300x larger than in the Roc code. (Atm the roc code won’t even run for data that large - see #6293.)
About this issue
- Original URL
- State: closed
- Created 3 years ago
- Comments: 16 (8 by maintainers)
This is not yet ready to merge, but on the
blitsortbranch (poorly named cause currently it is just quadsort and later will be fluxsort), I have some big sorting perf gains.This is just
python3 -c "n = 10000000; l = list(reversed(range(n))); l.sort(); l == list(range(n))"in python and in roc. With a final print depending on if the lists are equal. Much faster in Roc now!EDIT: Also, this is without special handling for reversed list, but with that enabled, roc takes 75ms here.
I’ve started a discussion on zulip with more analysis and to get help in finding out the cause.
Yes it’s pretty new, it was merged in on the fifth of December in PR #6184.
Thanks for the simplification @CrepeGoat. I don’t personally have time to look into this but my recommended next step would be to build with
roc build --optimize --profiling, and make a flamegraph. This will allow you to see what the program is actually spending time on.well I did no check before 😂 so thanks for putting in that work to confirm 👍
Agreed! I think we’re on the same page here 🙂