find_first_of: STL 算法中的一个性能陷阱
本文讨论了最著名的 find_first_of 实现中发现的性能问题，并提出了有用的改进和变通方法。
目录
引言
本文讨论了在最著名的 STL 实现 [1,2,3,4] 中，find_first_of 通用 STL 算法的效率问题。以下段落将证明，在这些 STL 实现中，find_first_of 实际上是 STL 算法中的一个性能陷阱，在性能关键型应用程序中必须避免使用。此外，本文还提出了 STL 实现者可以用来提高 find_first_of 性能的解决方案，以及 C++ 开发者可以用来替代这种低效通用算法的替代方案。
我的目的是直奔主题，不冗长介绍 C++ 模板或 STL 本身。为了理解本文，您需要对 C++ 模板、标准模板库 (STL) 以及 C++ 语言有很好的理解。
算法使用和行为
为了充分描述该算法的用法和行为，我从出色的 SGI STL 文档中借用了以下三个小节。[5] 详情请参阅原始文档。
原型
find_first_of 是一个重载名称；实际上有两个 find_first_of 函数。template <class InputIter, class ForwardIter>
InputIter find_first_of(InputIter first1, InputIter last1,
ForwardIter first2, ForwardIter last2);
template <class InputIter, class ForwardIter, class BinaryPredicate>
InputIter find_first_of(InputIter first1, InputIter last1,
ForwardIter first2, ForwardIter last2, BinaryPredicate comp);
描述
find_first_of 与 find 类似，它通过一个输入迭代器范围执行线性搜索。不同之处在于，find 搜索一个特定值，而 find_first_of 搜索几个值中的任何一个。具体来说，find_first_of 搜索范围 [first1, last1) 中与 [first2, last2) 中的任何元素首次出现的位置。请注意，这种行为类似于标准 C 库中的函数 strpbrk。
两个版本的 find_first_of 在比较元素相等性方面有所不同。第一个使用 operator==，第二个使用任意用户提供的函数对象 comp。第一个版本返回 [first1, last1) 中第一个迭代器 i，使得对于 [first2, last2) 中的某个迭代器 j，*i == *j。第二个版本返回 [first1, last1) 中第一个迭代器 i，使得对于 [first2, last2) 中的某个迭代器 j，comp(*i, *j) 为真。通常，如果不存在这样的迭代器 i，则两个版本都返回 last1。
复杂性
最多有(last1 - first1) * (last2 - first2) 次比较。find_first_of 与 strpbrk
find_first_of STL 算法是较旧的 strpbrk C 库函数的后继者。find_first_of 算法的主要优点是其通用性和灵活性。它可以轻松地处理各种容器和任意类型的元素，而 strpbrk 只能处理以 null 结尾的 char 字符串。但如果我们需要处理 char 字符串或可以轻松转换为以 null 结尾的 char 字符串的 std::string 对象呢？我们应该选择较新的 find_first_of 算法还是只使用较旧的 strpbrk 函数？
find_first_of 在理论上似乎更优越
STL 最显著的品质之一是它同时追求通用性和效率！更具体地说，1995 年，STL 的设计者 Alexander Stepanov 在其发表于 BYTE 杂志的文章 [7] 中明确指出，与用 C/C++ 代码编写的非通用版本相比，通用 STL 算法不应引入任何性能损失。同年，Stepanov 在一次采访中说：“效率是我非常关心的问题。以一种抽象算法，当您实例化它时却变得低效，这是很愚蠢的。” [8] 因此，几乎没有任何理由让任何开发人员怀疑使用 find_first_of STL 算法可能会引入任何性能问题。
此外，find_first_of 比 strpbrk 更安全，因为它执行边界检查，减少了缓冲区溢出的可能性。最后但同样重要的是，大多数 C++ 开发人员都反复读到和听到，最好使用现有的 STL 算法，如 find_first_of，而不是等效的 C 库函数，如 strpbrk。根据上述事实，C++ 开发人员最合理的选择是始终倾向于通用、灵活且更安全的 find_first_of STL 算法，即使在较旧的 strpbrk C 库函数也适用。
性能比较揭示了一个令人不快的惊喜
幸运的是，在像这样的文章中，我们可以花费时间进行性能测试，即使在最不寻常的情况下也是如此。因此，我们对 find_first_of STL 算法和 strpbrk 函数进行了性能比较。[s5] 在两种不同配置下 [s5] 的这些性能测试结果证明，当我们要搜索的值的数量 (M=last2-first2) 开始增加时，find_first_of 算法的表现非常糟糕！find_first_of STL 算法不仅比 strpbrk C 库函数慢得多，而且其时间复杂度似乎也不比 O(N*M) 更好。相比之下，strpbrk 具有卓越的 O(N) 时间复杂度 (N=last1-first1)。
拥有较低的复杂度是效率最低的一种，因为它实际上意味着当特定问题因素的大小增加时，性能将持续变差。不幸的是，选择使用 find_first_of STL 算法的开发人员将不得不承受严重的性能损失，尽管他做出了一个非常合理的选择。因此，find_first_of 最终成为 STL 算法中一个危险的性能陷阱。
仔细查看 find_first_of 的实现
不提及某些现代编译器中 strpbrk C 库函数经过高度优化和调整以最大限度地利用 CPU，甚至使用汇编指令实现，这是不公平的。然而，strpbrk 实现中的这些优势无法证明其相对于 find_first_of 实现的卓越复杂性。时间复杂度不受代码优化级别甚至 C/C++ 与汇编之间切换的影响。实际上，它也与硬件无关。只有核心算法中的设计缺陷或不幸的设计决策才能真正损害时间复杂度。因此，仔细研究最著名的 find_first_of 实现以确定性能问题的根源将非常有趣。之后，我们还将尝试提高这种通用算法的效率。
识别问题根源
以下 find_first_of 实现是 SGI STL 版本 3.3 的一部分。[1,5] 这是一个相当典型的实现，与目前非常流行的 MS-VC++ 和 GCC-C++ 编译器 [2,4] 所使用的实现非常相似，并且与 STLPort STL 实现 [3] 也相同。
template<typename InputIter, typename ForwardIter>
InputIter find_first_of(InputIter first1,
InputIter last1, ForwardIter first2, ForwardIter last2)
{
for ( ; first1 != last1; ++first1)
{
for (ForwardIter iter = first2; iter != last2; ++iter)
{
if (*first1 == *iter)
return first1;
}
}
return last1;
}
显然，这个典型的 find_first_of 实现由两个嵌套的 for 循环组成。外层循环逐个选取搜索范围 [first1, last1) 中的元素，并执行内层循环，内层循环在上面的代码片段中以粗体显示。内层循环为每个搜索范围元素运行；其唯一任务是确定所讨论的元素是否包含在范围 [first2, last2) 中。如果检测到包含，find_first_of 立即返回当前元素 (first1)。否则，它会继续，直到外层循环耗尽，最后返回 last1。
鉴于 [first2, last2) 范围实际上定义了我们正在搜索的元素集合，上述 find_first_of 实现的内层 for 循环实际上测试了集合成员关系。然而，当用于集合成员关系测试时，循环效率非常低，这种技术显然是 find_first_of 性能问题的根源。具体来说，上述 find_first_of 实现的内层循环在不匹配的情况下执行 (last2 - first2) 次迭代。最坏的情况是搜索范围 [first1, last1) 的所有元素都不匹配，总共执行 (last1 - first1) * (last2 - first2) 次迭代，正如 SGI STL 文档 [5] 所述。然而，find_first_of 和 strpbrk 之间的性能比较 [s5] 已经证明，这个迭代次数相当过多。在相同的情况下，strpbrk C 库函数的时间复杂度不比 O(last1 - first1) 更差，无论 [last2 - first2) 范围的大小如何。
dpx::find_first_of：高效的特化
既然 find_first_of 性能问题的根源已经确定，现在非常重要的是寻找可供 STL 实现者用来提高这种通用算法效率的技术。有趣的是，如果 find_first_of 的输入范围包含 signed 或 unsigned chars，我们可以利用一个字节整数最多只有 256 个不同值的事实。具体来说，一个专门用于 signed 或 unsigned chars 的 find_first_of 实现可以轻松准备一个名为 MapArray 的 256 字节 数组，使得对于每个一个字节整数 ch，如果 ch 的值包含在范围 [first2, last2) 中，则 MapArray[ch]=1，否则 MapArray[ch]=0。
准备好这个数组后，上述典型 find_first_of 实现的整个内层 for 循环 [s4.1] 可以有效地替换为表达式：if (MapArray[*first1] != 0) return first1。这个替换将主迭代次数减少到 (last1 - first1)，同时由于 MapArray 的准备而增加 (last2 - first2)+256 次操作。因此，这种专门的 find_first_of 实现的复杂度将是 (last1 - first1) + (last2 - first2)。这远远超过了最常用的 find_first_of 实现 [1,2,3,4]，同时与 strpbrk C 库函数的时间复杂度相当。
此增强型 find_first_of 特化版本的完整代码显示在以下代码片段中。与上一小节中典型的 find_first_of 实现相比，已修改的部分以粗体显示。[s4.1] 相同的代码已在两种不同的测试配置 [s5] 中进行基准测试，并已被证明在实践中非常高效，正如其理论复杂度所表明的那样。
// An efficient find_first_of implementation for
// one-byte elements only (specialization)
template<typename InputIter, typename ForwardIter>
InputIter find_first_of(InputIter first1,
InputIter last1, ForwardIter first2, ForwardIter last2)
{
unsigned char MapArray[256];
memset(MapArray, 0, 256);
for (ForwardIter iter = first2; iter != last2; ++iter)
MapArray[(unsigned char) *iter] = 1;
for ( ; first1 != last1; ++first1)
{
if (MapArray[(unsigned char) *first1] != 0)
return first1;
}
return last1;
}
/*
* Copyright (c) 2007
* Jim Xochellis
*
* Permission to use, copy, modify, distribute and
* sell this software for any purpose
* is hereby granted without fee, provided that the
* above copyright notice appears in
* all copies and that both that copyright notice
* and this permission notice appear in
* supporting documentation. Jim Xochellis makes
* no representations about the suitability
* of this software for any purpose. It is provided
* "as is" without express or implied
* warranty.
*
*/
尽管 dpx::find_first_of 特化仅适用于单字节整数，但这一事实丝毫没有降低其重要性。该特化仍然比 strpbrk C 库函数更通用。因此，它可以有效地缓解 find_first_of 算法与其后继者相比的缺点。此外，它将消除 C++ 开发人员在发现每次他们选择 find_first_of 而非 strpbrk 时必须付出的性能代价时的挫败感。此外，如果 STL 实现中包含这样的特化，find_first_of 的性能将自动提高，而无需开发人员进行任何特殊处理。
此外，我可以在上述推理中补充一点，许多 C++ 开发人员在使用通用 STL 算法时仍然非常犹豫，尽管这些算法中的大多数都非常优雅、用途广泛且 STL 保证了它们的性能。如果 STL 算法的性能比其 C 库对应项差得多——例如 find_first_of 与 strpbrk [s3.2] ——将使程序员更不愿意利用这些优秀的编程工具。此外，由于 Alexander Stepanov 很久以前就断言 [7] 通用 STL 算法不应比其用 C/C++ 代码编写的非通用版本带来任何性能损失，因此消除 STL 现有的任何严重性能缺陷对其声誉至关重要。出于所有这些原因，对单字节整数使用 find_first_of 特化可能非常有益。
然而，使用 dpx::find_first_of 特化也是有代价的。具体来说，该特化用于显着加快集合成员测试的字节数组在算法运行时会消耗 256 字节的 RAM。在 RAM 有限的情况下（例如嵌入式系统），这可能是禁止的。一种可能的解决方法是将 256 字节的数组替换为 256 位的数组。位数组将只消耗 32 字节的 RAM——减少 8 倍——同时仅稍微降低算法的性能，而不影响其复杂性。最终选择显然取决于 RAM 的可用性。
其他替代方案
除了 find_first_of 算法在单字节整数的情况下可以显著改进之外，C++ 开发人员还可以利用 C++ 和 STL 提供的其他高效替代方案，前提是他们了解 find_first_of 的性能问题。例如，他们可以使用关联容器，如 set [9] 和 hash_set [10]，它们专门设计用于高效的集合成员测试。因此，如果 [first2, last2) 范围的元素被加载到关联容器中，那么一个适当的函数对象与 find_if [11] STL 算法结合可以以更高效的方式有效地模仿 find_first_of 的行为。以下代码片段提供了两个示例，演示如何分别使用 set 和 hash_set 容器来高效地复制 find_first_of 算法。
//---------------------------------------------------
//SetMembershipFunctor: a functor used in conjunction
//with find_if to produce find_first_of alternatives
//---------------------------------------------------
template<typename Set>
struct SetMembershipFunctor : public std::unary_function<
typename Set::value_type, bool>
{
public:
SetMembershipFunctor(Set *setPtr)
{
mSetPtr = setPtr;
}
inline bool operator() (const typename Set::value_type val) const
{
return mSetPtr->find(val) != mSetPtr->end();
}
protected:
Set *mSetPtr;
};
//-----------------------------------------------
//A find_first_of alternative based on a std::set
//-----------------------------------------------
typedef std::set<element_type> set_of_elements;
set_of_elements s1(search_elements.begin(), search_elements.end());
SetMembershipFunctor<set_of_elements> memberOfSet1(&s1);
search_range_type::const_iterator it1 =
std::find_if(search_range.begin(), search_range.end(), memberOfSet1);
//-----------------------------------------------
//A find_first_of alternative based on a hash_set
//-----------------------------------------------
typedef hash_set<element_type> hash_set_of_elements;
hash_set_of_elements s2(search_elements.begin(), search_elements.end());
SetMembershipFunctor<set_of_elements> memberOfSet2(&s2);
search_range_type::const_iterator it2 =
std::find_if(search_range.begin(), search_range.end(), memberOfSet2);
此外，我们还可以通过使用排序范围来有效地模仿 find_first_of 算法的行为。也就是说，如果我们将 [first2, last2) 元素转换为排序范围，然后可以使用适当的函数对象与 find_if [11] STL 算法结合使用，如下面的代码片段所示，并且远远超越了最著名的 find_first_of 实现。
//-----------------------------------------------------------
//SortedRangeMembershipFunctor: a functor used in conjunction
//with find_if to produce find_first_of alternatives
//-----------------------------------------------------------
template<typename ForwardIter>
struct SortedRangeMembershipFunctor
: public std::unary_function<
typename std::iterator_traits<ForwardIter>::value_type, bool>
{
public:
SortedRangeMembershipFunctor(ForwardIter first, ForwardIter last)
: mFirst(first), mLast(last) {}
inline bool operator() (
const typename std::iterator_traits<ForwardIter>::value_type val) const
{
return std::binary_search(mFirst, mLast, val);
}
protected:
ForwardIter mFirst, mLast;
};
//----------------------------------------------------
//A find_first_of alternative based on a sorted ranges
//----------------------------------------------------
typedef std::vector<test_string::value_type> sorted_range;
sorted_range elementsRange(search_elements.begin(), search_elements.end());
std::sort(elementsRange.begin(), elementsRange.end());
SortedRangeMembershipFunctor<sorted_range::const_iterator>
memberOfRange(elementsRange.begin(), elementsRange.end());
search_range_type::const_iterator it =
std::find_if(search_range.begin(), search_range.end(), memberOfRange);
理论上，在 hash_set 容器上进行集合成员测试的时间复杂度仅为常数时间，而在 std::set 容器和排序范围上进行相同操作的复杂度是对数级的。因此，find_first_of 替代方案的预期时间复杂度对于基于 hash_set 的解决方案是 O(last1-first1)，对于其他两种方法是 O((last1-first1)*log(last2-first2))。性能测试 [s5] 实际上证实了上述复杂度估计，在实践中证明了这些方法相对于最著名的 find_first_of 实现的优越性。[2,4]
不幸的是，上述变通方法仅与 find_first_of 算法支持的数据类型的一个子集兼容。也就是说，它们只能与可排序或适合作为 hash_set 元素的项一起使用。因此，这些替代方案无法完全且无条件地替换更通用的 find_first_of STL 算法。
性能测试
在前面的章节中，本文讨论了在最著名的 find_first_of 实现中发现的性能问题 [s4.1]。本文还介绍了高效的 find_first_of 特化 [s4.2] 和其他一些选项 [s4.3]。在本节中，我们将通过实际运行和计时来衡量和比较这些技术的速度。性能测试基于以下规则
- 测试场景相当简单。两个著名的
find_first_of实现 [2,4]、strpbrkC 库函数 [6]、dpx::find_first_of特化 [s4.2] 以及本文介绍的其他find_first_of替代方案 [s4.3] 在处理大量数据时进行了计时。具体来说，每个被测试的算法都扫描并处理了正好N个项目，寻找M个不同值中的任何一个的首次出现。为了确保准确的计时测量，输入数据以这样一种方式伪造：搜索条件仅在第N+1个项目处满足。N=last1-first1&M=last2-first2在find_first_of[s2.1] 中。 - 在所有测试中，搜索过程中被处理的项目数
N保持不变。因此，这个因素可以安全地排除在导致计时变化的因素之外。 - 测试过程中唯一实际变化的因素是我们要搜索的值的数量
M。这些性能测试的主要任务是演示M因素的增加如何影响每个被测试算法的耗时。 - 这些测试中唯一使用的项目类型是单字节整数。这实际上是一个相当强制性的决定，因为
strpbrkC 库函数和dpx::find_first_of特化都只适用于单字节整数。 - 测试中使用了两种不同的配置。在每种配置中，硬件、操作系统、编译器、
find_first_of(STL) 实现和strpbrk(C 库) 实现都是故意不同的。所有测试都执行了两次：在每种配置中各一次，使用完全相同的测试场景和代码。 - 用于测试的代码包含在本文顶部，可用于验证测试结果以及进一步实验。
测试结果已在以下两个图表中可视化：两个测试配置各一个图表，每个被测算法各一条图表线。两个图表中的纵轴表示经过时间，而横轴表示我们正在搜索的值的数量 M。经过时间的具体值已省略，因为它们依赖于配置，并且不是特别有用。最重要的是当 M 增加时，经过时间的变化。
性能测试 A
 |
