Andrei Alexandrescu

This was the best talk I saw at CppCon 2019

Sorting

• What is quick-select?

Naive Implementations

• qsort()

Better

• qsort() with fallback to small_sort()

Investigating small_sort

• Challenge: increase the THRESHOLD so sorting for 1000 elements work
• binary search is slower. Branch prediction is reader
• branchless even slower than binary
• middle-out insertion support: better comparison and better moves (13%) but no performance change
• stupid_small_sort(): make_heap(); insertion_sort(). Improvment in comparison, swaps; 9% slower
• Blended cost: (C(N) + M(n) + k(D(n))/n. (compares + swaps + distance)
• …

Timeline

• 1990’s OOP
• Inheritance and virtuals
• 2000’s Generic Programing
• Iterators and algos
• 2020’s: design by introspection
• Inspect and customize everything
• We can’t implement the best sort with generic programming

Questions

• Parametric complexity theory???