Como no puedo agregar comentarios todavía, haré un poco más de trabajo y analizaré todos. Estoy poniendo el análisis en la parte superior; sin embargo, los datos relevantes están debajo. (Nota: todo esto se hace en 6.12.3 también - no hay magia de GHC 7 todavía.)
Análisis:
Versión 1: espectáculo es bastante bueno para enteros, especialmente aquellos tan corto como lo hemos hecho. Hacer cadenas en realidad tiende a ser decente en GHC; sin embargo, leer cadenas y escribir cadenas grandes en los archivos (o stdout, aunque no le gustaría hacer eso) es donde su código puede rastrearse completamente. Sospecho que muchos de los detalles detrás de por qué esto es tan rápido se deben a optimizaciones inteligentes dentro del show para Ints.
Versión 2: Esta fue la más lenta del grupo cuando se compiló. Algunos problemas: el reverso es estricto en su argumento. Lo que esto significa es que no se beneficia de poder realizar cálculos en la primera parte de la lista mientras está calculando los siguientes elementos; tienes que calcularlos todos, voltearlos y luego hacer tus cálculos (a saber, (`mod` 10)) en los elementos de la lista. Si bien esto puede parecer pequeño, puede conducir a un mayor uso de la memoria (tenga en cuenta los 5 GB de memoria de montón asignados aquí también) y cálculos más lentos. (Para resumir, no use el reverso.)
Versión 3: ¿Recuerda que acabo de decir que no use el reverso? Resulta que, si lo sacas, este cae a 1.79s de tiempo total de ejecución, apenas más lento que la línea de base. El único problema aquí es que a medida que profundizas en el número, estás construyendo el lomo de la lista en la dirección incorrecta (esencialmente, estás consintiendo "en" la lista con recursión, en lugar de consingrar "en" la lista).
Versión 4: Esta es una implementación muy inteligente. Se beneficia de varias cosas buenas: por un lado, Quote debería usar el algoritmo euclidiano, que es logarítmico en su argumento más amplio. (Tal vez es más rápido, pero no creo que haya nada que sea más que un factor constante más rápido que Euclid.) Además, usted está en la lista como se discutió la última vez, por lo que no tiene que resolver ningún rollo de lista como usted ir - la lista ya está completamente construida cuando vuelves a analizarla. Como puede ver, el rendimiento se beneficia de esto.
Este código fue probablemente el más lento en GHCi porque muchas de las optimizaciones realizadas con la bandera -O3 en GHC se ocupan de hacer listas más rápido, mientras que GHCi no haría nada de eso.
Lecciones: contras de la manera correcta en una lista, esté pendiente de rigurosidad intermedia que puede ralentizar los cálculos, y hacer algo de trabajo de campo en el estudio de las estadísticas de grano fino de rendimiento de su código. También compila con las banderas -O3: cuando no lo haces, todas aquellas personas que dedican muchas horas a hacer GHC súper rápido obtienen grandes ojos de cachorro para ti.
datos:
acabo de tomar todas las cuatro funciones, las puse en una .hs archivo, y luego cambiado si es necesario para reflejar la función en uso. Además, superé tu límite hasta 5e6, porque en algunos casos el código compilado se ejecutaría en menos de medio segundo en 1e6, y esto puede comenzar a causar problemas de granularidad con las medidas que estamos realizando.
Opciones del compilador: use ghc --make -O3 [nombre del archivo] .hs para que GHC haga algo de optimización. Volcaremos las estadísticas al error estándar usando dígitos + RTS -sstderr.
Dumping a -sstderr nos da salida que se parece a esto, en el caso de digits1:
digits1 +RTS -sstderr
12000000
2,885,827,628 bytes allocated in the heap
446,080 bytes copied during GC
3,224 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 5504 collections, 0 parallel, 0.06s, 0.03s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.61s ( 1.66s elapsed)
GC time 0.06s ( 0.03s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.67s ( 1.69s elapsed)
%GC time 3.7% (1.5% elapsed)
Alloc rate 1,795,998,050 bytes per MUT second
Productivity 96.3% of total user, 95.2% of total elapsed
Hay estadísticas de claves aquí:
- total de la memoria en uso: sólo 1 MB medios esta versión es muy eficiente en el uso del espacio.
- Tiempo total: 1.61s significa nada ahora, pero veremos cómo se ve en comparación con las otras implementaciones.
- Productividad: Esto es solo un 100% menos recolección de basura; ya que estamos en el 96,3%, esto significa que no estamos creando una gran cantidad de objetos que dejan tirados en la memoria ..
Muy bien, vamos a pasar a la versión 2.
digits2 +RTS -sstderr
12000000
5,512,869,824 bytes allocated in the heap
1,312,416 bytes copied during GC
3,336 bytes maximum residency (1 sample(s))
13,048 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 10515 collections, 0 parallel, 0.06s, 0.04s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 3.20s ( 3.25s elapsed)
GC time 0.06s ( 0.04s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 3.26s ( 3.29s elapsed)
%GC time 1.9% (1.2% elapsed)
Alloc rate 1,723,838,984 bytes per MUT second
Productivity 98.1% of total user, 97.1% of total elapsed
Bien, entonces estamos viendo un patrón interesante.
- La misma cantidad de memoria utilizada. Esto significa que esta es una implementación bastante buena, aunque podría significar que tenemos que probar en entradas de muestra más altas para ver si podemos encontrar una diferencia.
- Tarda el doble de tiempo. Volveremos a algunas especulaciones sobre por qué esto es más tarde.
- En realidad es un poco más productivo, pero dado que GC no es una gran parte de ninguno de los programas, esto no nos ayuda en nada importante.
Versión 3:
digits3 +RTS -sstderr
12000000
3,231,154,752 bytes allocated in the heap
832,724 bytes copied during GC
3,292 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 6163 collections, 0 parallel, 0.02s, 0.02s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 2.09s ( 2.08s elapsed)
GC time 0.02s ( 0.02s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 2.11s ( 2.10s elapsed)
%GC time 0.7% (1.0% elapsed)
Alloc rate 1,545,701,615 bytes per MUT second
Productivity 99.3% of total user, 99.3% of total elapsed
bien, así que estamos viendo algunos patrones extraños.
- Todavía estamos en 1 MB de memoria total en uso. Así que no hemos golpeado nada de memoria ineficiente, lo cual es bueno.
- No estamos exactamente en digits1, pero tenemos digits2 beat con bastante facilidad.
- Muy poco GC. (Tenga en cuenta que cualquier cosa por encima del 95% la productividad es muy buena, así que no estamos realmente se trata de algo demasiado importante en este caso.)
Y, por último, la versión 4:
digits4 +RTS -sstderr
12000000
1,347,856,636 bytes allocated in the heap
270,692 bytes copied during GC
3,180 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 2570 collections, 0 parallel, 0.00s, 0.01s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.09s ( 1.08s elapsed)
GC time 0.00s ( 0.01s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.09s ( 1.09s elapsed)
%GC time 0.0% (0.8% elapsed)
Alloc rate 1,234,293,036 bytes per MUT second
Productivity 100.0% of total user, 100.5% of total elapsed
Wowza! Vamos a descomponerlo:
- Todavía estamos en 1 MB en total. Esto es casi seguro una característica de estas implementaciones, ya que permanecen en 1 MB en las entradas de 5e5 y 5e7. Un testimonio de la pereza, si se quiere.
- Cortamos aproximadamente el 32% de nuestro tiempo original, lo cual es bastante impresionante.
- Sospecho que los porcentajes aquí reflejan la granularidad en el monitoreo de -sstderr en lugar de cualquier cálculo sobre partículas superlumínicas.
Compilar el código anterior en lugar de ejecutarlo en GHCi da resultados muy diferentes. 'digits4' es 1.8 veces más rápido que' digits' cuando se compila w/-O3. – gawi
Probablemente, el compilador optimice 'showInt', mientras que ghci no hará ninguna optimización. – fuz
compila el código con al menos -O2 (como dijo gawi), luego usa el criterio de referencia, y por amor a todo lo que es bueno, no uses 'mod', usa' rem' !!! –