配置
描述
|
性能测试 B
 |
配置
描述
|
关注点
显然，所有被测试算法的执行时间都取决于搜索过程中所处理的项目数量 N。另一方面，我们要搜索的值的数量 M 对上述算法的性能有影响。这种影响可能从微不足道到严重不等，具体取决于每个算法的设计。这些事实可以在图中直观地观察到。因此，六个被测试算法实际上可以根据它们的时间复杂度分为三类
- M 的影响微不足道，时间复杂度为 O(N)。两个图表都表明，
strpbrk函数（B 线）、dpx::find_first_of特化（C 线）和基于hash_set的find_first_of替代方案（E 线）的性能在M增加时几乎不受影响。然而，基于hash_set的替代方案比其他两个对应方案显著慢。 - M 的影响轻微，时间复杂度为 O(N*log(M))。基于
std::set(D 线) 和排序范围 (F 线) 的find_first_of替代方案在M增加时会略微变慢。 - M 的影响严重，时间复杂度为 O(N*M)。两种测试配置的
find_first_of实现（A 线）在M增加时都显著变慢。这两个实现是这些性能测试中效率最低的算法。
结论
毫无疑问，find_first_of 通用 STL 算法是较旧的 strpbrk C 库函数的泛化，理论上更通用、更优越。[s3.1] 不幸的是，在最著名的 STL 实现中 [1,2,3,4]，find_first_of 算法在抽象时忽略了其效率缺陷 [s4.1]。这使得它在性能关键型应用程序中相当危险！[s3.2]
问题最糟糕的部分是，很少有 C++ 开发人员会怀疑 find_first_of 通用算法与 strpbrk C 库函数相比的性能缺陷。[s3] 普通程序员将承受完全意想不到的性能损失，实际上陷入了性能陷阱。幸运的是，只要 STL 实现者愿意在其库中包含一些用于单字节整数的高效 find_first_of 特化，就像本文中介绍的那样 [s4.2]，就有办法摆脱这个陷阱。
然而，如果程序员完全意识到 find_first_of 的效率问题，情况可能会好得多。C++ 开发者可以利用许多高效的替代方案和变通方法 [s4.3]，以避免使用这种效率低下的通用 STL 算法。结果表明，find_first_of 可能是一个我们应该学习如何避免的 STL 算法！
在研究了许多著名的 STL 实现之后，我的总体结论是，尽管通用 STL 算法理论上可以与非通用对应算法的性能竞争，但要使其在实践中真正实现，仍有许多工作要做。不幸的是，我对 STL 通用算法在效率方面相对缓慢的进化速度并不特别满意。这最终是我撰写此类文章的原因，就像我之前关于 search_n 实现效率低下的文章一样。[12] 作为结语，我想再次重复 Alexander Stepanov 的话 [8]：“以一种抽象算法，当您实例化它时却变得低效，这是很愚蠢的。”
关于本文的更多信息
致谢
文章文本和代码的部分内容来源于 SGI/HP 的 STL 实现和文档。版权所有 © 1996-1999
硅谷图形计算机系统公司
特此授予免费使用、复制、修改、分发和销售本软件及其文档的许可，但前提是所有副本中均应包含上述版权声明，并且支持文档中应包含该版权声明和本许可声明。硅谷图形公司不对本软件适用于任何目的做出任何声明。本软件按“原样”提供，不附带任何明示或暗示的保证。
版权所有 © 1994
惠普公司
特此授予免费使用、复制、修改、分发和销售本软件及其文档的许可，但前提是所有副本中均应包含上述版权声明，并且支持文档中应包含该版权声明和本许可声明。惠普公司不对本软件适用于任何目的做出任何声明。本软件按“原样”提供，不附带任何明示或暗示的保证。
修订历史
- 2007年4月19日
- 初始发布。
- 2007年6月18日
- 文章已编辑并移至 CodeProject.com 主文章库。