在C语言中，比较两个整数的最快方法是什么？

Question

在C语言中，比较两个整数的最快方法是什么？

9

uint64_t n;      // two 32-bit integers

return ( (uint32_t)(n >> 32) == (uint32_t)n );

如何以原子方式比较uint64_t的32个最高有效位和32个最低有效位中的值？

我认为一种可怕的解决方案是：获取自旋锁，读取32位最低有效位，读取32位最高有效位，进行比较并获得结果，释放自旋锁，返回结果。是否有一种不需要获取自旋锁就可以完成的方法？

- brooksbp

6

这不完全取决于底层架构而不是 C 语言本身吗？ - dreamlax

5个回答

7

除非您还可以确保写入它们始终是原子的，否则整个操作（内存中两个值的原子比较）是没有意义的。它还受到固有竞争条件的影响；在您确定它们相等之时，它们可能已经改变，反之亦然。无论您试图解决什么问题，几乎肯定需要使用锁，而不是原子操作。

- R.. GitHub STOP HELPING ICE

3

如果您的平台可以原子地检索64位数字，则可以在不使用锁的情况下完成。如果可能，首先以您喜欢的方式（例如，在64位Windows上进行InterlockedOr64（ptr，0），如果您有32位x86 CPU，则没有办法 - 除非您拥有不早于Pentium的英特尔CPU并确保您的64位值为64位对齐，不确定其他供应商的x86 CPU），然后执行与检索到的值进行比较。
显然，您无法以可移植的方式完成此操作。在无法原子地获取64位数字的平台上，无法在不使用锁的情况下完成此操作。

编辑

由于某些极具误导性的想法在这个讨论中获得了严重的流行，我觉得我的职责是写一些关于未能使用32位数字的Compare&Exchange来解决问题的注意事项。

假设我们有x86平台，那么我们可以编写asm代码:

    mov eax, [num+4]
    lock cmpxchg [num], eax
    jz  equal_case_code
    ; non-equal case code follows
equal_case_code:
    ; equal case code follows

显然，这个实现不是原子的 - 线程可能会在mov和cmpxchg指令之间中断（因为一条指令中不允许两个内存操作数）。

来自不同API的基于32位的Compare&Exchange函数（例如Win32 API的InterlockedCompareExchange）也无法提供正确的解决方案，因为它们的语义只允许对一个32位内存地址进行原子访问。

- Serge Dundich

1

在32位x86上，您应该能够使用LOCK FILD以原子方式加载64位。 - augustss

@augustss：不，你不能这样做。“LOCK前缀只能添加到以下指令中，并且只能添加到目标操作数为内存操作数的指令形式中：ADD、ADC、AND、BTC、BTR、BTS、CMPXCHG、CMPXCH8B、DEC、INC、NEG、NOT、OR、SBB、SUB、XOR、XADD和XCHG。”（Intel® 64和IA-32体系结构软件开发人员手册，第2A卷：指令集参考，A-M）。 - Serge Dundich

1

我相信只要64位值对齐（因此不跨越缓存行），fild已经是原子的了（没有锁前缀）。在古老的CPU上，FPU是外部的，可能不是这样，但在任何现代设备上都应该是这样的。 - R.. GitHub STOP HELPING ICE

@R..: "我认为，只要64位值对齐，fild已经是原子操作了（没有锁定前缀），至少对于英特尔CPU来说是这样的 - 我还没有查看其他厂商的文档。但是，我假设解决方案没有对齐限制。我会更新我的答案，使其更加清晰明了。" - Serge Dundich

@zvrba：您能解释一下我的回答中最初的错误在哪里吗？我的信息来自英特尔文档（而不是您的评论），我对回答进行了非常小的更改（用斜体突出显示），以响应@R..的评论。这是您的建设性批评吗？ - Serge Dundich

显示剩余3条评论

0

使用联合体怎么样？就像这样：

typedef union {
    uint32_t small[2];
    uint64_t full;
} bigint_t;

然后你去做：

uint64_t n;      // two 32-bit integers

bigint_t mybigint;
mybigint.full = n;
return mybigint.small[0] == mybigint.small[1];

我不知道这是否是最快的方法，但如果你不将 uint64_t 复制到联合体中，而直接使用该联合体，它应该会相当快，因为对于比较操作来说它并不需要做任何额外的操作。

- Markus Pilman

4

如果您读取的联合体成员不是最后用于写入的联合体成员，则行为未定义。 - dreamlax

@dreamlax - 你确定吗？如果是这样的话，我很乐意看到对此的参考资料，因为我认为这是可行的（也许在特定的编译器中，但不符合严格的C标准吗？）。 - Eli Iser

@dreamlax 至少对于gcc来说，它肯定是有效的，就我所记得的，Unix套接字库使用这种机制来表示IP地址。你能提供一个参考吗？ - Markus Pilman

@Eli @Markus：https://dev59.com/questions/1nI-5IYBdhLWcg3whYsr - dreamlax

1

特别是要看看Andrey的回答。 - dreamlax

@dreamlax - 太好了，感谢链接。我在VS2010中运行了这段代码，并得到了期望的结果，包括小端字节序。 - Eli Iser

0

使用内联汇编将64位整数加载到MMX或SSE寄存器中（64位读取是原子性的），然后比较两半。

- zvrba

（64位读取是原子性的）你为什么这么认为？如果你使用SMP系统，这并不是保证的（除非你使用LOCK指令前缀，但这在FPU/MMX/SSE指令中是不允许的）。 - Serge Dundich

是的，它们是。英特尔手册第3A卷，第8.1.1节：保证原子操作：“P6系列处理器（以及之后的新处理器）保证以下附加内存操作始终以原子方式执行：对符合缓存行大小的缓存内存的非对齐16位、32位和64位访问。” - zvrba

@zvrba：“适当的对齐”。没错。这意味着您依赖于对齐（这是实现相关的，即编译器特定的），或者您必须自己确保适当的对齐。对于P6或更新的处理器来说都是正确的（因此不适用于旧处理器）。而且可能不适用于某些非英特尔x86 CPU。在我看来，条件太多了。 - Serge Dundich

一堆“可能”的东西在实践中很容易验证，如果必要的话。我还没有看到你对这个问题提出任何合理的答案。请找到一个不需要任何特殊设置（如对齐等）并且不依赖于特定 CPU 的解决方案。 - zvrba

1

@zvrba：“确保找到一种不需要任何特殊设置（对齐等）且不针对特定CPU的解决方案。” 很明显，通用解决方案（适用于任何CPU）是使用锁。很明显，没有锁且不针对特定CPU的解决方案不存在（因此我无法提供这样的解决方案 - 没有人可以）。 - Serge Dundich

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eli Iser · Accepted Answer

如何在两个不同的地址上使用比较交换操作呢？例如：CMPXCHG (int*)&n, (((int*)&n)+1)（注意 - 这实际上是行不通的）。编辑：将语法更改为更接近实际x86语法。正如Serge所指出的，对于大多数汇编程序来说，在一个汇编指令中使用两个内存地址是不被支持的，因此这种方式不能直接从内存中工作。这意味着这种方法不能用于以原子方式比较64位变量的两个32位部分。一些汇编语言（至少PowerPC）能够提供特殊的指令（对于PowerPC，LWARX和STWCX），可以以多线程安全的方式使其工作，但这并不完全符合OP的要求，也不能在x86上工作。