找到最少3个数字的最快方法？

Question

在我写的一个程序中,在这个例程中,20%的时间用于在内循环中找出最少3个数字:

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建议的变化,但是使用min()的汇编版本没有明显的性能提升.但是,通过使用-march = i686编译程序,我获得了12.5%的提升,我想这是因为整个程序正在获得gcc使用此选项生成的新的更快指令的好处.谢谢你的帮助.

PS - 我使用ruby探测器来测量性能(我的C程序是一个由ruby程序加载的共享库),所以我只能花时间花在ruby程序调用的顶级C函数上,最终调用min ()在堆栈中.请看这个问题.

Answer 1

假设你的编译器没有去吃午餐,这应该编译为两个比较和两个条件移动.不可能做得更好.

如果您发布编译器实际生成的程序集,我们可以看到是否有任何不必要的东西会降低它的速度.

要检查的首要问题是例程实际上是内联的.编译器没有义务这样做,如果它正在生成一个函数调用,那么对于这样一个简单的操作来说,这将是非常昂贵的.

如果调用真的被内联,那么循环展开可能是有益的,正如DigitalRoss所说,或者矢量化可能是有可能的.

编辑:如果你想对代码进行矢量化,并且正在使用最新的x86处理器,你将需要使用SSE4.1 pminud指令(内在:) _mm_min_epu32,它带有两个四个无符号整数的向量,并产生四个无符号的向量整数.结果的每个元素是两个输入中相应元素的最小值.

我还注意到你的编译器使用了分支而不是条件移动; 你可能应该首先尝试一个使用条件移动的版本,看看在你进行矢量实现的比赛之前是否能获得任何加速.

Answer 2

首先确保使用适当的-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可以帮助你避免分支延迟 - 你只需通过传入就可以得到它而没有任何内联asm -march.当内联到更大的功能时,这可能更有效,可能只有四个装配操作.如果你需要比这更快的东西,看看你是否可以让SSE向量操作在整个算法的上下文中工作.

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代码快,也可能不快.

这取决于很多因素.如果分支不可预测,通常cmov会胜出(在某些x86架构上)OTOH内联汇编器始终是优化器的问题,因此对周围代码的优化惩罚可能会超过所有增益.

Btw Sudhanshu,听听这段代码如何与你的testdata一起表演会很有趣.

Answer 4

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

Answer 5

我的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.