go-pdqsort - Pattern Defeating Quicksort in Go
source link: https://www.tuicool.com/articles/2aaIjmB
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
go-pdqsort is my implementation of pattern defeating sort in golang. I knew about pattern defeating sort from rust’s standard library documentation. I’ve never heard about this algorithm and it immediately intrigues my interest. I googled about it and found the original implementation and their discussion threads on hacker news and reddit . Then I read the technical report from Orson Peters. The key observation from the algorithm is that merely reducing the miss rate from CPU branch prediction, it would make the sorting speed greatly improved (no need to flush the cache line etc), so the technique adopted was to put the index of the array in the buckets and don’t swap them immediately, but put them in the right bin and swap them in one batch at the end of the loop. This works perfectly in the language with zero cost abstraction like C/C++ and Rust. I wasn’t sure about that would work in the heap-managed languages like golang, python and ruby etc, since most of the things are on the heap (with pointer indirection) and often results into cache misses, the impact of branch prediction miss rate might be neglectable. (For sure it would depend on the escape analysis in golang compiler, it would put the things on stack if it doesn’t escape in general). Though my hunch was that it would be slower, it still a good practice to implement the algorithm by myself so that I would get to know the details of the algorithm. And here are the results
implementation speed pdqsort 80874 ns/op std-lib sort 69828 ns/opI am not sure about what std-lib’s sort is, but it looks like introsort since it switches to heapsort when the recursion is too deep, and it incorporates the techniques from shellsort as well, but the main part is still Bently’s quicksort technique. You can tell from the result that pdqsort is significantly slower than std-lib’s sort, probably due to the overhead of those memory batch swap, where it triggers extra allocation or cache eviction, pretty much as expected.
If you are interested in the algorithm, you could check out the code by yourself.
Recommend
-
50
uncaptcha Defeating Google's audio reCaptcha system with 85% accuracy. Disclaimer unCaptcha is intended to be a proof of concept. As of the time of
-
77
UACMe Defeating Windows User Account Control by abusing built-in Windows AutoElevate backdoor. System Requirements x86-32/x64 Windows 7/8/8.1/10 (client, some methods however works on server version too)...
-
231
README.md nonoCAPTCHA An async Python library to automate solving ReCAPTCHA v2 by audio, using Microsoft Azure's Speech-to-Text API. Disclaimer This project is for educational a...
-
47
The quicksort algorithm has the best case complexity of O(n log n) when each pivot in the sort divides the list into two equal uniform pieces [1]. The worst case occurs when the pivot always divides the list into one lis...
-
4
Pattern-defeating Quicksort - Orson Peters300 viewsFeb 28, 202214DislikeShareSave
-
6
pdqsort-qsort 可以对抗输入数据模式的排序算法。 quick sort 在输入数据接近有序的情况下,效率不高。 Pattern-defeating quicksort (pdqsort) is a novel sorting algorithm that combines the fast average case of...
-
13
use pdqsort · golang/go@72e77a7 · GitHub Permalink Brows...
-
11
Golang 的排序演算法將換成 pdqsort,LLVM libc++ 換成 BlockQuicksort 在 Hacker News 首頁上看到的消息,Golang 將會把
-
5
继Go 1.18支持泛型后,Go 将在下个版本中支持pdqsort排序算法再次引起了开发者们的热切讨论。
-
2
Go’s new sorting algorithm: pdqsort
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK