3 ms·

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 cod

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?

rightbyte 4y ago
> 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.
- nathell 4y ago
  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.
mtlmtlmtlmtl 4y ago
Sounds like the sort of thing dtrace or bpftrace might be able to do.
anacrolix 4y ago
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.
- saagarjha 4y ago
  Not at all. Try running perf against your computer and you’ll see differently.
- CyberDildonics 4y ago
  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.
- adgjlsfhk1 4y ago
  Pretty sure something like 80% of CPU time and power is spent pointer chasing in bad OO code.
  - andromeduck 4y ago
    I'd imagine that or string ops.

rightbyte 4y ago

> 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.

nathell 4y ago
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.

mtlmtlmtlmtl 4y ago

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

anacrolix 4y ago

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.

saagarjha 4y ago
Not at all. Try running perf against your computer and you’ll see differently.
CyberDildonics 4y ago
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.
adgjlsfhk1 4y ago
Pretty sure something like 80% of CPU time and power is spent pointer chasing in bad OO code.
- andromeduck 4y ago
  I'd imagine that or string ops.