"5 centavos" para hablar sobre Sorts

Como continuación del tema , quiero compartir mi código, que supera a std::sort() de las versiones actuales de la Biblioteca GNU C ++ y (aproximadamente, no hay datos exactos) repite el resultado de "Ordenar Alexandrescu" con CppCon 2019 .

Condiciones de la tarea

En el código (no C++ ), se requirió un esfuerzo razonable para que la ordenación no fuera peor que std::sort() para deshacerse de la sobrecarga de usar la biblioteca qsort() . Incluyendo, por lo tanto, use macros en lugar de plantillas.
A su vez, si clasifica "ratones" en lugar de "elefantes", el costo de qsort() bastante grande: aritmética de direcciones adicionales y una llamada indirecta a la función de comparación.

Resultado

Según la información disponible, esta combinación de algoritmos y características de implementación es más rápida que muchas otras opciones en un sentido práctico:

• por el número de comparaciones y movimientos (medidos mediante la sustitución de la clase C++ para contar comparaciones y tareas).
• por el volumen de código de máquina (ocupa poco espacio en el caché).
• por el volumen del código fuente y su transparencia.
• en secuencias aleatorias largas, la ganancia tiende a 3-5%, dependiendo de SORT_THRESHOLD .
• hasta 1.5-2-3 veces más rápido con datos ordenados o predominantemente ordenados.
• una ligera pérdida solo en secuencias muy cortas en orden inverso.

Es muy probable que esta opción sea un poco más rápida y / o un poco más lenta que la gran mayoría de los tipos, pero descubrir esto es literalmente un trabajo titánico que no puedo permitirme.

Es interesante si alguien compara esta opción con las opciones actuales en Tarantool, PostgreSQL, SQLite y MySQL. Espero que Kaamos no pueda pasar con su SysBench .

¿Cómo está Alexandrescu?

En el primer comentario de RPG18, había un enlace a una actuación reciente de Andrei Alexandrescu "La velocidad se encuentra en la mente de las personas" , donde conduce a una idea bastante similar, pero se dirige a la pila más cerca de la final.

El rendimiento me pareció un poco prolongado (si la olegbunina hubiera dado 90 minutos al menos una vez ...), pero los números no son suficientes. En particular, quiero ver el comportamiento de clasificación con el aumento de N , ya que un aumento en el umbral de finalización de QuickSort conduce a una aceleración en tamaños grandes y una desaceleración a tamaños pequeños, etc.

Sin embargo, a juzgar por las cifras que cita Alexandrescu, la opción descrita de repente da una aceleración similar. Sin embargo, hasta que encontré el código que se muestra a Alexandrescu en su forma final, para "tomar y comparar", y no hay tiempo para codificar por video (escriba si lo encuentra o lo hace).

Lado ideológico

El lado teórico e ideológico del "algoritmo" es bastante simple:

1. Para secuencias no cortas, utilizamos QuickSort con todas las optimizaciones aceptables:
   
   • No utilizar recursivamente la pila interna de posiciones en punteros.
   • Como elemento de apoyo, utilizamos la mediana del primer, medio y último elemento.
   • No clasificamos porciones pequeñas, lo dejamos para ShellSort.
   • Después de dividir, siempre colocamos la parte más grande en la pila; como resultado, la pila no puede ser más profunda que Log2(N) .
2. Agregar-ordenar datos usando ShellSort:
   
   • Número mínimo de pases.
   • el paso en la primera pasada está correlacionado con el tamaño máximo del segmento sin clasificar.
   • totalice solo dos pases con los pasos 8 e (inevitablemente) 1.
3. El uso de ShellSort le permite aumentar de manera relativamente segura el umbral de salida para QuckSort. Como resultado, tenemos una combinación de una de las mejores opciones de QuickSort con ahorros debido a una salida anterior y una clasificación previa un poco más rápida.

Cabe señalar que, dependiendo de la arquitectura del procesador y las condiciones de la aplicación, puede aumentar la ganancia en secuencias largas hasta un 10-15% al ​​elegir SORT_THRESHOLD dentro de 128-256. Sin embargo, esto ralentiza el procesamiento de secuencias con el orden inverso y cerca de él.
Sin embargo, este es un buen bono si comprende que el orden inverso es poco probable en sus datos, o si puede detectar de manera económica tales casos y ejecutar una bifurcación con un pequeño SORT_THRESHOLD .

PS
La opción de clasificación descrita fue "rehecha" para mi proyecto libmdbx (base de datos de valores clave incrustados rápidamente con ACID), en la que el otro día se actualizaron las descripciones README y API (en realidad reescritas). Por lo tanto, agradeceré tanto la corrección de errores tipográficos como los consejos y sugerencias. Él mismo, por regla general, no es visible falta de alguna información.