performance - Mejora de la implementación de treap.

optimization data-structures

Question

Aquí está mi implementación de una especie de treap (con claves implícitas y alguna información adicional almacenada en nodos): http://hpaste.org/42839/treap_with_implicit_keys

De acuerdo con los datos de perfil, GC lleva 80% de tiempo para este programa. Según tengo entendido, esto se debe al hecho de que cada vez que se "modifica" un nodo, se recrea cada nodo de la ruta a la raíz.

¿Hay algo que pueda hacer aquí para mejorar el rendimiento o tengo que descender al reino de la mónada ST?

Answer 1

Usando GHC 7.0.3, puedo reproducir tu pesado comportamiento de GC:

  $ time ./A +RTS -s
  %GC time      92.9%  (92.9% elapsed)
  ./A +RTS -s  7.24s user 0.04s system 99% cpu 7.301 total

Pasé 10 minutos recorriendo el programa. Esto es lo que hice, en orden:

• Fije la bandera de GHC -H, aumentando los límites en el GC
• Cheque desempaquetar
• Mejorar en línea
• Ajustar el área de asignación de primera generación.

Resultando en una aceleración de 10 veces, y GC alrededor del 45% del tiempo.

En orden, usando la bandera magic -H GHC, podemos reducir ese tiempo de ejecución bastante:

  $ time ./A +RTS -s -H
  %GC time      74.3%  (75.3% elapsed)
  ./A +RTS -s -H  2.34s user 0.04s system 99% cpu 2.392 total

¡No está mal!

Los pragmas UNPACK en los nodos del Tree no harán nada, así que elimínelos.

update afeita más tiempo de ejecución:

 ./A +RTS -s -H  1.84s user 0.04s system 99% cpu 1.883 total

como lo hace la height

 ./A +RTS -s -H  1.74s user 0.03s system 99% cpu 1.777 total

Entonces, aunque es rápido, GC sigue dominando, ya que estamos probando la asignación, después de todo. Una cosa que podemos hacer es aumentar el tamaño de la primera generación:

 $ time ./A +RTS -s -A200M
 %GC time      45.1%  (40.5% elapsed)
 ./A +RTS -s -A200M  0.71s user 0.16s system 99% cpu 0.872 total

Y aumentar el umbral de despliegue, como sugirió JohnL, ayuda un poco,

 ./A +RTS -s -A100M  0.74s user 0.09s system 99% cpu 0.826 total

¿Cuál es qué, 10 veces más rápido que empezamos? No está mal.

Usando ghc-gc-tune , puede ver el tiempo de ejecución como una función de -A y -H ,

Curiosamente, los mejores tiempos de ejecución utilizan valores -A muy grandes, por ejemplo

$ time ./A +RTS -A500M   
./A +RTS -A500M  0.49s user 0.28s system 99% cpu 0.776s