c++ - ¿Obligando a GCC a realizar la desactivación de bucles de las comprobaciones de tamaño de tiempo de ejecución de memcpy?

memmove

Question

¿Existe alguna forma confiable de forzar a GCC (o cualquier compilador) a factorizar las comprobaciones de tamaño en tiempo de ejecución en memcpy() fuera de un bucle (donde ese tamaño no es una constante de tiempo de compilación, sino una constante dentro de ese bucle), especializando el bucle para cada uno? ¿Rango de tamaño relevante en lugar de verificar repetidamente el tamaño dentro de él?

Este es un caso de prueba reducido de una regresión de rendimiento reportada here para una biblioteca de código abierto diseñada para un análisis eficiente en memoria de grandes conjuntos de datos. _{(La regresión pasa a ser por uno de mis compromisos ...)}

El código original está en Cython, pero lo he reducido a un proxy C puro como el siguiente:

void take(double * out, double * in,
          int stride_out_0, int stride_out_1,
          int stride_in_0, int stride_in_1,
          int * indexer, int n, int k)
{
    int i, idx, j, k_local;
    k_local = k; /* prevent aliasing */
    for(i = 0; i < n; ++i) {
        idx = indexer[i];
        for(j = 0; j < k_local; ++j)
            out[i * stride_out_0 + j * stride_out_1] =
            in[idx * stride_in_0 + j * stride_in_1];
    }
}

Los pasos son variables; en general, ni siquiera se garantiza que las matrices sean contiguas (ya que pueden ser cortes no contiguos de matrices más grandes). Sin embargo, para el caso particular de las matrices contiguas c, he optimizado lo anterior a lo siguiente:

void take(double * out, double * in,
          int stride_out_0, int stride_out_1,
          int stride_in_0, int stride_in_1,
          int * indexer, int n, int k)
{
    int i, idx, k_local;
    assert(stride_out_0 == k);
    assert(stride_out_0 == stride_in_0);
    assert(stride_out_1 == 1);
    assert(stride_out_1 == stride_in_1);
    k_local = k; /* prevent aliasing */
    for(i = 0; i < n; ++i) {
        idx = indexer[i];
        memcpy(&out[i * k_local], &in[idx * k_local],
               k_local * sizeof(double));
    }
}

(Las afirmaciones no están presentes en el código original; en su lugar, comprueban la continuidad y, si es posible, invocan la versión optimizada y la versión no optimizada, si no).

Esta versión se optimiza muy bien en la mayoría de los casos, ya que el caso de uso normal es para pequeñas n y grandes k . Sin embargo, el caso de uso opuesto también ocurre ( n grande y k pequeña), y resulta para el caso particular de n == 10000 k == 4 (que no puede descartarse como representante de una parte importante de un flujo de trabajo hipotético), la versión memcpy() es 3,6 veces más lenta que la original. Esto se debe, aparentemente, principalmente al hecho de que k no es una constante de tiempo de compilación, como lo demuestra el hecho de que esta próxima versión funciona (casi o exactamente, dependiendo de la configuración de optimización) así como la original (o mejor, a veces) , para el caso particular de k == 4 :

    if (k_local == 4) {
        /* this optimizes */
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    } else {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    }

Obviamente, no es práctico codificar un bucle para cada valor particular de k , así que intenté lo siguiente (como primer intento que luego podría generalizarse, si funcionara):

    if (k_local >= 0 && k_local <= 4) {
        /* this does not not optimize */
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    } else {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    }

Desafortunadamente, esta última versión no es más rápida que la memcpy() original de memcpy() , que es algo desalentadora para mi fe en las capacidades de optimización de GCC.

¿Hay alguna manera de que pueda dar "sugerencias" adicionales a GCC (por cualquier medio) que le ayuden a hacer lo correcto aquí? (Y aún mejor, ¿hay "pistas" que podrían funcionar de manera confiable en diferentes compiladores? Esta biblioteca está compilada para muchos objetivos diferentes).

