c++ - Clasificación muy rápida de matrices de longitud fija utilizando redes de comparación

arrays sorting

Question

Tengo un código de rendimiento crítico que implica ordenar una matriz de longitud fija muy corta con entre 3 y 10 elementos en C ++ (el parámetro cambia en tiempo de compilación).

Se me ocurrió que una red de clasificación estática especializada para cada posible tamaño de entrada sería quizás una forma muy eficiente de hacerlo: hacemos todas las comparaciones necesarias para descubrir en qué caso estamos, luego hacemos el número óptimo de intercambios para clasificar la matriz

Para aplicar esto, usamos un poco de magia de plantilla para deducir la longitud de la matriz y aplicar la red correcta:

#include <iostream>
using namespace std;

template< int K >
void static_sort(const double(&array)[K])
{
    cout << "General static sort/n" << endl;
}

template<>
void static_sort<3>(const double(&array)[3])
{
    cout << "Static sort for K=3" << endl;
}


int main()
{

    double  array[3];

    // performance critical code.
    // ...
    static_sort(array);
    // ...

}

Obviamente es bastante complicado codificar todo esto, así que:

• ¿Alguien tiene alguna opinión sobre si vale la pena el esfuerzo?
• ¿Alguien sabe si esta optimización existe en cualquier implementación estándar de, por ejemplo, std :: sort?
• ¿Existe un lugar fácil para obtener el código que implementa este tipo de red de clasificación?
• Quizás sería posible generar una red de clasificación como esta usando estáticamente magia de plantilla.

Por ahora solo uso la ordenación por inserción con un parámetro de plantilla estática (como el anterior), con la esperanza de que fomente el desenrollado y otras optimizaciones en tiempo de compilación.

Tus pensamientos bienvenidos

