14 ms·

Changing std:sort at Google’s scale and beyond

566 points by ashvardanian 5y ago

techwiz137 5y ago
Do you need to have learned Computer Science to grasp the topic at hand here?
- deleted 5y ago
  [deleted]
jeffbee 5y ago
Huh. If I found that Reflection::ListFieldsMayFailOnStripped was a frequent caller of std::sort, to an extent that it was actually costing measurable CPU time, first thing I would do is find and fix all callers of that.
- gipp 5y ago
  "Fix" how exactly? I'm not quite sure what you're suggesting.
  - jeffbee 5y ago
    C++ proto reflection is a convenience. If it actually shows up at scale in production, that smells like a design error.
    - moultano 5y ago
      All things show up at scale in production at Google.
      - jeffbee 5y ago
        In one sense yes, but in another sense even though Google is large their threshold for something being worth fixing based on efficiency justifications is correspondingly large.
        foota 5y ago
        Frequently though, you're dealing with a death by a thousand paper cuts. Perhaps that call comes from some common library whose implementation requires reflection.
        moultano 5y ago
        It isn't though. A typical developer will never care about 0.1% of unnecessary CPU usage in their application, but at Google, depending on what component it's in, that can easily be a million dollar find.
        jcelerier 5y ago
        > In one sense yes, but in another sense even though Google is large their threshold for something being worth fixing based on efficiency justifications is correspondingly large. not everything is a linear relationship
        usefulcat 5y ago
        If you're measuring in terms of time, electricity, or hardware, then the threshold would tend to be lower for Google, not higher. A 0.1% savings on a million machines is ~1 million times more valuable than a 0.1% savings on a single machine. OTOH if the measurement is risk of breaking something, then it's not nearly so clear, since larger organizations tend to have more software and hardware, and therefore more opportunities for things to get broken.
        jeffbee 5y ago
        You're saying the opposite of what the other guy said, though. They said that at scale small things are big. I'm saying that at scale .001% is still .001%.
westurner 5y ago
> LLVM history: Back then we recognized some really interesting benchmarks and we didn’t recall anybody trying to really benchmark sorts on different data patterns for standard libraries. Timsort https://en.wikipedia.org/wiki/Timsort https://en.wikipedia.org/wiki/Timsort : > In the worst case, Timsort takes O(n log n) comparisons to sort an array of n elements. In the best case, which occurs when the input is already sorted, it runs in linear time, meaning that it is an adaptive sorting algorithm. [3] > It is advantageous over Quicksort for sorting object references or pointers because these require expensive memory indirection to access data and perform comparisons and Quicksort's cache coherence benefits are greatly reduced. [...] > Timsort has been Python's standard sorting algorithm since version 2.3 [~2002]. It is also used to sort arrays of non-primitive type in Java SE 7,[4] on the Android platform,[5] in GNU Octave,[6] on V8,[7] Swift,[8] and Rust.[9] Sorting algorithm > Comparison of algorithms https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o... Schwartzian transform https://en.wikipedia.org/wiki/Schwartzian_transform https://en.wikipedia.org/wiki/Schwartzian_transform : > In Python 2.4 and above, both the sorted() function and the in-place list.sort() method take a key= parameter that allows the user to provide a "key function" (like foo in the examples above). In Python 3 and above, use of the key function is the only way to specify a custom sort order (the previously supported cmp= parameter that allowed the user to provide a "comparison function" was removed). Before Python 2.4, developers would use the lisp-originated decorate–sort–undecorate (DSU) idiom,[2] usually by wrapping the objects in a (sortkey, object) tuple Big-O Cheatsheet https://www.bigocheatsheet.com/ https://www.bigocheatsheet.com/ Quicksort in Python 7 ways (and many other languages) on RosettaCode: https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Py...
- danlark 5y ago
  Thanks, I'll remove the note about "recalling"
  - westurner 5y ago
    xeus-cling didn't exist back then: https://github.com/jupyter-xeus/xeus-cling#a-c-notebook https://github.com/jupyter-xeus/xeus-cling#a-c-notebook https://github.com/fffaraz/awesome-cpp#debug https://github.com/fffaraz/awesome-cpp#debug A standard way to benchmark and chart {sorting algorithms, web framework benchmarks,} would be great. The TechEmpower "framework overhead" benchmarks might have at least average case sorting in there somewhere: https://www.techempower.com/benchmarks/#section=data-r20&hw=ph&test=fortune https://www.techempower.com/benchmarks/#section=data-r20&hw=...
