CppCon 2019: Speed Is Found In The Minds of People

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.