4 ms·
So how does this compare to PDQ, Crum, flux, etc? Do you have preliminary results?
by nwmcsween 4y ago
So how does this compare to PDQ, Crum, flux, etc? Do you have preliminary results?
- deleted 4y ago[deleted]
- kzrdude 4y agoNote that the author also is the author of PDQ. And there was some prior discussion on HN here: https://news.ycombinator.com/item?id=33827843 https://news.ycombinator.com/item?id=33827843
- orlp 4y agoI have some preliminary results I can share from the current draft paper: https://i.imgur.com/AUOJ1w0.png https://i.imgur.com/AUOJ1w0.png https://i.imgur.com/AP6DnIS.png https://i.imgur.com/AP6DnIS.png Note that the four bottom sorts (RustSort, StdSort, Pdqsort, IPS4o) are not stable. GlidesortN is glidesort using n elements of memory, Glidesort is the default memory setting and Glidesort1024 uses a fixed 1024 element buffer. Arm is a 2021 Apple M1, Amd is a 2018 Threadripper 2950x.
- moonchild 4y agoIs ips4o parallelised here?
- orlp 4y agoNo, it is running serially. IPS4o is inherently more cache efficient due to having a very wide partition operator, making it better on machines with smaller caches, and better in general for strings (where no matter how cache-local your algorithm is, the string pointer indirection mostly destroys it).
- scandum 4y agoThose are some awfully large array sizes. Not something I ever had the patience for to sit out, or optimize for, as it didn't seem like the most common real-world scenario. One thing glidesort appears to do extremely well is to branchless merge till the very end, this gets quite tricky when memory constrained. It does not seem worth it intuitively, but judging from the performance of rotate mergesort, it probably is.