Главная » Хабрахабр » Учим поросёнка на моноидах верить в себя и летать

Учим поросёнка на моноидах верить в себя и летать

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

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

$*\ *\ *$

Основной целью его создания и развития была необходимость в lingua franca для выражения и тестирования идей функционального программирования. Haskell — язык своеобразный и с особенной нишей. Он разрабатывался не для повседневной разработки, не для промышленного программирования, не для широкого использования. Этим оправданы его самые яркие особенности: ленивость, предельная чистота, акцент на типы и манипуляции с ними. Но до сих пор, самым главным, широко используемым и потрясающим своими возможностями продуктом, написанным на Haskell является… компилятор ghc. То, что он, действительно, используется для создания масштабных проектов в сетевой индустрии и в обработке данных — это добрая воля разработчиков, proof of concept, если угодно. Принцип, провозглашённый Саймоном Пейтоном-Джонсоном: "Избегать успеха любой ценой", необходим языку для того, чтобы оставаться таким инструментом. И это совершенно оправданно с точки зрения его предназначения — быть инструментом для исследований в области computer science. В ней жутко неудобно работать, и для повседневной практики она слишком уж ограничивает свободу действий, но без этих неудобств, без безкомпромиссного следования ограничениям не удастся наблюдать и изучать тонкие эффекты, которые потом превратятся в основу промышленных разработок. Haskell подобен стерильной камере в лаборатории какого-либо научного центра, разрабатывающего полупроводниковые технологии или наноматериалы. Мы изучаем звёзды и галактики не потому что рассчитываем получить от них прямую пользу, а потому что в масштабах этих непрактичных объектов квантовые, релятивистские и эффекты становятся наблюдаемы и изучаемы, настолько, что потом мы можем использовать это знание для разработки чего-то очень утилитарного. При этом, в промышленности стерильность уже будет нужна лишь в самом необходимом объёме, а результаты этих экспериментов появятся в наших карманах в виде гаджетов. Однако, из этой лаборатории вышли в практический мир линзы, монады, комбинаторный парсинг, широкое использование моноидов, методы автоматического доказательства теорем, декларативные функциональные менеджеры пакетов, на подходе линейные и зависимые типы. Так и Haskell с его "неправильными" строками, непрактичной ленивостью вычислений, жёсткостью некоторых алгоритмов вывода типов, с чрезвычайно крутой кривой входа, наконец, не позволяет с лёгкостью создать шустрое приложение на коленке или операционную систему. Но ни одном из этих чудесных языков я не стал бы использовать для преподавания принципов функционального программирования: я отвёл бы ученика в лабораторию, показал на ярких и чистых примерах как это работает, а потом уже можно "на заводе" увидеть эти принципы в действии в виде большого и непонятного, но очень быстрого станка. Это находит применение в менее стерильных условиях в языках Pyton, Scala, Kotlin, F#, Rust и многих других. И в соревнованиях какой язык круче, Haskell всегда будет вне обычных номинаций. Избегание успеха любой ценой — это защита от попыток засунуть в электронный микроскоп кофеварку, с целью его популяризации.

Так, написав изящную реализацию стековой машины, основанную на моноидальной композиции, с единственной целью — увидеть, работает ли эта моя идея, я тут же огорчился, обнаружив, что реализация работает блестяще, но жутко неэффективно! Однако, человек слаб, и во мне тоже живёт демон, который подзуживает сравнивать, оценивать и защищать "мой любимый язык" перед другими. Но, чёрт побери, в статье про поросёнка с которой начался весь этот разговор приводятся такие вкусные цифры: сотни миллисекунд у поросёнка, секунды у Pyton… а мой прекрасный моноид с этой же задачей не справляется и за час! Как будто я, и правда, собираюсь использовать её для серьёзных задач, либо продавать свою стековую машину на том же рынке, где предлагают виртуальные машины Pyton или Java. Мой микроскоп будет варить эспрессо не хуже кофемашины в коридоре института! Я должен добиться успеха! Хрустальный дворец можно разогнать и запустить в космос!

