查找3个数字中最小的方法最快？

Question

我写的一个程序中，在一个内部循环中有20%的时间用于查找三个数字的最小值，具体代码如下：

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{
    unsigned int m = a;
    if (m > b) m = b;
    if (m > c) m = c;
    return m;
}

有没有任何方法可以加快这个过程？如果需要，我也可以接受x86/x86_64的汇编代码。

编辑：回答一些评论：
* 使用的编译器是gcc 4.3.3。
* 就汇编而言，我只是一个初学者。我在这里询问汇编，是为了学习如何做到这一点。
* 我有一个四核Intel 64运行的计算机，因此支持MMX/SSE等技术。
* 很难在这里发布循环，但我可以告诉你这是一个经过高度优化的Levenshtein算法实现的循环部分。

这是编译器给出的非内联版本 min 的代码。

.globl min
    .type   min, @function
min:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    12(%ebp), %eax
    movl    16(%ebp), %ecx
    cmpl    %edx, %eax
    jbe .L2
    movl    %edx, %eax
.L2:
    cmpl    %ecx, %eax
    jbe .L3
    movl    %ecx, %eax
.L3:
    popl    %ebp
    ret
    .size   min, .-min
    .ident  "GCC: (Ubuntu 4.3.3-5ubuntu4) 4.3.3"
    .section    .note.GNU-stack,"",@progbits

内联版本在 -O2 优化的代码中（连我的标记 mrk = 0xfefefefe，在调用 min() 前后都被 gcc 优化掉了），所以我无法获得它的实现。

更新：我测试了 Nils 和 ephemient 建议的更改，但使用 min() 的汇编版本并没有明显的性能提升。然而，通过使用 -march=i686 编译程序，我获得了 12.5% 的性能提升，我想这是因为整个程序都可以受益于 gcc 生成的新的更快指令。感谢大家的帮助。

P.S. - 我使用 Ruby 分析器测量性能（我的 C 程序是由 Ruby 程序加载的共享库），因此我只能获取由 Ruby 程序调用的顶层 C 函数的耗时，这些函数最终会调用堆栈中的 min()。请参阅此 问题。

- Sudhanshu

---

看看该例程生成了什么汇编代码，看看是否能找到优化的方法。 - Anon.

你能发布一下你的编译器生成的汇编代码吗？没有看到这个，很难知道是否可能更快。 - Stephen Canon

此外，这个是如何被使用的呢？有些优化，例如向量操作，只能在特定情况下应用。我们可以期望什么级别的CPU支持呢？（SSE3？4.1？） - bdonlan

你能发一下出现问题的循环吗？在循环的上下文中进行优化可能是可行的。 - Larry Watanabe

如果这只占程序的20％，那么该程序有多简单？听起来像是一道作业题。 - No Refunds No Returns

你是怎么得出20%这个数字的？你是使用oprofile来发现它的吗？ - Free Wildebeest

Answer 1

首先确保您使用了适当的-march设置。GCC默认不使用原始i386不支持的任何指令，而允许其使用更新的指令集有时会产生很大的差异！在 -march=core2 -O2下，我得到：

min:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    12(%ebp), %ecx
    movl    16(%ebp), %eax
    cmpl    %edx, %ecx
    leave
    cmovbe  %ecx, %edx
    cmpl    %eax, %edx
    cmovbe  %edx, %eax
    ret

在这里使用cmov可能有助于避免分支延迟 - 只需通过传递-march，就可以获得它而无需任何内联汇编。当内联到较大的函数中时，这可能会更加高效，可能仅需四个汇编操作。如果需要比此更快的东西，请查看是否可以使SSE向量操作在您的整体算法环境中工作。

- bdonlan

---

+march建议加1分。仅使用该建议，我可以获得12.5%的提升。 :) - Sudhanshu

显然，您希望在现实生活中将其内联，而不是将参数传递到独立函数的堆栈上。但如果不是这样，您会想要使用“-fomit-frame-pointer”。（在更近期的GCC版本中，即使对于32位代码，默认情况下也会打开它。） - Peter Cordes

在Skylake上，需要注意cmovbe仍然是2个微操作，因为它需要ZF和CF。只读取CF或只读取SPAZO组中的标志位的CMOVcc只有一个微操作，因此cmovb更好。（在相等的情况下移动与否并不重要）。请参见此问答。 - Peter Cordes

Answer 2

假设你的编译器没有问题，这段代码应该被编译成两个比较和两个条件移动指令。无法做得更好。

