优化字符串操作函数

Peter Kankowski

3.54/5 (8投票s)

2004年12月27日

5分钟阅读

123594

406

优化字符串操作函数。

下载演示项目 - 3.81 Kb

摘要

VC++、GCC 等编译器为 x86 架构生成的 strncmp() 实现效率低下。如果这个函数调用位于内层循环中，你的应用程序性能可能会急剧下降。一组预处理器宏可以替换这个低效的函数，从而使你的代码更小、更快。

问题出在哪里？

文本搜索应用程序和解释器通常会将 strncmp() 放在内层循环中。本示例代码解释了“PRINT”和“GOTO”命令（当然，这只是一个简化的例子）。

char buf[] = "PRINT xyz";
if(0 == strncmp(buf, "PRINT", 5)) {
    DoPrint(buf+5);
}
else if(0 == strncmp(buf, "GOTO", 4)) {
    DoGoto(buf+4);
}

让我们看看 VC++ 6.0 是如何实现这个函数的（使用你喜欢的反汇编器查看代码）。

strncmp proc ; int strncmp(const char *s1, const char *s2, size_t len)
    ; function prolog
    push ebp
    mov ebp, esp
    push edi
    push esi
    push ebx
    ; if (0 == len) goto exit
    mov ecx, dword ptr [ebp+10]
    jcxz exit

    ; search for terminating zero in s1
    mov ebx, ecx
    mov edi, dword ptr [ebp+08]
    mov esi, edi
    xor eax, eax
    repnz scasb
    ;ecx = the smaller of two numbers: len and strlen(s1)
    neg ecx
    add ecx, ebx

    ;compare ecx bytes from s1 and s2
    mov edi, esi
    mov esi, dword ptr [ebp+0C]
    repz cmpsb
    ;compare the first different character in both strings
    mov al, byte ptr [esi-01]
    xor ecx, ecx
    cmp al, byte ptr [edi-01]

    ja smaller_s1 ; s1 is less than s2, should return -1
    je exit ; s1 == s2, should return zero
    ; ecx = -2
    dec ecx
    dec ecx
smaller_s1:
    ; if s1 was less than s2, return ~0 = -1
    ; if s1 was greater than s2, return ~(-2) = 1
    not ecx

exit:
    ; epilog: return the value
    mov eax, ecx
    pop ebx
    pop esi
    pop edi
    leave
    ret
end proc


; Using strncmp
; if(0 == strncmp(buf, "PRINT", 5)) {
    push 5
    lea    ecx, DWORD PTR [esp+4] ; buf
    push OFFSET PRINT
    push ecx
    call _strncmp
    add    esp, 12
    test eax, eax
    jne    SHORT skip
; DoPrint(buf+5)
    ;some printing stuff here
skip:

嗯，一行简单的 C 程序就产生了大量的机器码……有没有更简单的方法来比较字符串？当然有。

     cmp DWORD PTR [buf], 'NIRP'
     jnz skip
     cmp BYTE PTR [buf+4], 'T'
     jnz skip
; DoPrint
     ;printing
skip:

这四条指令就能完成与上面长代码相同的比较，而且速度更快、占用空间更小。我们首先比较字符串的前四个字符与“PRIN”。像 Pentium 或 Athlon 这样的 32 位处理器可以非常快速地读取和比较 4 个字节。只需一条 cmp 指令即可完成。

但是为什么是“NIRP”而不是“PRIN”？为什么字符是反转的？记住，x86 是小端序处理器：在从内存读取 DWORD 时，它会反转字节顺序。因此，我们也需要反转我们的字符串。处理器会读取反转后的 DWORD，与反转后的“PRIN”进行比较，然后判断它们是否相等。如果相等，它将继续比较第五个字符与“T”。如果所有条件都满足，将执行 DoPrint。否则，处理器将跳转到 skip 标签。

你不需要使用汇编来实现这个技巧。使用 C/C++ 也可以做到。

if(('P' | ('R' << 8) | ('I' << 16) | ('N' << 24)) == *(long*)buf &&
    'T' == buf[4]) {
    DoPrint(buf+5);
}

将生成完全相同的、漂亮的、快速的机器码。但这种晦涩的代码很难阅读和维护。让我们让工作更轻松，写一些宏。

宏及其用法

#ifdef UNICODE
#define cmp2ch(s,a,b) (*(long*)(s) == \
    ((unsigned short)(a) | (unsigned short)(b) << 16))
