Treap aplicación

Aquí está mi aplicación de un tipo de Treap (con teclas implícitas y alguna información adicional almacenada en los nodos): http://hpaste.org/42839/treap_with_implicit_keys Treap aplicación

De acuerdo con los datos de perfiles de GC toma 80% del tiempo para este programa. Por lo que yo entiendo, es causado por el hecho de que cada vez que un nodo es 'modificado', cada nodo en la ruta a la raíz es recreado.

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

Fuente

2011-01-07 adamax

@adamax: este comportamiento (recrear todo lo que hasta la raíz) es común en las estructuras inmutables, ¿ha leído Estructuras de datos puramente funcional por Chris Okasaki? http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf escribió varios artículos sobre esto. –

Quizás debas verificar esto ejecutando tu programa con '+ RTS -s -RTS' ya que no puedo ver este 80% del que hablas cuando lo ejecuté rápidamente usando 7.0.1, veo un 16% de tiempo dedicado en GC. – ScottWest

@ScottWest: lo compilo con ghc -O2 -prof --meke test.hs y lo ejecuto con ./test + RTS -s -RTS, dice% GC time 77.4% (77.4% transcurrido), el tiempo total es 8.7 segundos. Pero mi versión ghc es 6.12.1. Solo por interés, ¿cuál es el tiempo total en su sistema? – adamax

Usando GHC 7.0.3, puedo reproducir el comportamiento GC pesada:

$ 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

Me pasé 10 minutos pasar por el programa. Esto es lo que hice, en orden:

Conjunto bandera -H del GHC, el aumento de los límites de la GC
Comprobar desembalaje
Mejorar inlining
Ajuste el área de asignación de primera generación

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

en orden, usando la magia -H bandera de GHC, podemos reducir el tiempo de ejecución que un poco:

$ 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 DESEMPAQUE en los nodos Tree no harán nada, por lo tanto, quítelos.

Inlining update afeita más tiempo de ejecución:

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

al igual que inlining height

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

Así que si bien 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 primer tamaño de gen:

$ 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 aumentando el umbral de despliegue, como se sugiere johnl, ayuda un poco,

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

que es lo que, 10x más rápido que empezamos ? No está mal.

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

Time and GC

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

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

Fuente

2011-04-17 00:16:27

Guau, ¡eso es increíble! Tengo un comportamiento similar con ghc 6.12.1, la aceleración más grande viene dada por poner en línea 'update' y establecer el primer tamaño de gen. Una pregunta, ¿se olvidó de incluir la opción 'size' para -H? Simplemente -H no parece hacer nada, mientras que -H64m, por ejemplo, sí lo hace. – adamax

Con GHC 7, -H aumenta todos los límites para el GC –

Más precisamente, -H es una clase de "automático -A", aumenta la configuración -A pero sin aumentar el uso general de la memoria. Esto es posible porque estamos copiando GC, por lo que entre los principales GC hay mucha memoria sin utilizar. Aumentar -a no siempre es una buena idea- en algunos programas empeorará las cosas, debido a un mayor error en la caché. –

Respuesta

Cuestiones relacionadas