linux - como - compilar y ejecutar un programa

Uso excesivo del tiempo misterioso del sistema en un binario compilado por GHC

Question

Estoy trabajando en una exploración de delimitación automática de búsquedas basadas en restricciones. Como tal, mi punto de partida es el problema ENVIAR MÁS DINERO , con una solución basada en la selección no determinista sin reemplazo . Modifiqué el enfoque para contar el número de muestras realizadas, con el fin de medir mejor el impacto de agregar restricciones a la búsqueda.

import Control.Monad.State
import Control.Monad.Trans.List
import Control.Monad.Morph
import Data.List (foldl'')
type CS a b = StateT [a] (ListT (State Int)) b
select'' :: [a] -> [(a, [a])]
select'' [] = []
select'' (x:xs) = (x, xs) : [(y, x:ys) | ~(y, ys) <- select'' xs]
select :: CS a a
select = do
i <- lift . lift $ get
xs <- get
lift . lift . put $! i + length xs
hoist (ListT . return) (StateT select'')
runCS :: CS a b -> [a] -> ([b], Int)
runCS a xs = flip runState 0 . runListT $ evalStateT a xs
fromDigits :: [Int] -> Int
fromDigits = foldl'' (/x y -> 10 * x + y) 0
sendMoreMoney :: ([(Int, Int, Int)], Int)
sendMoreMoney = flip runCS [0..9] $ do
[s,e,n,d,m,o,r,y] <- replicateM 8 select
let send = fromDigits [s,e,n,d]
more = fromDigits [m,o,r,e]
money = fromDigits [m,o,n,e,y]
guard $ s /= 0 && m /= 0 && send + more == money
return (send, more, money)
main :: IO ()
main = print sendMoreMoney

Funciona, obtiene resultados correctos y mantiene un perfil de montón plano durante la búsqueda. Pero aun así, es lento. Es algo así como 20 veces más lento que sin contar las selecciones. Incluso eso no es terrible. Puedo vivir pagando una multa enorme para recopilar estos números de rendimiento.

Pero todavía no quiero que el rendimiento sea innecesariamente terrible, así que decidí buscar frutas de bajo rendimiento en términos de rendimiento. Y encontré algunos resultados desconcertantes cuando lo hice.

$ ghc -O2 -Wall -fforce-recomp -rtsopts statefulbacktrack.hs
[1 of 1] Compiling Main ( statefulbacktrack.hs, statefulbacktrack.o )
Linking statefulbacktrack ...
$ time ./statefulbacktrack
([(9567,1085,10652)],2606500)
real 0m6.960s
user 0m3.880s
sys 0m2.968s

Ese sistema de tiempo es completamente ridículo. El programa realiza salida una vez. ¿A dónde va todo? Mi siguiente paso fue verificar strace .

$ strace -cf ./statefulbacktrack
([(9567,1085,10652)],2606500)
% time seconds usecs/call calls errors syscall
------ ----------- ----------- --------- --------- ----------------
98.38 0.033798 1469 23 munmap
1.08 0.000370 0 21273 rt_sigprocmask
0.26 0.000090 0 10638 clock_gettime
0.21 0.000073 0 10638 getrusage
0.07 0.000023 4 6 mprotect
0.00 0.000000 0 8 read
0.00 0.000000 0 1 write
0.00 0.000000 0 144 134 open
0.00 0.000000 0 10 close
0.00 0.000000 0 1 execve
0.00 0.000000 0 9 9 access
0.00 0.000000 0 3 brk
0.00 0.000000 0 1 ioctl
0.00 0.000000 0 847 sigreturn
0.00 0.000000 0 1 uname
0.00 0.000000 0 1 select
0.00 0.000000 0 13 rt_sigaction
0.00 0.000000 0 1 getrlimit
0.00 0.000000 0 387 mmap2
0.00 0.000000 0 16 15 stat64
0.00 0.000000 0 10 fstat64
0.00 0.000000 0 1 1 futex
0.00 0.000000 0 1 set_thread_area
0.00 0.000000 0 1 set_tid_address
0.00 0.000000 0 1 timer_create
0.00 0.000000 0 2 timer_settime
0.00 0.000000 0 1 timer_delete
0.00 0.000000 0 1 set_robust_list
------ ----------- ----------- --------- --------- ----------------
100.00 0.034354 44039 159 total

Entonces ... strace me dice que solo 0.034354s se gastó en llamadas al sistema.

¿Dónde está el resto del tiempo del sistema informado por el time ?

Un punto de datos adicional: el tiempo de GC es realmente alto. ¿Hay alguna manera fácil de reducir eso?

$ ./statefulbacktrack +RTS -s
([(9567,1085,10652)],2606500)
5,541,572,660 bytes allocated in the heap
1,465,208,164 bytes copied during GC
27,317,868 bytes maximum residency (66 sample(s))
635,056 bytes maximum slop
65 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 10568 colls, 0 par 1.924s 2.658s 0.0003s 0.0081s
Gen 1 66 colls, 0 par 0.696s 2.226s 0.0337s 0.1059s
INIT time 0.000s ( 0.001s elapsed)
MUT time 1.656s ( 2.279s elapsed)
GC time 2.620s ( 4.884s elapsed)
EXIT time 0.000s ( 0.009s elapsed)
Total time 4.276s ( 7.172s elapsed)
%GC time 61.3% (68.1% elapsed)
Alloc rate 3,346,131,972 bytes per MUT second
Productivity 38.7% of total user, 23.1% of total elapsed

Información del sistema:

$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.10.1
$ uname -a
Linux debian 3.2.0-4-686-pae #1 SMP Debian 3.2.68-1+deb7u1 i686 GNU/Linux

Ejecutar una máquina virtual Debian 7 en VMWare Player 7.10 alojado en Windows 8.1.

Answer 1

Asegúrese de agregar -H128 a su línea de comandos de compilación después de

+ RTS -s

Tu evaluación se ve bien, así que eres bueno para ir allí.

Si realmente desea ir después de la lentitud en esta máquina virtual, aumente la prioridad de la secuencia en la máquina virtual (y la consola de máquina virtual ligeramente si lo desea).

Otra penalización inesperada se deberá a la confirmación de sincronización para GC (ya que se trata de SMP Debian en un sistema multinúcleo).

El GC tendrá aún más manipulación de VM para funcionar en cualquier sistema multinúcleo, lo que explica parcialmente la estadística del 61 por ciento del GC y su discrepancia de tiempo y esfuerzo. Las estadísticas no son confiables para la mayoría de las situaciones de todos modos

En realidad lo está haciendo bastante bien, especialmente si esto está en un i7 o posterior, por ejemplo.

Me sorprendería si la opción -H128 no resuelve esto.

Soy nuevo aquí, por favor avíseme si puedo ayudar más o si hay algo que necesite antes de repartir la recompensa.