使用比较器网络对固定长度数组进行快速排序

Question

我有一些性能关键的代码，涉及在C++中对一个非常短的、固定长度的数组进行排序，该数组在大约3到10个元素之间（参数在编译时更改）。

我想到了一种专门针对每个可能的输入大小的静态排序网络，可能是做这件事的一种非常有效的方式：我们执行所有必要的比较来确定我们所处的情况，然后执行最优数量的交换来对数组进行排序。

为了应用这种方法，我们使用一些模板技巧来推断出数组的长度并应用正确的网络：

#include <iostream>
using namespace std;

template< int K >
void static_sort(const double(&array)[K])
{
    cout << "General static sort\n" << endl;
}

template<>
void static_sort<3>(const double(&array)[3])
{
    cout << "Static sort for K=3" << endl;
}


int main()
{

    double  array[3];

    // performance critical code.
    // ...
    static_sort(array);
    // ...

}

很明显，编写所有这些代码会让人感到很麻烦，所以：

• 有人对此是否值得付出努力有任何看法吗？
• 有人知道类似std :: sort的标准实现中是否存在此优化吗？
• 有没有一个容易获取这种排序网络代码的地方？
• 也许可以使用模板魔术静态生成这样的排序网络..

目前我只使用具有静态模板参数的插入排序（如上所述），希望它能促进展开和其他编译时优化。

欢迎分享您的想法。

---

更新: 我编写了一些测试代码来比较“静态”插入排序和std::sort。 （当我说静态时，我是指数组大小固定且在编译时推断（可能允许循环展开等）。 我至少获得了20％的净改进（请注意，计时包括生成）。 平台：clang，OS X 10.9。

如果您想将其与您的stdlib实现进行比较，请单击此处https://github.com/rosshemsley/static_sorting查看代码。

我仍然没有找到一组漂亮的比较器网络排序器实现。

---

- Ross Hemsley

---

你是否实际尝试过检查排序在程序执行中是否需要相当长的时间？ - Shahbaz

数组大小在编译时已知吗？ - Andriy

@Shahbaz 不是的：这一步的性能对代码的性能至关重要，但是代码的性能对我来说并不重要...（这是为了一个蒙特卡罗模拟，我只会运行一次）。所以我没有进行任何高级测试。总的来说，这似乎是一个有趣的想法，可能会引起其他人的兴趣。 - Ross Hemsley

我记得有一个C语言排序网络生成器在某个网页上（不幸的是现在无法记起或找到它）。大约两年前，我用它来进行基准测试，并发现在5个以上的元素中，与std::sort的差异相当小或几乎不存在。无论如何，为了测试速度，使用代码生成可能是最简单的解决方案（如果您不想出于学术目的而进行模板编程）。这里有一个类似的网站，它只输出一对数组以进行比较/交换，但我认为可以在5分钟内将其包装在C代码中。 - Damon

@RossHemsley，那么你可能会浪费时间。我的建议是只需使用std::sort，然后使用分析器运行程序，看看它在该函数中花费了多少时间。也许std::sort也很聪明呢;) 当然，这个问题仍然很有趣。 - Shahbaz

Answer 1

这是一个小的类，它使用Bose-Nelson算法在编译时生成排序网络。

/**
 * A Functor class to create a sort for fixed sized arrays/containers with a
 * compile time generated Bose-Nelson sorting network.
 * \tparam NumElements  The number of elements in the array or container to sort.
 * \tparam T            The element type.
 * \tparam Compare      A comparator functor class that returns true if lhs < rhs.
 */
