performance - solidos - reciclaje

Opciones de RTS de GHC para recolección de basura

Question

Tengo un programa Haskell que procesa un archivo de texto y crea un Map (con varios millones de elementos). Todo puede funcionar durante 2-3 minutos. Descubrí que ajustar las opciones -H y -A hace una gran diferencia en el tiempo de ejecución.

Hay documentation sobre esta funcionalidad del RTS, pero es una lectura difícil para mí, ya que no conozco los algoritmos y términos de la teoría de GC. Estoy buscando una explicación menos técnica, preferiblemente específica para Haskell / GHC. ¿Hay alguna referencia sobre la elección de valores razonables para estas opciones?

EDITAR: Ese es el código, construye un trie para una lista dada de palabras.

buildTrie :: [B.ByteString] -> MyDFA 
buildTrie l = fst3 $ foldl'' step (emptyDFA, B.empty, 1) $ sort $ map B.reverse l where
    step :: (MyDFA , B.ByteString, Int) -> B.ByteString -> (MyDFA , B.ByteString, Int)
    step (dfa, lastWord, newIndex) newWord = (insertNewStates, newWord, newIndex + B.length newSuffix) where            
        (pref, lastSuffix, newSuffix) = splitPrefix lastWord newWord
        branchPoint = transStar dfa pref

        --new state labels for the newSuffix path
        newStates = [newIndex .. newIndex + B.length newSuffix - 1]
        --insert newStates
        insertNewStates = (foldl'' (flip insertTransition) dfa $ zip3 (branchPoint:init newStates) (B.unpack newSuffix) newStates)

Answer 1

En términos generales, la recolección de basura es una compensación de espacio / tiempo. Dale al GC más espacio, y tomará menos tiempo. Hay (muchos) otros factores en juego, el caché en particular, pero el intercambio de espacio / tiempo es el más importante.

La compensación funciona de la siguiente manera: el programa asigna memoria hasta que alcanza cierto límite (decidido por los parámetros de ajuste automático del GC, o explícitamente a través de opciones de RTS). Cuando se alcanza el límite, el GC rastrea todos los datos que el programa está utilizando actualmente y recupera toda la memoria utilizada por los datos que ya no se requieren. Cuanto más tiempo pueda retrasar este proceso, más datos se volverán inaccesibles ("muertos") mientras tanto, por lo que el GC evitará rastrear esos datos. La única manera de retrasar un GC es hacer que haya más memoria disponible para asignar; por lo tanto, más memoria equivale a menos GC, es decir, menos sobrecarga de GC. En términos generales, la opción -H de GHC le permite establecer un límite inferior en la cantidad de memoria utilizada por el GC, por lo que puede disminuir la sobrecarga del GC.

GHC utiliza un GC generacional , que es una optimización del esquema básico, en el que el montón se divide en dos o más generaciones. Los objetos se asignan a la generación "joven" y los que viven lo suficiente se promocionan a la generación "antigua" (en una configuración de 2 generaciones). La generación joven se recolecta con mucha más frecuencia que la generación anterior, con la idea de que "la mayoría de los objetos mueren jóvenes", por lo que las colecciones de generaciones jóvenes son baratas (no rastrean mucha información), pero recuperan mucha memoria. A grandes rasgos, la opción -A establece el tamaño de la generación joven, es decir, la cantidad de memoria que se asignará antes de que se recolecte la generación joven.

El valor predeterminado para -A es 512k: es una buena idea mantener la generación joven más pequeña que la caché L2, y el rendimiento generalmente disminuye si se excede el tamaño de la caché L2. Pero trabajar en la dirección opuesta es la compensación de espacio / tiempo de GC: usar un tamaño de generación joven muy grande podría superar los beneficios de caché al reducir la cantidad de trabajo que el GC tiene que hacer. Esto no siempre ocurre, depende de la dinámica de la aplicación, lo que dificulta que el GC se sintonice automáticamente. La opción -H también aumenta el tamaño de la generación joven, por lo que también puede tener un efecto adverso en el uso de la memoria caché.

La conclusión es: jugar con las opciones y ver qué funciona. Si tiene suficiente memoria, es posible que pueda obtener un aumento de rendimiento al usar -A o -H, pero no necesariamente.

Answer 2

Probablemente sea posible reproducir el problema para conjuntos de datos más pequeños, donde será más fácil ver lo que está sucediendo. En particular, sugiero que se familiarice con los perfiles:

• el capítulo de perfiles en el libro Real World Haskell proporciona una buena visión general, incluidos los problemas típicos que uno podría encontrar
• el capítulo de perfiles en el manual de GHC documenta la funcionalidad disponible

Luego, verifique si los perfiles de memoria que ve coinciden con sus expectativas (no necesita conocer todas las opciones de creación de perfiles para obtener gráficos útiles). La combinación de foldl'' estricta con una tupla no estricta como acumulador sería lo primero que miraría: si los componentes de la tupla no son forzados, esa recursión está acumulando expresiones no evaluadas.

Por cierto, puedes construir una buena intuición sobre tales cosas al tratar de evaluar tu código a mano para conjuntos de datos muy pequeños. Algunas iteraciones serán suficientes para ver si las expresiones se evalúan o permanecen sin evaluar de la manera que se ajuste a su aplicación.