Rendimiento de coincidencia de cadenas: gcc versus CPython

Mientras investigaba las compensaciones de rendimiento entre Python y C ++, he ideado un pequeño ejemplo, que se centra principalmente en una concordancia de subcadenas tontas.

Aquí está el C ++ relevante:

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

Lo anterior está construido con -O3.

Y aquí está Python:

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

Ambos toman un gran conjunto de patrones y archivos de entrada, y filtran la lista de patrones a los que se encuentran en el archivo mediante una búsqueda de subcadenas tontas.

Las versiones son:

  • gcc – 4.8.2 (Ubuntu) y 4.9.2 (cygwin)
  • python – 2.7.6 (Ubuntu) y 2.7.8 (cygwin)

Lo que me sorprendió es el rendimiento. He corrido tanto en un Ubuntu de baja especificación y Python fue más rápido en un 20%. Lo mismo en las PC de mediana especificación con cygwin: Python dos veces más rápido. El generador de perfiles muestra que más del 99% de los ciclos se gastan en la coincidencia de cadenas (la copia de cadenas y la comprensión de listas son insignificantes).

Obviamente, la implementación de Python es C nativa, y esperaba que fuera aproximadamente igual a C ++, pero no lo esperaba tan rápido.

Cualquier información sobre las optimizaciones de CPython relevantes en comparación con gcc sería muy bienvenida.

Para referencia, aquí están los ejemplos completos. Las entradas solo toman un conjunto de 50K HTLMs (todas leídas del disco en cada prueba, sin almacenamiento en caché especial):

Pitón:

 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  #include  #include  #include  #include  #include  #include  using namespace std; using MatchResult = unordered_map<string, vector>; static const size_t PATTERN_RESERVE_DEFAULT_SIZE = 5000; MatchResult serialMatch(const vector &filenames, const vector &patterns) { MatchResult res; for (auto &filename : filenames) { ifstream file(filename); const string fileContents((istreambuf_iterator(file)), istreambuf_iterator()); vector 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 filenames; ifstream filenamesListFile(argv[1]); std::copy(istream_iterator(filenamesListFile), istream_iterator(), back_inserter(filenames)); vector patterns; patterns.reserve(PATTERN_RESERVE_DEFAULT_SIZE); ifstream patternsFile(argv[2]); std::copy(istream_iterator(patternsFile), istream_iterator(), 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; } } 

El código de python 3.4 b'abc' in b'abcabc' (o b'abcabc'.__contains__(b'abc') como en tu ejemplo) ejecuta el método bytes_contains , que a su vez llama a la función en línea stringlib_find ; que delega la búsqueda a FASTSEARCH .

La función FASTSEARCH utiliza un algoritmo de búsqueda Boyer-Moore simplificado ( Boyer-Moore-Horspool ):

Implementación rápida de búsqueda / conteo, basada en una mezcla entre boyer-moore y horspool, con algunas campanas y silbidos más en la parte superior. para obtener más información, consulte: http://effbot.org/zone/stringlib.htm

También hay algunas modificaciones, como lo señalan los comentarios:

nota: fastsearch puede acceder a s[n] , lo cual no es un problema cuando se usan los tipos de cadenas comunes de Python, pero puede causar problemas si usa este código en otros contextos. también, el modo de conteo devuelve -1 si no es posible que haya una coincidencia en la cadena de destino, y 0 si realmente ha verificado coincidencias, pero no encontró ninguna. las personas que llaman tengan cuidado!


La basic_string::find() biblioteca estándar de GNU C ++ es tan genérica (y simple) como sea posible; solo intenta hacer coincidir el patrón en cada posición de cada carácter consecutivo hasta que encuentre la coincidencia.


TL; DR : La razón por la que la biblioteca estándar de C ++ es tan lenta en comparación con Python es porque intenta hacer un algoritmo genérico encima de std::basic_string , pero no lo hace de manera eficiente para los casos más interesantes; mientras que en Python, el progtwigdor obtiene de forma gratuita los algoritmos más eficientes caso por caso.