Ответ 1
Обновление. Оптимизация, выполняемая -O0 немного отличается от того, что я впервые понял. Также добавлена заметка о регистрации новой ошибки Trac.
Я могу воспроизвести это в GHC 8.2.2. Непосредственно оценивая выражение (или используя let связывать его с переменной, а затем оценивая ее), они быстро завершаются:
Prelude> length [1..10^8]
10000000 -- pretty fast
Prelude> let len = length [1..10^8]
Prelude> len
10000000 -- pretty fast
Prelude>
Однако, используя синтаксис let -free:
Prelude> len = length [1..10^8]
Prelude> len
10000000
Prelude>
занимает больше времени и выделяет много памяти, которая не освобождается до окончания сеанса.
Обратите внимание, что это специфично для GHCi и интерактивного режима - в реальной, скомпилированной программе Haskell проблем не было. Компиляция следующего будет выполняться быстро и не потреблять избыточную память:
len = length [1..10^8]
main = print len
Чтобы понять, что происходит, вы должны понимать, что Haskell способен выполнять две потенциальные оптимизации этого кода:
- Он может явно создать ленивый список и начать вычислять его длину, но определить, что как только начало списка будет подсчитано, эти элементы больше не понадобятся, что позволяет им немедленно собирать мусор.
- Он может определить, что ни один список не должен создаваться вообще, и через процесс, известный как "слияние списков", создает скомпилированный код, который рассчитывается непосредственно от 1 до 10 ^ 8, не пытаясь поместить эти числа в какую-либо структуру данных.
Когда этот код скомпилирован с оптимизацией (-O1 или -O2), GHC выполнит оптимизацию # 2. Скомпилированная версия будет работать быстро в небольшом количестве постоянной памяти (несколько мегабайт для среды выполнения). Если вы запустите это с помощью:
$ time ./Length +RTS -s
для сбора статистики вы обнаружите, что GHC по-прежнему выделяет около 1,6 гигабайта кучи, но на самом деле это означает сохранение отдельных значений Integer при их увеличении. (Так как значения в Haskell неизменяемы, для каждого приращения должно быть назначено новое Integer.) Если вы заставляете тип Int:
len = length [(1::Int)..10^8]
то программа выделит всего несколько килобайт кучи, и вы увидите, что действительно нет списка.
Оказывается, когда этот код компилируется без оптимизации (-O0), GHC выполняет только оптимизацию # 1 (как указано в @Carl), но ей удается сделать действительно хорошую работу, настолько, что, хотя статистика GHC показывает много распределения кучи, программа по-прежнему работает довольно быстро с очень небольшим объемом памяти.
Однако, когда этот код скомпилирован в байт-код в GHCi, используется не только оптимизация # 1, но и GHC не делает достаточно хорошей работы по сбору мусора. Генерируется огромный список с несколькими гигабайтами, а начало - сбор мусора почти так же быстро, как и его создание. Использование памяти заканчивается довольно большим, но, по крайней мере, относительно постоянным.
Вы можете увидеть это, включив статистику времени/памяти:
> :set +s
> length [1..10^8]
100000000
(1.54 secs, 7,200,156,128 bytes)
>
Это означает, что этот код фактически выделяет список 7.2 гигабайт; к счастью, его можно выбросить почти так же быстро, как он сгенерирован, поэтому память, используемая процессом GHCi после этого вычисления, будет по-прежнему достаточно умеренной.
Вы увидите следующее:
> let len = length [1..10^8]
> len
а также:
> len = length [1..10^8]
> len
прожевать точно такой же огромный объем памяти (около 7,2 концерта).
Разница заключается в том, что по какой - то причине, let версия позволяет список быть мусор, как он рассчитывает, и non- let версия не делает.
В конце концов, это почти наверняка ошибка GHCi. Это может быть связано с одной из существующих ошибок утечки пространства, о которых сообщалось (например, Trac # 12848 или # 14336), или, может быть, новой. Я решил записать его как # 14789, так что, возможно, кто-то взглянет на него.