Searching for the Sorting Record: Experiences in Tuning NOW-Sort

Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau,
David E. Culler, Joseph M. Hellerstein, and David A. Patterson,

We present our experiences in developing and tuning the performance of NOW-Sort, a parallel, disk-to-disk sorting algorithm. NOW-Sort currently holds two world records in database-industry standard benchmarks. Critical to the tuning process was the setting of expectations, which tell the programmer both where to tune and when to stop. We found three categories of useful tools: tools that help set expectations and configure the application to different hardware parameters, visualization tools that animate performance counters, and search tools that track down performance anomalies. All such tools must interact well with all layers of the underlying software (e.g., the operating system), as well as with applications that leverage modern OS features, such as threads and memory-mapped I/O.
Full paper: Postscript