kmp algorithm c++

Strstr más rápido que los algoritmos?

Question

Tengo un archivo que es 21056 bytes.

He escrito un programa en C que lee todo el archivo en un búfer, y luego usa múltiples algoritmos de búsqueda para buscar un token de 82 caracteres.

He usado todas las implementaciones de los algoritmos de la página "Exact String Matching Algorithms" . He utilizado: KMP, BM, TBM y Horspool. Y luego utilicé strstr y comparé cada uno de ellos.

Lo que me pregunto es que, cada vez que el strstr supera a todos los otros algoritmos. El único que a veces es más rápido es el BM.

¿No debería ser strstr el más lento?

Aquí está mi código de referencia con un ejemplo de evaluación comparativa de BM:

double get_time()
{
LARGE_INTEGER t, f;
QueryPerformanceCounter(&t);
QueryPerformanceFrequency(&f);
return (double)t.QuadPart/(double)f.QuadPart;
}

before = get_time();
BM(token, strlen(token), buffer, len);
after = get_time();
printf("Time: %f/n/n", after - before);

¿Podría alguien explicarme por qué strstr está superando a los otros algoritmos de búsqueda? Publicaré más código a petición si es necesario.

Answer 1

¿Por qué crees que strstr debería ser más lento que todos los demás? ¿Sabes qué algoritmo usa strstr ? Creo que es bastante probable que strstr utilice un algoritmo de código de ensamblaje afinado, específico del procesador, o mejor. En cuyo caso, no tiene la posibilidad de superarlo en C para tales puntos de referencia pequeños.

(La razón por la que creo que esto es probable es que a los programadores les encanta implementar tales cosas).

Answer 2

Horspool, KMP y otros son óptimos para minimizar el número de comparaciones de bytes.

Sin embargo, ese no es el cuello de botella en un procesador moderno. En un procesador x86 / 64, su cadena se está cargando en el caché L1 en trozos de ancho de línea de caché (generalmente 64 bytes). No importa qué tan inteligente sea su algoritmo, a menos que le brinde avances que sean más grandes que eso, no gana nada; y el código de Horspool más complicado es (al menos una búsqueda en la tabla) no puede competir.

Además, está atascado con la restricción de cadena "C" de terminación nula: EN ALGUNA PARTE el código tiene que examinar cada byte.

Se espera que strstr() sea ​​óptimo para una amplia gama de casos; por ejemplo, buscar cadenas pequeñas como "/r/n" en una cadena corta, así como otras mucho más largas en las que algún algoritmo más inteligente podría tener una esperanza. El bucle básico strchr / memcmp es bastante difícil de superar en todo el rango de posibles entradas.

Casi todos los procesadores compatibles con x86 desde 2003 han admitido SSE2. Si desensambla strlen() / x86 para glibc , puede haber notado que utiliza algunas operaciones SSE2 PCMPEQ y MOVMASK para buscar el terminador nulo de 16 bytes a la vez. La solución es tan eficiente que supera el obvio bucle súper simple, para cualquier cosa más larga que la cadena vacía.

Tomé esa idea y se me ocurrió una strstr() que supera a la strstr() glibc para todos los casos mayores de 1 byte, donde la diferencia relativa es bastante discutible. Si estás interesado, echa un vistazo a:

• Convergencia SSE2 y strstr()

• Un mejor strstr() sin código ASM

  Si le interesa ver una solución que no sea SSE2 que domine strstr() para cadenas de destino de más de 15 bytes, revise:

  que hace uso de comparaciones multibyte en lugar de strchr() , para encontrar un punto en el que hacer un memcmp.

Por cierto, probablemente ya se haya dado cuenta de que las operaciones x86 REP SCASB / REP CMPSB caen sobre su culo por algo más de 32 bytes, y no son una gran mejora para cadenas más cortas. Ojalá Intel hubiera dedicado un poco más de atención a eso, que a agregar operaciones de "cadena" SSE4.2.

Para cadenas lo suficientemente grandes como para que me importen, mis pruebas de rendimiento muestran que BNDM es mejor que Horspool, en general. BNDM es más tolerante con los casos "patológicos", como los objetivos que repiten el último byte de un patrón. BNDM también puede hacer uso de SSE2 (registros de 128 bits) de una manera que compita con los registros de 32 bits en eficiencia y costo de inicio. Código fuente here .

Answer 3

Imagina que quieres limpiar algo. Puede limpiarlo usted mismo o puede contratar diez limpiadores profesionales para que lo limpien. Si el trabajo de limpieza es un edificio de oficinas, la última solución sería preferible. Si el trabajo de limpieza fuera una ventana, la primera sería preferible.

Nunca obtiene ningún reembolso por el tiempo dedicado a la configuración para hacer el trabajo de manera eficiente porque el trabajo no toma mucho tiempo.

Answer 4

Sin ver su código, es difícil decir exactamente. strstr está muy optimizado, y generalmente está escrito en lenguaje ensamblador. Hace cosas como leer datos de 4 bytes a la vez y compararlos (giros de bits si es necesario si la alineación no es correcta) para minimizar la latencia de la memoria. También puede aprovechar cosas como SSE para cargar 16 bytes a la vez. Si su código solo carga un byte a la vez, es probable que la latencia de la memoria lo anule.

Use su depurador y recorra el desmontaje de strstr ; probablemente encontrará algunas cosas interesantes allí.