#define cmp4ch(s,a,b,c,d) (*(long*)(s) == \
    ((unsigned short)(a) | (unsigned short)(b) << 16) && \
    *(long*)(s+2) == \
    ((unsigned short)(c) | (unsigned short)(d) << 16))
#define set2ch(s,a,b) (*(long*)(s) = \
    ((unsigned short)(a) | (unsigned short)(b) << 16));
#define set4ch(s,a,b,c,d) (*(long*)(s) = \
    ((unsigned short)(a) | (unsigned short)(b) << 16), \
    *(long*)(s+2) = \
    ((unsigned short)(c) | (unsigned short)(d) << 16));
#else
#define cmp2ch(s,a,b) (*(short*)(s) == \
    ((unsigned char)(a) | (unsigned char)(b) << 8))
#define cmp4ch(s,a,b,c,d) (*(long*)(s) == \
     ((unsigned char)(a) | (unsigned char)(b) << 8 |   \
     (unsigned char)(c) << 16 | (unsigned char)(d) << 24))
#define set2ch(s,a,b) (*(short*)(s) = \
    ((unsigned char)(a) | (unsigned char)(b) << 8));
#define set4ch(s,a,b,c,d) (*(long*)(s) = \
     ((unsigned char)(a) | (unsigned char)(b) << 8 |   \
     (unsigned char)(c) << 16 | (unsigned char)(d) << 24));
#endif

cmp2ch 和 cmp4ch 宏分别用于比较字符串的 2 个和 4 个字符。以下示例显示了如何使用它们。

if(cmp4ch(buf, 'P','R','I','N') && buf[4] == 'T')
    DoPrint(buf+5);

另一个例子

if(cmp4ch(buf, 'Y','E','S','\0'))
    DoYes();

如果字符串等于“YES”，则调用 DoYes() 函数。

虽然宏看起来相当复杂，但它们会被编译成非常简单的机器码。请注意，所有移位和 OR 操作都在编译时进行求值，因此生成的代码只包含快速的比较（CMP 和 JNZ 指令）。

最后，让我们谈谈 set2ch 和 set4ch。顾名思义，这些宏可以快速地为 2 个或 4 个字符赋值。

set4ch(buf, 'P','R','I','N'); // Equivalent of strcpy(buf, "PRINT"),
set2ch(buf+4, 'T','\0');      // but much shorter and faster

同样的技巧也可以应用于其他函数，例如替换 strcat()。

TCHAR filename[MAX_PATH];
// Get path from control
int len = SendMessage(hwnd, WM_GETTEXT, 0, (LPARAM)filename);
if(*(p + len) != '\\')
   *(p + len) = '\\', len++;
// Append file name
set4ch(p + len, 'f', 'i', 'l', 'e');
set4ch(p + len + 4, '.', 't', 'x', 't');
*(p + len + 8) = '\0';
// Open the file
HANDLE hFile = CreateFile(filename, GENERIC_READ, FILE_SHARE_READ, ...);

可移植性和本地化

这些宏已在各种平台和编译器上进行了测试，包括 MS VC++ 6.0、LCC 3.8、MinGW 和 Linux 下的 GCC 3.2。测试编译并成功运行，生成了完美且快速的代码。我已将 cmpXch 宏在我的免费应用程序中使用了一年，并且没有任何问题。

当使用 #define UNICODE 编译时，宏会执行宽字符的比较。因此，在维护应用程序的 Unicode 和 ANSI 构建时应该没有困难。宏也可以轻松移植到 Win64。（如果有任何人能在 64 位处理器上测试它们，请在下方留言。）

本地化似乎比移植要困难得多。MS VC++ 可以正确地使用俄语字符以 Unicode 模式编译此行。

set4ch(str, TEXT('&#1064;'), TEXT('&#1080;'), TEXT('&#1083;'), TEXT('&#1086;'));

但是其他编译器生成的代码是错误的！LCC 3.8 无法正确地将字面 ASCII 字符转换为 Unicode（更不用说它无法优化移位操作了）。当定义 UNICODE 时，MinGW 也未能选择正确的俄语字符。

然而，宏对于英语（Unicode 和 ASCII 模式下）以及使用 8 位 ASCII 的任何语言都可以正常工作。如果你正在构建 BASIC 解释器或解析 HTML 标签，这对你来说应该足够了。当你需要对非英文字符进行 Unicode 支持时，你必须使用 MS VC++ 编译器。

不区分大小写的搜索

