News for hackers. Stuff that matters.
Re:Faster than radix sort: Kirkpatrick-Reisch sorting by jnxx on Tuesday June 09, 2020 @04:46AM (#23464917)
Yeah. I am wondering since a while whether well-known algorithms like the binary heap are still efficient on modern architectures, because their random memory access patterns.
Re:Faster than radix sort: Kirkpatrick-Reisch sorting by lorenzhs on Tuesday June 09, 2020 @05:16AM (#23465039)
For priority queues, which implementation is optimal depends a lot on your workload (do you need addressability, i.e., a decreaseKey operation? What is the typical ratio of insertions to deletions? Are your keys integers?). I found some slide decks that are mostly in English with some German in between that might go some way to answering your question:

[1] https://algo2.iti.kit.edu/sanders/courses/algen20/vorlesung.... slide 180-207, there are some up-to-date measurements on slide 204

[2] https://nms.kcl.ac.uk/stefan.edelkamp/lectures/ae/slide/AE-A...

There are also parallel priority queues which might be useful depending on your problem, especially if it can be reformulated to operate on batches ("give me the 20 smallest items", "insert these 50 items").

Re:Faster than radix sort: Kirkpatrick-Reisch sorting by contravariant on Tuesday June 09, 2020 @05:31AM (#23465095)
Look up cache-oblivious algorithms. Turns out that random memory access can often be improved upon with smart data structures.