Чистотой и прозрачностью архитектуры дворца? Но чем ты готов поступиться, — спрашивает меня ангел-математик? Демон и ангел оба упрямы, и мудрый даос, которого я тоже пускаю к себе пожить, предложил пойти по пути, устраивающему обоих, и идти по нему так долго, как получится. Гибкостью и расширяемостью, которую предоставляют гомоморфизмы из программ в другие решения? И так я познал суетные печаль и радость оптимизации. Однако не с целью выявить победителя, а чтобы познать сам путь, выяснить как далеко он ведёт, и получить новый опыт.

Сравнивать надо трансляторы (интерпретаторы или компиляторы), либо производительность программиста, пользующегося языком. Перед тем как начать, добавим ещё что сравнения языков по эффективности бессмысленно. Итак, мы сравниваем не Haskell и javascript, а производительность программ, выполняемых транслятором, скомпилированным ghc и программ, выполняемых, скажем, в каком-то конкретном браузере. В конце концов утверждение, что программы на C самые быстрые легко опровергнуть, написав полноценный интерпретатор C на BASIC, например. Весь код на Haskell, сопровождающий статью можно изучить в репозитории. Вся свинская терминология взялась из вдохновляющей статьи о стековых машинах.

Выходим из зоны комфорта

Коль скоро он попал во вторую статью, дадим ему имя monopig. Исходной позицией будет реализация моноидальной стековой машины в виде EDSL — маленького простого языка, который позволяет комбинируя два десятка примитивов, воздавать программы для виртуальной стековой машины. Соответственно, и он сам построен в форме моноида трансформации состояния машины. Его основой служит то обстоятельство, что языки для стековых машин образуют моноид с операцией конкатенации и пустой операцией в качестве единицы. Вся эта структура передаётся по цепочке эндоморфизмов от операции к операции, осуществляя вычислительный процесс. Состояние включает в себя стек, память в виде вектора (структуры, обеспечивающей случайный доступ к элементам), флаг аварийной остановки и моноидальный аккумулятор для накопления отладочной информации. Завершающим этапом строительства было создание моноидов трансформации в категории Клейсли, которые позволяют погрузить вычисления в произвольную монаду. Из структуры, которую образуют программы была построена изоморфная структура кодов программ, а из неё гомоморфизмы в другие полезные структуры, представляющие требования к программе по числу аргументов и памяти. С этой реализации и начнём. Так у машины появились возможности ввод-вывода и неоднозначных вычислений. Её код можно посмотреть здесь.

Процедурный код алгоритма приведём на языке javascript: Мы будем испытывать эффективность программы на наивной реализации решета Эратосфена, которая заполняет память (массив) нулями и единицами, обозначая простые числа нулём.

var memSize = 65536; var arr = [];
for (var i = 0; i < memSize; i++) arr.push(0); function sieve()
} n++; }
}

Тут исключено дурное шагание по уже заполненным ячейкам памяти. Алгоритм сразу немного оптимизирован. Вот как алгоритм переводится на monopig: Мой ангел-математик не согласился на действительно наивную версию из примера в проекте PorosenokVM, поскольку эта оптимизация стоит всего пяти инструкций стекового языка.

sieve = push 2 <> while (dup <> dup <> mul <> push memSize <> lt) (dup <> get <> branch mempty fill <> inc) <> pop fill = dup <> dup <> add <> while (dup <> push memSize <> lt) (dup <> push 1 <> swap <> put <> exch <> add) <> pop

А вот как можно записать эквивалентную реализацию этого алгоритма на идиоматичном Haskell, с использованием тех же типов, что и в monopig:

