A Long Journey of Changing std::sort Implementation at Scale - Danila Kutenin

Sorting algorithms have been improving for almost 50 years now with claims of better efficiency and various properties but the question of adopting a new one at scale is often left behind. At Google we replaced std::sort in the LLVM libc++ library to test it for hundreds of thousand calls. We faced many challenges which we had been fixing for 2 years including golden tests, efficiency problems, undefined behavior and broken production. In this talk we want to cover issues on how we improved debugging, benchmarking, how much better a new implementation was compared to the old one and what we have learned on this journey of improved sorting.
Danila Kutenin is a Senior Software Engineer at Google in the Efficiency team. For 7 years Danila had an experience in optimizing Search Engines, Databases and General efficiency.