【GAD译馆】关于字符串处理的一个声讨
译者：王磊（未来的未来） 审校：白芷（白芷）
这个文章是一个系列教程的一部分 - 去这里看整个教程的索引。
夸夸其谈和声讨通常不是这个博客的风格，但是在这篇文章里面我准备尝试一下。所以如果你好奇的话，这篇文章的实际信息内容将有如下这些：C字符串处理函数有点闹心。C 的std:: string也是如此。使用标准C / C 功能处理宽字符串绝对是一件可怕的事情。而VC 实现的这个功能就是一个死亡雷区。这就是这篇文章的内容。你不会从阅读这篇文章中学到什么东西。如果要继续阅读的话请自己承担风险。
更新： “cmf”在注释中指出，实际上C 函数似乎以我想要的方式做到了一些东西。有一次我在这个博客上咆哮过一次，当然我错了！ :)我还是坚持我在第一次发表这篇文章的时候对许多API漏洞的指责，正如我在回复中指出的那样，这个解决方案的可发现性是惊人的低。当我最初遇到这个问题的时候，因为我并不熟悉std :: wstring，我在网络上进行了搜索，找到了Stack Overflow和其他几个编码站点和邮件列表存档上相关的讨论，而且似乎没有一个页面显示出正确的解决方案。所以至少在这个情况上，我并不孤独。
背景
我把上个周末的大部分时间里都用在我感兴趣的英特尔“软件遮挡剔除”样本上。我试图优化一些热点，这个过程涉及到很多小的（或有时不太小的）修改代码，之后进行分析器运行，以查看它们是否有帮助。现在不幸的是，这个程序，至少在其原始版本中，在我的机器上加载了大约24秒的时间，并且每次在你可以启动分析运行之前都要等待这24秒（如果你需要得到一些有用的结果的话，需要另外10-20秒），所以我决定检查是否有一个简单的方式来缩短加载时间。
由于我已经设置了分析器，所以我决定先去看看加载阶段。我发现的第一个大的时间浪费出现在纹理加载器上，它没有必要去解压缩一个要大的多的DXT天空盒纹理，然后再次压缩它。 我不会详细介绍这一点。一旦我确定了这个问题，它很简单，可以修复，并减少加载时间到大约12秒左右。
我的下一个分析器运行结果表明：
我在配置文件类CPUTConfigFile中直接或间接调用的函数旁边放上一个红点。这让你好奇，不是吗？为了避免你觉得我在夸张，这里有热点榜第二位函数的一些调用堆栈，malloc的部分：
以下是对热点榜第二位函数的调用，free的部分：
而这里的memcpy，进一步下来：
我不得不说，多年来我已经做过了很多项目的优化工作，很少会看到一个单一的函数能在调用过程中留下如此之多的析构。 你通常会看到的模式是“局部性能热点”（一些函数完全占据了分析器的时间，就像我在第一轮分析中看到的纹理加载那样）或“由于层次太多而造成的死亡”，其中分析器的时间由许多“中间函数”所占据，这些“中间函数”会委托别的函数做实际的工作，但每次会增加一点开销。正如你可以看到的那样，这里发生的不是这两种情况。我们在这里遇到的是罕见的“各方面死亡”的变种。 为什么要解决层次太多这种性能问题，让我们直接去解决这个集束炸弹！
在这一点上，很明显，对于整个配置文件需要认真的做一些工作。但首先，我很好奇。 配置文件加载和配置块处理当然需要。 但是那个RemoveWhitespace函数在那里做什么呢？ 所以让我看下这个函数。
如何不去除空格？
我们直截了当地去做这个事情，这是代码。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | void RemoveWhitespace(cString &szString){ ＼＼＼Remove leading whitespace size_t nFirstIndex = szString.find_first_not_of(_L(' ')); if(nFirstIndex != cString::npos) { szString = szString.substr(nFirstIndex); } ＼＼＼Remove trailing newlines size_t nLastIndex = szString.find_last_not_of(_L('\n')); while(nLastIndex != szString.length()-1) { szString.erase(nLastIndex 1,1); nLastIndex = szString.find_last_not_of(_L('\n')); }; ＼＼＼Tabs nLastIndex = szString.find_last_not_of(_L('\t')); while(nLastIndex != szString.length()-1) { szString.erase(nLastIndex 1,1); nLastIndex = szString.find_last_not_of(_L('\t')); }; ＼＼＼Spaces nLastIndex = szString.find_last_not_of(_L(' ')); while(nLastIndex != szString.length()-1) { szString.erase(nLastIndex 1,1); nLastIndex = szString.find_last_not_of(_L(' ')); };} |
我现在和以前的同事确认，我一般都是一个相当冷静，轻松的人。 但是，在极度沮丧的时刻，我会（有时候）去“* headdesk *”，并且这样做是正确的。
这段代码并没有让我这么疯狂，但已经很接近了。
这个函数出错的地方有：
l 虽然它被认为该去掉所有前置和尾随的空白字符（从函数本身这一点并不是显而易见的，但在上下文中可以看的很清楚），但是它只会去掉前置的空格。所以举个简单的例子来说，前置的制表符不会被去掉，也不会去掉这些制表符之后的任何空格。
l 该函数将删除尾随的空格、制表符和换行符 - 只要它们按照这样的顺序出现：首先是所有空格，然后是所有制表符，然后是所有的换行符。 但是，字符串“test \ t \ n”将被修剪为“test \ t”， 制表符仍然完整，因为制表符剥离循环只会在删除位于字符串末尾的制表符，并且要之前已经发生过那些换行符被删除的情况。
l 它会删除它从前到后发现的空白字符，而不是从后到前发现的空白字符。由于C / C 字符串的工作原理，这是一个O（N2）操作。 举个简单的例子来说，取一个只包含制表符的字符串，这样的操作就是这么一个时间复杂度。
l 子串的操作创建了一个额外的临时字符串，虽然这个函数的其他部分还没有发生什么可怕的事情，但是现在可以看的很清楚为什么RemoveWhitespace函数同时在malloc，free和memcpy的调用堆栈中都表现的这么突出。
l 我们甚至不用讨论从前到后扫描字符串的次数。
这本身就不够好。但是事实证明，在这种情况下，这个函数不仅没有得到很好的实现，而且大部分的工作是完全不必要的。这是一个主要的调用者，ReadLine：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | CPUTResult ReadLine(cString &szString, FILE *pFile){ ＼＼＼ TODO: 128 chars is a narrow line. Why the limit? ＼＼＼Is this not really reading a line, but instead just reading the next 128 chars to parse? TCHAR szCurrLine[128] = {0}; TCHAR *ret = fgetws(szCurrLine, 128, pFile); if(ret != szCurrLine) { if(!feof(pFile)) { return CPUT_ERROR_FILE_ERROR; } } szString = szCurrLine; RemoveWhitespace(szString); ＼＼＼TODO: why are we checking feof twice in this loop? ＼＼＼ And, why are we using an error code to signify done? ＼＼＼eof check should be performed outside ReadLine() if(feof(pFile)) { return CPUT_ERROR_FILE_ERROR; } return CPUT_SUCCESS;} |
我会让评论区为他们说话 - 而对于这个记录来说，这个东西被认为应该是去读取一行，如果有一行会超过128个字符的话，点对点分析器将会失去同步。
但是，这里要注意的是，szString是从C风格（宽）字符串中分配的。所以这里的操作顺序是，我们首先分配一个cString（顺便说一下这是一个std :: wstring的typedef），复制我们读取出来的行，然后调用RemoveWhitespace，这可能会在这个substr调用里面创建另一个临时字符串，然后使用几个全字符串扫描和可能的内存移动进行跟踪。
除了这一切都是完全不必要的以外。即使我们需要输出的是一个cString，我们可以从C字符串的一个子集开始，而不是去做整个事情。所有RemoveWhitespace真正需要做的是告诉我们字符串的非空格部分的开始和结束位置。你可以使用C风格的字符串处理，或者如果你希望“感觉更像C ”，你可以通过迭代器操作来表达：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | static bool iswhite(int ch){ return ch == _L(' ') || ch == _L('\t') || ch == _L('\n');} templatestatic void RemoveWhitespace(Iter& start, Iter& end){ while (start < end && iswhite(*start)) start; while (end > start && iswhite(*(end - 1))) --end;} |
请注意，这不仅要短得多，而且在行的开头和结尾也能正确地处理所有类型的空格。 我们然后做的事情不再是原始的字符串分配：
1 2 3 4 5 6 7 8 9 | ＼＼＼TCHAR* obeys the iterator interface, so... TCHAR* start = szCurrLine; TCHAR* end = szCurrLine tcslen(szCurrLine); RemoveWhitespace(start, end);szString.assign(start, end); |
请注意我如何使用迭代器的分隔符形式来设置单个副本的字符串。 没有更多的子字符串操作，没有更多的临时或O（N2）循环，并且在读取之后，我们扫描整个字符串不超过两次，其中一次是在tcslen中。 （tcslen是相当于TCHAR的strlen的MS扩展，可能是普通的char或是wchar_t，具体取决于是否定义了UNICODE - 此代码恰好是使用“Unicode”，即UTF-16）。
只有另外两个地方会调用RemoveWhitespace，这两个调用与我们刚刚看到的调用相同，所以它们也很容易解决。
问题解决了？
不完全是这样。即使是在受控的情况下执行RemoveWhitespace函数，我们仍然在读取几兆字节的文本文件，并且每行代码中仍然有1到3个临时字符串分配，以及还是需要执行一些分配操作来把数据实际存储到位于CPUTConfigBlock中的最终位置。
让我们长话短说，这段代码仍然非常需要重写，以减少字符串的处理，所以我就这么做了。我的新代码只需一次将整个文件读入内存缓冲区（该应用程序以原始形式占用了1.5GB的内存，我们可以在一个程序段中为文本文件分配650K），然后实现更合理的扫描程序来处理数据，并且不会执行任何字符串操作，直到我们需要将值存储在它的最终位置。现在，因为新的扫描器假设ASCII字符的结尾还是ASCII字符，所以实际上不能正常使用某些字符编码，比如说是Shift-JIS，其中看上去像是ASCII的字符可能出现在多字节字符编码的中间（配置文件格式很像INI文件，所以'['、']'和'='是特殊字符，方括号可以在Shift-JIS序列中显示为第二个字符）。然而，它仍然适用于US-ASCII文本、ISO Latin系列和UTF-8编码，我认为这个配置文件读取器是可以接受的。我仍然希望支持Unicode字符作为标识符，这意味着我遇到了一个问题：一旦我已经识别出所有的字节及其在文件中的扩展区，想要使用标准的C 功能把相应的字节序列变成std :: wstring对象肯定不应该很难对吧？真的，我所需要的就是一个带有这个签名的函数：
1 | void AssignStr(cString& str, const char* begin, const char* end); |
转换字符串，它有多难？
事实证明：这相当的困难。我可以再次尝试在我的cString上使用assign。 如果输入恰好只是ASCII的话，这可以正常“工作”。但是它只是将每个字节值转换成相应的Unicode代码值，如果我们的输入文本文件中包含有非ASCII字符，这明显是错误的。
好的，所以我们可以把我们的字符序列变成一个std :: string，然后把它转换成一个std :: wstring，让我们先暂时不去介意这里面的临时变量，我们稍后可以解决这个问题。。。。等等，什么？ 实际上没有官方的方法来将一个包含多字节字符的字符串转换成wstring？ 这是多么的莫名其妙！
好吧，C 这个小气鬼。让我们坚持使用C。现在实际上有一个标准的函数mbstowcs，可以将多字节编码转换为wchar_t字符串，并在通常的情况称为“省略不必要的元音”的C风格。 只有在两个指针分隔的输入字符串上不能使用该函数！ 那是因为当它接受输出缓冲区的大小的时候，它假设输入的是以0终止的C字符串。对于大多数C字符串处理函数来说，这可能是一个合理的假设，但对于通常用于输入解析的东西来说，这绝对是一个问题，因为我们通常不能保证在正确的地方有NULL字符。
但是让我们先假设下，我们愿意修改输入数据（让const去死），并暂时在结尾覆盖NULL字符，所以我们可以使用mbstowcs - 让我现在对这个函数做一个评论， mbstowcs_s，mbstowcs的Microsoft扩展安全版本，接受两个输出缓冲区大小的参数，但仍然没有办法控制要读取多少个输入字符 - 如果你决定扩展标准API，为什么你不在同一时间修复它？ 无论如何，如果我们只是在源字符串中修补，来满足mbstowcs的使用条件，那对我们有帮助吗？
好吧，这取决于你愿意以多大的宽松度来执行C 标准。整个行动的目标是减少临时分配的数量。那么，mbstowcs函数需要的是一个wchar_t输出缓冲区，并按照它是C字符串的方式进行写入，包括终止NUL。 std :: wstring也分配了内存，正常的实现将会存储一个终止的值为0 的wchar_t字符，但是据我所知，这实际上并不是保证的行为。 在任何情况下，都有一个问题，因为我们需要在输出字符串中保留正确数量的wchar，但又不能保证这样做是安全的：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | void AssignStr(cString& str, const char* begin, const char* end){ ＼＼＼ patch a terminating NUL into *end char* endPatch = (char*) end; char oldEnd = *end; *endPatch = 0; ＼＼＼mbstowcs with NULL arg counts how many wchar_t's would be ＼＼＼generated size_t numOut = mbstowcs(NULL, begin, 0); ＼＼＼ make sure str has the right size str.resize(numOut, ' '); ＼＼＼convert characters including terminating NUL and hope it's ＼＼＼going to be OK? mbstowcs(&str[0], begin, numOut 1); ＼＼＼ restore the original end *endPatch = oldEnd;} |
这可能会起作用，也可能没有。 据我所知，只要是在特定字符串上首次调用c_str（）的时候，std :: wstring实现只会懒惰地在结尾附加一个NULL字符。 无论哪种方式，它都相当粗糙。我想我可以把大小调整到numOut 1个元素，然后在mbstowcs完成后再做另一个大小调整，这样的话肯定是安全的。
无论哪种方式都是完全不同的。 这是一个非常重要的字符串操作，做了一个完全合理的事情，而且，如果我使用fgetws的话，C语言的IO系统实际上会隐式的替我来做这个事情。为什么处理这个事情的所有函数对于这种用法而言是如此糟糕？有没有人看过这个，并且认为期望人们编写这样的代码是合理的？ 这是在搞什么鬼？
它变得更好了
不过还不行。因为当我实际写这些代码（而不是总结这个博客文章）的时候，我没有想到在源字符串中进行NULL字节的修补。所以我使用了一个可以按字符执行的替代API：C函数mbtowc。现在，可怕的是，因为它是按字符执行的，并且不能保证在同一个调用中看到多字节序列中的所有字符，所以它必须保持其所看到的部分多字节序列的状态以便对整个多字节序列进行解码，所以它不是线程安全的，POSIX定义了一个扩展版本的mbrtowc，它让你传递一个指向该状态的指针，这使得它线程安全。在这一点上，我不关心线程安全性（这个代码是单线程的），而且在我们的例子中，我实际上知道开始和结束之间的字符会被正确的解析。所以我不用担心这个问题。另外，我只是假设字符串通常可能比原来的多字节字符串的宽字符字节数要少，而不是在第二个遍历中实际去数下正确的wchar_t数。即使这样做是错误的（传统编码不会发生），我们写的std ::wstring可以动态调整大小，所以没有多少地方可以出错。所以我结束了这个实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | void AssignStr(cString& dest, const char* begin, const char* end){ dest.clear(); if (end <= begin) return; size_t len = end - begin; size_t initial = len 1; ＼＼＼ assume most characters are 1-byte dest.reserve(initial); const char* p = start; while (p < end) { wchar_t wc; int len = mbtowc(&wc, p, end - p); if (len < 1) ＼＼＼NUL byte or error break; p = len; dest.push_back(wc); }} |
这看起来很合理吧？是吧？
在稍后一个分析会话中，我注意到性能有所改善，但事实证明，我显然错误地做了一个假设，就像std :: vector对应的部分一样，std :: wstring :: push_back将基本上等价于编译成 dest.data [dest.len ] = wc。 相反，我在VTune中看到的（有一种病态的迷恋）围绕着std :: wstring :: insert的调用有大约二十个内联指令，像精神错乱一样。在正式发布版中对每个字符都是如此。
这可能是VC STL做的一些愚蠢的事情。 在这一点上，我不想调查为什么会发生这种情况。无论如何，我只是往这样一个有点精神错乱的情况下加了一点量。所以让我们停止思考并开始编码。 所以我想，嘿，如果添加东西到字符串里显然是一个昂贵的操作，那么让我们摊薄它呢？所以我做了这个事情：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | void AssignStr(cString& dest, const char* begin, const char* end){ dest.clear(); if (end <= begin) return; static const int NBUF = 64; wchar_t buf[NBUF]; int nb = 0; size_t len = end - begin; size_t initial = len 1; ＼＼＼ assume most characters are 1-byte dest.reserve(initial); const char* p = start; while (p < end) { int len = mbtowc(&buf[nb ], p, end - p); if (len < 1) ＼＼＼ NUL byte or error break; p = len; if (p >= end || nb >= NBUF) { dest.append(buf, buf nb); nb = 0; } }} |
它还是很慢，而且我还是为了这个调用得到了大量狗屎一样的内联函数。事实证明，这是因为我调用了通常的“输入迭代器”变体，而它会逐字符的叠加。 我怎么这么傻！ 我真正应该调用的是dest.append（buf，nb）。当然！ 一旦我想到了这一点，我就再一次做分析，并确定，这一次没有神奇的std :: string函数那种混乱的情况了。最后，任务完成了，对吧？
不不不，没有那么快。
哦，不不不，还有一个最后的“惊喜”等着我。我惊讶的发现这一点，因为我们已经在我的第一个分析文件截图中就已经看到了它。
是的，就是这些我们一直在调用的C函数？ 在VC 的C运行时库中，由于某些原因，所有这些函数都会调用C 对象的构造函数。
我不会评论这一段。我在这篇文章的前几段就停止关心这个事情了。让我们继续，将C 代码放在你的C运行时库中。这会让你快乐一些。
因此，事实证明，VC 具有多字节转换函数的两个版本：一个使用当前语言环境（这个信息你可以使用_get_current_locale（）进行查询），另一个使用显式的locale_t参数。如果你不自己传入一个locale，那么mbtowc等函数会自动调用_get_current_locale（），最后由于某种原因会调用一个C 构造函数。（我不在乎这是为什么，我现在很快乐，啦啦啦）。
而且我最后决定舍弃掉可移植性 - 嘿，它是一个只能在VC 上运行的项目，而且会调用_get_current_locale（）一次，把它传递给我所有的调用，而魔术构造函数就消失了，而最后的迹象表明问题出在字符串处理那里。
万岁。
总结
那么，我们在这里得到了什么：我们有一个C 字符串类，显然可以很容易地写出可怕的破解代码而不去注意它，同时也不提供一些核心功能，也就是同时使用std :: wstring和非UTF16字符集接口的应用程序（几乎没人这么做，我确定！）所需要的那些功能。我们有一些C函数，但是就算竭尽全力也很难正确使用它们。我们有Microsoft的扩展版本，决定修正这些函数的正确方法是修复缓冲区溢出，我们有POSIX扩展版本，决定修正这些函数的正确方法是修复其全局状态固有的竞争条件。这两个版本都声称他们的修改比另一个更重要，还有一个派系将原来的C标准库作为唯一的正确的方式，忽略了这个API显然是非常可怕的。同时，std :: wstringget赢得了另外一个需要关注的修复，通过将从C API在没有额外复制的情况下实际获取数据的难度提高到一个完全不需要的高度（我可以提醒你，我只在这里使用C的 API，因为似乎不是一个官方C API！），而VC 标准库通过某种方式证明其有一定的缺陷，它让push_back预先分配字符串而成为一个非常昂贵的操作。对于我们这次小型表演的最后一个演员，看看一个C代码竟然会调用构造函数，真是天神下凡，我真的大开眼界从没看过。
正如我的朋友Casey Muratori所说的那样：写这些代码的每一个人都应该被解雇。
现在请原谅我，因为我正在绑绷带，并擦干我的桌子上的血。
【版权声明】
原文作者未做权利声明，视为共享知识产权进入公共领域，自动获得授权。