如果您发布您的编译器实际生成的汇编代码，我们可以看看是否有任何不必要的东西在减慢它的速度。

首先要检查的是例程是否真的被内联了。编译器并没有义务这样做，如果它正在生成函数调用，那么对于这样一个简单的操作来说，这将是非常昂贵的。

如果调用确实已经被内联，那么展开循环可能是有益的，就像DigitalRoss所说的那样，或者可能进行向量化。

编辑：如果您想向量化代码，并且使用的是最新的x86处理器，则需要使用SSE4.1 pminud 指令（内嵌：_mm_min_epu32），它接受两个四个无符号整数的向量，并生成一个四个无符号整数的向量。结果的每个元素都是两个输入中相应元素的最小值。

我还注意到您的编译器使用分支而不是条件移动；在您开始进行矢量实现之前，您应该先尝试使用条件移动的版本，看看是否可以获得任何加速。

- Stephen Canon

---

我猜想任何收益都将来自于外部环境而非这个函数本身。+1 - Michael Easter

外部上下文进行了大量优化。它对包含2.88百万个字符串的数据库进行计算。在优化之前，它需要4秒钟才能给出结果。经过一周的重度优化，现在只需要150毫秒。最新的性能分析运行显示，“min”占用了20%的时间。 - Sudhanshu

我的唯一建议是查看一下一直在调用min的内容，并查看是否可以减少对min本身的调用。 - Bill Lynch

循环展开是其中一个已经存在的优化，还有其他几个。该例程正在内联，我在反汇编代码中找不到“min”符号。我对矢量化部分感到好奇 - 也许应该去阅读一下相关内容。谢谢。 - Sudhanshu

Answer 3

我对x86汇编器的实现有些看法，采用GCC语法。应该很容易将其翻译成另一种内联汇编器语法：

int inline least (int a, int b, int c)
{
  int result;
  __asm__ ("mov     %1, %0\n\t"
           "cmp     %0, %2\n\t" 
           "cmovle  %2, %0\n\t"
           "cmp     %0, %3\n\t"
           "cmovle  %3, %0\n\t" 
          : "=r"(result) : 
            "r"(a), "r"(b), "r"(c)
          );
  return result;
}

---

新的和改进的版本：

int inline least (int a, int b, int c)
{
  __asm__ (
           "cmp     %0, %1\n\t" 
           "cmovle  %1, %0\n\t"
           "cmp     %0, %2\n\t"
           "cmovle  %2, %0\n\t" 
          : "+r"(a) : 
            "%r"(b), "r"(c)
          );
  return a;
}

---

注意：它可能比C代码快也可能不快。

这取决于许多因素。通常，如果分支不可预测（在某些x86架构上），cmov会胜出。另一方面，内联汇编始终是优化器的问题，因此周围代码的优化惩罚可能超过所有收益。

顺便说一句，Sudhanshu，很有趣听到这段代码如何处理您的测试数据。

- Nils Pipenbrinck

---

这个对于无符号整数比较也适用吗？如果这样听起来有些幼稚，我很抱歉。 - Sudhanshu

哎呀，写完自己的代码才发现这个问题。是的，你可以使用无符号类型；只需将 cmovle 更改为 cmovbe 即可。 - ephemient

如我在下面的回复中所提到的，一旦您传递了一个适当的-march标志，GCC就会自动执行此优化 - 只是它不在原始80386的指令集中，而GCC会出于（极端）谨慎而犯错 :) - bdonlan

Nils、ephemient、bdonlan - 所有这些建议看起来都不错。让我明天回复你结果。感谢你的帮助。 - Sudhanshu

GCC不再进行此优化。该优化仍然存在于GCC中，但已被禁用。而是使用分支版本。原因是编译器很难猜测分支是否可预测，并确保分支预测得到使用，因此不使用cmovcc。 - Nils Pipenbrinck

Answer 4

这个替换方案在我的 AMD Phenom 上运行速度大约快了 1.5%：

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{
    asm("cmp   %1,%0\n"
        "cmova %1,%0\n"
        "cmp   %2,%0\n"
        "cmova %2,%0\n"
        : "+r" (a) : "r" (b), "r" (c));
    return a;
}

结果可能会有所不同；一些x86处理器对CMOV的处理效果并不好。

- ephemient

---

不错，比我的例子好。你可以为 b 添加一个 %-修饰符，以便在寄存器分配方面具有更多的灵活性。 - Nils Pipenbrinck

使用适当的-march设置，GCC会自动完成此操作，并且这也有助于代码的其他部分。 - bdonlan

