Нужно было сложить 1+1 — я написал функциональный язык программирования
Needed 1+1, built a functional programming language
Студент получил задание по структурам данных: вычислить 1+1+1 с помощью бинарного дерева. Вместо простого решения он решил построить вычислитель, а затем добавил замыкания, сборщик мусора, собственный аллокатор памяти, REPL и FFI на C. В процессе он столкнулся с неожиданным расходом памяти: fib(40) требовал более 12 ГБ и падал из-за OOM. Пришлось реализовать арена-аллокатор и сборщик мусора, чтобы справиться с миллиардами узлов.
Fib(40) буквально занял 12+ ГИГАБАЙТ, прежде чем упасть из-за нехватки памяти. Почему? Потому что он порождает примерно 1,3 миллиарда узлов. При 48 байтах на узел это ~62,4 ГБ выделенной памяти под узлы.
- CodesInChaos
Десятое правило Гринспуна в программировании:
> Любая достаточно сложная программа на C или Fortran содержит ad hoc, неформально специфицированную, кишащую багами, медленную реализацию половины Common Lisp.
- tromp
> В общем, я построил движок редукции графов
Я сделал то же самое для своей производительной реализации чисто функционального языка программирования BLC/BLC2,
которая в 400+ строках содержит движок редукции графов для комбинаторной логики, в которую программы лямбда-исчисления преобразуются алгоритмом абстракции скобок Киселёва.
- heronbank
Знакомо. Потратил неделю на оптимизацию запроса, который выполняется дважды в год для отчёта, который никто не читает. Кроличья нора реальна.
- gnarlouse
Это напоминает мне десятилетия назад, когда... подожди, я всё ещё писал код года три назад.
- Joker_vD
> Дело в том, что все наши узлы указывают друг на друга внутри этого блока памяти. Когда мы делаем realloc с увеличенным размером, он может переместиться на новый адрес памяти. Полностью ломая все наши указатели и вызывая segfault! Как нам решить эту проблему?
Хранить индексы в массиве арены? Возможно, вы даже можете использовать 4-байтовые индексы и сократить использование памяти...
> Fib(40) буквально занял 12+ ГИГАБАЙТ, прежде чем сработал OOM и произошёл краш. Почему? Потому что он порождает примерно 1,3 миллиарда узлов.
Ладно, может быть, вы можете оставить 8-байтовые индексы.
> Сборщик мусора mark-and-sweep, который мы только что завершили, — это stop-the-world сборщик мусора. И алгоритм, который мы запускаем, по своей природе экспоненциален.
Как насчёт копирующего сборщика? Рекурсивный Фибоначчи генерирует много мусора, но, насколько я помню, его живой набор на самом деле довольно мал в любой отдельный момент времени. Если вам нужен бенчмарк для GC, когда ваша функция действительно имеет огромный живой набор, то что-то вроде
def garbage(n):
if n == 0:
return None
return (garbage(n-1), garbage(n-1))
должно сработать; если у вас нет подходящей структуры данных, вы можете смоделировать это с помощью замыканий довольно тривиально.
> И мы можем что-то сделать с тем, как мы вычисляем fib
Вы имеете в виду "переключиться с рекурсивного обхода AST" или "написать неэкспоненциальный Фибоначчи"?