Los resultados citados son para GCC 4.6.3 en Ubuntu de 32 bits con el indicador "-O2", pero también he probado versiones de GCC 4.7.2 y "-O3" con resultados similares (pero no idénticos). He publicado mi arnés de prueba en LiveWorkspace , pero los tiempos son de mi propia máquina usando el comando time(1) (no sé qué tan confiables son los tiempos de LiveWorkspace).

EDITAR: También he considerado simplemente establecer un "número mágico" para un tamaño mínimo con el que llamar a memcpy() , y podría encontrar ese valor con pruebas repetidas, pero no estoy seguro de qué tan generalizable serían mis resultados. compiladores / plataformas. ¿Hay alguna regla general que pueda usar aquí?

EDICIÓN ADICIONAL: k_local variables k_local realizadas son inútiles en este caso, en realidad, ya que no es posible realizar un alias; esto se redujo de algunos experimentos que realicé donde era posible ( k era global) y olvidé que lo cambié. Solo ignora esa parte.

EDITAR ETIQUETA: Realizado, también puedo usar C ++ en versiones más recientes de Cython, así que etiquetar como C ++ en caso de que haya algo que pueda ayudar desde C ++ ...

EDICIÓN FINAL: En lugar de (por ahora) bajar a ensamblar para un memcpy() especializado memcpy() , la siguiente parece ser la mejor solución empírica para mi máquina local:

    int i, idx, j;
    double * subout, * subin;
    assert(stride_out_1 == 1);
    assert(stride_out_1 == stride_in_1);
    if (k < 32 /* i.e. 256 bytes: magic! */) {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            subout = &out[i * stride_out_0];
            subin = &in[idx * stride_in_0];
            for(j = 0; j < k; ++j)
                subout[j] = subin[j];
        }
    } else {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            subout = &out[i * stride_out_0];
            subin = &in[idx * stride_in_0];
            memcpy(subout, subin, k * sizeof(double));
        }
    }

Esto usa un "número mágico" para decidir si llamar a memcpy() o no, pero aún así optimiza el caso para arreglos pequeños que se sabe que son contiguos (por lo tanto, es más rápido que el original, en la mayoría de los casos, ya que el original no lo hace). suposición).

Answer 1

Creo que la mejor manera es experimentar y descubrir el valor óptimo de "k" para cambiar entre el algoritmo original (con un bucle) y su algoritmo optimizado usando memcpy. La "k" óptima variará entre las diferentes CPU, pero no debería ser drásticamente diferente; esencialmente se trata de la sobrecarga de llamar a memcpy, la sobrecarga de memcpy en sí mismo al elegir el algoritmo óptimo (basado en el tamaño, la alineación, etc.) frente al algoritmo "ingenuo" con un bucle.

memcpy es un intrínseco en gcc, sí, pero no hace magia. Lo que básicamente hace es que si el argumento del tamaño se conoce en tiempo de compilación y es pequeño (no sé cuál es el umbral), GCC reemplazará la llamada a la función memcpy con el código en línea. Si el argumento de tamaño no se conoce en el momento de la compilación, siempre se realizará una llamada a la función de biblioteca memcpy.

Answer 2

En última instancia, el problema en cuestión es uno de pedirle al optimizador que haga suposiciones sobre el comportamiento en tiempo de ejecución basado en múltiples variables. Si bien es posible proporcionar al optimizador algunos consejos de tiempo de compilación mediante el uso de las declaraciones ''const'' y ''register'' en las variables clave, en última instancia, depende del optimizador para hacer muchas suposiciones. Además, aunque memcpy () puede ser intrínseco, no está garantizado que lo sea, e incluso si lo es, la implementación puede variar bastante.