template <unsigned NumElements, class Compare = void> class StaticSort
{
    template <class A, class C> struct Swap
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            T t = Compare()(v0, v1) ? v0 : v1; // Min
            v1 = Compare()(v0, v1) ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A> struct Swap <A, void>
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            // Explicitly code out the Min and Max to nudge the compiler
            // to generate branchless code.
            T t = v0 < v1 ? v0 : v1; // Min
            v1 = v0 < v1 ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A, class C, int I, int J, int X, int Y> struct PB
    {
        inline PB(A &a)
        {
            enum { L = X >> 1, M = (X & 1 ? Y : Y + 1) >> 1, IAddL = I + L, XSubL = X - L };
            PB<A, C, I, J, L, M> p0(a);
            PB<A, C, IAddL, J + M, XSubL, Y - M> p1(a);
            PB<A, C, IAddL, J, XSubL, M> p2(a);
        }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 1>
    {
        inline PB(A &a) { Swap<A, C> s(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 2>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J); Swap<A, C> s1(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 2, 1>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J - 1); Swap<A, C> s1(a, I, J - 1); }
    };

    template <class A, class C, int I, int M, bool Stop = false> struct PS
    {
        inline PS(A &a)
        {
            enum { L = M >> 1, IAddL = I + L, MSubL = M - L};
            PS<A, C, I, L, (L <= 1)> ps0(a);
            PS<A, C, IAddL, MSubL, (MSubL <= 1)> ps1(a);
            PB<A, C, I, IAddL, L, MSubL> pb(a);
        }
    };

    template <class A, class C, int I, int M> struct PS <A, C, I, M, true>
    {
        inline PS(A &a) {}
    };

public:
    /**
     * Sorts the array/container arr.
     * \param  arr  The array/container to be sorted.
     */
    template <class Container> inline void operator() (Container &arr) const
    {
        PS<Container, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };

    /**
     * Sorts the array arr.
     * \param  arr  The array to be sorted.
     */
    template <class T> inline void operator() (T *arr) const
    {
        PS<T*, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };
};

#include <iostream>
#include <vector>

int main(int argc, const char * argv[])
{
    enum { NumValues = 32 };

    // Arrays
    {
        int rands[NumValues];
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
    }

    std::cout << "\n";

    // STL Vector
    {
        std::vector<int> rands(NumValues);
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
    }

    return 0;
}

基准测试

以下基准测试是使用clang -O3编译并在我的2012年中期Macbook Air上运行的。

对于排序1百万个数组的时间（以毫秒为单位）如下：
数组大小为2、4、8的毫秒数依次为1.943、8.655和20.246。

这里是6个元素小数组每次排序的平均时钟数。基准测试代码和示例可在此问题找到：
Fixed length 6 int array的最快排序

Direct call to qsort library function   : 342.26
Naive implementation (insertion sort)   : 136.76
Insertion Sort (Daniel Stutzbach)       : 101.37
Insertion Sort Unrolled                 : 110.27
Rank Order                              : 90.88
Rank Order with registers               : 90.29
Sorting Networks (Daniel Stutzbach)     : 93.66
Sorting Networks (Paul R)               : 31.54
Sorting Networks 12 with Fast Swap      : 32.06
Sorting Networks 12 reordered Swap      : 29.74
Reordered Sorting Network w/ fast swap  : 25.28
Templated Sorting Network (this class)  : 25.01 

它在处理6个元素时与问题中最快的示例一样快。

用于基准测试的代码可以在这里找到。

它包含更多功能和进一步优化，以在真实数据上获得更强大的性能。

- Vectorized

---

使用它时，我没有面对32个std::pair<int, int>的快速排序问题。但是很好的干净代码，谢谢。 - amirali

如果它是一个uint32_t对的数组，就把这些对转换成uint64_t, 对数组进行排序，然后再转回去。这将允许静态排序使用min/max指令。 - Vectorized

Answer 2

其他答案很有趣且相当不错，但我认为我可以提供一些额外的回答要素，逐点说明：

• 值得付出努力吗？好吧，如果您需要对整数的小集合进行排序，并且排序网络已经调整到尽可能利用某些指令，那么这可能值得一试。下面的图表展示了使用不同排序算法对大小为0-14的一百万个int数组进行排序的结果。正如您所看到的，如果您确实需要它，排序网络可以提供显着的加速。

• No standard implementation of std::sort I know of use sorting networks; when they are not fine-tuned, they might be slower than a straight insertion sort. libc++'s std::sort has dedicated algorithms to sort 0 thru 5 values at once but they it doesn't use sorting networks either. The only sorting algorithm I know of which uses sorting networks to sort a few values is Wikisort. That said, the research paper Applying Sorting Networks to Synthesize Optimized Sorting Libraries suggests that sorting networks could be used to sort small arrays or to improve recursive sorting algorithms such as quicksort, but only if they are fine-tuned to take advantage of specific hardware instructions.

  The access aligned sort algorithm is some kind of bottom-up mergesort that apparently uses bitonic sorting networks implemented with SIMD instructions for the first pass. Apparently, the algorithm could be faster than the standard library one for some scalar types.

• I can actually provide such information for the simple reason that I developed a C++14 sorting library that happens to provide efficient sorting networks of size 0 thru 32 that implement the optimizations described in the previous section. I used it to generate the graph in the first section. I am still working on the sorting networks part of the library to provide size-optimal, depth-optimal and swaps-optimal networks. Small optimal sorting networks are found with brute force while bigger sorting networks use results from the litterature.

  Note that none of the sorting algorithms in the library directly use sorting networks, but you can adapt them so that a sorting network will be picked whenever the sorting algorithm is given a small std::array or a small fixed-size C array:

  using namespace cppsort;
  
  // Sorters are function objects that can be
  // adapted with sorter adapters from the
  // library
  using sorter = small_array_adapter<
      std_sorter,
      sorting_network_sorter
  >;
  
  // Now you can use it as a function
  sorter sort;
  
  // Instead of a size-agnostic sorting algorithm,
  // sort will use an optimal sorting network for
  // 5 inputs since the bound of the array can be
  // deduced at compile time
  int arr[] = { 2, 4, 7, 9, 3 };
  sort(arr);
  

  As mentioned above, the library provides efficient sorting networks for built-in integers, but you're probably out of luck if you need to sort small arrays of something else (e.g. my latest benchmarks show that they are not better than a straight insertion sort even for long long int).

• You could probably use template metaprogramming to generate sorting networks of any size, but no known algorithm can generate the best sorting networks, so you might as well write the best ones by hand. I don't think the ones generated by simple algorithms can actually provide usable and efficient networks anyway (Batcher's odd-even sort and pairwise sorting networks might be the only usable ones) [Another answer seems to show that generated networks could actually work].

