c++ - La combinación interna sin sucursales es más lenta que la fusión interna con una rama

performance sorting

Question

Recientemente, hice una pregunta sobre la revisión de código para revisar un algoritmo de clasificación llamado QuickMergeSort . No entraré en los detalles, pero en algún momento el algoritmo realiza un mergesort interno: en lugar de usar memoria adicional para almacenar los datos para fusionar, intercambia los elementos para fusionarse con elementos de otra parte de la secuencia original, que no está De lo contrario, preocupado por la fusión. Aquí está la parte del algoritmo que me preocupa: la función que realiza la fusión:

template<
    typename InputIterator1,
    typename InputIterator2,
    typename OutputIterator,
    typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result, Compare compare={})
    -> void
{
    for (; first1 != last1; ++result) {
        if (first2 == last2) {
            std::swap_ranges(first1, last1, result);
            return;
        }

        if (compare(*first2, *first1)) {
            std::iter_swap(result, first2);
            ++first2;
        } else {
            std::iter_swap(result, first1);
            ++first1;
        }
    }
    // first2 through last2 are already in the right spot
}

Esa función fue adaptada de la función epónimo en la implementación libc ++ de std::inplace_merge ; esta nueva versión intercambia elementos con otra parte de la matriz original en lugar de mover elementos de la matriz auxiliar.

Como la fusión es interna , me di cuenta de que no necesitaba dos tipos de entrada por separado: InputIterator1 y InputIterator2 son siempre iguales. Luego me di cuenta de que, dado que las operaciones en first2 y first2 siempre eran las mismas, podía almacenarlas en una matriz de dos elementos y usar el resultado de la comparación para indexar la matriz para saber qué iterador intercambiar e incrementar. Con ese pequeño truco, me deshago de la rama y obtengo un algoritmo de fusión principalmente sin sucursales:

template<
    typename InputIterator,
    typename OutputIterator,
    typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator first1, InputIterator last1,
                        InputIterator first2, InputIterator last2,
                        OutputIterator result, Compare compare={})
    -> void
{
    InputIterator store[] = { first1, first2 };

    for (; store[0] != last1; ++result) {
        if (store[1] == last2) {
            std::swap_ranges(store[0], last1, result);
            return;
        }

        bool cmp = compare(*store[1], *store[0]);
        std::iter_swap(result, store[cmp]);
        ++store[cmp];
    }
    // first2 through last2 are already in the right spot
}

Ahora, la cosa es: con esta nueva función half_inplace_merge , el algoritmo de clasificación general es 1,5 veces más lento que con half_inplace_merge original, y no tengo idea de por qué. Probé varios niveles de optimización del compilador, varios trucos para evitar posibles problemas de aliasing, pero parece que el problema proviene del propio truco sin sucursales.

Entonces, ¿alguien puede explicar por qué el código sin sucursales es más lento?

Adición: para aquellos que quieran ejecutar el mismo punto de referencia que yo ... bueno, será un poco difícil: utilicé los puntos de referencia de una biblioteca personal, que incluyen muchas cosas; deberá descargar la biblioteca , agregar este archivo en alguna parte y ejecutar este benchmark después de haber agregado la línea requerida para invocar quick_merge_sort cerca de la sección resaltada (deberá redirigir la salida estándar del programa a un archivo en un subdirectorio de profiles ). Luego, deberá ejecutar este script de Python para ver los resultados y agregar quick_merge_sort a la línea resaltada. Tenga en cuenta que NumPy y matplotlib necesitan ser instalados.

Answer 1

La siguiente es solo una breve explicación intuitiva:

Si escalamos todo y suponemos que los iteradores son punteros normales, podemos en el primer ejemplo almacenar todos los iteradores en los registros.

En el código sin ramas, no podemos hacer eso fácilmente, debido a store[cmp] , y ++store[cmp] , y eso implica una sobrecarga para todos los usos de store[0] y store[1] .

Por lo tanto (en este caso) es más importante maximizar el uso de registros que evitar ramas.

Answer 2

Una gran diferencia es el producto de dos condiciones.

La primera condición está relacionada con el código original. La fusión in situ es tan eficiente que sería difícil idear algo significativamente más rápido, incluso si se codifica manualmente en el nivel de lenguaje ensamblador. La aplicación de genéricos es sencilla, por lo que el compilador ** produjo el mismo ensamblaje con o sin él. Debido a que la implementación del algoritmo es eficiente, solo unas pocas instrucciones de máquina añadidas al ciclo pueden producir el cambio proporcional significativo indicado en la pregunta.