sieve' :: Int -> Vector Int -> Vector Int
sieve' k m | k*k < memSize = sieve' (k+1) $ if m ! k == 0 then fill' k (2*k) m else m | otherwise = m fill' :: Int -> Int -> Vector Int -> Vector Int
fill' k n m | n < memSize = fill' k (n+k) $ m // [(n,1)] | otherwise = m

Vector и инструменты для работы с ним, не слишком обычные для повседневной работы в Haskell. Здесь используется тип Data. k возвращает k-тый элемент вектора m, а m // [(n,1)] — устанавливает элементу с номером n значение 1. Выражение m ! Дело в том, что структуры с произвольным доступом в функциональной реализации неэффективны и по этой причине нелюбимы. Пишу это здесь, потому что мне пришлось лезть за ними в справку, притом, что я работаю в Haskell едва ли не каждый день.

А чтобы отвязаться от конкретного компьютера, давайте сравнивать скорости выполнения этих трёх программ, отнеся их к производительности программы на javascript, прогонявшейся в Chrome. По условиям соревнования, заданным в статье про поросёнка, алгоритм прогоняется 100 раз.

Мало того, что monopig тормозит безбожно, так ещё и нативная версия не многим лучше! Ужас-ужас!!! Как учат нас коучи — так дальше жить нельзя, пора выходить из зоны комфорта, которую нам предоставляет Haskell! Haskell, конечно, крут, но не настолько же, чтобы уступать программе, выполняемой в браузере?!

Преодолеваем лень

Для этого скомпилируем программу на monopig с флагом -rtsopts для ведения учёта статистики времени выполнения и посмотрим что нам стоит прогнать решето Эратосфена один раз: Давайте разбираться.

