Трубопровод трубопровода имеет странное время выполнения - PullRequest
Новая
       7

Трубопровод трубопровода имеет странное время выполнения

5 голосов
/ 06 июня 2019

Я тестирую производительность этой рекурсивной функции Haskell, которая многократно суммирует первые 100000000 целых чисел бесконечного списка (используя конвейер Conduit) и печатает истекшее время каждого выполнения: 

import Conduit
import Data.Time.Clock

evaluate_listC 0 = return ()
evaluate_listC i = do
    startTime <- getCurrentTime
    print $ runConduitPure $ yieldMany [1..] .| takeC 100000000 .| sumC
    endTime <- getCurrentTime
    print $ diffUTCTime endTime startTime
    evaluate_listC (i-1)

Компиляция (с флагом -O) и выполнение кода, и повторение функции 10 раз, я получаю следующие времена выполнения: 

38.2066878s
4.3696857s
1.3367605s
0.9950032s
0.9399968s
0.9039936s
0.9079987s
0.9119587s
0.9090151s
0.8749654s

Почему первая итерация (а также вторая) занимают больше времени, а следующие - невероятно быстрее?

1 Ответ

1 голос
/ 12 июня 2019

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

Скорее всего, список [1..] (или, возможно, какое-то более крупное выражение, включающее этот список) "поднимается" как постоянная аппликативная форма (CAF) на верхний уровень. Поскольку список генерируется во время этой первой итерации, он сохраняется как «постоянный» объект кучи для будущих итераций.

Первая итерация занимает много времени в части , потому что она выделяет и генерирует список, хотя из-за "распределителя ударов" GHC, распределение происходит очень быстро, и фактически генерация списка, вероятно, занимает всего несколько секунд. Большую часть времени, скорее всего, тратят на сбор мусора. Время GC масштабируется с размером «важного» материала, который необходимо спасти (скопировать) из распределителя бампа, и вы создаете здесь большой постоянный список.

Более поздние итерации намного быстрее, потому что они могут выполнять суммирование Conduit по существующему списку. Вероятно, это требует некоторого распределения промежуточных результатов, но большинство из них не задерживаются, поэтому GC намного меньше, и итерации бывают быстрыми.

Причина, по которой вторая и третья итерации немного медленнее, чем более поздние, связана с сборщиком мусора GHC. Первоначально и постоянный большой список, и другие полупостоянные (например, необходимые только на короткое время или для текущей итерации) объекты кучи копируются из распределителя ударов. Дальнейшая сборка мусора включает повторное копирование того же постоянного списка, в то же время позволяя собирать просроченные полупостоянные объекты. В конечном итоге список переносится в следующее поколение, а все объекты, не входящие в список, остаются в первом поколении.

После того, как постоянный список и полупостоянные «другие объекты» полностью разделены на разные поколения, список больше не нужно переписывать во время GC первого поколения, и время итерации уменьшается примерно до секунды.

...