python - 字符串匹配性能 : gcc versus CPython

Question

在研究 Python 和 C++ 之间的性能权衡时，我设计了一个小示例，主要关注哑子字符串匹配。

这里是相关的C++:

using std::string;
std::vector<string> matches;
std::copy_if(patterns.cbegin(), patterns.cend(), back_inserter(matches),
   [&fileContents] (const string &pattern) { return fileContents.find(pattern) != string::npos; } );

上面是用-O3构建的。

这里是 Python:

def getMatchingPatterns(patterns, text):
    return filter(text.__contains__, patterns)

它们都采用大量模式和输入文件，并使用哑子字符串搜索将模式列表过滤为在文件中找到的模式。

版本是:

• gcc - 4.8.2 (Ubuntu) 和 4.9.2 (cygwin)
• python - 2.7.6 (Ubuntu) 和 2.7.8 (cygwin)

令我惊讶的是性能。我在低规范的 Ubuntu 和 Python 上都运行过，速度提高了大约 20%。在带有 cygwin 的中等规范 PC 上也是如此——Python 快两倍。Profiler 显示 99+% 的周期花在了字符串匹配上(字符串复制和列表解析无关紧要)。

很明显，Python 实现是原生 C，我预计它与 C++ 大致相同，但没想到它这么快。

欢迎任何深入了解与 gcc 相比的相关 CPython 优化。

作为引用，这里有完整的例子。输入只需要一组 50K HTLM(每次测试都从磁盘读取，没有特殊缓存):

python :

import sys

def getMatchingPatterns(patterns, text):
   return filter(text.__contains__, patterns)

def serialScan(filenames, patterns):
   return zip(filenames, [getMatchingPatterns(patterns, open(filename).read()) for filename in filenames])

if __name__ == "__main__":
   with open(sys.argv[1]) as filenamesListFile:
      filenames = filenamesListFile.read().split()
   with open(sys.argv[2]) as patternsFile:
      patterns = patternsFile.read().split()

   resultTuple = serialScan(filenames, patterns)
   for filename, patterns in resultTuple:
      print ': '.join([filename, ','.join(patterns)])

C++:

#include <iostream>
#include <iterator>
#include <fstream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;
using MatchResult = unordered_map<string, vector<string>>;
static const size_t PATTERN_RESERVE_DEFAULT_SIZE = 5000;

MatchResult serialMatch(const vector<string> &filenames, const vector<string> &patterns)
   {
   MatchResult res;
   for (auto &filename : filenames)
      {
      ifstream file(filename);
      const string fileContents((istreambuf_iterator<char>(file)),
                                         istreambuf_iterator<char>());
      vector<string> matches;
      std::copy_if(patterns.cbegin(), patterns.cend(), back_inserter(matches),
                   [&fileContents] (const string &pattern) { return fileContents.find(pattern) != string::npos; } );

      res.insert(make_pair(filename, std::move(matches)));
      }
   return res;
   }

int main(int argc, char **argv)
    {
    vector<string> filenames;
    ifstream filenamesListFile(argv[1]);
    std::copy(istream_iterator<string>(filenamesListFile), istream_iterator<string>(),
             back_inserter(filenames));

    vector<string> patterns;
    patterns.reserve(PATTERN_RESERVE_DEFAULT_SIZE);
    ifstream patternsFile(argv[2]);
    std::copy(istream_iterator<string>(patternsFile), istream_iterator<string>(),
             back_inserter(patterns));

    auto matchResult = serialMatch(filenames, patterns);

    for (const auto &matchItem : matchResult)
      {
      cout << matchItem.first << ": ";
      for (const auto &matchString : matchItem.second)
         cout << matchString << ",";
      cout << endl;
      }
    }

Answer 1

python 3.4 代码 b'abc' in b'abcabc' (或在您的示例中为 b'abcabc'.__contains__(b'abc'))执行 bytes_contains 方法，它又调用内联函数 stringlib_find ;它将搜索委托(delegate)给 FASTSEARCH .

FASTSEARCH然后函数使用简化的 Boyer-Moore搜索算法(Boyer-Moore-Horspool):

fast search/count implementation, based on a mix between boyer- moore and horspool, with a few more bells and whistles on the top. for some more background, see: http://effbot.org/zone/stringlib.htm

如评论所述，也有一些修改:

note: fastsearch may access s[n], which isn't a problem when using Python's ordinary string types, but may cause problems if you're using this code in other contexts. also, the count mode returns -1 if there cannot possible be a match in the target string, and 0 if it has actually checked for matches, but didn't find any. callers beware!

---

GNU C++ Standard Library basic_string<T>::find() 实现尽可能通用(和愚蠢)；它只是在每个连续的字符位置上愚蠢地尝试匹配模式，直到找到匹配为止。

---

TL;DR:C++ 标准库与 Python 相比如此慢的原因是因为它试图在 std::basic_string<char> 之上执行通用算法。 ，但对于更有趣的情况却无法有效地做到这一点；而在 Python 中，程序员可以根据具体情况免费获得最有效的算法。