如何加快比较std::string与字符串字面量的速度？

Question

我有一堆代码，其中类型为std::string的对象与字符串字面值进行相等比较。类似于这样：

//const std:string someString = //blahblahblah;
if( someString == "(" ) {
   //do something
} else if( someString == ")" ) {
   //do something else
} else if// this chain can be very long

比较时间累积到了相当严重的程度（是的，我进行了剖析），因此加速将会很好。

代码会将字符串与许多短字符串文字进行比较，并且这种比较几乎无法避免。将字符串声明为std::string可能是不可避免的 - 类似这样的代码有数千行。保留字符串文字和使用==进行比较也可能是不可避免的 - 重写整个代码将会很麻烦。

问题在于Visual C++11附带的STL实现使用了一种有点奇怪的方法。 ==被映射到std::operator==(const basic_string&, const char*)，它调用basic_string::compare(const char*)，后者又调用std::char_traits<char>(const char*)，后者调用strlen()来计算字符串字面量的长度。然后比较运行两个字符串，并且两个字符串的长度都传递到该比较中。

编译器难以分析所有这些内容，并生成遍历字符串字面量两次的代码。对于短字面量来说，这不需要太多时间，但每次比较都涉及遍历字面量两次而不是一次。简单地调用strcmp()很可能会更快。

我是否可以做些什么，比如编写一个自定义比较器类，在这种情况下有助于避免遍历字符串文字两次？

- sharptooth

---

如果你分析出问题在于对strlen()的调用，为什么不与一组预构造的std::string const对象进行比较，而是继续与字符串字面值进行比较？ - Dietmar Kühl

拦截比较操作而不修改客户端代码会很棘手... 我建议尝试添加一个 template <size_t N> std::operator(const str&, const char (c&)[N]) - 如果它能够更明确地绑定，那么您可以为0、1、2、3、4的N进行特化，并推迟到现有的比较或者使用 memcmp。您可以使用例如从 c_str() 转换为 int16/int32 的 mem 强制转换进行单个比较... - Tony Delroy

我明白了。假设您的字符串文字不包含空字符，您可以将其与已知长度的创建文字进行比较。我会在我的答案中添加一个大纲。 - Dietmar Kühl

@TonyD：看起来绑定正常。 - sharptooth

你可以通过这样做避免所有与char_traits和意外计算有关的问题：char const *s = someString.c_str(); if ( !std::strcmp(s, "(")) { 等。 - M.M

Answer 1

与Dietmar的解决方案类似，但需要编辑较少：您可以将字符串（仅一次）包装起来，而不是每个文字都包装

#include <string>
#include <cstring>
struct FastLiteralWrapper {
    std::string const &s;

    explicit FastLiteralWrapper(std::string const &s_) : s(s_) {}

    template <std::size_t ArrayLength>
    bool operator== (char const (&other)[ArrayLength]) {
        std::size_t const StringLength = ArrayLength - 1;
        return StringLength == s.size()
            && std::memcmp(s.data(), other, StringLength) == 0;
    }
};

你的代码变成了：

const std:string someStdString = "blahblahblah";
// just for the context of the comparison:
FastLiteralWrapper someString(someStdString);
if( someString == "(" ) {
   //do something
} else if( someString == ")" ) {
   //do something else
} else if// this chain can be very long

注意：最快的解决方案 - 以更多编辑为代价 - 可能是构建一个（完美的）哈希或字典树，将字符串文字映射到枚举常量，然后只需在查找的值上切换。 长的if / else if链通常散发着不好的味道，在我看来。

- Useless

Answer 2

除了C++14的string_literal之外，你可以很容易地编写一个解决方案：

1. For comparison with a single character, use a character literal and:

   bool operator==(const std::string& s, char c)
   {
     return s.size() == 1 && s[0] == c;
   }
   

2. For comparison with a string literal, you can use something like this:

   template<std::size_t N>
   bool operator==(const std::string& s, char const (&literal)[N])
   {
     return s.size() == N && std::memcmp(s.data(), literal, N-1) == 0;
   }
   

免责声明：

• 第一个可能是多余的，
• 只有在您发现比以前有所改善时才这样做。

- rubenvb

---

对于与char的比较（或作为第二个N为1的特殊化），我会尝试*s.c_str() == c - 我的直觉是它会更快（在我检查过的每个实现中，size()都需要指针减法 - 优化了快速的end()而不是size()）。 - Tony Delroy

@Tony 如果s比您的文字字面量长怎么办？ - rubenvb

嗯...我应该专注于我的电影 :-/. 这确实需要测试第二个字节的NUL，以减少性能差异。当rhs已知为ASCIIZ时，您可以像我之前在问题评论中所述那样使用强制转换和int16_t比较，但这在某些系统上存在对齐问题。 - Tony Delroy

@Dietmar 是的，确实如此。这很容易解决 :-P - rubenvb

Answer 3

如果您需要比较一系列长字符串，很可能有潜力使用前缀比较来分组，以实现共同处理。特别是在将已知的一组字符串与输入字符串进行相等性比较时，也可以使用完美哈希并基于由它们生成的整数来键控操作。

由于使用完美哈希可能具有最佳性能，但还需要对代码布局进行重大更改，因此替代方案可以确定编译时字符串文字的大小，并在比较时使用这个大小。例如：

class Literal {
    char const* d_base;
    std::size_t d_length;
public:
    template <std::size_t Length>
    Literal(char const (&base)[Length]): d_base(base), d_length(Length - 1) {}
    bool operator== (std::string const& other) const {
        return other.size() == this->d_length
            && !other.memcmp(this->d_base, other.c_str(), this->d_length);
    }
    bool operator!=(std::string const& other) const { return !(*this == other); }
};
bool operator== (std::string const& str, Literal const& literal) {
    return literal == str;
}
bool operator!= (std::string const& str, Literal const& literal) {
    return !(str == literal);
}

显然，这假设您的文字不包含空字符('\0')，除了隐式添加的终止空字符以外，否则静态长度将会被扭曲。使用 C++11 constexpr 可以防范这种可能性，但没有任何好理由，代码会变得更加复杂。您可以使用类似以下方式比较字符串：

if (someString == Literal("(")) {
    ...
}
else if (someString == Literal(")")) {
    ...
}

- Dietmar Kühl

---

难道不应该是 ... memcmp(...) == 0 吗？ - Useless

Answer 4

另外两个想法：

A) 使用词法分析器工具（如flex）构建有限状态自动机，将字符串转换为整数令牌值，取决于它匹配的内容。

