Математика и секс
Октябрь 31st, 2013

TheSlowestLisp

В продолжение темы вываливаю еще один мой коротенький проект в открытый доступ: TheSlowestLisp.

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

Отличительные особенности реализации:

1. Целью было написать максимально краткую и простую реализацию, не обращая внимания на то «как правильно». Весь проект был написан за вечер.

2. Еще одной целью было интенсивное использование нового стандарта C++11. Он, правда, используется довольно половинчато, т.к. я писал под MSVC2010, а там многие вещи не поддерживаются (из-за этого в коде много некрасивых for; поскольку std::for_each всё равно по сути сменяется новым range-based-for, я решил не использовать именно для него STL).

3. Обозначенные причины делают мою реализацию крайне медленной.

4. Функционал очень сильно кастрирован. Реализация построена таким образом, что расширение её представляется крайне простым занятием, то есть каждый может доточить этот LISP под себя. Исключение составляют пожалуй только макросы и континуации, которые так просто тут не реализуешь (об этом чуть ниже), а так же всякие специальные символы типа ‘, ` и ,.

5. Во много это переложение Lispy на C++, хотя нельзя сказать, что всё совсем уж такое же — C++ накладывает много своих ограничений на используемый инструментарий, плюс я реализовывал некоторые вещи по-другому.

Собственно перечень доступных функций:

Арифметика: +, — (бинарный), /, *, =.

Пары: cons, car, cdr, null?.

Предопределенная константа: nil.

Выход из REPL: exit.

Специальные формы: if, define (обычный, не MIT), lambda (только одна процедура в последнем параметре, т.е. необходим begin), set!, begin.

Типы данных: целые, вещественные, пары.

Скажу пару слов о быстродействии.

Основная проблема с быстродействием связана с неэффективным внутренним типом данных, который представляет собой разновидность класса variant, только реализованную топорно руками, а внутри везде используются switch-и.

У нормального программиста на C++ сразу должен возникнуть сигнал в бошке: switch — это плохо. На самом деле в данном конкретном случае это действительно плохо, но совсем по другой причине. Дело в том, что во внутреннем union помимо примитивных типов могут лежать так же string, vector и function, а union позволяет хранить их только в виде указателей. Это приводит к излишне частому выполнению операций new и delete, которые сами по себе тяжелы.

Использование объектного полиморфизма (есть интерфейс LispData и унаследованные от него Integer, Float, List и прочие) именно по этой причине было бы в разы эффективнее: вместо указателей можно было бы хранить собственно сами объекты. Доступ до них был бы примерно таким же быстрым, но не приходилось бы постоянно выделять и деаллоцировать память под них. То есть приходилось бы всё равно, но сильно реже.

Дополнительно к этому нужно было бы конечно реализовать свои аллокаторы памяти и сборку мусора, COW-оптимизации, сделать более эффективный класс для пар (сейчас это vector из двух элементов — именно таким образом я поступил, т.к. у меня уже был тип List для синтаксического анализа и я в угоду скорости разработки не стал придумывать что-то новое).

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

Две проблемные возможности, которые реализовать не так просто, это уже упомянутые макросы и call/cc. Первые реализовать принципиально не сложно, но потребуются усилия. Это просто должен быть отдельный код, а не две строчки на функцию, просто в силу самой умности макросов в LISP.

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

На этом в общем-то всё. Опять же, может быть кому и сгодится, я сам может быть иногда буду туда еще комитить.

37 комментариев »

  1. О боже, какое говно

    Comment by cppmaster — 31.10.2013 @ 14:17
  2. @ cppmaster:
    Реализуйте до завтра с нуля так, чтобы было хорошо.

    Comment by Хеллер — 31.10.2013 @ 14:38
  3. легко: flex+bison

    Comment by cppmaster — 31.10.2013 @ 14:50
  4. @ cppmaster:
    Вперёд.

    flex+bison если что позволяют реализовать только синтаксис и лексику. У меня код этих частей в сумме занимает 83 строки, зачем тут flex и bison, особенно учитывая, что время компиляции тут вообще никак не решает?

    Comment by Хеллер — 31.10.2013 @ 14:53
  5. @ cppmaster:
    Ну хотя в принципе ссылка на bison+flex в этом контексте говорит о том, что вы мало что знаете о компиляции. Так что можно не начинать, да.

    Comment by Хеллер — 31.10.2013 @ 14:58
  6. это говорит о том, что я не смотрел дальше того, что ты называешь лексическим и синтаксическим анализатором

    Comment by cppmaster — 31.10.2013 @ 15:30
  7. @ cppmaster:
    да лан) даже заголовок как бы намекает что это не cutting edge state of the art и все такое.

    Comment by Anton — 31.10.2013 @ 17:16
  8. как раз очень похоже на современный art — наложить кучу и выставить на всеобщее обозрение

    Comment by cppmaster — 31.10.2013 @ 17:57
  9. @ cppmaster:
    Давайте тогда конкретно:
    1) Чем хуже мой лексер, нежели тот, что выдаст flex?
    2) Чем хуже мой синтаксический анализатор, нежели тот, что выдаст bison?

    Ну например расскажите мне в терминах быстродействия. С flex, сразу говорю — ответить проще. Во сколько раз лексический анализ моего парсера будет работать медленнее, чем оптимальный парсер, который строит flex? Тот же вопрос про bison (тут оценка будет лишь примерной). Оптимизации компилятора и подсчет инструкций на конкретные jmp и mov, понятное дело, не в счет.

    То есть действительно работает медленнее (о чем я пишу), но вот конкретно эти фазы — во сколько раз? Если вы не знаете ответа на этот вопрос, то вы видимо говно, которое на знает о чем говорит. (Кстати, вы «легко» уже пишите?)

    Comment by Хеллер — 31.10.2013 @ 18:45
  10. Хеллер:

    тебя троллят, а ты ведёшься

    Comment by Синий (за Русь) — 31.10.2013 @ 20:55
  11. @ Синий (за Русь):
    Ну я не то чтобы ведусь, в данном конкретном случае товарищ откровенную ахинею пишет, но заткнуть подобным вопросом его довольно легко.

    Comment by Хеллер — 31.10.2013 @ 22:19
  12. Рома, подскажи, пожалуйста.
    Сегодня в 2 часа ночью у нас по району шастала рота «мушкетёров», дружно хором, что-то орали на весь район. Разобрал только «Один за всех и все за одного». Кто это такие могли быть?

    Comment by Dima — 01.11.2013 @ 09:43
  13. @ Dima:
    Националисты либо футбольные фанаты (скорее первое, т.к. вроде вчера не было футбола). Впрочем, чаще всего это одни и те же люди — футбольные фанаты это и есть основной состав наци.

    Comment by Хеллер — 01.11.2013 @ 09:46
  14. @ Dima:
    А хотя нет, вру. Был вчера футбол, причем с погромом. Так что это футбольные фанаты. Хотя опять же, разница тут невелика — состав людей там практически один и тот же.

    Comment by Хеллер — 01.11.2013 @ 09:49
  15. @ Хеллер:
    Ну ок, допустим, синтаксис лиспа настолько прост, что нам не нужен лекс и як, конечно, если тебя не смущает ограниченность синтаксиса и не хочется сделать по-человечески. Существенного прироста это не даст.
    Но весь код — говно и сущий пиздец

    Comment by cppmaster — 01.11.2013 @ 12:49
  16. @ cppmaster:
    Ну укажи на кодстайл дефекты, ёба.

    Comment by measure_0 — 01.11.2013 @ 13:00
  17. @ cppmaster:
    :) Ответ довольно прост про быстродействие, и вы его дали не верно. Оба парсера асимптотически будут работать за линейное время, но мой лексер работает в худшем случае до семи раз медленнее, чем парсер, который сгенерит flex (в среднем можно ожидать, что в 1.5-3 раза медленнее в зависимости от деталей реализации и того что сделает компилятор). Причина довольно простая. flex генерит таблицу переходов состояний, и на каждый символ ввода производится лишь один lookup в этой таблице. Всё. У меня каждый символ проверяется несколько раз на то, что это за символ — грубо говоря switch на низком уровне развернется в последовательность if/else и на каждый символ будет проверяться не скобка ли это, не пробельный ли это символ и т.п. Таких проверок 7 штук, включая eof.

    Насчет синтаксиса LISP вы не то слово подобрали. Он не ограничен — он прост. И в этом его гениальность. Практически все идеи в современном программировании растут первоначально из LISP. Ну например исключения — впервые они появились в LISP в 1975 году и использовали они именно этот «ограниченный» синтаксис без каких-либо расширений (в C++ они появились лишь в 1993-ем). Генераторы, сопроцедуры — это тоже всё родилось в LISP-е, а в больлинстве языков этого нет до сих пор. Краткость синтаксиса LISP очень изящно сочетается с генетическим программированием (наверное 50% всех современных проектов в этой области используют его), в нем же элементарно реализуется множественный полиморфизм (мультиметоды), из него на 80% выросла библиотека <algorithm> в C++, ну и т.д. Достоинства Лиспа перечислять можно сколько угодно долго.

    У LISP есть три проблемы:
    1. Скобки. Это проблема историческая — до появления удобных редакторов, подсвечивающих нужные скобки и определения, писать на нём было трудно. (По этой же причине Python не мог бы стать популярен до 95-го года).
    2. Массово процедурное образование программистов. Въехать в функциональное программирование большинству оказывается неподъемной задачей из-за того, что на первом курсе был Pascal.
    3. Простота. Из-за этой простоты каждый может реализовать свой диалект LISP и процесс этот совершенно не поддается никакой стандартизации. В итоге моё знание Racket совершенно не помогает мне читать код на MzScheme, равно как программисту MzScheme будет не понятен код Common LISP, а последние не поймут о чем там написано в Clojure.

    Comment by Хеллер — 01.11.2013 @ 13:33
  18. Хеллер написал:

    switch на низком уровне развернется в последовательность if/else и на каждый символ будет проверяться не скобка ли это, не пробельный ли это символ и т.п.

    Щито? Собери и посмотри, во что он там «развернётся». Обычно switch-case компилируется в таблицу переходов, для чего он, собственно, и нужен. (Код не смотрел.)

    Dima написал:

    Сегодня в 2 часа ночью у нас по району шастала рота «мушкетёров», дружно хором, что-то орали на весь район. Разобрал только «Один за всех и все за одного». Кто это такие могли быть?

    Halloween?

    Comment by Anonymous — 01.11.2013 @ 18:44
  19. @ Anonymous:
    Во-первых, я изначально указал в вопросе, что компиляторные оптимизации не рассмариваем. Во-вторых, таблицы переходов именно в этом случае не получится — она используется для более-менее последовательных по значению кейсов, либо же когда их довольно много. В противном случае повышаются шансы вылезти за кеш где это излишне, что только ухудшает быстродействие. В ситуации приведенного кода умный компилятор сгенерит бинарный поиск, но опять же это уже оптимизация, которая не регламентирована языком и так компилировать никто не обязан. Поэтому договорились изначально не рассматривать оптимизированный код.

    Comment by Хеллер — 03.11.2013 @ 01:00
  20. > континуации
    Пиздец, а чем тебе слово «продолжение» не угодило?

    «Три проблемы Лиспа» из комментариев тоже выглядят как-то нелепо.
    1. В лекциях SICP 86-го года Абельсон показывает текстовый редактор с подсветкой парных скобочек (Edwin, если я не ошибаюсь), да и Емаксу как бы 37 лет (а в нём поддержка Лиспа была изначально, хоть и своего диалекта).
    2. Вообще это никак не «проблема Лиспа». Ну, есть низкосортные программисты, которые только в терминах процедур думать способны и своим образованием не занимаются, Лисп-то тут причём?
    3. У меня другой опыт — начинал, кажется, с PLT Scheme, помню, что с той поры читал и писал код на разных Лиспах (Shen, Clojure, Common Lisp) и никогда это у меня больших затруднений не вызывало, даже когда я только осваивал эти языки.

    Если что, я прекрасно понимаю, что Лисп — штука не идеальная, но вот перечисленные проблемы адекватно положение вещей не описывают.

    А вообще, ты давно функциональным программированием интересуешься? Если не ошибаюсь, видел как-то твои негативные комментарии про Хаскель.

    P.S.: И убери ты нахуй обязательность оставления email к комментарию. Ну не хочу я палить свой адрес, честное слово, заебало придумывать всякий трэш в это поле.

    Comment by Andrew — 03.11.2013 @ 04:28
  21. Хеллер написал:

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

    gcc -O0 генерит таблицу переходов для 5+ кейсов. Если начал говорить о производительности и о том, во что код скомпилируется — возьми и проверь результат напрямую.

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

    За какой кэш? У тебя там один байт проверяется, не?

    Comment by Anonymous — 03.11.2013 @ 11:20
  22. @ Andrew:
    Континуации запомнил еще давно, про то что это называется на русском языке продолжением узнал сегодня только, на русском не видел ничего достойного по функциональному программированию вообще.

    Про Хаскель я маловероятно что мог говорить что-то плохое, так как я его не знаю, хотя у меня в планах его изучение — выглядит он очень привлекательно. Вероятно, я мог лишь аппонировать недалеким людям, которые считают, что он совершит революцию и программирование никогда не станет прежним и т.д. Но тут я оппонировал не Хаскелю, а именно конкретным индивидам.

    Означенные проблемы — это проблемы с точки зрния рынка. Емакс далеко не каждый стает использовать (я не стану использовать ни его ни вим), то что 99% не понимают рекурсии проблема в том числе и лиспа — с такими условиями лисп не завоюет своей доли рынка. Разница в диалектах довольно существенная, когда речь идет о макросах или о встроенной библиотеке. Естественно, что разобраться можно, так же как я разберусь в каком-нибудь Java или C#, хотя никогда их не изучал, но это понимание будет не глубоким, код я хоть и напишу, но он будет не лучшего качества, не говоря уже о переносимости компиляторов (этот пункт я действительно хреново выразил, сейчас думаю мысль понятнее).

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

    Comment by Хеллер — 03.11.2013 @ 11:22
  23. @ Anonymous:
    Таблица переходов должна где-то храниться. Проверка символа всего одного, но на каждый переход в таблице должна быть запись. Если эти значения последовательны, то проблемы нет. Если эти значения — в значительной степени случайно выбранные из 256 возможных (плюс default), то хранить нужно намного больше данных. Это неэффективно. Я не знаю что скомпилирует gcc, я до конца праздников не имею компьютера, но даже если он генерит таблицу переходов, не факт, что ее же скомпилит другой компилятор.

    Но вообще глупый разговор. При анализе быстродействия закладываться на опитимизатор как-то странно.

    Comment by Хеллер — 03.11.2013 @ 11:35
  24. Всем привет. Может кто-нибудь посоветовать литературу по архитектуре ПК в духе просто о сложном??

    Comment by banaz — 03.11.2013 @ 18:51
  25. @ banaz:
    Computer Organization and Design by David A. Patterson and John L. Hennessy

    Comment by measure_0 — 03.11.2013 @ 19:59
  26. @ measure_0:
    Спасибо. А на нашем языке ничего приемлемого не пишется?

    Comment by banaz — 03.11.2013 @ 22:32
  27. @ banaz:
    Computer Systems. A Programmer’s Perspective, 2nd Edition (Randal E. Bryant, David R. O’Hallaron, 2010).
    На русский по-видимому переведено 1-е издание: «Компьютерные системы. Архитектура и программирование. Взгляд программиста». Но читать (любую компьютерную литературу) рекомендую в оригинале.

    @ Хеллер:
    Это не оптимизация, это реализация. Сравнивать производительность гипотетического кода на flex с выхлопом гипотетического плохого компилятора не менее странно.
    Про jump table я упомянул потому, что это ожидаемый код для конструкции switch-case. А значит и противопоставлять их друг другу ошибочно.

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

    default не влияет вообще никак. Значения у тебя не случайно выбранные и, скорее всего, в диапазоне меньшем чем 128. Посмотрел код — диапазон 31. На каждое значение — указатель. То есть таблица будет 128/256 байт и из L1 кэша не вылезет. Да и если бы вылазила, для такого кода это на производительности вряд ли бы сказалось.

    Я сомневаюсь, что между тривиальным парсером на C и его аналогом с использованием flex будет какая-то разница в производительности. Да ещё и не ясно в какую сторону, если будет.

    Но вообще согласен, разговор ни о чём.

    Comment by Anonymous — 03.11.2013 @ 22:47
  28. @ Anonymous:
    В таком случае, может изучение стоит начать с архитектуры калькулятора или принципа работы батарейки? Уж о таких вещах в Советах должны были писать

    Comment by banaz — 03.11.2013 @ 23:21
  29. @ banaz:
    Нет, не стоит.

    Comment by Anonymous — 04.11.2013 @ 00:36
  30. @ Хеллер:
    Скажи что-нибудь оценочное про Delphi, плз.

    Comment by drobnbobn — 04.11.2013 @ 03:48
  31. >> целью было интенсивное использование нового стандарта C++11.
    >> я писал под MSVC2010

    Ты так шутишь штоле?

    А вообще мне было бы интересно узнать о тебе как о программисте. Выкладывай свои фишки на гитхаб, мы тебя форкнем блеать.
    Расскажи отдельным постом (лучше с фотками) за что и где и сколько получаешь лавандоса.

    Comment by Святой Отец — 04.11.2013 @ 22:28
  32. @ Святой Отец:
    У меня не так много фишек, которые можно выложить, для меня программирование — это заработок главным образом. Мне интересны всякие темы из computer science, но в этой области сложно что-то придумать в одиночку, не обладая корпусами, временем, местом, куда приложить и т.п. Программирую только на работе и по работе.

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

    Comment by Хеллер — 05.11.2013 @ 10:56
  33. @ drobnbobn:
    Меня довольно сильно тошнит от языка Pascal еще со времен МИФИ, я не в состоянии адекватно оценивать Delphi. Ну и потом от него вообще уже давно никаких новостей не слышно — я как-то думал, что он скорее мертв, чем жив, хоть я и не интересовался. Особенно на фоне того, что языки программирования сейчас в принципе очень быстро развиваются, есть ощущение, что Delphi жесточайше устарел. Хотя не знаю точно, не интересовался.

    Comment by Хеллер — 05.11.2013 @ 11:47
  34. @ Святой Отец:
    По поводу нынешней своей работы я не особо удовлетворён, сейчас думаю куда валить, так что писать что-то не интересно.

    Comment by Хеллер — 05.11.2013 @ 11:54
  35. http://ibigdan.livejournal.com/13990157.html

    Comment by Аноним — 05.11.2013 @ 17:48
  36. @ Аноним:
    Это на самом деле копипаста старая с форумов МИФИ, на неё тут в блоге уже многократно ссылка проскакивала. Всё так, да.

    Comment by Хеллер — 05.11.2013 @ 18:40
  37. @ Хеллер:
    Я нынче фрилансю на питоне за $15/ч. На жизнь хватает, свободного времени куча.

    Comment by Святой Отец — 07.11.2013 @ 23:36

RSS feed for comments on this post. TrackBack URI

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

This work is licensed under GPL - 2009 | Powered by Wordpress using the theme aav1
SEO Powered by Platinum SEO from Techblissonline