$ ghc -O -rtsopts ./Monopig4.hs
[1 of 1] Compiling Main ( Monopig4.hs, Monopig4.o )
Linking Monopig4 ... $ ./Monopig4 -RTS -sstderr "Ok" 68,243,040,608 bytes allocated in the heap 6,471,530,040 bytes copied during GC 2,950,952 bytes maximum residency (30667 sample(s)) 42,264 bytes maximum slop 15 MB total memory in use (7 MB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 99408 colls, 0 par 2.758s 2.718s 0.0000s 0.0015s Gen 1 30667 colls, 0 par 57.654s 57.777s 0.0019s 0.0133s INIT time 0.000s ( 0.000s elapsed) MUT time 29.008s ( 29.111s elapsed) GC time 60.411s ( 60.495s elapsed) <-- утечка времени здесь! EXIT time 0.000s ( 0.000s elapsed) Total time 89.423s ( 89.607s elapsed) %GC time 67.6% (67.5% elapsed) Alloc rate 2,352,591,525 bytes per MUT second Productivity 32.4% of total user, 32.4% of total elapsed

Всё остальное время по памяти бегал сборщик мусора и убирался за ленивыми вычислениями. Последняя строчка говорит нам, что программа занималась продуктивными вычислениями лишь треть времени. Здесь главная особенность Haskell оказала нам дурную услугу, пытаясь создать несколько миллиардов отложенных трансформаций вектора и стека. Сколько раз нам повторяли в детстве, что лениться нехорошо!

Поменять вычисления на строгие совсем несложно — ставим знак ! в объявлении типа стека и памяти и тем самым делаем эти поля строгими. Ангел-математик в этом месте воздымает палец и радостно рассказывает о том, что ещё со времён Алонзо Чёрча, существует теорема, утверждающая, что стратегия вычислений не влияет на их результат, а значит, мы вольны в её выборе из соображений эффективности.

data VM a = VM { stack :: !Stack , status :: Maybe String , memory :: !Memory , journal :: !a }

Ничего больше менять не будем и сразу проверим результат:

$ ./Monopig41 +RTS -sstderr "Ok" 68,244,819,008 bytes allocated in the heap 7,386,896 bytes copied during GC 528,088 bytes maximum residency (2 sample(s)) 25,248 bytes maximum slop 16 MB total memory in use (14 MB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 129923 colls, 0 par 0.666s 0.654s 0.0000s 0.0001s Gen 1 2 colls, 0 par 0.001s 0.001s 0.0006s 0.0007s INIT time 0.000s ( 0.000s elapsed) MUT time 13.029s ( 13.048s elapsed) GC time 0.667s ( 0.655s elapsed) EXIT time 0.001s ( 0.001s elapsed) Total time 13.700s ( 13.704s elapsed) %GC time 4.9% (4.8% elapsed) Alloc rate 5,238,049,412 bytes per MUT second Productivity 95.1% of total user, 95.1% of total elapsed

Общие затраты памяти всё равно остались внушительными из-за неизменяемости данных, но главное, теперь, когда мы ограничили ленивость данных, у сборщика мусора появилась возможность лениться, на его долю осталось лишь 5% всей работы. Продуктивность существенно выросла. Заносим новую запись в рейтинг.

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

Впускаем изменения в жизнь

Vector хорош, но используя его, мы тратим кучу времени на копирование, во имя сохранения чистоты вычислительного процесса. Тип Data. Vector. Заменив его на тип Data. Правильным решением было бы вывести память из состояния машины и обеспечить доступ к внешнему вектору, воспользовавшись категорией Клейсли. Unpacked мы, хотя бы экономим на упаковке структуры, но это принципиально не меняет картину. Vector. При этом наряду с чистыми векторами, можно использовать так называемые изменяемые (мутабельные) векторы Data. Mutable.

Подключим соответствующие модули и подумаем, как нам иметь дело с изменяемыми данными в чистой функциональной программе.

import Control.Monad.Primitive
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as M

Они содержатся в монадах класса PrimMonad (к ним относятся ST или IO), куда чистые программы аккуратно просовывают им инструкции к действиям, написанные кристальным функциональным языком на драгоценном пергаменте. Эти грязные типы, как полагается, изолируются от чистой публики. Не все программы для нашей машины используют память, так что обрекать на погружение в монаду IO всю архитектуру нет необходимости. Таким образом, поведение этих нечистых животных определяется строго правоверными сценариями и не представляет опасности. Наряду с чистым подмножеством языка monopig мы создадим четыре инструкции, обеспечивающие обращение к памяти и только они будут иметь доступ к опасной территории.

Тип чистой машины становится короче:

data VM a = VM { stack :: !Stack , status :: Maybe String , journal :: !a }

Кроме того, имеет смысл определить несколько типов-синонимов для упрощения сигнатур. Конструкторы программ и сами программы этого изменения почти не заметят, но поменяются их типы.

type Memory m = M.MVector (PrimState m) Int
type Logger m a = Memory m -> Code -> VM a -> m (VM a)
type Program' m a = Logger m a -> Memory m -> Program m a

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

geti :: PrimMonad m => Int -> Program' m a
geti i = programM (GETI i) $ \mem -> \s -> if (0 <= i && i < memSize) then \vm -> do x <- M.unsafeRead mem i setStack (x:s) vm else err "index out of range" puti :: PrimMonad m => Int -> Program' m a
puti i = programM (PUTI i) $ \mem -> \case (x:s) -> if (0 <= i && i < memSize) then \vm -> do M.unsafeWrite mem i x setStack s vm else err "index out of range" _ -> err "expected an element" get :: PrimMonad m => Program' m a
get = programM (GET) $ \m -> \case (i:s) -> \vm -> do x <- M.read m i setStack (x:s) vm _ -> err "expected an element" put :: PrimMonad m => Program' m a
put = programM (PUT) $ \m -> \case (i:x:s) -> \vm -> M.write m i x >> setStack s vm _ -> err "expected two elemets"

Динамически определяемые индексы для команд put и get не гарантируют безопасности и ангел-математик не разрешил в них проводить опасные обращения. Демон-оптимизатор предложил сразу ещё немного сэкономить на проверке допустимых значений индекса в памяти, ведь для команд puti и geti индексы известны на этапе создания программы и неверные значения можно отсеять заранее.

Но она очень чётко показывает изменяемым данным их место — они должны быть снаружи. Вся эта возня с выведением памяти в отдельный аргумент кажется сложной. Чистые функции знают что с ними делать, но эти объекты никогда не станут гражданами первого класса, и готовить пиццу прямо в лаборатории не стоит. Напоминаю, что мы пытаемся провести в стерильную лабораторию разносчика пиццы с пиццей.

Давайте проверим что мы купили этими изменениями:

$ ./Monopig5 +RTS -sstderr "Ok" 9,169,192,928 bytes allocated in the heap 2,006,680 bytes copied during GC 529,608 bytes maximum residency (2 sample(s)) 25,248 bytes maximum slop 2 MB total memory in use (0 MB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 17693 colls, 0 par 0.094s 0.093s 0.0000s 0.0001s Gen 1 2 colls, 0 par 0.000s 0.000s 0.0002s 0.0003s INIT time 0.000s ( 0.000s elapsed) MUT time 7.228s ( 7.232s elapsed) GC time 0.094s ( 0.093s elapsed) EXIT time 0.000s ( 0.000s elapsed) Total time 7.325s ( 7.326s elapsed) %GC time 1.3% (1.3% elapsed) Alloc rate 1,268,570,828 bytes per MUT second Productivity 98.7% of total user, 98.7% of total elapsed

В восемь раз сократилось использование памяти, в 180 раз увеличилась скорость выполнения программы, а сборщик мусора остался почти совсем без работы. Вот это уже прогресс!

mut., которое медленнее нативного решения на js в десять раз, но кроме него и нативное решение на Haskell, использующее изменяемые векторы. В рейтинге появилось решение monopig st. Вот его код:

fill' :: Int -> Int -> Memory IO -> IO (Memory IO)
fill' k n m | n > memSize-k = return m | otherwise = M.unsafeWrite m n 1 >> fill' k (n+k) m sieve' :: Int -> Memory IO -> IO (Memory IO)
sieve' k m | k*k < memSize = do x <- M.unsafeRead m k if x == 0 then fill' k (2*k) m >>= sieve' (k+1) else sieve' (k+1) m | otherwise = return m

Запускается он следующим образом

main = do m <- M.replicate memSize 0 stimes 100 (sieve' 2 m >> return ()) print "Ok"

Просто нужно его с умом использовать. И теперь Haskell наконец показывает, что он не игрушечный язык. Кстати, в приведённом коде используется то, что тип IO () образует полугруппу с операцией последовательного выполнения программ (>>), и с помощью stimes мы повторили 100 раз вычисления тестовой задачи.

Теперь понятно, отчего происходит такая нелюбовь к функциональным массивам и почему никто не помнит, как с ними работать: как только Haskell-программисту становятся всерьёз нужны структуры с произвольным доступом, он переориентируется на изменяемые данные и работает в монадах ST или IO.

Ведь мы не можем одновременно превращать код и в чистые программы и в монадические, это не разрешает делать система типов. Выведение в особую зону части команд ставит под вопрос законность изоморфизма код$\longleftrightarrow$программа. Гомоморфизм код$\longrightarrow$программа теперь разбивается на несколько гомоморфизмов для разных подмножеств языка. Однако классы типов достаточно гибки для того, чтобы этот изоморфизм существовал. Как именно это сделано, можно увидеть в полном [коде]() программы.

Не останавливайся на достигнутом

Этот способ непригоден для рекурсивных функций, но отлично подходит для базовых компонентов и функций-сеттеров. Ещё немного изменить продуктивность программы поможет исключение лишних вызовов функций и встраивание их кода непосредственно с помощью прагмы {-# INLINE #-}. Monopig51.hs). Он уменьшает время выполнения тестовой программы ещё на 25% (см.

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

program code f = programM code (const f) programM code f (Just logger) mem = Program . ([code],) . ActionM $ \vm -> case status vm of Nothing -> logger mem code =<< f mem (stack vm) vm _ -> return vm
programM code f _ mem = Program . ([code],) . ActionM $ \vm -> case status vm of Nothing -> f mem (stack vm) vm _ -> return vm

Почему это должно сработать, ведь о том есть логгирование или нет, компоненты программ узнают "в последний момент", перед самым выполнением? Теперь функции-исполнители должны явно указывать наличие или отсутствие логгирования не при помощи заглушки none, а пользуясь типом Maybe (Logger m a). Haskell — ленивый язык и тут это играет нам на руку. Разве не будет ненужный код вшит на этапе формирования композиции программ? Эта оптимизация сократила время выполнения программы ещё на 40% (см. Именно перед выполнением и формируется окончательный код, оптимизированный под конкретную задачу. Monopig52.hs).

Он уже достаточно шустро носится, чтобы и ангел и демон могли успокоиться. На этом мы завершим работу над ускорением моноидального поросёнка. Мне же хотелось обойтись минимальными изменениями и, в основном, на уровне типов. Это, конечно, не C, у нас всё ещё используется чистый список в качестве стека, но замена его на массив приведёт к основательному перелопачиванию кода, и отказу от использования элегантных шаблонов в определениях базовых команд.

Простой подсчёт числа шагов или использования стека работают неплохо (мы сделали поле журнала строгим), но их объединение в пару уже начинает кушать память, приходится возиться с пинками с помощью seq, что уже изрядно раздражает. Некоторые проблемы остаются при ведении журнала. Так что тратить своё время на ускорение ради ускорения я уже не буду. Но, скажите, кто будет логировать 14 миллиардов шагов, если отладить задачу можно на первых сотнях?

В нашем случае, моноидальная композиция компонентов программы создаёт такие трассы либо во время формирования программы из компонентов EDSL, либо при работе гомоморфизма fromCode. Осталось лишь добавить, что в статье про поросёнка, в качестве одного из методов оптимизации вычислений, приводится трассировка: выделение линейных участков кода, трасс, внутри которых вычисления можно производить минуя главный цикл диспетчеризации команд (блок switch). Этот способ оптимизации достаётся нам бесплатно, так сказать, по построению.

$*\ *\ *$

Всё это нужно для нормальной работы. В экосистеме Haskell существует много изящных и быстрых решений, таких как потоки Conduits или Pipes, есть отличные замены типу String и шустрые создатели XML, такие как blaze-html, а парсер attoparsec — это эталон комбинаторного анализа для LL(∞)-грамматик. Haskell был и остаётся исследовательским инструментом, удовлетворяющим специфическим требованиям, не нужным широкой публике. Но ещё нужнее — исследования, приводящие к этим решениям. Это можно сделать, и это классно, но не нужно. Я видел на Камчатке, как асы на вертолёте Ми-4 закрывали на спор коробок спичек, надавливая на него колесом шасси, вися в воздухе.

Но, всё-таки, это классно!!


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Перевод] Интервью с Дэвидом Гобелем

Дэвид любезно согласился дать LEAF очень интересное интервью. Дэвид Гобель – изобретатель, филантроп, футурист и ярый сторонник технологий омоложения; вместе с Обри де Греем он известен как один из основателей Methuselah Foundation и как автор концепции Longevity Escape Velocity (LEV), ...

10 долларов на хостинг: 20 лет назад и сегодня

Всё кругом дорожает, а технологии дешевеют. Когда-то компьютер или мобильный телефон могли позволить себе единицы, сейчас эти устройства есть в каждой российской семье. Цена мегабайта за последние 20 лет упала в несколько тысяч раз. Ещё один пример — хостинг. В ...