64

我知道这是一个微优化,所以我纯粹出于好奇而问。

从逻辑上讲,微处理器不需要比较相等运算符的两个操作数的所有位来确定“假”结果。

请注意,这是与编程相关的,因为它会影响程序的执行速度。

4

10 回答 10

53

通常,微处理器使用电子门进行比较,而不是像那样逐步进行比较。它一次检查所有位。

于 2009-06-23T00:02:49.073 回答
33

这取决于您的平台,但一般情况下,它的性能相同。

例如,在 X86 上,您可以通过查看汇编的工作方式来了解这一点。查看X86 程序集控制流操作- 无论您是在做相等还是不相等,它都是作为 2 个操作完成的。

首先,您执行 CMP(比较)操作。然后,您检查比较是否相等、不相等等。这只是检查比较的结果——在这两种情况下,您都在进行 2 次操作。

然而,在许多高级编程语言中,情况有所不同。许多语言根据相等性来定义不等式——要检查不等式,您先进行相等性检查,然后再检查它是否为假。这导致这些语言中的平等(微观上)更快。许多语言也允许您专门编写两者 - 但许多人倾向于用相等来编写不等式,这再次使等式通常稍微快一些。

于 2009-06-23T00:08:13.757 回答
12

听起来您应该阅读Intel 64 and IA-32 Architectures Optimization Reference Manual

在您使用的说明中查找“管道延迟”和“管道延迟”。可以说,你对 int 所做的一切都需要大约 1 个时钟周期来执行(每秒 40 亿个)。从内存中读取数据可能需要 100-1000 次,具体取决于您使用的数据量。重要得多。

于 2009-06-23T00:08:17.703 回答
11

比较通常被实现为忽略结果的减法。CPU 中的加法器将同时对所有位进行操作,因此这是一个恒定时间操作。

然后相等性只是确定输出是否为 0。在 x86 上,作为比较结果设置了一些标志,并且通过 jz 或 jnz 完成分支(如果为零则跳转,如果不为零则跳转)。所以不,不会有真正的速度差异。

其他平台(例如 ARM 和 IA64)的行为类似。

于 2009-06-23T00:04:19.273 回答
4

正如其他答案所暗示的那样,指令本身将以相同的速度执行。

您可能会遇到差异的地方是分支预测或缓存效果。这会因处理器和编译器而异,因此无法一概而论。如果您处于这会有所作为的水平,那么唯一知道的方法就是尝试并测量。

于 2009-06-23T00:34:11.053 回答
4

如果您想将此问题提出更一般的问题,则必须考虑 TRUE 和 FALSE 答案的合理分布,并且必须考虑任意字长,包括比寄存器更长的字长。

在搜索算法中(排序可以被认为是搜索的扩展),使用“<”或“<=”等运算符比“==”更常见。这是因为“==”运算符的结果分布倾向于高度偏向“假”,因此它们每次执行的熵低(即信息产量低)。这意味着它们必须执行更多次才能获得相同的信息 - 见证线性搜索。

在任何一种情况下,它们都需要 O(字长)个位比较,但是,如果字长 <= 寄存器长度,则比较会并行进行,进位传播可能会有一点延迟。(实际上,在我看来,在典型的不相等情况下,任何一个比较都可以在第一个不相等位上停止,如果相等的概率足够小,那可能很早就发生了。)

于 2009-06-24T20:18:57.233 回答
2

比较操作发生在微处理器时钟信号的上升沿(或下降沿)。然后下一个操作发生在下一个时钟周期。因此,就执行速度而言,对于当今市场上的几乎每个处理器而言,相等和不等式所花费的时间都是相同的。

我说几乎是因为我记得读过一些处理器,这些处理器应该不是基于时钟,而是基于操作时间,所以如果比较操作确实比添加操作快,那么一组n比较将花费更少的时间n补充。但我有 99% 的把握这只是一些研究项目,而不是商业产品 :)

于 2009-06-23T00:03:29.103 回答
2

有一些小情况可能会产生一些影响。

在 ARM 处理器上(对于 32 位/非拇指指令集架构 (ISA)),所有指令都是有条件的。有时,尽管有多个条件,但您可以摆脱具有单个分支(从头到尾)的内部循环。在少数情况下,具有逻辑比较 ( TEQ) 会干扰少数标志(影响负数 (N) 和零 (Z),但不影响进位 (C) 或溢出 (V)),允许毛茸茸的代码避免分支指令(未采用) .

相反,IIRC(我从未真正对其进行过编程,但在十多年前看过 C 编译器的输出)68000 具有仅用于寄存器 D4 的文字 EOR/XOR 指令。所以算术比较可能会更好(尽管您仍然可以忽略无关的标志 - 关键是指令集有点不规则)。

正如之前的海报所提到的,大部分操作都与内存、磁盘、网络和 Web 服务延迟有关。

于 2009-06-23T01:15:37.117 回答
2

每个人都假设的一个方面是他在谈论寄存器级指令。每个人都是对的,它基本上在 CPU 级别上没有实际意义。甚至更高级别的大多数高级操作都将不等式写成对等式的调用被否定。

然而,在更高的层次上,使用提问者的优化可以双向工作。也就是说,平等可以像不平等一样有效地写作。

此外,对于与装配操作有关的人来说,CMP 和 SUB 之间的唯一区别是设置了哪些标志。它们通常使用机器的相同部分执行,因为 CMP 必须返回表示相等、小于和大于的标志。

于 2009-06-25T11:24:25.047 回答
1

进行这样的比较所花费的时间通常是一个时钟周期。

32 位处理器将同时处理所有 32 位;64 位将一次执行 64 位。

如果管道中存在延迟或停顿,那将是因为操作数不可用并且必须被获取。 这就是开销最大的地方。但这将在适合处理器架构的块中完成,因此它仍然会作为 32 位或 64 位单元被拉入。

于 2009-06-23T00:08:08.890 回答