** Los detalles de la compilación a lo largo de esta respuesta fueron usando g ++ 6.2.1 20160916, el paquete predeterminado de Fedora 24 dnf, junto con LINUX kernel 4.8.8-200.fc24.x86_64. El tiempo de ejecución fue Intel i7-2600 8M caché. También para Atmel SAM3X8E ARM Cortex-M3 con brazo-ninguno-eabi-g ++ 4.8.3-2014q1.

La segunda condición está relacionada con la compilación del segundo truco descrito en el párrafo 3 oración 2 de la pregunta. El primer truco, la reducción de tipos en la plantilla, no produjo ningún cambio significativo en el lenguaje ensamblador. El segundo truco produjo diferencias de nivel de ensamblaje que afectaban el flop en la salida del compilador para las dos llamadas.

Este truco precompilador puede facilitar las pruebas.

#ifdef ORIG
#define half_inplace_merge half_inplace_merge_orig
#else // ORIG
#define half_inplace_merge half_inplace_merge_slow
#endif // ORIG
...
half_inplace_merge(niInA.begin(), niInA.end(),
        niInB.begin(), niInB.end(),
        niOut.begin(), compare);

La ejecución y la comparación utilizando estos comandos en un shell bash explota el pirateo precompilador.

g++ -DORIG -S -fverbose-asm -o /tmp/qq.orig.s /tmp/qq.cpp
g++ -DSLOW -S -fverbose-asm -o /tmp/qq.slow.s /tmp/qq.cpp
araxis.sh /tmp/qq.orig.s /tmp/qq.slow.s  # to run Araxis Merge in Wine

Estas instrucciones son el resultado de inicializar la tienda InputIterator [], pero eso está fuera del bucle.

leaq    -48(%rbp), %rax #, _4
movq    -64(%rbp), %rdx # first1, tmp104
movq    %rdx, (%rax)    # tmp104, *_5
leaq    8(%rax), %rdx   #, _9
movq    -96(%rbp), %rax # first2, tmp105
movq    %rax, (%rdx)    # tmp105, *_9

La ralentización principal se produce al eliminar la referencia de los dos elementos contenidos en la tienda [], según lo necesiten las versiones compare y swap, y eso está dentro del ciclo. Estas instrucciones no existen en la versión sin el segundo truco.

movb    %al, -17(%rbp)  # _27, cmp
movzbl  -17(%rbp), %eax # cmp, _29
cltq
...
movzbl  -17(%rbp), %edx # cmp, _31
leaq    -48(%rbp), %rax #, tmp121
movslq  %edx, %rdx  # _31, tmp122
salq    $3, %rdx    #, tmp123
addq    %rdx, %rax  # tmp123, _32

Aunque hay una duplicación de código en los cuerpos del condicional para la versión sin el truco, eso solo afecta la compacidad del código, agregando dos llamadas, cinco movimientos y una instrucción de comparación. El número de ciclos de CPU requeridos para realizar la fusión in situ es el mismo entre las ramas resultantes de la comparación, y ambos carecen de las instrucciones enumeradas anteriormente.

Para cada una de las permutaciones de sintaxis probadas, eliminar la redundancia en las ramas para mejorar la compacidad ineludiblemente conduce a instrucciones adicionales requeridas a lo largo de la ruta de ejecución.

Los detalles de las secuencias de instrucciones para las diversas permutaciones discutidas hasta ahora variarán de compilador a compilador, selección de opciones de optimización e incluso las condiciones para llamar a las funciones.

En teoría, es posible que un compilador emplee una regla de refactorización AST (árbol de símbolos abstracto) (o su equivalente) para detectar y reducir los requisitos de memoria del programa y del ciclo de la CPU para cualquier versión de la función. Dichas reglas tienen antecedentes (patrones de búsqueda) que coinciden con el patrón que se optimizará dentro del código.

Optimizar la velocidad del código con el segundo truco requeriría un antecedente de regla que coincida con la puntuación atípica [] de la abstracción tanto dentro como fuera del bucle. Detectar la redundancia de la sucursal sin el segundo truco es un objetivo más razonable.

Integrando las dos instrucciones dentro de cada rama, uno puede ver cómo los dos patrones similares en el AST pueden ser lo suficientemente simples como para que un antecedente de regla de refactorización coincida y realice la reducción de tamaño de código deseada. Habría muy poca ganancia de velocidad para este caso, si lo hubiera.

if (compare(*first2, *first1)) {
    std::iter_swap(result, first2 ++);
} else {
    std::iter_swap(result, first1 ++);
}