24 ms·
Go will use pdqsort in next release
- dang 4y agoRecent and related: Changing std:sort at Google’s scale and beyond - https://news.ycombinator.com/item?id=31098822 https://news.ycombinator.com/item?id=31098822 - April 2022 (144 comments)
- onionisafruit 4y agoGood for them. It’s good to improve on the standard library sort, but if you’re looking for performance you probably aren’t just blindly using the standard library sort anyway. You try a few things until you find the one that is best for your situation.
- jchw 4y agoThis is true, but it’s definitely still a very nice win. For things where either performance isn’t very critical or there just isn’t time to micro-optimize, it’s nice when the standard library provides best-in-class general solutions for problems. The philosophy is sort of the same as that of a rising tide lifts all boats. The difference it makes could still be a quality of life improvement without the element of necessity. Overall, I think the Go standard library does pretty good here, and yet it could still do better, and it’s definitely nice to see it improve.
- Xavdidtheshadow 4y ago> if you're looking for performance you probably aren't just blindly using the standard library sort anyway That's so interesting- I think I have the opposite response. I figure unless I'm doing a very specific case that doesn't fit well with the stdlib sort (for some specific reason), It's probably good enough. Those language folks usually know their stuff, who am I to try something else?
- nicoburns 4y agoAre you looking at that from a perspective of implementing your own sort if you’re not using the stdlib one? From my perspective I can likely install and try out a drop-in replacement library in about 60 seconds. So if sorting is a bottleneck then why wouldn’t I?
- onionisafruit 4y agoI agree that it is relatively rare for sort to be your bottleneck. What I meant is that in that relatively rare circumstance most people are going to look outside the standard library and try a few different sorts. My comment also had a more dismissive tone than I intended.
- buryat 4y agoso the behavior is going to change: sorting becomes unstable, i.e. it doesn't preserve the relative order of equal elements. I'm pretty sure this will affect users
- sanxiyn 4y agoGo's sort was already unstable.
- buryat 4y agooh, that's pretty cool
- deleted 4y ago[deleted]
- ayanamist 4y agoIf you want a stable sort, you should always use https://pkg.go.dev/sort#SliceStable https://pkg.go.dev/sort#SliceStable This PR only modifies Slice method which is declared as "is not guaranteed to be stable"
- Asraelite 4y agoGo already randomizes the order of keys in map iterations to discourage relying on undefined behavior. It would be funny if they randomized the order of equal elements in what would otherwise be a stable algorithm for the same reason.
- skunkworker 4y agoCurrently sort is not guaranteed to be stable. https://github.com/golang/go/blob/master/src/sort/sort.go#L41 https://github.com/golang/go/blob/master/src/sort/sort.go#L4...
- dehrmann 4y agoIs it stable, but not guaranteed to be stable, or is it unstable? If it just happens to be stable, code somewhere will eventually depend on that behavior.
- memorable 4y agoConcidentally I just read an old HN thread that says pdqsort is the best unstable sorting algorithm a few hours ago or so.
- pastaking 4y agoOn a side note, this change's author is from ByteDance. It's great to see everyone working together on open source.
- limoce 4y agoThat makes sense. ByteDance has many employees who have experiences in competitive programming. These guys tend to be more sensitive and aggressive in algorithmic changes.
- sydthrowaway 4y agoThe ByteDance interviews must be tough, but what they're making is completely trash. I'm not talking about the quality of their product.
- hcbasedhacker 4y ago
- jrockway 4y agoYou created a brand new HN account to shitpost about Rob Pike? I'm not even mad, that's amazing.
- Koffiepoeder 4y agoTo be honest, this is not a shitpost in my opinion. He might really have met Pike and Pike really might have said that some day.
- mhh__ 4y agoDoes this bar serve anything other than everclear?
- wiz21c 4y agoThe idea is not bad but it sounds a bit extreme... Indeed choosing the right sorting algorithm is important and depends on one's problem to solve. But, 99.99% of the time, a general, all-round algorithm will do the job within 99% of the best-one's performance... But when it fails, well, it will fail big... In my experience, some devs (me included :-)) make tests with a reduced dataset 'cos they can iterate faster and then go in production without testing on a real-size dataset. All of a sudden, the o(n²) edge case becomes, well, a problem :-)
- dehrmann 4y agoWith how long we've been studying sorting algorithms, I'm amazed we're still coming up with optimizations that yield real-world improvements.
- rav 4y agoGiven that sorting algorithms are evaluated on practical merits on real-world hardware - when the hardware changes, sometimes the sorting algorithm has to change too.
- deleted 4y ago[deleted]
- Cthulhu_ 4y agoIt's not just the algorithms, but the hardware as well; the base algorithms we were taught in school were usually aimed at single-threaded applications, but in the past two decades, multithreading and parallelisation has become mainstream.
- karelpeeters 4y agoThat's not particularly relevant, no standard library sort method is using multithreading in the background. It actually is about algorithmic improvements.
- morelisp 4y agoFor sorting algorithms many of the "algorithmic improvements" are caching / locality / access pattern improvements, as latency differences get more extreme and cache sizes grow. (At multiple levels, L1/L2 vs. RAM, RAM vs. disk, node vs. network.) So it's still very much tied to changes in hardware. Whether you call that an "algorithmic improvement" or not is mostly semantics, it would not have been called such in the 80s but it would be today - what properties we consider part of "the algorithm" has also changed to meet hardware changes. Even whether it's "parallelization" is somewhat semantics - if you change an algorithm to avoid a pipeline stall, is that designing it for parallelization? I guess not because it's single-threaded, but again someone in the 70s/80s might say yes because two things are happening at once.
- verst 4y agoThis solution was developed by a SWE 2 candidate in the FAANG on-site interview loop. /s (Just joking but some interviews indeed feel that way)
- randunel 4y agoI was wondering about the morality of using candidates' solutions in your products. Does the hiring company own the test results? Does the candidate? What if the candidate gets hired, who owns the solution, then? The candidate does not get paid to solve the interview test, but it could be seen as a collaborative effort on both the company and the candidate, since both put time and engineering resource in it.
- powersnail 4y agoIs algorithm copyright-able? If it can be regarded as an intellectual property, does that mean that the company would be infringing on the candidate’s right?
- iampivot 4y agoXOR certainly was patented for use to display mouse cursors.
- dijit 4y agoIt is immoral to use candidate answers in your product, assuming you don’t hire them. If you do hire them then I guess it becomes fine, but otherwise definitely immoral. The problem is that we’re fleshy meatbags and easily influenced. It’s possible we internalise answers to interview questions and then “spontaneously” come up with them later, without _knowingly_ stealing the idea. This happens sometimes in comedy, and the comedian apologises. You can usually tell the difference in comedy between plagiarism and accidental theft because the joke is delivered much differently but has the same core. It would be harder with interview answers.
- biztos 4y ago
- Shadonototra 4y agoGo is a great language, reading the code in this PR is so easy
- kevincox 4y agoOn the other hand without generics they are literally using a text templating language to generate the code.
- morelisp 4y agoGenerics alone wouldn't be sufficient to replace the code generator, you'd also need specialization and/or overloading, or at least some significantly different syntax allowed for comparing primitive types.
- kevincox 4y agoI think it probably would in this case. They appear to be substituting just a comparison function. They could instead take a generic type argument that had the desired functions defined. Then you would just need to write the top level wrappers with the different names. In fact they could probably have done this with a traditional Go interface if they weren't worried about missed optimizations.
- deleted 4y ago[deleted]
- yencabulator 4y agoI fear the generic version would miss on those same optimizations, and that is the real reason it's written like it is. Remember, Go generics use gcshape stenciling, not C++ style templates.
- icholy 4y agoI believe OP is being sarcastic.
- dejongh 4y agoWow. I did not expect such a simple improvement to have such a big effect.
- Maksadbek 4y agoIMO, These changes does not look that simple.
- orlp 4y agoI think I will copy/paste my comment from a thread from yesterday (https://news.ycombinator.com/item?id=31098822 https://news.ycombinator.com/item?id=31098822), which incidentally was also referring to pdqsort, as it is just as relevant here: Hi all, I'm the author of pdqsort. 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.
- MaxBarraclough 4y agoSee also this 2017 thread on pdqsort: https://news.ycombinator.com/item?id=14661659 https://news.ycombinator.com/item?id=14661659 Direct link to the GitHub home of pdqsort (in C++), which has some performance comparisons: https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort
- B-Con 4y agoI did a quick Google search for pdqsort and found this HN post: https://news.ycombinator.com/item?id=14666710 https://news.ycombinator.com/item?id=14666710 > I think it's fair to say that pdqsort (pattern-defeating quicksort) is overall the best unstable sort and timsort is overall the best stable sort in 2017, at least if you're implementing one for a standard library. _hrfd called it 5 years ago.
- dhzhzjsbevs 4y agohttps://news.ycombinator.com/item?id=31107187 https://news.ycombinator.com/item?id=31107187 Maybe not anymore?
- The_rationalist 4y ago
- lifefeed 4y agoThis is a small thing, but I love that it uses Heapsort as its fallback. Heapsort is such a pretty algorithm and I always like seeing it used in the wild.
- alanbernstein 4y agoThis is my first time reading about pdqsort. I haven't read through the paper, but it's a neat concept, sort of a hybrid that can reduce to a radix sort-like behavior. The cost is instability and slightly worse behavior for, I suppose, higher-entropy inputs. It's interesting to think that sorting has a maximum "total complexity", distributed across the whole input space. And this hybrid algorithm kind of shapes that distribution, squeezing efficiency out of one part of the space, and into another, more practically meaningful part.