如何使用此技术执行不区分大小写的搜索？一种可能的解决方案是比较前两个字符的所有可能组合（例如，“PRINT”的 PR、pr、Pr、pR）。如果此比较返回 true，我们则使用 strcmpi、lstrcmpi 或 CharUpper 来检查字符串的其余部分。

if(cmp2ch(buf, 'P', 'R') || cmp2ch(buf, 'P', 'r') ||
   cmp2ch(buf, 'p', 'R') || cmp2ch(buf, 'p', 'r')) {
        char tmp[5];
        *(long*)tmp = *(long*)buf; // Fast copy 4 chars from buf to tmp
        tmp[4] = buf[4];           // or: memcpy(tmp, buf, 5 * sizeof(TCHAR));
        CharUpperBuff(tmp, 5); // Convert 5 chars to uppercase
        if(cmp4ch(tmp, 'P', 'R', 'I', 'N') && tmp[4] == 'T')
            DoPrint(buf+5);    // Compare converted characters
}

另一种变体（晦涩但更快）

if((cmp2ch(buf, 'P', 'R') || cmp2ch(buf, 'P', 'r') ||
    cmp2ch(buf, 'p', 'R') || cmp2ch(buf, 'p', 'r')) &&
   (cmp2ch(buf+2, 'I', 'N') || cmp2ch(buf+2, 'I', 'n') ||
    cmp2ch(buf+2, 'i', 'N') || cmp2ch(buf+2, 'i', 'n'))
    && (buf[4] == 'T' || buf[4] == 't'))
        DoPrint(buf+5);

如果你只需要比较英文字母，可以使用一个非常快速的技巧。请注意，每个大写字母的第五位都为 0，而对应的小写字母的第五位都为 1。

0100 0001 — A	0100 0010 — B	0100 0011 — C	0100 0100 — D
0110 0001 — a	0110 0010 — b	0110 0011 — c	0110 0100 — d

通过将字母与 1101 1111 = 0xDF 进行 AND 运算来清除此位。这样我们就能得到所有大写字母，并将它们与常量进行比较。

if(('P' | ('R' << 8) | ('I' << 16) | ('N' << 24)) == (*(long*)buf & 0xDFDFDFDF)
    && (buf[4] & 0xDF) == 'T') {
        DoPrint(buf+5);
    }

虽然这段代码极其快速且代码量小，但它只适用于英文字母。添加数字或括号会引入错误。例如，“{”将被转换为“[”，而此代码将无法正常工作。

if(('[' | ('A' << 8)) == (*(short*)buf & 0xDFDF)) {
        ReportError(); // Will call ReportError() for "[a", "{a", "[A", "{A"
    }

这可以重写为：

if(('[' | ('A' << 8)) == (*(short*)buf & 0xDFFF)) {
        ReportError(buf+5); // Will call ReportError() for both "[a" and "[A"
    }

这段代码通过与 DF 进行 AND 运算来转换第二个字母，但保持第一个字母不变。

缓冲区长度警告

你应该始终检查字符串比较是否会超出可用缓冲区长度。避免这种代码：

char buf[256], *p = buf;
GetBuf(&buf, 256); // Read 256 characters from anywhere
do {
    if(cmp2ch(p, '\r', '\n'))
        DoSomething(p);
} while(*p++);

记住，你使用 cmp2ch 比较的是当前字符和下一个字符。如果字符串中只有 256 个字符，最后一轮迭代将尝试将第 256 个和第 257 个字符与“\r\n”进行比较。因此，在分配缓冲区时，你应该额外增加一个字符。

char buf[257], *p = buf;
GetBuf(&buf, 256); // Read 256 characters from anywhere
...

或者，如果你知道字符串长度，只需进行 (长度 - 1) 轮迭代。

char *buf = (char*)malloc(len), *p = buf;
GetBuf(&buf, len); // Read len characters from anywhere
len--; // Don't compare the last character
while(len > 0) {
    if(cmp2ch(p, '\r', '\n'))
        DoSomething(p);
    len--, p++;
}
free(buf);

未来

当然，这些宏不能被认为是比较字符串的优雅方法。但 C 标准库和 CString 类似的类甚至更糟。strcmp() 和其他字符串操作函数已被证明非常庞大且效率低下，它们会显著减慢你的内层循环的速度。

问题出在 C 语言本身。它没有内置的字符串类型，所以编译器无法优化字符串操作代码。我希望有编译器开发者能读到这篇文章，并考虑一种具有快速字符串处理功能的语言。如果任何编译器能够自动应用这些技巧，那就太好了。

变更历史

12-24-2004:

第一个版本。