Компилятор Glasgow Haskell

Глава 5 из книги "Архитектура приложений с открытым исходным кодом", том 2.

Оригинал: The Glasgow Haskell Compiler
Авторы: Simon Marlow и Simon Peyton-Jones
Перевод: Н.Ромоданов

5.5. Система времени выполнения

Система времени выполнения (Runtime System - RTS) представляет собой библиотеку, написанную, в основном в коде на C, которая компонуется с каждой программой Haskell. С ее помощью поддерживается инфраструктура, необходимая для запуска скомпилированного кода Haskell. Поддерживаются следующие основные компоненты:

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

Ключевые проектные решения

В этом разделе мы рассмотрим два проектных решения системы RTS, которые мы рассматриваем, как особенно успешные.

Слой блоков памяти

Сборщик мусора построен поверх слоя, управляющего блоками памяти, размер которых кратен 4 Кб. Слой блоков памяти имеет очень простой интерфейс API:

typedef struct bdescr_ {
    void *               start;
    struct bdescr_ *     link;
    struct generation_ * gen;   // генерация
    // .. другие различные поля
} bdescr;

bdescr * allocGroup (int n);
void     freeGroup  (bdescr *p);
bdescr * Bdescr     (void *p);  // макро

Это единственный интерфейс API, используемый сборщиком мусора для выделения и освобождения памяти. Блоки памяти выделяются с помощью операции allocGroup и освобождаются с помощью операции freeGroup. В каждом блоке есть небольшая структура, ассоциированная с эти блоком, которая называется дескриптором блока - block descriptor (bdescr). Операция Bdescr(p) возвращает дескриптор блока, ассоциированный с произвольным адресом p; это только расчет адреса, который вычисляется исходя из значения p и компилируется в несколько арифметических инструкций и манипуляций с битами.

Сборщик мусора должен управлять несколькими различными областями памяти, например, выделяемые по разные нужды, и каждая из этих областей, возможно, должна с течением времени увеличиваться или уменьшаться. Когда области памяти представлены в виде списка связанных блоков, то в сборщике мусора GC не возникает трудностей с выделением в непрерывном адресном пространстве областей памяти различного размера.

В реализации слоя блоков памяти использовались методы, хорошо известные в интерфейсе API языка C — malloc()/free(); поддерживаются списки свободных блоков различных размеров и выполняется объединение соседних свободных областей. Тщательно разрабатывались операции freeGroup() и allocGroup() с тем, чтобы их сложность была O(1).

Одно из главных преимуществ такого проектного решения состоит в том, что для него требуется очень незначительная поддержка со стороны операционной системы, и, следовательно, оно хорошо подходит для обеспечения переносимости. В слое блоков необходимо выделять память размером, кратным 1 Мб, с выравниванием по границе 1 Мб. Хотя ни в каких из обычных ОС такая функциональная возможность не предоставляется непосредственно, она, с учетом того, что эти ОС действительно предоставляют, реализуется без особых трудностей. Преимущество в том, что компилятор GHC не зависит от конкретных особенностей организации адресного пространства, используемого ОС, и он мирно сосуществует с другими потребителями адресного пространства, такими как совместно используемые библиотеки и потоки операционной системы.

Имеются дополнительные накладные расходы, затрачиваемые слоем блоков памяти на управление цепочками блоков вместо того, чтобы пользоваться непрерывно выделенной памятью. Впрочем, мы обнаружили, что эти расходы больше, чем затраты на обеспечение гибкости и переносимости; например, в слоек блоков есть вполне определенный простой алгоритм параллельной сборки мусора, который необходимо реализовать [MHJP08].

Легковесные потоки и распараллеливание

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

Во всех операционных системах предоставляются потоки, которые работают отлично, проблема в том, что они слишком дороги. Типичная ОС справляется с обработкой тысячи потоков, тогда как мы хотим управлять миллионами потоков.

«Зеленые» потоки (green threads), иначе известные как легковесные потоки или потоки пользовательского пространства, представляют собой хорошо известную технологию, которая позволяет избежать перегрузки потоками операционной системы. Идея состоит в том, что управление потоками осуществляется с помощью самой программы или с помощью библиотеки (в нашем случае, системы RTS), а не с помощью операционной системы. Управление потоками в пространстве пользователя должно быть менее затратным, поскольку в операционной системе будет меньшее количество взаимодействий между потоками.

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

Зеленые потоки могут быть гораздо более эффективными, чем потоки ОС, так зачем кому-то использовать потоки ОС? С зелеными потоками возникают следующие три основные проблемы:

Оказывается, что все это трудно реализовывать с зелеными потоками. Тем не менее, мы упорно продолжали в компиляторе GHC заниматься зелеными потоками и нашли решения для всех трех типов проблем:

• Когда поток языка Haskell осуществляет внешний вызов, еще один поток операционной системы берет на себя выполнение остальных потоков языка Haskell [MPT04]. Для этой цели поддерживается небольшой пул потоков операционной системы, и новые потоки создаются по требованию.
• Планировщик компилятора GHC мультиплексирует большое количество легковесных потоков языка Haskell в несколько тяжеловесных потоков операционной системы; он реализует прозрачную модель потоков типа M:N. Обычно значение N выбирается равным количеству ядер процессора в машине, что позволяет добиться реального распараллеливания, но без дополнительных накладных расходов, которые есть в случае, когда полновесный поток операционной выделяется для каждого легковесного потока языка Haskell.

  Для того чтобы запустить код на языке Haskell, в потоке операционной системы должен быть подготовлена определенная среда (в оригинале статьи она называется Capability, т. е. Способность или Возможность — прим.пер.): структура данных, в которых хранятся ресурсы, необходимые для выполнения кода на языке Haskell, такие как песочница (память, где создаются новые объекты). В каждый конкретный момент каждая конкретная копия среды может храниться только в одном потоке операционной системы. Мы также называем такую среду «Контекстом выполнения языка Haskell», но в коде в настоящее время используется термин Capability.

• Мы предоставляем интерфейс API для создания граничного потока (bound thread): потока языка Haskell, который привязан к одному конкретному потоку операционной системы, так что любой внешний вызов, осуществляемый потоком языка Haskell, гарантированно будет реализовываться с помощью этого потока операционной системы.

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

При этом в реализации есть одна проблема, с которой пользователи иногда сталкиваются, в частности, в случае, когда измеряют производительность программы. Выше мы говорили, что легковесные потоки выигрывают по эффективности только при переключении контекста в «безопасных точках», местах в коде, которые компилятор определяет как безопасные, когда внутреннее состояние виртуальной машины (стек, куча, регистры и т.д. ) находятся в надлежащем порядке и когда может использоваться сборка мусора. В компиляторе GHC безопасной точкой является место, где происходит выделение памяти, что почти во всех программах Haskell происходит достаточно регулярно, так что программы выполняют не более, чем несколько десятков инструкций, не попав в безопасную точку. Тем не менее, в хорошо оптимизированном коде можно найти циклы, которые выполняют много итераций без выделения памяти. Это, как правило, часто происходит в программах оценки производительности (например, в функциях, вычисляющих факториал или числа Фибоначчи). В реальном коде такая ситуация встречается реже, хотя это также случается. Отсутствие безопасных точек не позволяет запустить планировщик, что может иметь пагубные последствия. Эту проблему можно решить, но не без ухудшения производительности таких циклов, и часто это сводится к сохранению результата каждой итерации во внутренних циклах. Возможно, это просто компромисс, с которым мы должны смириться.

---

Продолжение статьи: Разработка компилятора GHC

---

---