Si el objetivo es lograr el máximo rendimiento, a veces simplemente no debe confiar en la tecnología para descifrarlo, sino hacerlo directamente. El mejor consejo para esta situación es el uso del ensamblador en línea para abordar el problema. Al hacerlo, le permite evitar todos los escollos de una solución de "caja negra" complementada por las heurísticas del compilador y el optimizador, y declarar finamente su intención. El beneficio clave para el uso del ensamblador en línea es la capacidad de evitar los empujes / saltos y el código de "generalización" extraña en la solución al problema de copia de memoria y la capacidad de aprovechar directamente la capacidad del procesador para resolver el problema. El inconveniente es el mantenimiento, pero dado que solo necesita dirigirse a Intel y AMD para cubrir la mayor parte del mercado, no es insuperable.

También podría agregar que esta solución podría permitirle aprovechar múltiples núcleos / subprocesos y / o una GPU si / cuando esté disponible para hacer la copia en paralelo y obtener realmente una ganancia de rendimiento. Si bien la latencia podría ser mayor, el rendimiento probablemente también sería mucho mayor. Si, por ejemplo, podría aprovechar una GPU si está presente, podría lanzar un núcleo por copia y copiar miles de elementos en una sola operación.

La alternativa a esto es depender del compilador / optimizador para hacer las mejores suposiciones para usted, usar las declaraciones ''const'' y ''register'' donde puede ofrecer sugerencias del compilador y usar números mágicos para derivar basándose en la "mejor solución" caminos ... esto, sin embargo, será excepcionalmente dependiente del compilador / sistema y su millaje variará ampliamente de una plataforma / entorno a otro.

Answer 3

SSE / AVX y Alineación

Si está encendido, por ejemplo, un procesador Intel moderno, entonces el uso de las instrucciones SSE o AVX es una opción. Si bien no se trata específicamente de GCC, vea this Si está interesado y lleno de caché, creo que Intel hace una versión de su compilador para Linux y Windows, y supongo que viene con su propio conjunto de bibliotecas.

También está este post .

Hilos (eek)

He tenido exactamente este tipo de problema hace bastante tiempo, un memcpy () que lleva demasiado tiempo. En mi caso, fue un memcpy grande () (1MByte o menos) en lugar de muchos más pequeños como lo está haciendo.

Obtuve un muy buen kilometraje al escribir mi propio memcpy () de múltiples hilos, donde los hilos eran persistentes y se me asignó una parte del trabajo mediante una llamada a mi propia función pmemcpy (). Los hilos persistentes significaban que la sobrecarga era bastante baja. Conseguí una mejora x4 para 4 núcleos.

Por lo tanto, si fuera posible dividir sus bucles en una cantidad razonable de hilos (elegí uno por núcleo disponible), y tuvo el lujo de unos cuantos núcleos de repuesto en su máquina, podría obtener un beneficio similar.

Lo que hace la gente en tiempo real - DMA

Aparte de eso, tengo el placer de jugar con un poco de hardware OpenVPX bastante exótico. Básicamente, se trata de un montón de tableros en una caja grande con una interconexión RapidIO serial de alta velocidad entre ellos. Cada placa tiene un motor DMA que lleva los datos a través de sRIO a la memoria de otra placa.

El proveedor al que fui es bastante inteligente en cómo maximizar el uso de una CPU. Lo más inteligente es que los motores DMA son bastante inteligentes: se pueden programar para hacer cosas como transformaciones matriciales sobre la marcha, extracción de tiras, cosas que estás tratando de hacer, etc. Y debido a que es una pieza separada de hardware, la CPU mientras tanto, no está atado, por lo que puede estar ocupado haciendo otra cosa.

Por ejemplo, si está haciendo algo como el procesamiento del Radar de Apertura Sintética, siempre terminará haciendo una gran transformación de matriz. Lo bueno es que la transformación en sí misma no toma tiempo de CPU en absoluto, simplemente mueve los datos a otra placa y llega transformada.

De todos modos, tener el beneficio de ese tipo de cosas realmente hace que uno desee que las CPU Intel (y otras) tengan motores DMA integrados capaces de funcionar con memoria-memoria en lugar de solo con periféricos de memoria. Eso haría que las tareas como la tuya sean realmente rápidas.