- Morwenn

Answer 3

已知对于N<16，有最优或至少最佳长度比较器网络，因此至少有一个相当不错的起点。但是，由于最优网络不一定设计用于使用SSE或其他向量算术实现的最大级别的并行性，所以只能说是相当好的起点。

另一个要点是，对于某些N的一些最优网络是稍微大一点的N+1最优网络的退化版本。

根据wikipedia：

已知最多10个输入的最优深度分别为0、1、3、3、5、5、6、6、7、7。

这意味着，我将致力于实现N={4, 6, 8和10}的网络，因为深度约束无法通过额外的并行性来模拟（我认为）。我还认为，在SSE寄存器（还使用一些min/max指令）或甚至在RISC架构中的一些相对较大的寄存器集中工作，与“众所周知”的排序方法（例如快速排序）相比，由于没有指针算术和其他开销，将提供明显的性能优势。

此外，我希望使用臭名昭著的循环展开技巧Duff's device来实现并行网络。 编辑 当输入值已知为正IEEE-754浮点数或双精度浮点数时，值得一提的是比较也可以作为整数执行。（float和int必须具有相同的字节序）

- Aki Suihkonen

---

有趣的一点关于 float 和 int。我从未注意到位模式上的小于关系对于两者的解释是相同的。我需要验证这一点。 - Shahbaz

Duff的设备是一种巧妙的方法，可以使用switch在所需的起始点跳转到未展开的循环中。您可以只是简单地展开循环而不使用Duff的设备。也许我在这里漏掉了什么，但听起来您正在将“Duff的设备”用作展开的同义词（这是不正确的）。 - Peter Cordes

我可能是指使用带有“fall through”的switch case，但你是对的——没有必要跳转到起始点并循环。如果可能的话，“fall through”只会重用不同网络的代码。 - Aki Suihkonen

Answer 4

让我分享一些想法。

有人对这是否值得付出努力有任何意见吗？

无法给出正确的答案。您必须对实际代码进行分析以找到答案。 在我的实践中，当涉及到低级别的分析时，瓶颈总是不在我想象的地方。

是否有人知道在 std::sort 等标准实现中是否存在此优化?

例如，Visual C++ 实现的 std::sort 用于小向量的插入排序。我不知道是否存在使用最优排序网络的实现。

也许可以使用模板机制静态生成这样的排序网络

有一些用于生成排序网络的算法，如 Bose-Nelson、Hibbard 和 Batcher 算法。由于 C++ 模板是图灵完备的，因此您可以使用 TMP 实现它们。但是，这些算法不能保证提供理论上的最小比较器数量，因此您可能需要硬编码最优网络。

- Andrey

---

1. 在进行任何测试之前，我征求意见，因为涉及的工作可能相当大。
2. 我知道std::sort通常对小输入使用插入排序。但问题是是否有任何实现考虑了固定长度数组或比较器网络？
3. 我对模板代码没问题，我想要比较器网络！
4. TMP（通常）是图灵完备的，因此如果存在一种生成比较器网络的算法，那么这是可能的。但可能非常糟糕。问题只是出于兴趣而已 ;)

- Ross Hemsley