Recientemente hice una pregunta sobre 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 fusionarlos con elementos de otra parte de la secuencia original, que no es No estoy 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 del 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.

Dado que la combinación es interna , me di cuenta de que en realidad no necesitaba tener dos tipos de entrada separados: InputIterator1 y InputIterator2 son siempre iguales. Luego me di cuenta de que, dado que las operaciones en first1 y first2 eran siempre 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 en su mayoría sin ramas:

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 el 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 alias, pero parece que el problema proviene del propio truco sin ramas.

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


Anexo: 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, para agregar este archivo en alguna parte y ejecutar este punto de referencia 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 profiles). Luego, deberá ejecutar este script de Python para ver los resultados, agregando quick_merge_sort a la línea resaltada. Tenga en cuenta que es necesario instalar NumPy y matplotlib.

34
Morwenn 13 dic. 2016 a las 22:53

2 respuestas

La mejor respuesta

Una diferencia tan grande es el producto de dos condiciones.

La primera condición está relacionada con el código original. La combinación en el lugar es tan eficiente que sería difícil diseñar 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 ensamblado con o sin él. Debido a que la implementación del algoritmo es eficiente, solo unas pocas instrucciones de máquina agregadas al ciclo son capaces de producir el cambio proporcional significativo indicado en la pregunta.

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

La segunda condición está relacionada con la recopilació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 afectaron al fracaso en la salida del compilador para las dos llamadas.

Este truco del 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 comparación usando estos comandos en un shell bash aprovecha el truco del 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 InputIterator store [], pero eso está fuera del ciclo.

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 principal ralentización viene al eliminar la referencia a los dos elementos contenidos en la tienda [], según sea necesario para la comparación y el intercambio, 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 duplicación de código en los cuerpos del condicional para la versión sin el truco, eso solo impacta la compacidad del código, agregando dos llamadas, cinco movimientos y una instrucción de comparación. El número de ciclos de CPU necesarios para realizar la combinación en el lugar es el mismo entre las ramas que resultan de la comparación y ambas carecen de las instrucciones enumeradas anteriormente.

Para cada una de las diversas permutaciones de sintaxis probadas, eliminar la redundancia en las ramas para mejorar la compacidad conduce inevitablemente a instrucciones adicionales necesarias 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 un compilador a otro, la 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 abstractos) (o su equivalente) para detectar y reducir tanto la memoria del programa como los requisitos de ciclo de CPU para cualquiera de las versiones de la función. Dichas reglas tienen antecedentes (patrones de búsqueda) que coinciden con el patrón a optimizar dentro del código.

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

Al integrar las dos declaraciones dentro de cada rama, se 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 en este caso, si es que hay alguna.

if (compare(*first2, *first1)) {
    std::iter_swap(result, first2 ++);
} else {
    std::iter_swap(result, first1 ++);
}
13
Douglas Daseeco 21 dic. 2016 a las 14:37

La siguiente es solo una breve explicación intuitiva:

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

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

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

3
Hans Olsson 20 dic. 2016 a las 16:52