Hacker News Reader

Comment by nathell | Hacker News Reader

This got me thinking about sorting.

I wonder how many times per day (or, indeed, per second) my computer does sorting of any kind. I just checked a largish codebase I'm working on, and about 0.12% SLOCs invoke the standard library's sort. But that's just a random codebase. What about the kernel, the browser, the VMs, the graphical subsystem of the OS? Could I capture all these sorts' inputs to generate My Real-Life Sorting Corpus of One Day's Worth of Data? And then compare the performance of different sorting algorithms on that corpus?

I'm pretty sure this kind of research has been done before. Can someone point me towards relevant literature?

View on HN

> Could I capture all these sorts' inputs to generate My Real-Life Sorting Corpus of One Day's Worth of Data?

You could wrap the lib containing the sort function and write the input to some file.

It is easy of it is C at least.

It is easy enough to wrap libc's qsort() with LD_PRELOAD, sure. The problem is heterogeneity: qsort() is by far not the only sort implementation the machine is running. Even identifying them all might be a daunting task, not to mention figuring out how to wrap them.

Sounds like the sort of thing dtrace or bpftrace might be able to do.

sorting and searching are like 50% of what the CPU ever does. the benefits of ground breaking improvements there are huge. makes me think of proebsting's law, I don't know if this applies here.

This is not true. Power and transistor wise most of what a CPU does isn't even about running instructions, it is instruction reordering, cache, speculation, prefetching, write queueing and other techniques to minimize the effects of memory latency.

Instruction wise this is not true either. Sorting is a O(N log n) problem and log n is never going to be above 64. A cpu spending lots of time sorting implies that it is constantly throwing away the sorted results.

Pretty sure something like 80% of CPU time and power is spent pointer chasing in bad OO code.

I'd imagine that or string ops.

Not at all. Try running perf against your computer and you’ll see differently.

Reply on news.ycombinator.com