"Allegro" Means Both Fast and Happy. Coincidence?
summary
Takes std::sort (GCC baseline) on 1M random doubles, replaces the small-range routine with a custom heapified insertion: a faster make-heap, branch elimination by turning conditionals into arithmetic, and an unguarded insertion loop so the inner loop is tiny. Raising the cutoff from 32 to 64 cuts comparisons and swaps and drops wall time ~3% in tests and yields up to ~6% speedup versus std::sort; exposes average access distance as a better predictor than counts.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:33Subtitle #2
- 6:51Sorting
- 8:28Why is Quicksort Popular?
- 13:40Challenge
- 18:22Why Not Binary Insertion Sort?
- 23:26Tip: Try Silly Things
- 25:51Net Optimization
- 28:03GNU heapify
- 33:50Optimization is Imagination
- 42:13Inner Loop
- 48:04Comparisons (baseline: red)
- 51:53Trying Silly Things
- 52:33A Helpful Metric
- 53:33Average Access Distance
- 54:08Summary