Actualización: escribí un código de prueba para comparar una inserción ''estática'' corta y std :: sort. (Cuando digo estático, quiero decir que el tamaño de la matriz es fijo y deducible en tiempo de compilación (lo que presumiblemente permite desenrollar bucles, etc.). Obtengo al menos una mejora de NET del 20% (tenga en cuenta que la generación está incluida en el tiempo). clang, OS X 10.9.

El código está aquí https://github.com/rosshemsley/static_sorting si desea compararlo con sus implementaciones de stdlib.

Aún no he encontrado un buen conjunto de implementaciones para los clasificadores de redes de comparación.

Answer 1

Déjame compartir algunos pensamientos.

¿Alguien tiene alguna opinión sobre si vale la pena el esfuerzo?

Es imposible dar una respuesta correcta. Tienes que perfilar tu código real para descubrirlo. En mi práctica, cuando se trata de perfiles de bajo nivel, el cuello de botella no siempre estaba donde yo pensaba.

¿Alguien sabe si esta optimización existe en cualquier implementación estándar de, por ejemplo, std :: sort?

Por ejemplo, la implementación de Visual C ++ de std::sort utiliza la ordenación por inserción para vectores pequeños. No estoy al tanto de una implementación que utilice redes de clasificación óptimas.

Tal vez sería posible generar una red de clasificación como esta usando estáticamente magia de plantilla

Existen algoritmos para generar redes de clasificación, como los algoritmos de Bose-Nelson, Hibbard y Batcher. Como las plantillas C ++ son Turing-completas, puede implementarlas usando TMP. Sin embargo, no se garantiza que esos algoritmos proporcionen el número teóricamente mínimo de comparadores, por lo que es posible que desee codificar de forma rígida la red óptima.

Answer 2

Se conocen redes comparativas óptimas o al menos de mejor longitud para N <16, por lo que hay al menos un punto de partida bastante bueno. Bastante, ya que las redes óptimas no están necesariamente diseñadas para un nivel máximo de paralelismo alcanzable con, por ejemplo, SSE u otras aritméticas de vectores.

Otro punto es que algunas redes óptimas para algunos N son versiones degeneradas para una red óptima ligeramente mayor para N + 1.

De la wikipedia :

Las profundidades óptimas para hasta 10 entradas son conocidas y son respectivamente 0, 1, 3, 3, 5, 5, 6, 6, 7, 7.

Dicho esto, buscaría la implementación de redes para N = {4, 6, 8 y 10}, ya que la restricción de profundidad no puede ser simulada por un paralelismo adicional (creo). También creo que la capacidad de trabajar en registros de SSE (también usando algunas instrucciones mín / máx) o incluso algún registro relativamente grande establecido en la arquitectura RISC proporcionará una notable ventaja de rendimiento en comparación con los métodos de clasificación "bien conocidos" como el quicksort debido a ausencia de aritmética del puntero y otros gastos generales.

Además, buscaría implementar la red paralela utilizando el infame bucle que desenrollaba el dispositivo de Duff .

EDITAR Cuando se sabe que los valores de entrada son flotantes o dobles IEEE-754 positivos, también vale la pena mencionar que la comparación también se puede realizar como enteros. (float e int deben tener el mismo endianness)

Answer 3

Las otras respuestas son interesantes y bastante buenas, pero creo que puedo proporcionar algunos elementos adicionales de respuesta, punto por punto:

• ¿Vale la pena el esfuerzo? Bueno, si necesita ordenar pequeñas colecciones de enteros y las redes de clasificación están sintonizadas para aprovechar al máximo algunas instrucciones, podría valer la pena el esfuerzo. El siguiente gráfico presenta los resultados de ordenar un millón de matrices de int de tamaño 0-14 con diferentes algoritmos de clasificación. Como puede ver, las redes de clasificación pueden proporcionar una aceleración significativa si realmente la necesita.

• No hay implementación estándar de std::sort que conozco de las redes de clasificación de uso; cuando no están afinados, pueden ser más lentos que un tipo de inserción recta. El std::sort libc ++ tiene algoritmos dedicados para ordenar de 0 a 5 valores a la vez pero tampoco usa redes de clasificación. El único algoritmo de clasificación que conozco que usa redes de clasificación para ordenar algunos valores es Wikisort . Dicho esto, el trabajo de investigación Applying Sorting Networks para Synthesize Optimized Sorting Libraries sugiere que las redes de clasificación podrían usarse para ordenar arreglos pequeños o para mejorar algoritmos de clasificación recursivos como quicksort, pero solo si están ajustados para aprovechar las instrucciones de hardware específicas .

  El algoritmo de ordenación alineado por el acceso es una especie de combinación ascendente que aparentemente usa redes de clasificación bitónicas implementadas con instrucciones SIMD para la primera pasada. Aparentemente, el algoritmo podría ser más rápido que la biblioteca estándar para algunos tipos escalares.

• De hecho, puedo proporcionar esa información por la sencilla razón de que desarrollé una biblioteca de clasificación C ++ 14 que ofrece redes de clasificación eficaces de tamaño 0 a 32 que implementan las optimizaciones descritas en la sección anterior. Lo usé para generar el gráfico en la primera sección. Todavía estoy trabajando en la parte de redes de clasificación de la biblioteca para proporcionar redes de tamaño óptimo, profundidad óptima y transferencias óptimas. Las redes de clasificación óptimas pequeñas se encuentran con la fuerza bruta, mientras que las redes de clasificación más grandes usan los resultados de la literatura.

  Tenga en cuenta que ninguno de los algoritmos de clasificación en la biblioteca usa directamente redes de clasificación, pero puede adaptarlas para que se elija una red de ordenación cada vez que se le dé al algoritmo de clasificación una pequeña std::array o una pequeña matriz C de tamaño fijo:

  using namespace cppsort;
  
  // Sorters are function objects that can be
  // adapted with sorter adapters from the
  // library
  using sorter = small_array_adapter<
      std_sorter,
      sorting_network_sorter
  >;
  
  // Now you can use it as a function
  sorter sort;
  
  // Instead of a size-agnostic sorting algorithm,
  // sort will use an optimal sorting network for
  // 5 inputs since the bound of the array can be
  // deduced at compile time
  int arr[] = { 2, 4, 7, 9, 3 };
  sort(arr);

  Como se mencionó anteriormente, la biblioteca proporciona redes de clasificación eficientes para enteros integrados, pero probablemente no tenga suerte si necesita ordenar arreglos pequeños de otra cosa ( por ejemplo, mis últimos puntos de referencia muestran que no son mejores que una ordenación de inserción directa) incluso por long long int ).

• Probablemente pueda usar metaprogramación de plantillas para generar redes de clasificación de cualquier tamaño, pero ningún algoritmo conocido puede generar las mejores redes de clasificación, por lo que también podría escribir las mejores a mano. No creo que los generados por algoritmos simples en realidad puedan proporcionar redes utilizables y eficientes de todos modos (las redes de ordenamiento pares y par impar de Batcher podrían ser las únicas utilizables) [Otra respuesta parece mostrar que las redes generadas en realidad podrían funcionar] .

