Параметры GHC RTS для сбора мусора

У меня есть программа Haskell, которая обрабатывает текстовый файл и создает Map (с несколькими миллионами элементов). Все это может продолжаться 2-3 минуты. Я обнаружил, что настройка параметров -H и -A делает большую разницу в времени выполнения.

Существует документация об этой функциональности RTS, но это трудно прочитать для меня, так как я не знаю алгоритмов и терминов из Теория ГК. Я ищу менее техническое объяснение, желательно для Haskell/GHC. Есть ли ссылки на выбор разумных значений для этих параметров?

EDIT: Что код, он строит trie для данного списка слов.

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)

Ответ 1

Вообще говоря, сбор мусора - это компромисс между пространством и временем. Дайте GC больше места, и это займет меньше времени. В игре есть (многие) другие факторы, в частности кеш, но компромисс между пространством и временем является самым важным.

Компромисс работает следующим образом: программа выделяет память до тех пор, пока она не достигнет определенного предела (определяется параметрами автоматической настройки GC или явно через параметры RTS). Когда предел достигнут, GC отслеживает все данные, которые в настоящее время использует программа, и восстанавливает всю память, используемую данными, которые больше не требуются. Чем дольше вы можете задержать этот процесс, тем больше данных станет недоступным ( "мертвым" ) тем временем, поэтому GC избегает отслеживания этих данных. Единственный способ отсрочить GC - сделать больше памяти доступной для распределения; следовательно, больший объем памяти равняется меньшему количеству GC, равно более низкому потоку GC. Грубо говоря, опция GHC -H позволяет установить нижнюю границу объема памяти, используемой GC, поэтому может снизить накладные расходы GC.

GHC использует GC генерирующего поколения, который является оптимизацией базовой схемы, в которой куча делится на два или более поколений. Объекты выделяются в "молодое" поколение, а те, которые живут достаточно долго, попадают в "старое" поколение (в настройке 2 поколения). Молодое поколение собирается гораздо чаще, чем старое поколение, идея состоит в том, что "большинство объектов умирают молодыми", поэтому коллекции молодого поколения дешевы (они не тратят много данных), но они восстанавливают много памяти. Грубо говоря, опция -A устанавливает размер молодого поколения - то есть объем памяти, который будет выделен до того, как будет собрано молодое поколение.

Значение по умолчанию для -A равно 512k: рекомендуется сохранить молодое поколение меньше, чем кэш L2, и производительность, как правило, падает, если вы превысите размер кеша L2. Но работа в обратном направлении - это компромисс между пространством/временем GC: использование большого размера молодого поколения может перевесить преимущества кеша, уменьшив объем работы, которую должен выполнить GC. Это не всегда происходит, это зависит от динамики приложения, что затрудняет автоматическую настройку GC. Опция -H также увеличивает размер молодого поколения, поэтому также может отрицательно влиять на использование кеша.

Суть в том, что: поиграйте с опциями и посмотрите, что работает. Если у вас много памяти, вы можете получить повышение производительности, используя либо -A или -H, но не обязательно.

Ответ 2

Вероятно, возможно воспроизвести проблему для небольших наборов данных, где будет легче увидеть, что происходит. В частности, я предлагаю ознакомиться с профилированием:

глава раздел профилирования в руководстве GHC документирует доступные функции

Затем проверьте, соответствуют ли профили памяти вашим ожиданиям (вам не нужно знать обо всех параметрах профилирования, чтобы получить полезные графики). Сочетание строгой foldl' с нестрогим кортежем как аккумулятора будет первым, на что я бы посмотрел: если компоненты кортежа не принудительно, эта рекурсия создает неуравновешенные выражения.

Btw, вы можете создать хорошую интуицию в отношении таких вещей, пытаясь оценить ваш код вручную для действительно крошечных наборов данных. Достаточно нескольких итераций, чтобы увидеть, будут ли выражения оцениваться или оставаться неоцененными в соответствии с вашим приложением.