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

---

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

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

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

---

#cppcon #cppprogramming #cpp

[Roibarkan]

38:31 [slide 60] I believe the comment code in the ‘day_diff_{a, b}’ is a little misleading. I think the issue in that situation relates to ‘transitivity of incomparability’. In the suggested case where (day_diff_{a, c} == X && day_diff_b == -X) is that both (a, b) and (b, c) are incomparable (i.e. both enter the if-statement), but (a, c) might actually be comparable (i.e ‘cmp(a, c)||cmp(c, a)’) due to the CompareCloser() function.
Great talk!!!

[Roibarkan]

43:04 [slide 60] regarding the use of integer comparator for float elements - is the only issue relates to potential overflows and NaNs/Inf, or if it’s also problematic in case all the floats in the range are finite and within the numeric limits of int.

[ignatloskutov]

Speaking of NaNs, it's kinda misleading to say it "NaN thinks it is equal to 3.0" (46:18 and the previous explainations as well): in terms of equality comparison, it doesn't think it's equal to anything. NaN is indeed equivalent to 3.0 in the sense that it is neither less-than or greater-than 3.0. When speaking of sorts, it's not the equality, it's the equivalence induced by the ordering is what we care about.

[ignatloskutov]

Sort not being stable by default and having stable_sort as "sort with the stability property" makes IMO more sense than having something named "unstable_sort" (what does "unstable" mean? what exact property does that algorithm have that the ordinary sort doesn't?).

[niklkelbon]

Why you dont add this checks on ub sanitizer? No one will use flags for it.
Why do not add special algorithm to check comparator to stl algorithms?