Answer 4

Hace poco escribí una pequeña clase que usa el algoritmo Bose-Nelson para generar una red de clasificación en tiempo de compilación.

/**
 * A Functor class to create a sort for fixed sized arrays/containers with a
 * compile time generated Bose-Nelson sorting network.
 * /tparam NumElements  The number of elements in the array or container to sort.
 * /tparam T            The element type.
 * /tparam Compare      A comparator functor class that returns true if lhs < rhs.
 */
template <unsigned NumElements, class Compare = void> class StaticSort
{
    template <class A, class C> struct Swap
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            T t = Compare()(v0, v1) ? v0 : v1; // Min
            v1 = Compare()(v0, v1) ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A> struct Swap <A, void>
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            // Explicitly code out the Min and Max to nudge the compiler
            // to generate branchless code.
            T t = v0 < v1 ? v0 : v1; // Min
            v1 = v0 < v1 ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A, class C, int I, int J, int X, int Y> struct PB
    {
        inline PB(A &a)
        {
            enum { L = X >> 1, M = (X & 1 ? Y : Y + 1) >> 1, IAddL = I + L, XSubL = X - L };
            PB<A, C, I, J, L, M> p0(a);
            PB<A, C, IAddL, J + M, XSubL, Y - M> p1(a);
            PB<A, C, IAddL, J, XSubL, M> p2(a);
        }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 1>
    {
        inline PB(A &a) { Swap<A, C> s(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 2>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J); Swap<A, C> s1(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 2, 1>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J - 1); Swap<A, C> s1(a, I, J - 1); }
    };

    template <class A, class C, int I, int M, bool Stop = false> struct PS
    {
        inline PS(A &a)
        {
            enum { L = M >> 1, IAddL = I + L, MSubL = M - L};
            PS<A, C, I, L, (L <= 1)> ps0(a);
            PS<A, C, IAddL, MSubL, (MSubL <= 1)> ps1(a);
            PB<A, C, I, IAddL, L, MSubL> pb(a);
        }
    };

    template <class A, class C, int I, int M> struct PS <A, C, I, M, true>
    {
        inline PS(A &a) {}
    };

public:
    /**
     * Sorts the array/container arr.
     * /param  arr  The array/container to be sorted.
     */
    template <class Container> inline void operator() (Container &arr) const
    {
        PS<Container, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };

    /**
     * Sorts the array arr.
     * /param  arr  The array to be sorted.
     */
    template <class T> inline void operator() (T *arr) const
    {
        PS<T*, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };
};

#include <iostream>
#include <vector>

int main(int argc, const char * argv[])
{
    enum { NumValues = 32 };

    // Arrays
    {
        int rands[NumValues];
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: /t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "/n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: /t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "/n";
    }

    std::cout << "/n";

    // STL Vector
    {
        std::vector<int> rands(NumValues);
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: /t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "/n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: /t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "/n";
    }

    return 0;
}

Puntos de referencia

Los siguientes puntos de referencia se compilan con clang -O3 y se ejecutan en mi macbook air de mediados de 2012.

Tiempo (en milisegundos) para ordenar 1 millón de matrices.
El número de milisegundos para matrices de tamaño 2, 4, 8 es 1.943, 8.655, 20.246 respectivamente.

Aquí están los relojes promedio por tipo para pequeñas matrices de 6 elementos. El código de referencia y los ejemplos se pueden encontrar en esta pregunta:
Tipo más rápido de longitud fija 6 int array

Direct call to qsort library function   : 342.26
Naive implementation (insertion sort)   : 136.76
Insertion Sort (Daniel Stutzbach)       : 101.37
Insertion Sort Unrolled                 : 110.27
Rank Order                              : 90.88
Rank Order with registers               : 90.29
Sorting Networks (Daniel Stutzbach)     : 93.66
Sorting Networks (Paul R)               : 31.54
Sorting Networks 12 with Fast Swap      : 32.06
Sorting Networks 12 reordered Swap      : 29.74
Reordered Sorting Network w/ fast swap  : 25.28
Templated Sorting Network (this class)  : 25.01 

Funciona tan rápido como el ejemplo más rápido en la pregunta para 6 elementos.

El código utilizado para los puntos de referencia se puede encontrar aquí .