字符串匹配性能:gcc与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(每次测试都从磁盘读取,没有特殊的缓存):

蟒蛇:

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; 将搜索委托给FASTSEARCH.

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

快速搜索/计数实施,基于boyer-moore和horspool之间的混合,顶部还有一些铃声和口哨声.有关更多背景信息,请参阅:http://effbot.org/zone/stringlib.htm

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

注意:fastsearch可以访问s[n],这在使用Python的普通字符串类型时不是问题,但如果您在其他上下文中使用此代码,则可能会导致问题.此外,-1 如果目标字符串中不可能存在匹配,并且0实际上已检查匹配但未找到任何匹配,则计数模式返回.来电者要小心!

的GNU C++标准库basic_string<T>::find()实现是通用的(和哑)成为可能; 它只是尝试在每个连续的角色位置上愚蠢地匹配模式,直到找到匹配.

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