使用 SSE2 实现冒泡排序

codekaizen

4.88/5 (21投票s)

2008 年 2 月 11 日

Ms-PL

11分钟阅读

81485

365

使用 SSE2 实现“通用糟糕算法”能提高多少速度？

下载源代码 - 6.24 KB

引言

当我们坐下来解决一个计算问题时，最直接的解决方案通常是最差的。例如，让我们看一下冒泡排序。对于刚开始思考排序问题并且有电脑来完成工作的人来说，这可能是第一个出现的算法：从前两个元素开始，比较它们，如果列表中的顺序颠倒就交换它们，然后移动到下一个元素。无论列表的初始条件如何，该算法的表现都同样“好”。给定列表中的 n 个元素，总共需要 n²-n 次比较。通常，我们会很快放弃这种算法，注意到这种 O(n²) 的性能会非常非常快地失控，这使得冒泡排序在面对实现起来并没有难太多但性能好得多的算法时几乎无用。

但是，我们可以用它来做一件事——测试我们能多快地运行一个糟糕的算法。由于性能会几何级数下降（具体来说是二次方下降），我们会更清楚地看到不同实现之间的性能差异，因为将项目数量加倍将使算法所需的时间增加远不止一倍。此外，冒泡排序非常容易实现，当你第一次手工编写 SSE2 汇编指令时，这将大有帮助。

背景

我正在为 NetTopologySuite 编写一系列计算几何算法，其中一些算法的性能为 O(n²)。由于这些算法大多是数值性的并且执行排序，而替代算法似乎难以实现，我想找到一种方法来利用现代硬件来加速操作。由于如今大多数人的计算机（包括 Intel 和 AMD）都配备了 SSE2，因此选择 SSE2 进行工作似乎是个不错的选择。

在我研究各种存储数字的数据结构时，我还沮丧地发现，Java 在对数字数组进行排序方面做得更好，因为（在运行时浏览进程代码页后）Sun 的 HotSpot Java VM 利用了 SSE2 指令，而 MS 的 CLR JIT 编译器却没有。这真令人震惊。我想再次纠正这一点，于是拿出了 C++/CLI 武器来重新获得对该平台的某些掌控。 voilà：一个托管程序集，它能击败所有竞争者。可惜它无法验证。我认为 MS 在这方面的 JIT 编译器还有很多工作要做，才能让 JIT 生成更多专用代码，尤其是在向量数组方面。

准备使用 SSE2

编写 SSE2 指令时首先要知道的是，我们将使用宽度为 16 字节（128 位）的寄存器和内存位置。寄存器的名称是 XMM0 到 XMM7（64 位系统还有 XMM8 到 XMM15）。它们通常被分成两个 64 位区域，称为“四字”（用于双精度浮点值）。它们也可以被分成四个 32 位区域，称为“双字”（用于单精度浮点值）。整数、字和字节也存在类似的划分。整个长度称为“双四字”。寄存器看起来像这样

XMM register

如果你习惯了 x86 平台上的通用寄存器（EAX、EBX 等），这些寄存器的大小是它们的四倍。

为了将数据移入和移出这些寄存器，你需要¹使用对 16 字节（128 位）边界对齐的内存块。MS CRT 有一个函数可以为我们完成这个任务：_aligned_malloc。它返回一个 void*，我们可以将其强制转换为 double* 来获取我们的数字列表。

代码进展

接下来我发现的是，关于编写 SSE2 汇编的指导很少。当然，有一些关于基本操作用法或数据移动的简单示例，以及关于网上（以及 CodeProject 上）相当高级的数值方法的示例，但我找不到任何展示如何基于指令构建基本通用算法的示例。

Intel 处理器手册是必不可少的，尽管它们更多是作为参考，任何使用都需要经过大量的试错才能推断出来。此外，在进行常规的 32 位 x86 汇编编程之后，使用 SSE2 感觉就像处理器中的一个独立的世界。有几种方法可以从 XMM 寄存器与通用寄存器（如 EAX、EBX 等）进行通信。最终，我找到了 MOVMSKPD 命令，并意识到比较（如我使用的 CMPLTPD）会设置四字中的所有位，而 MOVMSKPD 的掩码会将其中一位提取到一个给定的寄存器中。我之前在使用符号位作为某种重要信息时遇到了困难——当然，在 IEEE 754 双精度浮点数中它是符号位，但它也仅仅是一位，并且我可以用它来进行控制流。在为此而挣扎之后，我发现这正是 Intel Basic Architecture 手册（第 11.6.12 节）中所描述的。

