如何用C++库实现基于键的对象快速排序？（适配AVX512）

现有对象数组T *O，以及由K[i] = f(O[i])定义的键数组double *K，sizeof(T)取16字节（最大不超过32字节）。需按照K[i] < K[j]时O[i]排在O[j]之前的规则对O排序，性能要求极高。已知ips4o、Google Highway Quicksort等库与std::sort接口兼容，可快速排序K。当前可选方案是定义P[i] = (i, K[i])，按元组第二个元素排序后，通过O2[i] = O[P[i]]; memcpy(O, O2, ...);重新排列对象，但该方案非原地排序且最终步骤缓存性能极差。请问是否存在更快的方法？例如有库可在排序K时同步移动O中的数据？本次限定场景为x86-64架构CPU且支持AVX512扩展。

1. 使用支持多数组同步排序的高性能库 #

ips4o、Google Highway Quicksort这类专为x86-64和AVX优化的排序库，支持通过自定义迭代器或元素结构体实现键与对象的同步排序，无需额外索引数组或二次复制：

结构体打包排序 #

将键和对象打包成单个结构体，直接排序结构体数组，排序过程中同步移动键与对象：

#include <ips4o/ips4o.hpp>

struct SortElement {
    double key;
    T obj;
};

// 构造结构体数组（若内存允许，可直接在原K、O内存上构造，减少拷贝）
SortElement* elements = new SortElement[n];
for (size_t i = 0; i < n; ++i) {
    elements[i].key = K[i];
    elements[i].obj = O[i];
}

// 用ips4o排序（自动利用AVX512优化）
ips4o::sort(elements, elements + n, [](const SortElement& a, const SortElement& b) {
    return a.key < b.key;
});

// 将排序后的对象写回原O数组
for (size_t i = 0; i < n; ++i) {
    O[i] = elements[i].obj;
}
delete[] elements;

绑定迭代器实现原地同步排序 #

若不想额外分配结构体数组，可实现一个绑定K和O的自定义随机访问迭代器，让排序库在排序键的同时自动交换对应的对象：

#include <ips4o/ips4o.hpp>

struct PairIterator {
    using value_type = std::pair<double, T>;
    using reference = std::pair<double&, T&>;
    using pointer = void;
    using difference_type = ptrdiff_t;
    using iterator_category = std::random_access_iterator_tag;

    double* k_ptr;
    T* o_ptr;

    PairIterator(double* k, T* o) : k_ptr(k), o_ptr(o) {}

    reference operator*() const { return {*k_ptr, *o_ptr}; }
    PairIterator& operator++() { ++k_ptr; ++o_ptr; return *this; }
    PairIterator operator++(int) { auto tmp = *this; ++*this; return tmp; }
    PairIterator& operator--() { --k_ptr; --o_ptr; return *this; }
    PairIterator operator--(int) { auto tmp = *this; --*this; return tmp; }
    PairIterator operator+(difference_type n) const { return {k_ptr + n, o_ptr + n}; }
    PairIterator& operator+=(difference_type n) { k_ptr += n; o_ptr += n; return *this; }
    PairIterator operator-(difference_type n) const { return {k_ptr - n, o_ptr - n}; }
    difference_type operator-(const PairIterator& other) const { return k_ptr - other.k_ptr; }
    bool operator==(const PairIterator& other) const { return k_ptr == other.k_ptr; }
    bool operator!=(const PairIterator& other) const { return !(*this == other); }
    bool operator<(const PairIterator& other) const { return k_ptr < other.k_ptr; }
};

// 直接原地同步排序K和O
ips4o::sort(PairIterator(K, O), PairIterator(K + n, O + n),
            [](const auto& a, const auto& b) { return a.first < b.first; });

这种方式完全原地操作，排序过程中交换的是对应位置的K元素和O元素，缓存局部性远优于二次复制方案，且ips4o会自动利用AVX512指令批量处理数据，最大化性能。

2. 优化原索引方案的原地排列 #

若必须使用索引排序，可替换二次复制为原地循环排列算法，避免额外内存开销，同时用AVX512向量指令优化元素移动：

#include <immintrin.h>

void in_place_permute_avx512(T* O, const size_t* P, size_t n) {
    std::vector<bool> visited(n, false);
    constexpr size_t vec_size = 2; // AVX512一次处理2个16字节的T

    for (size_t i = 0; i < n; ) {
        if (!visited[i]) {
            size_t j = i;
            T temp = O[j];
            visited[j] = true;
            // 处理单个循环链
            while (!visited[P[j]]) {
                size_t next_j = P[j];
                std::swap(O[j], temp);
                j = next_j;
                visited[j] = true;
            }
            O[j] = temp;
            ++i;
        } else {
            // 批量跳过已访问的位置（利用向量指令加速）
            size_t batch = std::min(vec_size, n - i);
            __m512i mask = _mm512_loadu_si512(reinterpret_cast<const __m512i*>(&visited[i]));
            mask = _mm512_cmpeq_epi8_mask(mask, _mm512_set1_epi8(0));
            if (mask == 0) {
                i += batch;
                continue;
            }
            // 找到第一个未访问的位置
            size_t first_unvisited = i + __builtin_ctzll(mask);
            i = first_unvisited;
        }
    }
}

该算法通过循环链将元素直接放到目标位置，无需额外的O2数组，同时利用AVX512指令批量检测已访问标记，减少分支开销。

3. 手动利用AVX512优化排序核心逻辑 #

对于极致性能需求，可基于AVX512指令手动实现排序的partition阶段：批量加载多个键进行比较，然后批量移动对应的键和对象。例如，在quicksort的partition步骤中，用_mm512_loadu_pd加载8个double键，用_mm512_cmp_pd_mask生成比较掩码，再根据掩码批量移动对应的K和O元素（_mm512_mask_moveu_epi8处理16字节的T）。不过这种方式开发成本高，建议优先使用成熟的高性能库。

内容的提问来源于stack exchange，提问作者asdfldsfdfjjf