B) 使用长度来打破长的elseif链，可能部分地以表驱动的方式实现

为什么不在顶部获取字符串something的长度，然后只比较可能匹配的文字？

如果有很多，可能值得将其转化为表驱动和使用映射和函数指针。你可以仅特殊处理单个字符文字，例如使用函数查找表。

快速查找非匹配项和常见长度可能足够，并且不需要过多的代码重构，但更易于维护以及更快速。

int len = strlen (something);
if ( ! knownliterallength[ len]) {
    // not match
    ...
} else {
    // First char may be used to index search, or literals are stored in map with *func()

    switch (len)
    {
        case 1:  // Could use a look table index by char and *func()
            processchar( something[0]);
        break;

        case 2: // Short strings
        case 3: 
        case 4:
            processrunts( something);
        break

        default:
        //  First char used to index search, or literals are stored in map with *func()
            processlong( something);
        break
   }
}

- Rob11311

Answer 5

您可以采用字符串池技术来加速字符串比较: 构建一个大的哈希表包含所有创建出来的字符串。确保每当一个字符串对象被创建时，首先从哈希表中查找它，只有在没有预先存在的对象时才创建新对象。自然地，这个功能应该封装在您自己的字符串类中。

一旦完成了这个步骤，字符串比较就相当于比较它们的地址。

实际上，这是一种非常古老的技术，最初是由LISP语言推广开来的。

---

这种方法更快的原因在于每个字符串只需要被创建一次。如果您小心处理，就不会从相同的输入字节中多次生成相同的字符串，因此字符串创建开销由您处理的输入数据量来控制。而且对所有输入数据进行哈希一次也并不困难。

另一方面，比较倾向于反复涉及相同的字符串(如与文字字符串比较)，当您编写某种解析器或解释器时，这些比较将减少为单个机器指令。

- cmaster - reinstate monica

---

避免膨胀！你会让硬件工程师失业的 :) - Rob11311

这是一个很棒的技巧，但根据具体的应用需求、数据和硬件，可能会效率低下。像“最快的字符串比较”和“一次哈希所有输入数据并不是什么大问题”这样的说法有些夸张。 - Tony Delroy

仅对静态字符串文字进行哈希处理类似于基于FSA表的解决方案，从概念上讲。基于strlen + str [0] + str [1]％NOT_VERY_BIG number的快速哈希函数将大大减少比较次数，只要静态字符串文字的分布均匀。只需要251个元素的表就足够了，只需要1KiB。 - Rob11311

避免使用非常长的if...else if比较链，仍然需要通过函数指针在表中进行处理。希望CPU分支预测器能够良好地工作。 - Rob11311

Answer 6

这并不是最美观的解决方案，但在需要比较大量短字符串（例如脚本解析器中的运算符和控制字符/关键字）时，它已被证明非常快速。

创建一个基于字符串长度的搜索树，并仅比较字符。如果在特定实现中使得清晰易懂，尝试将已知字符串表示为枚举。

以下是简短的示例：

enum StrE {
  UNKNOWN = 0 ,
  RIGHT_PAR ,
  LEFT_PAR ,
  NOT_EQUAL ,
  EQUAL
};

StrE strCmp(std::string str)
{
  size_t l = str.length();
  switch(l)
  {
    case 1:
    {
      if(str[0] == ')') return RIGHT_PAR;
      if(str[0] == '(') return LEFT_PAR;
      // ...
      break;
    }
    case 2:
    {
      if(str[0] == '!' && str[1] == '=') return NOT_EQUAL;
      if(str[0] == '=' && str[1] == '=') return EQUAL;
      // ...
      break;
    }
    // ...
  }
  return UNKNOWN;
}



int main()
{
  std::string input = "==";

  switch(strCmp(input))
  {
    case RIGHT_PAR:
      printf("right par");
      break;
    case LEFT_PAR:
      printf("left par");
      break;
    case NOT_EQUAL:
      printf("not equal");
      break;
    case EQUAL:
      printf("equal");
      break;
    case UNKNOWN:
      printf("unknown");
      break;
  }
}

- Martin G