c++ - 字母比较比数字比较慢吗？

Question

请耐心等待。

几个月前，我记得我的算法老师与我们讨论桶排序的实现(在我的算法书中称为分布排序)及其工作原理。基本上，我们不是按面值取数字，而是通过二进制表示开始比较，如下所示:

// 32 bit integers.
Input:  9 4

4: 00000000 00000000 00000000 00000110
9: 00000000 00000000 00000000 00001001
// Etc.

然后开始从右到左比较。

// First step.
4: 0
9: 1

Output: 9 4

// Second step
4: 1
9: 0

Output: 4 9 // Technically a stable algorithm, but we cannot observe that here.

// Third step

4: 1
9: 0

Output: 4 9

// Fourth step

4: 0
9: 1

Output: 9 4

就是这样；其他 28 次迭代都是零，因此输出不会再改变。现在，像这样比较一大堆字符串就可以了

// strings
Input: "Christian" "Denis"

Christian: C h r i s t i a n
Denis:     D e n i s

// First step.
Christian: n
Denis:     s

Output: Christian, Denis

// Second step
Christian: a
Denis:     i

Output: Denis, Christian

// ... 

等等。

我的问题是，比较带符号的字符(字节数字)是否比比较整数快？

如果我不得不假设，比较 1 字节的 char 比 4 字节的整数更快。它是否正确？我可以对 wchar_t 或 UTF-16/32 格式做出相同的假设吗？

Answer 1

在 C 或 C++ 中，char 只是一个单字节整数(尽管“一个字节”可能是也可能不是 8 位)。这意味着在典型情况下，您需要处理的唯一区别是单字节比较是否比多字节比较快。

至少在大多数情况下，答案是否定的。许多 RISC 处理器根本没有处理单个字节的指令，因此对单个字节的操作是通过将字节符号扩展为字、对字进行操作，然后(如有必要)屏蔽所有单个字节之外的位回零——即，对整个字进行操作通常可以是对单个字节进行操作的速度的三倍左右。

即使在像 x86 这样直接支持单字节操作的系统上，它们通常仍然较慢(在现代处理器上)。有几件事促成了这一点。首先，使用当前模式“自然”大小的寄存器的指令比使用其他大小的指令具有更简单的编码。其次，相当多的 x86 处理器具有所谓的“部分寄存器停顿”——尽管这都是隐式的，但它们在内部做一些类似于 RISC 的事情，对全尺寸寄存器执行操作，然后将其与原始值的其他字节。例如，如果您在 AL 中产生一个结果然后引用 EAX，那么与您在 EAX 中产生结果开始相比，该序列将花费更长的时间执行。

OTOH，如果您查看足够旧的处理器，则可能(而且经常)相反。举一个极端的例子，考虑一下 Intel 8080 或 Zilog Z80。两者都有一些 16 位指令，但通过 ALU 的路径只有 8 位宽——例如，一个 16 位加法实际上是作为两个连续的 8 位加法执行的。如果只用 8 位运算就可以了，速度大约是原来的两倍。尽管 8 位处理器在台式机上是一种(遥远的)内存，但它们仍在某些嵌入式应用程序中使用，因此这也并非完全过时。