“AVX512 intrinsics are more powerful and better-suited for optimal sorting. https://arxiv.org/abs/1704.08579 Of course this presumes you have AVX512 hardware. (AMD gets it in Zen 3.) In the meantime, AVX2 will have to do.”
A Novel Hybrid Quicksort Algorithm Vectorized using AVX-512 on Intel Skylake
The modern CPU's design, which is composed of hierarchical memory and SIMD/vectorization capability, governs the potential for algorithms to be transformed into efficient implementations. The release of the AVX-512 changed things radically, and motivated us to search for an efficient sorting algorithm that can take advantage of it. In this paper, we describe the best strategy we have found, which is a novel two parts hybrid sort, based on the well-known Quicksort algorithm. The central partitioning operation is performed by a new algorithm, and small partitions/arrays are sorted using a branch-free Bitonic-based sort. This study is also an illustration of how classical algorithms can be adapted and enhanced by the AVX-512 extension. We evaluate the performance of our approach on a modern Intel Xeon Skylake and assess the different layers of our implementation by sorting/partitioning integers, double floating-point numbers, and key/value pairs of integers. Our results demonstrate that our approach is faster than two libraries of reference: the GNU \emph{C++} sort algorithm by a speedup factor of 4, and the Intel IPP library by a speedup factor of 1.4.
候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“If you define inline bool swap_if( bool c, int& a, int& b) { int ta = a, tb = b; a = c ? tb: ta; b = c ? ta: tb; return c; } and then use it in partition's inner loop like right += swap_if( *left < pivot, *left, *right);..., compiled with Clang (which generates `cmov` instructions), a simplest-possible quicksort is more than twice as fast …”
“SIMD based sorting isn't new, e.g. djbsort: https://sorting.cr.yp.to/. I find it strange the paper doesn't cite it or compare to it at all. EDIT: to be fair it does seem that Bramas' first published work on SIMD sorting (that I could find) predates djbsort, https://arxiv.org/abs/1704.08579. A comparison would still be nice though.”