在 C 中创建泛型小于函数

Question

我希望实现类似的东西

int memcmp ( const void * ptr1, const void * ptr2, size_t num );

但要区分两种情况 (1) < and (2) =,> 而不是 (3)>。我的目标是减少使用的指令数量，假设在标准笔记本电脑（x86 架构）上运行。

Answer 1

问题的解决方案很可能就是

#define less(a,b,n) (memcmp(a,b,n) < 0)

。

使用

memcmp

有很多优点，因为编译器可能会高度优化它的使用。它可能会查看您用作输入的内容并相应地内联

memcmp

，从而给出最有效的代码。

例如，

memcmp

需要在内部将每个字节转换为

unsigned char

并处理未对齐的数据。但是，如果您在 x86_64 上提供两块 8 字节对齐的数据，则机器代码可能没有理由逐字节地咀嚼它。

这是一个例子，我将一个“less”函数的半天真版本拼凑在一起，其工作原理类似于

memcmp

：

#include <string.h>
#include <stdio.h>

bool lesscmp (const void* obj1, const void* obj2, size_t size)
{
  const unsigned char* o1 = (const unsigned char*)obj1;
  const unsigned char* o2 = (const unsigned char*)obj2;

  for(size_t i=0; i<size; i++)
  {
    if(o1[i] != o2[i])
    {
      return o1[i] < o2[i];
    }
  }
  return 0;
}

int main (void)
{
  char s1[] = "This is some data";
  char s2[] = "This is some other data";

  printf("%d\n", memcmp(s1,s2,sizeof s1) < 0);
  printf("%d\n", memcmp(s2,s1,sizeof s1) < 0);
  printf("%d\n", memcmp(s1,s1,sizeof s1) < 0);
  printf("%d\n", lesscmp(s1,s2,sizeof s1));
  printf("%d\n", lesscmp(s2,s1,sizeof s1));
  printf("%d\n", lesscmp(s1,s1,sizeof s1));
}

在实现它时，我很快就意识到了一个问题：虽然我们正在寻找

<

结果，但我们必须在字节相等的情况下继续循环。当它们不存在时，我们就可以开始寻找

<

，但需要进行额外的比较。

因为 C 没有像“use <= but store the less or equal statuses separately, so we can loop based on the equal flag but return the less flag". On the assembler level we can likely do that however, making this function a good candidate for inline assembler in case we care deeply about performance. And yet unless we happen to be some x86 assembler guru, we can probably not hope to beat the compiler even with hand-crafted assembler.

查看Compiler Explorer中生成的代码（gcc -O3 x86），我们可以得出结论，我自制的函数一团糟：

lesscmp:
        test    rdx, rdx
        je      .L5
        xor     eax, eax
        jmp     .L4
.L3:
        add     rax, 1
        cmp     rdx, rax
        je      .L5
.L4:
        movzx   ecx, BYTE PTR [rsi+rax]
        cmp     BYTE PTR [rdi+rax], cl
        je      .L3
        setb    al
        ret
.L5:
        xor     eax, eax
        ret

cmp

到处都是——它的树枝比圣诞树还多！这根本不会表现得很好。

而等效的

memcmp

调用有时是内联的，导致各种奇特的 x86 内在函数、硬编码的“幻数”等以及很少的分支（如果有的话）。效率更高。

因此，结论是“过早的优化”仍然是万恶之源，而无论目标如何，

memcmp(...) < 0

都可能是实现此目的的最佳解决方案。