Something1234 5y ago
I'm confused, so the comparison function can modify the list? I thought most sorting algorithms assumed the contents of the list was constant. Why would I want my comparator to ever modify the list under sort?
- danlark 5y ago
  You don't, it's just not disallowed :)
  - infogulch 5y ago
    "because it prevents the user from writing a comparison function that modifies the list while sorting" is not a reason I would expect to prefer rust, and yet here we are.
    - mbrubeck 5y ago
      It's possible in Rust too, but only for a subset of element types: those that support shared mutation (also known as "internal mutation"). For example, a type containing an `AtomicU32` or a `Mutex<T>` or a `Cell<T>` could have an `Ord::cmp` implementation that alters its value, and the compiler will not prevent this.
      - orlp 5y ago
        Yes, I had a nasty bug in an initial version of glidesort where I (naively) assumed that I could create a temporary copy of an element by doing a memcpy and call the comparison function on this temporary copy a bunch of times before throwing it away, since I assumed the comparison function would not mutate the copy. Unfortunately interior mutability means this would lead to potential double drops, and it was just not sound.
    - account42 5y ago
      The comparison operator is not actually mutating the list, which would not be allowed in C++ either. Instead it is dynamically generating the < comparison operator for the elements in the list based on the order for which elements it is evaluated. The order for two elements remains fixed once examined and in the end it always ends up with a valid totally ordered comparison operator. The only thing required for this to work is that the comparison operator can have mutable state and that the same shared state is used for all comparisons in the sorting algorithm (asided from thread-safety so you'd need adjustments for a parallel sort).
hu3 5y ago
offtopic: Such a great engineer and yet their blog says: Website Powered by WordPress.com. I find the pragmatism worthy of praise. I've been meaning to start blogging since forever but I keep planning and researching about blog platforms/tools and never get to the point.
- haolez 5y ago
  Making use of existing tools and being able to manage their shortcomings is an important engineering skill.
- sydthrowaway 5y ago
  - hatware 5y ago
    Did one person design the SR-71...?
    - sydthrowaway 5y ago
      yes
      - hatware 5y ago
        He was the head of the engineering team. He didn't go into a cave and come out with completed designs...
        sydthrowaway 5y ago
        Who gets credit for a really good movie?
        samhw 5y ago
        …the people who made it? I know none of us sit through the credits, but I can assure you they do typically carry on rolling for quite some time.
dekhn 5y ago
Great fun read. I love this stuff; when I first learned C++ many years ago I didn't really know much about complexity and what I have learned over the years is that complexity costs depend a lot on the underlying data distributions.
pikseladam 5y ago
wow. that was really impressive. scale is different kind of monster. it is like an end game boss. Thank you for sharing it. I learned a lot.
samueloph 5y ago
I'm starting to question my understanding of algorithmic complexity, the author says things like "complexity being worst case O(n \log n)" and seems to talk about big O notation used for average cases as well. I've learned that big O notation is always and exclusively about the worst case, for average and best cases we use Theta Θ and Omega Ω, respectively. Do people not follow these definitions strictly? Has the author committed a mistake or am I missing something? I did experience an interviewer once saying that my complexity analysis was wrong as the worst case would be extremely rare to hit, I did try to explain nicely that big O notation is always about the worst case, and that they were thinking about big Theta instead, now I wonder if I was wrong.
- waynecochran 5y ago
  You are mixing two things together. The "average/expected case" and the "worst case" are two different functions, each with their own O, Θ, Ω.
- SQueeeeeL 5y ago
  You should look into amortized complexity. That's the formalized name for worst case runtime over multiple trials.
- bsedlm 5y ago
  In my opinion, nothing about big-O and related omega, theta, etc, is at all strict. Maybe I value "pure symbolic clairty" too much. I do see a very pragmatic usefullness to the complexity notation.
- larsrc 5y ago
  There are variations, that's what we learned back at Uni. Expected O(f(n)), average O(f(n)), amortised O(f(n)), even expected amortised O(f(n)). "Expected" implied a randomised algorithm.
  - tsimionescu 5y ago
    > "Expected" implied a randomised algorithm. Not necessarily. It can be the "expected" number of steps over the range of unknown inputs even for a deterministic algorithm.
DontGiveTwoFlux 5y ago
OP describes systems which seed tests with non-determinism to catch users who write tests relying on undefined behavior, such as order of equal elements. Writing tests against these systems is a game changer (once you figure out what’s going on and why there are flakes). I’m a huge fan of this subtle change which has spared me at least one bug. It also allows library authors to gain the advantage of not accidentally producing a behavior that induces Hyrum’s law. Kudos to the team for making this work at scale.
- im3w1l 5y ago
  Depending on ASLR for randomization is ironically an extreme case of Hyrums law.
a_e_k 5y ago
> If you compare by a boolean variable, for example, partition data by existence of something, it’s very tempting to write std::sort call. > We saw a pattern of sort+resize a lot. These seem like good opportunities for clang-tidy checks.
10000truths 5y ago
I never really understood why a standard library would insist on having a single "sort" function (or at best, a "sort" and "stable sort"). Why not just provide explicit quick sort, merge sort etc. functions and let users choose which they want? Sorting is one of the first things a budding computer scientist learns, and the research on sorting algorithms is well-trodden ground by now, so I don't see how it could be a usability issue. I'd like to be able to choose from these criteria without having to rely on external libraries: - How does it perform on average? - How does it perform on pathological inputs? - Is it stable? - Does it allocate? Not to mention constraints that an application can take advantage of: - What if the data is already mostly sorted? (insertion sort) - What if writes are very expensive? (cycle sort) - What if all the data are integers? (radix sort) And so on. Trying to force a one-size-fits-all solution seems rather silly at this point.
- dijit 5y ago
  There are such things as sensible defaults though. Timsort being a somewhat famous example, which uses the fact that python datastructures are known length to figure out the best sorting method for the size. If you need something more exotic then you likely know more about what you're doing, but most people writing software who need a sort function usually don't need more than timsort.
  - morelisp 5y ago
    > uses the fact that python datastructures are known length to figure out the best sorting method for the size. That... does not match with my knowledge of how timsort works. The sorting method is chosen based on the array length, and every sorting algorithm in every language knows that. It's extremely suboptimal for some types because Python's typing is so weak! Timsort succeeds because it has many good heuristics to optimize common properties of its merge intervals.
- yupper32 5y ago
  There are defaults for all sorts of functions. find() functions on an array in many languages use some default. Parameters often have defaults when not set. Strings often have a default encoding. The vast majority of the time, the default works well enough. Why make things more complicated than they need to be? It also has the added benefits of helping more junior engineers when reading the code. "Cycle sort? What is that doing?" "Insertion sort? I was taught that was inefficient! I should spend time updating this code to a better sorting algorithm! My tech lead would love my initiative." Or we just use sort(), and we all move on with our lives.
timmytokyo 5y ago
"It took us around 20 years to find something really appropriate, thanks to Andrei Alexandrescu." The way this is written, it sounds as if Andrei Alexandrescu is responsible for the 20 year delay.
evmar 5y ago
The "use ASLR for random seed" trick in there is pretty cute, but I noticed it will just silently not work in non-ASLR settings, and in particular under Wasm.
- sedatk 5y ago
  Is there any other way to generate entropy without an OS dependency?
  - mhh__ 5y ago
    timestamp counter?
    - sedatk 5y ago
      Only works on x86.
      - mhh__ 5y ago
        As far as entropy generation goes other architectures have equivalents, albeit a few more instructions than just rdtsc
- spb 5y ago
  Recent versions of Lua use this trick as well.
- IshKebab 5y ago
  Not the end of the world though surely.
orlp 5y ago
Hi all, I'm the author of pdqsort that's credited in the post (to be clear: the authors acknowledged pdqsort at the bottom, I am not associated with the posted work directly). I recently held a talk at my institute on efficient in-memory sorting and the ideas in pdqsort, in case you're interested in hearing some of the theory behind it all: https://www.youtube.com/watch?v=jz-PBiWwNjc https://www.youtube.com/watch?v=jz-PBiWwNjc Next week I will hold another talk in the Dutch seminar on data systems design (https://dsdsd.da.cwi.nl/ https://dsdsd.da.cwi.nl/) on glidesort, a new stable sorting algorithm I've been working on. It is a combination of adaptive quicksort (like pdqsort, fully adaptive for many equal elements) and an adaptive mergesort (like timsort, fully adaptive for long pre-sorted runs). It is the first practical implementation of an algorithm I'm aware of that's fully adaptive for both. Like pdqsort it uses modern architecture aware branchless sorting, and it can use an arbitrary buffer size, becoming faster as you give it more memory (although if given a constant buffer size it will degrade to O(n (log n)^2) in theory, in practice for realistic workloads it's just a near-constant factor (c ~<= 3-5) slower). The source code isn't publish-ready yet, I have to still do some extra correctness vetting and testing, and in particular exception-safety is still not yet fully implemented. This is important because I wrote it in Rust where we must always give back a valid initialized array, even if a comparison operator caused a panic. But I do have some performance numbers to quote, that won't significantly change. For sorting 2^24 randomly shuffled distinct u32s using a buffer of 2^23 elements (n/2), glidesort beats Rust's stdlib slice::sort (which is a classic timsort also using a buffer of n/2) by a factor of 3.5 times. When stably sorting the same numbers comparing only their least significant 4 bits, it beats stdlib slice::sort by 12.5 times using 6.5 times fewer comparisons, both numbers on my Apple M1 Macbook. All of this is just using single-threaded code with a generic comparison function. No SIMD, no threads, no type-specific optimizations. Finally, glidesort with a buffer size of >= n/2 is faster than pdqsort.
- mlochbaum 5y ago
  Any chance you could comment on fluxsort[0], another fast quicksort? It's stable and uses a buffer about the size of the original array, which sounds like it puts it in a similar category as glidesort. Benchmarks against pdqsort at the end of that README; I can verify that it's faster on random data by 30% or so, and the stable partitioning should mean it's at least as adaptive (but the current implementation uses an initial analysis pass followed by adaptive mergesort rather than optimistic insertion sort to deal with nearly-sorted data, which IMO is fragile). There's an in-place effort called crumsort[1] along similar lines, but it's not stable. I've been doing a lot of work on sorting[2], in particular working to hybridize various approaches better. Very much looking forward to seeing how glidesort works. [0] https://github.com/scandum/fluxsort https://github.com/scandum/fluxsort [1] https://github.com/scandum/crumsort https://github.com/scandum/crumsort [2] https://mlochbaum.github.io/BQN/implementation/primitive/sort.html https://mlochbaum.github.io/BQN/implementation/primitive/sor...
forrestthewoods 5y ago
An interesting takeaway here is that custom comparators are really hard to write correctly. There are a lot of constraints that aren’t obvious. I suspect there should be a new std::verify_weak_ordering to help people write tests that perform n^3 tests on potential data to ensure a comparator is safe to use.
- jcelerier 5y ago
  MSVC and GCC's standard libraries implementations both have a debug mode which has been checking that for almost two decades.
  - forrestthewoods 5y ago
    Are you sure about that? I just ran an MSVC test that calls std::sort on a std::vector<float> containing a variety of values including infinity, negative infinity, and NaN. I compiled and ran under debug mode. There were no errors or exceptions. The end result was extremely incorrect. Maybe there's some extra flag to turn on even more tests. I've always found MSVC STL to be completely impossible to use in debug mode for any real project.
    - jcelerier 5y ago
      I'll double check - maybe the checking code only gets called when a custom comparator is provided, not the default < which would be used there.
      - jcelerier 5y ago
        After double check: std::sort(<some floats with NaNs>); indeed does not assert, what does assert (with a nice "invalid comparator" message in MSVC) is std::sort(..., [] (float a, float b) { return a <= b; }); std::sort(..., [] (float a, float b) { return true; }); or anything else that is not a correct < implementation. I'd assume they don't want to introduce a check for the FP case as it would break pretty much all the code on earth which assumes that NaNs and Infs do not exist.
hbn 5y ago
Sorry if this seems pedantic in the grand scheme of the topic, but is the indentation in the code samples messed up, or is there some kind of logic to it? I've never seen anything like that, and I find it pretty difficult to read.
- bogwog 5y ago
  Looks normal to me (except it seems like some snippets indent with 2 spaces while others indent with 4). The line spacing is weird though.
- danlark 5y ago
  Sorry, it definitely was a little inconsistent as I stored all snippets without proper formatting and I tried at the same time align texts for phones, etc Failed at everything. Will improve
DrBazza 5y ago
Quite a long interesting read. Unless I missed it, I recall that there’s optimal solutions for sorting up to 7?? items. I can’t find the reference, but unsurprisingly I read it a dlang forum post by Andrei Alexandrescu. Anyone have a link to that aspect of sorting?
- tialaramex 5y ago
  Under the section heading "Reinforcement learning for small sorts", there are diagrams of the small sorts, for 3, 4 and 5 items. They also explain that down here you're at the mercy of the physical hardware. Emitting one fewer x86 instruction does not necessarily make your program faster, still if it's not slower then smaller programs are good too.
seanp2k2 5y ago
Thanks, I'm going to write all this out on a whiteboard the next time someone asks me to sort a linked list in a technical interview. Edit: just wanted to clarify that the point I'm trying to make here is that if you want to ask someone if they've memorized the answer to that question, go ahead and ask it in a technical interview, because the real well-considered answer looks like the linked article, and my honest non-smartass answer is that one should use the library function and not try to implement it themselves until they've done sufficient research into the problem to prove to a reasonable degree that they indeed do need to re-implement sort() and that it's in the best interests of the business to fund such a project. Would love to read this over the phone to a recruiter and have them tell me that it's not what they have on their sheet.
- scatters 5y ago
  If you need to write a sort from scratch it's because you're in some weird restricted environment without a standard library. Not because you need to get a few percent better performance sorting some gargantuan data set. Being able to put together a sort from compares and swaps (or inserts, or whatever you have available) is at least evidence that you won't either panic or storm off when the tools you have are something less than ideal.
  - naniwaduni 5y ago
    "You have a weird bespoke data structure" is an example of an "environment" where you might not have a sort that works for your data in your standard library. Of course, if you're in that situation, you're not using a weird bespoke data structure for a mere few percent better performance.
  - gumby 5y ago
    Also in in such an environment (real world not interview) you almost always have constraints on your data and/or requirements that allow you to write something faster or smaller (depending on your needs) that can beat the standard implementation because it doesn’t have to handle corner cases (or as this post shows, some major cases as well).
  - 5y ago
pierrebai 5y ago
In the first example of problematic calls to nth_element, there is another bug: if the container contains nothing, it will call nth_element with begin(), begin() - 1, ... Also, typo: "compare functions much comply" -> "compare functions must comply"
- account42 5y ago
  The function is trying to get the median, which is not defined for an empty set. With this particular implementation, there is an assert for that: https://github.com/shogun-toolbox/shogun/blob/9b8d85/src/shogun/mathematics/linalg/LinalgNamespace.h#L1816 https://github.com/shogun-toolbox/shogun/blob/9b8d85/src/sho... Unrelated, but from the same section: > Fixes are trivial, access the nth element only after the call being made. Be careful. Wouldn't the proper fix to do the nth_element for the larget element first (for those cases that don't do that already) and then adjust the end to be the begin + larger_n for the second nth_element call? Otherwise the second call will check [begin + larger_n, end) again for no reason at all.
tialaramex 5y ago
Fun safety problems. Towards the end of this post, the author mentions a bunch of places where std::sort() blows up if your data or your sort rule doesn't exhibit strict weak ordering. In some cases you get a bad sort, which feels fair enough since you violated the rules the sort algorithm is relying on, but in others it literally has Undefined Behaviour in C++. Notably Rust's sort() and unstable_sort() do not have this problem, because of course these are safe Rust, and safe Rust doesn't have Undefined Behaviour. But why can this work? First up, one bullet which gets dodged is that Rust's floating point types (f32 and f64) are not Ord. Rust acknowledges that NaN != NaN and therefore we can't expect to go around sorting a slice of floating point values. In C++ that's on the programmer, in C++ the fact you can write a < b means that type counts as ordered, even though it trivially isn't for several built-in types. So if you simply naively try to sort an [f32] Rust says you can't because it isn't Ord, you will need to write a lambda or whatever to Order these f32s and then if some of them are NaN your lambda is responsible for deciding what to do about that. But even if we insist on getting in harm's way, safe Rust promises to protect us anyway. For example if I make an array of a thousand misfortunate::OnewayGreater<u8>s they're only one byte each, yet they all insist they're Ordered greater than each other and even than themselves, Rust's sort() doesn't cause Undefined Behaviour on this input. It may never succeed, since all the elements to be "sorted" insist they're greater than each other, but it definitely won't segfault, trash unrelated memory or cause chaos.
- nullc 5y ago
  > or cause chaos Running forever is pretty chaotic.
  - ElectricalUnion 5y ago
    Running forever is pretty stable. Halting is chaotic.
    - tialaramex 5y ago
      A trivial infinite loop is Undefined Behaviour in C++ but it is a completely reasonable thing to write in Rust and works fine, in fact Rust's underlying loop is an infinite loop unless you explicitly provide some way to break out of it, which you usually will.
gwern 5y ago
I'd like to hear more about the reinforcement learning part. The patch literally just says 'Reinforcement Learning'. Not very helpful!
lauv0x 5y ago
genzweedsmoker 5y ago
dang 5y ago
Recent and related: Go will use pdqsort in next release - https://news.ycombinator.com/item?id=31106157 https://news.ycombinator.com/item?id=31106157 - April 2022 (112 comments)
AtNightWeCode 5y ago
Seems like mostly a pointless change and it will break some software. Most developers never read the docs. There is always a question about how much rope you should give the users but in these cases my experience tells me that even if the docs clearly state something users will rely on real world results, not the docs. Especially if the development is test driven or if testing is done mainly with automatic tests. I would expect better decisions from the GO team. This is a poor decision not in line with the promises of GO. What did you have to do to not make a breaking change? Add something new and mark the old obsolete? Damn cool algorithm though.

566 points by ashvardanian 5y ago

techwiz137 5y ago

Do you need to have learned Computer Science to grasp the topic at hand here?

deleted 5y ago
[deleted]

jeffbee 5y ago

Huh. If I found that Reflection::ListFieldsMayFailOnStripped was a frequent caller of std::sort, to an extent that it was actually costing measurable CPU time, first thing I would do is find and fix all callers of that.

gipp 5y ago
"Fix" how exactly? I'm not quite sure what you're suggesting.
- jeffbee 5y ago
  C++ proto reflection is a convenience. If it actually shows up at scale in production, that smells like a design error.
  - moultano 5y ago
    All things show up at scale in production at Google.
    - jeffbee 5y ago
      In one sense yes, but in another sense even though Google is large their threshold for something being worth fixing based on efficiency justifications is correspondingly large.
      - foota 5y ago
        Frequently though, you're dealing with a death by a thousand paper cuts. Perhaps that call comes from some common library whose implementation requires reflection.
      - moultano 5y ago
        It isn't though. A typical developer will never care about 0.1% of unnecessary CPU usage in their application, but at Google, depending on what component it's in, that can easily be a million dollar find.
      - jcelerier 5y ago
        > In one sense yes, but in another sense even though Google is large their threshold for something being worth fixing based on efficiency justifications is correspondingly large. not everything is a linear relationship
      - usefulcat 5y ago
        If you're measuring in terms of time, electricity, or hardware, then the threshold would tend to be lower for Google, not higher. A 0.1% savings on a million machines is ~1 million times more valuable than a 0.1% savings on a single machine. OTOH if the measurement is risk of breaking something, then it's not nearly so clear, since larger organizations tend to have more software and hardware, and therefore more opportunities for things to get broken.
        jeffbee 5y ago
        You're saying the opposite of what the other guy said, though. They said that at scale small things are big. I'm saying that at scale .001% is still .001%.

westurner 5y ago

> LLVM history: Back then we recognized some really interesting benchmarks and we didn’t recall anybody trying to really benchmark sorts on different data patterns for standard libraries. Timsort https://en.wikipedia.org/wiki/Timsort https://en.wikipedia.org/wiki/Timsort : > In the worst case, Timsort takes O(n log n) comparisons to sort an array of n elements. In the best case, which occurs when the input is already sorted, it runs in linear time, meaning that it is an adaptive sorting algorithm. [3] > It is advantageous over Quicksort for sorting object references or pointers because these require expensive memory indirection to access data and perform comparisons and Quicksort's cache coherence benefits are greatly reduced. [...] > Timsort has been Python's standard sorting algorithm since version 2.3 [~2002]. It is also used to sort arrays of non-primitive type in Java SE 7,[4] on the Android platform,[5] in GNU Octave,[6] on V8,[7] Swift,[8] and Rust.[9] Sorting algorithm > Comparison of algorithms https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o... Schwartzian transform https://en.wikipedia.org/wiki/Schwartzian_transform https://en.wikipedia.org/wiki/Schwartzian_transform : > In Python 2.4 and above, both the sorted() function and the in-place list.sort() method take a key= parameter that allows the user to provide a "key function" (like foo in the examples above). In Python 3 and above, use of the key function is the only way to specify a custom sort order (the previously supported cmp= parameter that allowed the user to provide a "comparison function" was removed). Before Python 2.4, developers would use the lisp-originated decorate–sort–undecorate (DSU) idiom,[2] usually by wrapping the objects in a (sortkey, object) tuple Big-O Cheatsheet https://www.bigocheatsheet.com/ https://www.bigocheatsheet.com/ Quicksort in Python 7 ways (and many other languages) on RosettaCode: https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Py...

danlark 5y ago
Thanks, I'll remove the note about "recalling"
- westurner 5y ago
  xeus-cling didn't exist back then: https://github.com/jupyter-xeus/xeus-cling#a-c-notebook https://github.com/jupyter-xeus/xeus-cling#a-c-notebook https://github.com/fffaraz/awesome-cpp#debug https://github.com/fffaraz/awesome-cpp#debug A standard way to benchmark and chart {sorting algorithms, web framework benchmarks,} would be great. The TechEmpower "framework overhead" benchmarks might have at least average case sorting in there somewhere: https://www.techempower.com/benchmarks/#section=data-r20&hw=ph&test=fortune https://www.techempower.com/benchmarks/#section=data-r20&hw=...

Something1234 5y ago

I'm confused, so the comparison function can modify the list? I thought most sorting algorithms assumed the contents of the list was constant. Why would I want my comparator to ever modify the list under sort?

danlark 5y ago
You don't, it's just not disallowed :)
- infogulch 5y ago
  "because it prevents the user from writing a comparison function that modifies the list while sorting" is not a reason I would expect to prefer rust, and yet here we are.
  - mbrubeck 5y ago
    It's possible in Rust too, but only for a subset of element types: those that support shared mutation (also known as "internal mutation"). For example, a type containing an `AtomicU32` or a `Mutex<T>` or a `Cell<T>` could have an `Ord::cmp` implementation that alters its value, and the compiler will not prevent this.
    - orlp 5y ago
      Yes, I had a nasty bug in an initial version of glidesort where I (naively) assumed that I could create a temporary copy of an element by doing a memcpy and call the comparison function on this temporary copy a bunch of times before throwing it away, since I assumed the comparison function would not mutate the copy. Unfortunately interior mutability means this would lead to potential double drops, and it was just not sound.
  - account42 5y ago
    The comparison operator is not actually mutating the list, which would not be allowed in C++ either. Instead it is dynamically generating the < comparison operator for the elements in the list based on the order for which elements it is evaluated. The order for two elements remains fixed once examined and in the end it always ends up with a valid totally ordered comparison operator. The only thing required for this to work is that the comparison operator can have mutable state and that the same shared state is used for all comparisons in the sorting algorithm (asided from thread-safety so you'd need adjustments for a parallel sort).

hu3 5y ago

offtopic: Such a great engineer and yet their blog says: Website Powered by WordPress.com. I find the pragmatism worthy of praise. I've been meaning to start blogging since forever but I keep planning and researching about blog platforms/tools and never get to the point.

haolez 5y ago
Making use of existing tools and being able to manage their shortcomings is an important engineering skill.
sydthrowaway 5y ago
- hatware 5y ago
  Did one person design the SR-71...?
  - sydthrowaway 5y ago
    yes
    - hatware 5y ago
      He was the head of the engineering team. He didn't go into a cave and come out with completed designs...
      - sydthrowaway 5y ago
        Who gets credit for a really good movie?
        samhw 5y ago
        …the people who made it? I know none of us sit through the credits, but I can assure you they do typically carry on rolling for quite some time.

dekhn 5y ago

Great fun read. I love this stuff; when I first learned C++ many years ago I didn't really know much about complexity and what I have learned over the years is that complexity costs depend a lot on the underlying data distributions.

pikseladam 5y ago

wow. that was really impressive. scale is different kind of monster. it is like an end game boss. Thank you for sharing it. I learned a lot.

samueloph 5y ago

I'm starting to question my understanding of algorithmic complexity, the author says things like "complexity being worst case O(n \log n)" and seems to talk about big O notation used for average cases as well. I've learned that big O notation is always and exclusively about the worst case, for average and best cases we use Theta Θ and Omega Ω, respectively. Do people not follow these definitions strictly? Has the author committed a mistake or am I missing something? I did experience an interviewer once saying that my complexity analysis was wrong as the worst case would be extremely rare to hit, I did try to explain nicely that big O notation is always about the worst case, and that they were thinking about big Theta instead, now I wonder if I was wrong.

waynecochran 5y ago
You are mixing two things together. The "average/expected case" and the "worst case" are two different functions, each with their own O, Θ, Ω.
SQueeeeeL 5y ago
You should look into amortized complexity. That's the formalized name for worst case runtime over multiple trials.
bsedlm 5y ago
In my opinion, nothing about big-O and related omega, theta, etc, is at all strict. Maybe I value "pure symbolic clairty" too much. I do see a very pragmatic usefullness to the complexity notation.
larsrc 5y ago
There are variations, that's what we learned back at Uni. Expected O(f(n)), average O(f(n)), amortised O(f(n)), even expected amortised O(f(n)). "Expected" implied a randomised algorithm.
- tsimionescu 5y ago
  > "Expected" implied a randomised algorithm. Not necessarily. It can be the "expected" number of steps over the range of unknown inputs even for a deterministic algorithm.

DontGiveTwoFlux 5y ago

OP describes systems which seed tests with non-determinism to catch users who write tests relying on undefined behavior, such as order of equal elements. Writing tests against these systems is a game changer (once you figure out what’s going on and why there are flakes). I’m a huge fan of this subtle change which has spared me at least one bug. It also allows library authors to gain the advantage of not accidentally producing a behavior that induces Hyrum’s law. Kudos to the team for making this work at scale.

im3w1l 5y ago
Depending on ASLR for randomization is ironically an extreme case of Hyrums law.

a_e_k 5y ago

> If you compare by a boolean variable, for example, partition data by existence of something, it’s very tempting to write std::sort call. > We saw a pattern of sort+resize a lot. These seem like good opportunities for clang-tidy checks.

10000truths 5y ago

I never really understood why a standard library would insist on having a single "sort" function (or at best, a "sort" and "stable sort"). Why not just provide explicit quick sort, merge sort etc. functions and let users choose which they want? Sorting is one of the first things a budding computer scientist learns, and the research on sorting algorithms is well-trodden ground by now, so I don't see how it could be a usability issue. I'd like to be able to choose from these criteria without having to rely on external libraries: - How does it perform on average? - How does it perform on pathological inputs? - Is it stable? - Does it allocate? Not to mention constraints that an application can take advantage of: - What if the data is already mostly sorted? (insertion sort) - What if writes are very expensive? (cycle sort) - What if all the data are integers? (radix sort) And so on. Trying to force a one-size-fits-all solution seems rather silly at this point.

dijit 5y ago
There are such things as sensible defaults though. Timsort being a somewhat famous example, which uses the fact that python datastructures are known length to figure out the best sorting method for the size. If you need something more exotic then you likely know more about what you're doing, but most people writing software who need a sort function usually don't need more than timsort.
- morelisp 5y ago
  > uses the fact that python datastructures are known length to figure out the best sorting method for the size. That... does not match with my knowledge of how timsort works. The sorting method is chosen based on the array length, and every sorting algorithm in every language knows that. It's extremely suboptimal for some types because Python's typing is so weak! Timsort succeeds because it has many good heuristics to optimize common properties of its merge intervals.
yupper32 5y ago
There are defaults for all sorts of functions. find() functions on an array in many languages use some default. Parameters often have defaults when not set. Strings often have a default encoding. The vast majority of the time, the default works well enough. Why make things more complicated than they need to be? It also has the added benefits of helping more junior engineers when reading the code. "Cycle sort? What is that doing?" "Insertion sort? I was taught that was inefficient! I should spend time updating this code to a better sorting algorithm! My tech lead would love my initiative." Or we just use sort(), and we all move on with our lives.

timmytokyo 5y ago

"It took us around 20 years to find something really appropriate, thanks to Andrei Alexandrescu." The way this is written, it sounds as if Andrei Alexandrescu is responsible for the 20 year delay.

evmar 5y ago

The "use ASLR for random seed" trick in there is pretty cute, but I noticed it will just silently not work in non-ASLR settings, and in particular under Wasm.

sedatk 5y ago
Is there any other way to generate entropy without an OS dependency?
- mhh__ 5y ago
  timestamp counter?
  - sedatk 5y ago
    Only works on x86.
    - mhh__ 5y ago
      As far as entropy generation goes other architectures have equivalents, albeit a few more instructions than just rdtsc
spb 5y ago
Recent versions of Lua use this trick as well.
IshKebab 5y ago
Not the end of the world though surely.

orlp 5y ago

Hi all, I'm the author of pdqsort that's credited in the post (to be clear: the authors acknowledged pdqsort at the bottom, I am not associated with the posted work directly). I recently held a talk at my institute on efficient in-memory sorting and the ideas in pdqsort, in case you're interested in hearing some of the theory behind it all: https://www.youtube.com/watch?v=jz-PBiWwNjc https://www.youtube.com/watch?v=jz-PBiWwNjc Next week I will hold another talk in the Dutch seminar on data systems design (https://dsdsd.da.cwi.nl/ https://dsdsd.da.cwi.nl/) on glidesort, a new stable sorting algorithm I've been working on. It is a combination of adaptive quicksort (like pdqsort, fully adaptive for many equal elements) and an adaptive mergesort (like timsort, fully adaptive for long pre-sorted runs). It is the first practical implementation of an algorithm I'm aware of that's fully adaptive for both. Like pdqsort it uses modern architecture aware branchless sorting, and it can use an arbitrary buffer size, becoming faster as you give it more memory (although if given a constant buffer size it will degrade to O(n (log n)^2) in theory, in practice for realistic workloads it's just a near-constant factor (c ~<= 3-5) slower). The source code isn't publish-ready yet, I have to still do some extra correctness vetting and testing, and in particular exception-safety is still not yet fully implemented. This is important because I wrote it in Rust where we must always give back a valid initialized array, even if a comparison operator caused a panic. But I do have some performance numbers to quote, that won't significantly change. For sorting 2^24 randomly shuffled distinct u32s using a buffer of 2^23 elements (n/2), glidesort beats Rust's stdlib slice::sort (which is a classic timsort also using a buffer of n/2) by a factor of 3.5 times. When stably sorting the same numbers comparing only their least significant 4 bits, it beats stdlib slice::sort by 12.5 times using 6.5 times fewer comparisons, both numbers on my Apple M1 Macbook. All of this is just using single-threaded code with a generic comparison function. No SIMD, no threads, no type-specific optimizations. Finally, glidesort with a buffer size of >= n/2 is faster than pdqsort.

mlochbaum 5y ago
Any chance you could comment on fluxsort[0], another fast quicksort? It's stable and uses a buffer about the size of the original array, which sounds like it puts it in a similar category as glidesort. Benchmarks against pdqsort at the end of that README; I can verify that it's faster on random data by 30% or so, and the stable partitioning should mean it's at least as adaptive (but the current implementation uses an initial analysis pass followed by adaptive mergesort rather than optimistic insertion sort to deal with nearly-sorted data, which IMO is fragile). There's an in-place effort called crumsort[1] along similar lines, but it's not stable. I've been doing a lot of work on sorting[2], in particular working to hybridize various approaches better. Very much looking forward to seeing how glidesort works. [0] https://github.com/scandum/fluxsort https://github.com/scandum/fluxsort [1] https://github.com/scandum/crumsort https://github.com/scandum/crumsort [2] https://mlochbaum.github.io/BQN/implementation/primitive/sort.html https://mlochbaum.github.io/BQN/implementation/primitive/sor...

forrestthewoods 5y ago

An interesting takeaway here is that custom comparators are really hard to write correctly. There are a lot of constraints that aren’t obvious. I suspect there should be a new std::verify_weak_ordering to help people write tests that perform n^3 tests on potential data to ensure a comparator is safe to use.

jcelerier 5y ago
MSVC and GCC's standard libraries implementations both have a debug mode which has been checking that for almost two decades.
- forrestthewoods 5y ago
  Are you sure about that? I just ran an MSVC test that calls std::sort on a std::vector<float> containing a variety of values including infinity, negative infinity, and NaN. I compiled and ran under debug mode. There were no errors or exceptions. The end result was extremely incorrect. Maybe there's some extra flag to turn on even more tests. I've always found MSVC STL to be completely impossible to use in debug mode for any real project.
  - jcelerier 5y ago
    I'll double check - maybe the checking code only gets called when a custom comparator is provided, not the default < which would be used there.
    - jcelerier 5y ago
      After double check: std::sort(<some floats with NaNs>); indeed does not assert, what does assert (with a nice "invalid comparator" message in MSVC) is std::sort(..., [] (float a, float b) { return a <= b; }); std::sort(..., [] (float a, float b) { return true; }); or anything else that is not a correct < implementation. I'd assume they don't want to introduce a check for the FP case as it would break pretty much all the code on earth which assumes that NaNs and Infs do not exist.

hbn 5y ago

Sorry if this seems pedantic in the grand scheme of the topic, but is the indentation in the code samples messed up, or is there some kind of logic to it? I've never seen anything like that, and I find it pretty difficult to read.

bogwog 5y ago
Looks normal to me (except it seems like some snippets indent with 2 spaces while others indent with 4). The line spacing is weird though.
danlark 5y ago
Sorry, it definitely was a little inconsistent as I stored all snippets without proper formatting and I tried at the same time align texts for phones, etc Failed at everything. Will improve

DrBazza 5y ago

Quite a long interesting read. Unless I missed it, I recall that there’s optimal solutions for sorting up to 7?? items. I can’t find the reference, but unsurprisingly I read it a dlang forum post by Andrei Alexandrescu. Anyone have a link to that aspect of sorting?

tialaramex 5y ago
Under the section heading "Reinforcement learning for small sorts", there are diagrams of the small sorts, for 3, 4 and 5 items. They also explain that down here you're at the mercy of the physical hardware. Emitting one fewer x86 instruction does not necessarily make your program faster, still if it's not slower then smaller programs are good too.

seanp2k2 5y ago

Thanks, I'm going to write all this out on a whiteboard the next time someone asks me to sort a linked list in a technical interview. Edit: just wanted to clarify that the point I'm trying to make here is that if you want to ask someone if they've memorized the answer to that question, go ahead and ask it in a technical interview, because the real well-considered answer looks like the linked article, and my honest non-smartass answer is that one should use the library function and not try to implement it themselves until they've done sufficient research into the problem to prove to a reasonable degree that they indeed do need to re-implement sort() and that it's in the best interests of the business to fund such a project. Would love to read this over the phone to a recruiter and have them tell me that it's not what they have on their sheet.

scatters 5y ago
If you need to write a sort from scratch it's because you're in some weird restricted environment without a standard library. Not because you need to get a few percent better performance sorting some gargantuan data set. Being able to put together a sort from compares and swaps (or inserts, or whatever you have available) is at least evidence that you won't either panic or storm off when the tools you have are something less than ideal.
- naniwaduni 5y ago
  "You have a weird bespoke data structure" is an example of an "environment" where you might not have a sort that works for your data in your standard library. Of course, if you're in that situation, you're not using a weird bespoke data structure for a mere few percent better performance.
- gumby 5y ago
  Also in in such an environment (real world not interview) you almost always have constraints on your data and/or requirements that allow you to write something faster or smaller (depending on your needs) that can beat the standard implementation because it doesn’t have to handle corner cases (or as this post shows, some major cases as well).
- 5y ago

pierrebai 5y ago

In the first example of problematic calls to nth_element, there is another bug: if the container contains nothing, it will call nth_element with begin(), begin() - 1, ... Also, typo: "compare functions much comply" -> "compare functions must comply"

account42 5y ago
The function is trying to get the median, which is not defined for an empty set. With this particular implementation, there is an assert for that: https://github.com/shogun-toolbox/shogun/blob/9b8d85/src/shogun/mathematics/linalg/LinalgNamespace.h#L1816 https://github.com/shogun-toolbox/shogun/blob/9b8d85/src/sho... Unrelated, but from the same section: > Fixes are trivial, access the nth element only after the call being made. Be careful. Wouldn't the proper fix to do the nth_element for the larget element first (for those cases that don't do that already) and then adjust the end to be the begin + larger_n for the second nth_element call? Otherwise the second call will check [begin + larger_n, end) again for no reason at all.

tialaramex 5y ago

Fun safety problems. Towards the end of this post, the author mentions a bunch of places where std::sort() blows up if your data or your sort rule doesn't exhibit strict weak ordering. In some cases you get a bad sort, which feels fair enough since you violated the rules the sort algorithm is relying on, but in others it literally has Undefined Behaviour in C++. Notably Rust's sort() and unstable_sort() do not have this problem, because of course these are safe Rust, and safe Rust doesn't have Undefined Behaviour. But why can this work? First up, one bullet which gets dodged is that Rust's floating point types (f32 and f64) are not Ord. Rust acknowledges that NaN != NaN and therefore we can't expect to go around sorting a slice of floating point values. In C++ that's on the programmer, in C++ the fact you can write a < b means that type counts as ordered, even though it trivially isn't for several built-in types. So if you simply naively try to sort an [f32] Rust says you can't because it isn't Ord, you will need to write a lambda or whatever to Order these f32s and then if some of them are NaN your lambda is responsible for deciding what to do about that. But even if we insist on getting in harm's way, safe Rust promises to protect us anyway. For example if I make an array of a thousand misfortunate::OnewayGreater<u8>s they're only one byte each, yet they all insist they're Ordered greater than each other and even than themselves, Rust's sort() doesn't cause Undefined Behaviour on this input. It may never succeed, since all the elements to be "sorted" insist they're greater than each other, but it definitely won't segfault, trash unrelated memory or cause chaos.

nullc 5y ago
> or cause chaos Running forever is pretty chaotic.
- ElectricalUnion 5y ago
  Running forever is pretty stable. Halting is chaotic.
  - tialaramex 5y ago
    A trivial infinite loop is Undefined Behaviour in C++ but it is a completely reasonable thing to write in Rust and works fine, in fact Rust's underlying loop is an infinite loop unless you explicitly provide some way to break out of it, which you usually will.

gwern 5y ago

I'd like to hear more about the reinforcement learning part. The patch literally just says 'Reinforcement Learning'. Not very helpful!

lauv0x 5y ago

genzweedsmoker 5y ago

dang 5y ago

Recent and related: Go will use pdqsort in next release - https://news.ycombinator.com/item?id=31106157 https://news.ycombinator.com/item?id=31106157 - April 2022 (112 comments)

AtNightWeCode 5y ago

Seems like mostly a pointless change and it will break some software. Most developers never read the docs. There is always a question about how much rope you should give the users but in these cases my experience tells me that even if the docs clearly state something users will rely on real world results, not the docs. Especially if the development is test driven or if testing is done mainly with automatic tests. I would expect better decisions from the GO team. This is a poor decision not in line with the promises of GO. What did you have to do to not make a breaking change? Add something new and mark the old obsolete? Damn cool algorithm though.