¿Cómo funciona memchr() bajo el capó?

performance d

Question

Antecedentes: estoy tratando de crear una implementación de funcionalidad de lenguaje D pura que sea más o menos equivalente al memchr de C, pero utiliza matrices e índices en lugar de punteros. La razón es para que std.string funcione con la evaluación de la función de tiempo de compilación. Para aquellos de ustedes que no estén familiarizados con D / D, las funciones se pueden evaluar en tiempo de compilación si se cumplen ciertas restricciones. Una restricción es que no pueden usar punteros. Otra es que no pueden llamar a las funciones C ni usar el lenguaje ensamblador en línea. Tener la biblioteca de cadenas en funcionamiento en tiempo de compilación es útil para algunos hacks de código de tiempo de compilación.

Pregunta: ¿Cómo funciona el memchr bajo el capó para funcionar tan rápido como lo hace? En Win32, todo lo que he podido crear en D puro usando bucles simples es al menos 2 veces más lento incluso con técnicas de optimización obvias como deshabilitar la comprobación de límites, desenrollar bucles, etc. ¿Qué tipos de trucos no obvios están disponibles para algo tan simple como encontrar un personaje en una cadena?

Answer 1

Aquí está el memchr () de FreeBSD (licencia BSD) de memchr.c . El navegador de código fuente en línea de FreeBSD es una buena referencia para ejemplos de código con licencia BSD probados por el tiempo.

void *
memchr(s, c, n)
    const void *s;
    unsigned char c;
    size_t n;
{
    if (n != 0) {
        const unsigned char *p = s;

        do {
            if (*p++ == c)
                return ((void *)(p - 1));
        } while (--n != 0);
    }
    return (NULL);
}

Answer 2

memchr como memset y memcpy generalmente reducen a una cantidad bastante pequeña de código de máquina. Es poco probable que pueda reproducir ese tipo de velocidad sin incluir un código de ensamblaje similar . Un tema importante a considerar en una implementación es la alineación de datos .

Una técnica genérica que puede usar es insertar un centinela al final de la cadena que se busca, lo que garantiza que la encontrará. Le permite mover la prueba para el final de la secuencia desde el interior del ciclo, hasta después del ciclo.

Answer 3

Esta implementación de memchr de newlib es un ejemplo de memchr de optimización de alguien: está leyendo y probando 4 bytes a la vez (aparte de memchr, otras funciones en la biblioteca newlib están aquí ).

Por cierto, la mayor parte del código fuente de la biblioteca MSVC en tiempo de ejecución está disponible, como parte opcional de la instalación de MSVC (por lo tanto, podría ver eso).

Answer 4

Sugeriría echar un vistazo a la fuente de GNU libc . En cuanto a la mayoría de las funciones, contendrá una versión C genérica optimizada de la función y versiones optimizadas de lenguaje ensamblador para la mayor cantidad posible de arquitecturas compatibles, aprovechando los trucos específicos de la máquina.

La versión x86-64 SSE2 combina los resultados de pcmpeqb en toda una línea de caché de datos a la vez (cuatro vectores 16B), para amortizar la sobrecarga de la salida temprana pmovmskb / test / jcc .

gcc y clang son actualmente incapaces de auto-vectorizar bucles con if() break condiciones de salida anticipadas, por lo que hacen ingenuo byte a la vez asm de la implementación obvia de C.