从技术上讲，"+r" 应该是 "+&r"，因为它是在读取所有纯输入之前编写的。尽管如此，GCC 目前可能选择不共享 a 和 b 的相同寄存器，即使它知道它们是相同的。此外，在后来的 Intel CPU 上，cmovae 更有效率（仅读取 CF，而不是 CF 和 ZF，因此在 Skylake 上只有 1 个微操作 / https://uops.info）。 - Peter Cordes

Answer 5

SSE2指令扩展包含一个整数min指令，可以一次选择8个最小值。请参见http://www.intel.com/software/products/compilers/clin/docs/ug_cpp/comm1046.htm中的_mm_mulhi_epu16。

- Mark Ransom

---

_mm_mulhi_epu16是一个向量化的16位乘法高位指令，不能用于计算32位整数的最小值。你实际需要的内嵌函数是_mm_min_epu32。 - Stephen Canon

@StephenCanon 这不是真的，因为 _mm_min_epu32 比较两个打包的 __m128i 值。OP 需要的是水平最小值，据我所知在 SSE 中不存在。 - Jakub Arnold

@JakubArnold：你需要两次使用 _mm_min_epu32，每个输入都在单独向量的低元素中。如果您使用上部元素，则可以并行进行4个单独的3路最小值，但如果您需要将结果存储在整数寄存器中，则可能不值得使用 movd 用于标量。否则值得考虑；movd 加载/存储是可以的。 - Peter Cordes

或者你需要SSE4.1 _mm_minpos_epu16 来对一个向量进行无符号水平最小值的操作，但这只适用于16位元素。 _mm_mulhi_epu16 似乎完全没有用处，因为它是一个高半16位乘法。(pmulhuw) - Peter Cordes

Answer 6

首先，看一下反汇编代码。这会告诉你很多信息。例如，按照现有的写法，有两个if语句（这意味着有两种可能的分支预测错误），但我猜想一个像样的现代C编译器会有一些聪明的优化方法可以避免分支。我很想知道。

其次，如果你的libc有特殊的内置min/max函数，请使用它们。例如，GNU libc有用于浮点数的fmin/fmax函数，并声称“在某些处理器上，这些函数可以使用特殊的机器指令比等效的C代码更快地执行这些操作”。也许对于无符号整数也有类似的东西。

最后，如果你要对一堆数字进行这样的操作，那么可能有向量指令可以做到这一点，这可以提供显著的加速。但是，即使使用向量单元时，我甚至看到过非向量代码更快的情况。类似“将一个无符号整数加载到向量寄存器中，调用向量最小函数，获取结果”看起来很愚蠢，但实际上可能更快。

- Ken

---

谢谢你的指引，Ken - 我一定会查看向量指令，我想这也是Mark和Stephen所提到的。 - Sudhanshu

Answer 7

你可以尝试像这样做以节省声明和不必要的比较：

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{ 
    if (a < b)
    {
        if (a < c) 
             return a; 
        else 
             return c;
    }

    if (b < c)
        return b;
    else return c;
}

- Paul Sasik

---

我怀疑这不会好到哪里去——最初的赋值将在编译器中被转换为重命名，现在分支预测器中有三个分支占用了空间，而不是两个。 - bdonlan

这是两种比较方式。现在的区别是你正在使用分支而不是条件移动 - 我猜这可能会更慢。即使忽略了你正在使用管道。 - Anon.

我认为这个计算的是三个输入中的最大值，而不是最小值。至少对于a = 5，b = 2，c = 3是这样。 - Michael Easter

在这里要小心。现在有额外的分支，导致代码更大，这两者都有其自身的缺点。（此外，这是max，但你的意思很清楚。） - jason

作业很便宜。真的，除非你必须要占用内存，否则它们比错过一个分支要便宜得多。 - Anon.

Answer 8

如果您只进行一次比较，您可能希望手动展开循环。

首先，请尝试让编译器为您展开循环，如果无法实现，请自行操作。这将至少减少循环控制开销...

- DigitalRoss

Answer 9

这些都是很好的答案。冒着被指责没有回答问题的风险，我也会看其他80%的时间。Stackshots 是我发现值得优化的代码的最爱方式，特别是当你发现你不绝对需要的函数调用时。

- Mike Dunlavey

Answer 10

是的，后期汇编，但我的天真优化是：

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{
    unsigned int m = a;
    if (m > b) m = b;
    if (m > c) return c;
    return m;
}

- Hamish Grubijan

---

任何编译器都可以完成这种转换（哪种形式更高效并不容易说清楚！）。 - bdonlan