我还不得不尝试了三四种方法，才弄清楚如何从寄存器到寄存器移动数据。我主要在 SHUFPD 上挣扎，它会混洗寄存器和高低四字中的值，UNPCKHPD，它可以将两个寄存器的高四字复制到目标寄存器，以及 UNPCKLPD，它作用于低四字。然后，我偶然发现了使用 MINPD 和 MAXPD，它们执行比较并移动值。结合 SHUFPD 操作将两个寄存器中的四字颠倒，我就可以在仅几条指令中比较和移动数据，并且完全在寄存器中完成。我怀疑这种方法不适用于较小的值，例如单精度浮点值或整数，因为值的排列组合数量超过了可用寄存器的数量。

代码

提供的代码包含一个方法，该方法以“ASM”代码块的形式实现了冒泡排序算法，并在其周围有一个托管的 C++/CLI 框架来运行它并将一些有趣的数据输出到控制台。这种方法还强调了使用 C++/CLI 手工编码汇编块并从 C#、VB.NET 或 IronPython 等任何托管语言轻松使用它们的可能性。

设置好对齐缓冲区（见上文）后，我们可以获取列表的地址并设置我们的循环

// values is a double* to an _aligned_malloc() block
// byteCount is the size of the aligned buffer at *values
 
    _asm
    {
        // save state
        pusha;
begin:
        mov  esi, values;        // get pointer to data
 
        // init loop counters to itemCount
        //    ECX: outer loop counter
        //    EDX: inner loop counter
        mov  ecx, 0;
 
outer_loop:
        // check if counter is 0; end sorting if true
        cmp  ecx, byteCount;
        je   end_outer;
 
        // reset inner loop counter
        mov  edx, byteCount;
        sub  edx, ecx;
 
        // setup data indexer
        mov  ebx, 0
 
inner_loop:
        cmp  edx, 16;
        je   end_inner;

接下来是主体部分，这里使用了 SSE2 寄存器和指令。每个 SSE2 指令通常有两种变体：用于处理多个数据值的打包变体，以及用于处理单个值的标量变体。我们想要打包变体，以便我们可以一次比较两个数字。打包变体以“pd”结尾，表示“packed double”（打包双精度）。

首先，我们将数据从缓冲区移入

// load xmm registers with data to sort
movapd xmm0, [esi+ebx];
movapd xmm1, xmm0;
movapd xmm2, [esi+ebx+16];
movapd xmm3, xmm2;

现在，我们有了列表中前四个条目的两个副本：第一个在 XMM0 和 XMM1 寄存器中，第二个在 XMM2 和 XMM3 寄存器中。XMM0 和 XMM1 寄存器看起来像这样

由于我们不确定这两个值在寄存器内的顺序，我们需要对它们进行比较。为此，我们将每对中的双精度浮点值在其中一个寄存器中交换（这就是为什么我们将每对加载到两个寄存器中的原因）

// reverse values to compare
shufpd xmm1, xmm1, 1;
shufpd xmm3, xmm3, 1;

指令 SHUFPD 代表“Shuffle Packed Double”（混洗打包双精度）。它接受一个“立即数操作数”，该操作数根据值提供不同的行为。在这种情况下，立即数操作数为 1，SHUFPD 将目标寄存器的低四字复制到目标寄存器的高四字，并将源寄存器的低四字复制到目标寄存器的高四字，像这样

当与同一寄存器调用时，SHUFPD 会交换寄存器内的双精度浮点值。

现在，寄存器 XMM0、XMM1、XMM2 和 XMM3 处于一种状态，使得从 XMM0 或 XMM1 中的某个选择以及从 XMM2 或 XMM3 中的某个选择可以得到四个排序后的元素。诀窍在于找到 SSE2 指令来决定保留哪一对寄存器。在仔细研究 Intel 处理器手册几个月（大约一个多月）后，我找到了一些可行的指令：MINPD 和 MAXPD。它们会保留一对 XMM 寄存器中的最小值或最大值。然而，这样做会覆盖源寄存器。我能想到的唯一方法就是将最小/最大比较安排好，以便将最小值放入 [0-1] 寄存器，将最大值放入 [2-3] 寄存器，就是将 XMM0 寄存器保存为一个临时副本。我将其放入 XMM4。我对此并不满意，因为我曾暗自希望将算法的两个集合交错处理，并使用 XMM4-XMM7 寄存器来实现这一点。通过将 XMM0 寄存器保存到 XMM4，这就无法实现了。当然，我可以使用内存位置来存储它，但我正试图避免这样做（寄存器到寄存器是处理器能达到的最快速度）。另一方面，在同一遍中做两倍的工作可能值得，但我还没有测试过。所以，这是保存它的代码

// save value for use in max compare
movapd xmm4, xmm0;

现在进行一系列比较，将最小的值推入 XMM0 和 XMM1，将最大的值推入 XMM2 和 XMM3

// push the minimum values down into xmm[0-1]
minpd xmm0, xmm2;
minpd xmm1, xmm2;

// push the maximum values up into xmm[2-3]
maxpd xmm2, xmm4;
maxpd xmm3, xmm4;

代码不是很直观，让我们仔细看看。指令 MINPD 按顺序比较两个 XMM 寄存器中的每个双精度浮点值——也就是说，源寄存器的低 64 位与目标寄存器的低 64 位进行比较，源寄存器的高 64 位与目标寄存器的高 64 位进行比较。它将每个比较的最小值放在源寄存器中。由于 XMM0 和 XMM1 是相互的反射，因此使用 MINPD 将 XMM2 分别与这两个寄存器进行比较，将导致 XMM2 寄存器中的高低四字中的较小值存储在 XMM0 和 XMM1 中。同样的事情也发生在 MAXPD 上，只是它更明显地选择了较大的值。由于 XMM0 和 XMM1 可能被 MINPD 与 XMM2 的比较完全覆盖，我们使用了我们在开始时保存的 XMM4 寄存器。

最后，我们需要进行寄存器内部的比较，以确保寄存器内的两个双精度浮点值已排序

// order the doubles in xmm[0-1]
order_min0:
        movapd xmm4, xmm0;
        shufpd xmm4, xmm4, 1;
        cmpltpd xmm4, xmm0;
        movmskpd eax, xmm4;
        cmp eax, 2;
        je order_min1;
        shufpd xmm0, xmm0, 1;
order_min1:
        movapd xmm4, xmm1;
        shufpd xmm4, xmm4, 1;
        cmpltpd xmm4, xmm1;
        movmskpd eax, xmm4;
        cmp eax, 2;
        je finish_min;
        shufpd xmm1, xmm1, 1;
finish_min:
        minpd xmm0, xmm1;
 
        // order the doubles in xmm[2-3]
order_max0:
        movapd xmm4, xmm2;
        shufpd xmm4, xmm4, 1;
        cmpltpd xmm4, xmm2;
        movmskpd eax, xmm4;
        cmp eax, 2;
        je order_max1;
        shufpd xmm2, xmm2, 1;
order_max1:
        movapd xmm4, xmm3;
        shufpd xmm4, xmm4, 1;
        cmpltpd xmm4, xmm3;
        movmskpd eax, xmm4;
        cmp eax, 2;
        je finish_max;
        shufpd xmm3, xmm3, 1;
finish_max:
        maxpd xmm2, xmm3;

这里的技巧是使用 CMPLTPD（Compare Less Than Packed Double，比较打包双精度小于）根据比较结果是真还是假，将 XMM 寄存器的高低 64 位设置为全 1 或全 0。每个四字中的一个位（双精度浮点值中的符号位）通过允许通用寄存器和 XMM 寄存器同时使用的少数操作之一提取出来：MOVMSKPD 到 EAX，结果值将是两位：0、1、2 或 3。高位对应于 XMM 寄存器操作数的高四字，低位对应于低四字，像这样

在 EAX 中的值 2（二进制：10）表示高四字小于低四字，这正是我们想要的。如果值不是 2，我们通过调用 SHUFPD（立即数操作数为 1）来交换它们。当值被交换后，我们可以将它们与原始寄存器进行比较，以确定哪个更小，从而确定要保留的顺序。

此时，寄存器 XMM0 和 XMM2 已正确排序，我们将它们保存回数据缓冲区，然后继续进行冒泡排序中的下一对。

结果

排序的速度似乎几乎是标量指针实现的两倍，但略逊一筹。这大致符合我们的预期，因为 SSE2 版本在执行相同数量的指令时进行了两倍的比较——毕竟，这就是向量处理器的全部优势。当处理少量数据（例如少于 64 个）时，情况并非如此。在这种情况下，SSE2 的开销似乎使指针实现更快。也许，可以通过让处理器在处理数据之前将内存页面预取到缓存中来消除这种开销。下图显示了一个典型运行

如果我们将其与使用指针的标量实现进行比较，会发现以下计时

进一步研究

我已将此代码作为 CodePlex 上一个项目的一部分：Code Rule。这个想法是通过多种语言/框架实现算法，以帮助可视化算法和运行它们的机器的相对性能。

使用此示例的一些更有趣的尝试包括使用预取技术来控制即将进入数据缓存的数据，如果缓冲区太大而无法放入处理器的数据缓存中。利用 64 位系统上的额外寄存器或多核机器上的其他核心也会很有用。当然，如果实现一个更好的算法，比如快速排序，这最终才会有实际意义。

参考

我主要使用了 Intel 处理器手册，卷 1、卷 2A 和卷 2B 来构建这个示例。这些以及更多内容也可以在这里找到。

脚注

好吧，你不需要这样做，但是，你可能真的、真的想这样做，因为否则这将是一个巨大的性能损失。

历史

2008-02-12 - 风格编辑。
2008-02-11 - 初始提交。