Есть ли в Haskell неотъемлемая «стоимость переноса» мусорных преобразователей?

Нет, лень сама по себе не приводит к большому количеству копий в GC. Однако неспособность программиста правильно управлять лень, безусловно, могла привести к этому. Например, если персистентная структура данных окажется заполненной цепочками переходников из-за ленивой модификации, то в конечном итоге она будет сильно раздута.

Еще одна важная проблема, с которой вы можете столкнуться, как упомянул Даниэль Вагнер, — это стоимость неизменности. Хотя в Haskell, безусловно, можно программировать с изменяемыми структурами, гораздо более идиоматично работать с неизменяемыми структурами, когда это возможно. Проекты неизменяемых структур имеют различные компромиссы. Например, те, которые предназначены для высокой производительности при постоянном использовании, как правило, имеют низкие коэффициенты ветвления для увеличения общего доступа, что приводит к некоторому раздуванию, когда они используются эфемерно.

тл;др: Большая часть того, что JVM делает в кадрах стека, GHC делает в куче. Если вы хотите сравнить статистику кучи/GC GHC с эквивалентом JVM, вам действительно нужно учитывать часть немного байтов/циклов, которые JVM тратит на передачу аргументов в стек или копирование возвращаемых значений между кадрами стека.

Длинная версия:

Языки, ориентированные на JVM, обычно используют стек вызовов. Каждый вызываемый метод имеет активный фрейм стека, который включает в себя хранилище для переданных ему параметров, дополнительных локальных переменных и временных результатов, а также место для «стека операндов», используемого для передачи аргументов и получения результатов от других методов, которые он вызывает.

В качестве простого примера, если код Haskell:

bar :: Int -> Int -> Int
bar a b = a * b
foo :: Int -> Int -> Int -> Int
foo x y z = let u = bar y z in x + u

были скомпилированы в JVM, байтовый код, вероятно, выглядел бы примерно так:

public static int bar(int, int);
  Code:
    stack=2, locals=2, args_size=2
       0: iload_0   // push a
       1: iload_1   // push b
       2: imul      // multiply and push result
       3: ireturn   // pop result and return it

public static int foo(int, int, int);
  Code:
    stack=2, locals=4, args_size=3
       0: iload_1   // push y
       1: iload_2   // push z
       2: invokestatic bar   // call bar, pushing result
       5: istore_3  // pop and save to "u"
       6: iload_0   // push x
       7: iload_3   // push u
       8: iadd      // add and push result
       9: ireturn   // pop result and return it

Обратите внимание, что вызовы встроенных примитивов, таких как imul, и пользовательских методов, таких как bar, включают копирование/перемещение значений параметров из локального хранилища в стек операндов (с использованием инструкций iload), а затем вызов примитива или метода. Затем возвращаемые значения необходимо сохранить/извлечь в локальное хранилище (с помощью istore) или вернуть вызывающему объекту с помощью ireturn; иногда возвращаемое значение можно оставить в стеке, чтобы оно служило операндом для вызова другого метода. Кроме того, хотя это не указано явно в байтовом коде, инструкция ireturn включает копирование из стека операндов вызываемого объекта в стек операндов вызывающего объекта. Конечно, в реальных реализациях JVM предположительно возможны различные оптимизации для уменьшения копирования.

Когда что-то еще в конце концов вызывает foo для выполнения вычисления, например:

some_caller t = foo (1+3) (2+4) t + 1

(неоптимизированный) код может выглядеть так:

       iconst_1
       iconst_3
       iadd      // put 1+3 on the stack
       iconst_2
       iconst_4
       iadd      // put 2+4 on the stack
       iload_0   // put t on the stack
       invokestatic foo
       iconst 1
       iadd
       ireturn

Опять же, подвыражения вычисляются с большим количеством операций "заталкивания" и "извлечения" в стек операндов. В конце концов, foo вызывается, его аргументы помещаются в стек, а результат извлекается для дальнейшей обработки.

Все это выделение и копирование происходит в этом стеке, поэтому в этом примере не задействовано выделение кучи.

А что произойдет, если тот же самый код скомпилировать с помощью GHC 8.6.4 (без оптимизации и для конкретности на архитектуре x86_64)? Что ж, псевдокод сгенерированной сборки выглядит примерно так:

foo [x, y, z] =
    u = new THUNK(sat_u)                   // thunk, 32 bytes on heap
    jump: (+) x u

sat_u [] =                                 // saturated closure for "bar y z"
    push UPDATE(sat_u)                     // update frame, 16 bytes on stack
    jump: bar y z

bar [a, b] =
    jump: (*) a b

Вызовы/переходы к «примитивам» (+) и (*) на самом деле сложнее, чем я их представлял, из-за задействованного класса типов. Например, переход к (+) больше похож на:

    push CONTINUATION(\f -> f x u)         // continuation, 24 bytes on stack
    jump: (+) dNumInt                      // get the right (+) from typeclass instance

Если вы включите -O2, GHC оптимизирует этот более сложный вызов, но также оптимизирует все остальное, что интересно в этом примере, так что ради аргумента давайте представим, что приведенный выше псевдокод точен.

Опять же, foo бесполезен, пока его кто-нибудь не назовет. Для приведенного выше примера some_caller часть кода, вызывающая foo, будет выглядеть примерно так:

some_caller [t] =
    ...
    foocall = new THUNK(sat_foocall)       // thunk, 24 bytes on heap
    ...

sat_foocall [] =                           // saturated closure for "foo (1+3) (2+4) t"
    ...
    v = new THUNK(sat_v)                   // thunk "1+3", 16 bytes on heap
    w = new THUNK(sat_w)                   // thunk "2+4", 16 bytes on heap
    push UPDATE(sat_foocall)               // update frame, 16 bytes on stack
    jump: foo sat_v sat_w t

sat_v [] = ...
sat_w [] = ...

Обратите внимание, что почти все это выделение и копирование происходит в куче, а не в стеке.

Теперь давайте сравним эти два подхода. На первый взгляд кажется, что виновата ленивая оценка. Мы повсюду создаем эти преобразователи, в которых не было бы необходимости, если бы оценка была строгой, верно? Но давайте посмотрим на один из этих преобразователей более внимательно. Рассмотрим преобразователь для sat_u в определении foo. Это 32 байта / 4 слова со следующим содержимым:

// THUNK(sat_u)
word 0:  ptr to sat_u info table/code
     1:  space for return value
     // variables we closed over:
     2:  ptr to "y"
     3:  ptr to "z"

Создание этого thunk принципиально не отличается от кода JVM:

       0: iload_1   // push y
       1: iload_2   // push z
       2: invokestatic bar   // call bar, pushing result
       5: istore_3  // pop and save to "u"

Вместо того, чтобы помещать y и z в стек операндов, мы загрузили их в блок памяти, размещенный в куче. Вместо того, чтобы выталкивать результат из стека операндов в локальное хранилище нашего фрейма стека и управлять фреймами стека и адресами возврата, мы оставили место для результата в санке и перед передачей управления bar поместили 16-байтовый фрейм обновления в стек.

Точно так же при вызове foo в some_caller вместо вычисления подвыражений аргументов путем помещения констант в стек и вызова примитивов для помещения результатов в стек мы создали преобразователи в куче, каждый из которых включал указатель на информационную таблицу/код. для вызова примитивов с этими аргументами и пространством для возвращаемого значения; кадр обновления заменил учет стека и копирование результатов, неявное в версии JVM.

В конечном счете, переходы и кадры обновления являются заменой GHC для передачи параметров и результатов на основе стека, локальных переменных и временного рабочего пространства. Большая часть действий, происходящих в кадрах стека JVM, происходит в куче GHC.

Теперь большая часть содержимого фреймов стека JVM и кучи GHC быстро становится мусором. Основное отличие состоит в том, что в JVM фреймы стека автоматически удаляются при возврате функции после того, как среда выполнения скопировала важные данные (например, возвращаемые значения). В GHC куча нуждается в сборке мусора. Как уже отмечали другие, среда выполнения GHC построена на идее, что подавляющее большинство объектов кучи немедленно станет мусором: для начального выделения объектов кучи используется быстрый распределитель, и вместо того, чтобы копировать важные вещи каждый раз, когда функция возвращается (что касается JVM), сборщик мусора копирует его, когда куча ударов заполняется.

Очевидно, приведенный выше игрушечный пример нелеп. В частности, все станет намного сложнее, когда мы начнем говорить о коде, который работает с объектами Java и АТД Haskell, а не с Ints. Однако это служит иллюстрацией того, что прямое сравнение использования кучи и циклов GC между GHC и JVM не имеет особого смысла. Конечно, точный учет на самом деле не представляется возможным, поскольку подходы JVM и GHC слишком фундаментально различаются, и доказательством будет реальная производительность. По крайней мере, сравнение между яблоками использования кучи GHC и статистики сборщика мусора должно учитывать некоторую часть циклов, которые JVM тратит на отправку, извлечение и копирование значений между стеками операндов. В частности, по крайней мере некоторая часть инструкций JVM return должна учитываться в «скопированных байтах» GHC.

Что касается вклада «лени» в использование кучи (и, в частности, «мусора» в куче), его сложно выделить. Преобразователи действительно играют двойную роль в качестве замены передачи операндов на основе стека и в качестве механизма отложенной оценки. Конечно, переход от лени к строгости может уменьшить количество мусора — вместо того, чтобы сначала создавать преобразователь, а затем, в конечном итоге, вычислять его для другого замыкания (например, конструктора), вы можете просто создать оцениваемое замыкание напрямую — но это просто означает, что вместо ваша простая программа, выделяющая умопомрачительные 172 гигабайта в куче, может быть, строгая версия «всего» выделяет скромные 84 гигабайта.

Насколько я вижу, конкретный вклад ленивых вычислений в «скопированные байты» должен быть минимальным — если замыкание важно во время GC, его нужно будет скопировать. Если это еще неоцененный преобразователь, он будет скопирован. Если он был оценен, нужно будет скопировать только окончательное закрытие. Во всяком случае, поскольку преобразователи для сложных структур намного меньше, чем их оцененные версии, лень обычно копирует байты уменьшать. Вместо этого обычное большое преимущество строгости заключается в том, что она позволяет определенным объектам кучи (или объектам стека) быстрее превращаться в мусор, поэтому мы не сталкиваемся с утечками пространства.