Dopasowywanie ciągów: gcc kontra CPython

Question

Podczas badania kompromisów wydajności między Pythonem i C++ opracowałem mały przykład, który koncentruje się głównie na dopasowaniu podłańcucha.

Oto istotne 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; }); 

Powyższe jest zbudowany z -O3.

I tu jest Python:

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

Obaj podejmują duży-owski zestaw wzorów i pliku wejściowego oraz filtr w dół listę wzorców do tych znalezionych w pliku za pomocą niemego szukanie podciągu .

wersje są:

• GCC - 4.8.2 (Ubuntu) i 4.9.2 (Cygwinem)
• pyton - 2.7.6 (Ubuntu) i 2.7.8 (Cygwinem)

Co mnie zaskoczyło, to przedstawienie. Uruchomiłem obie na Ubuntu o niskim poziomie szczegółowości, a Python był szybszy o około 20%. To samo na mid-spec PC z cygwin - Python dwa razy szybciej. Profiler pokazuje, że 99 +% cykli jest spędzanych na dopasowywaniu ciągów znaków (kopiowanie ciągów i wyliczenia list są nieistotne).

Oczywiście, implementacja Pythona jest natywnym C, a spodziewałem się, że będzie mniej więcej taki sam jak C++, ale nie oczekiwał tego tak szybko.

Każdy wgląd w odpowiednie optymalizacje CPython w porównaniu z gcc byłby mile widziany.

Tutaj znajdą Państwo pełne przykłady dla odniesienia. Wejścia prostu wziąć zestaw 50K HTLMs (wszystko odczytać z dysku w każdym teście, nie ma specjalnych buforowania):

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

Pyton kod 3,4 b'abc' in b'abcabc' (lub b'abcabc'.__contains__(b'abc') jak w twoim przykładzie) wykonuje metodę bytes_contains, która z kolei wywołuje funkcję wypowiedzianą stringlib_find; który deleguje wyszukiwanie do FASTSEARCH.

Funkcja FASTSEARCH następnie wykorzystuje zmodyfikowaną Boyer-Moore wyszukiwarki algorytmu:

szybkie wyszukiwanie/liczenie wdrożenia, opartego na połączeniu pomiędzy boyer- Moore i horspool, z kilkoma bardziej wodotryski na górze. jakiegoś tła więcej, zobacz: http://effbot.org/zone/stringlib.htm

Istnieją pewne modyfikacje też, jak zauważył w komentarzach:

uwaga: fastsearch mogą uzyskać dostęp s[n], co nie jest problemem przy korzystaniu Pythona zwykłe typy ciągów, ale mogą powodować problemy, jeśli używasz tego kodu w innych kontekstach. również tryb licznika zwraca -1 , jeśli nie można dopasować w ciągu docelowym, a 0, jeśli faktycznie sprawdził pod kątem zgodności, ale nie znalazł żadnego. dzwoniący uwaga!

---

Realizacja GNU C++ Standard Library basic_string<T>::find() jest jako generic (i głupi), jak to możliwe; po prostu próbuje głupio dopasować wzór do każdej kolejnej pozycji postaci, dopóki nie znajdzie dopasowania.

---

TL; DR: Powodem C++ Standardowa biblioteka jest tak powolny w porównaniu do Pythona to dlatego, że próbuje zrobić ogólny algorytm na górze std::basic_string<char>, ale udaje mu się go skutecznie dla bardziej interesujący sprawy; mając na uwadze, że w Pythonie programista otrzymuje bezpłatnie najbardziej efektywne algorytmy dla każdego przypadku z osobna.