rust-lang / datafrog

A lightweight Datalog engine in Rust
Apache License 2.0
796 stars 43 forks source link

Switch back to a stable sort #9

Closed lqd closed 6 years ago

lqd commented 6 years ago

I was testing rayon's parallel sort on Relations when I noticed we were using std's sort_unstable even though we (albeit not completely 100% sure why) saw the stable sort perform better. So let's bring it back until we have more measurements/benchmarks :)

This locally improves, on clap:

frankmcsherry commented 6 years ago

There are places where the stable sort is def better, because it is a merge sort that looks for sorted runs and if they exist it is better than the pattern defeating quicksort (the unstable implementation). The stable sort has run-time guarantees, which is another mark it its favor. Seems good to me. :)

lqd commented 6 years ago

The hype update :) — numbers on unreleased software: