July 27th, 2015

Book

http://compilers.cs.uni-saarland.de/papers/lkh15_cgo.pdf
https://github.com/AnyDSL/impala/tree/master/src/impala

Попросил я тут ссылки на state of the art of control flow analysis of higher-order languages. Дали статью по Impala. Вот же ж люди продуктивные - на С++ компилятор пишут, и их не тошнит.

В-общем, анализировать код они никак не анализируют - CPS-ят, лямбда-лифтят (превращают свободные переменные в параметры) да скармливают LLVM, в надежде на то, что она как-то разрулит. Но LLVM, что поразительно, разруливает довольно хорошо, судя по микробенчмаркам.

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

Интересно, однако, что их IR очень похож на мой IR из HNC. Похож тем, что разрушают скоупы и восстанавливают их с помощью доминаторного анализа. Вместо моих (хупловских) меток узлов используют указатели С++, как я понял. Но суть та же - отсутствие конфликтов имён.

Также интересно, что суть "оптимизаций" та же самая - устранить лишние функции.

Но они поставили себе более трудную задачу - справиться в условиях эффектов и общей рекурсии. БОльшая часть статьи посвящена героической борьбе с рекурсией. А CPS нужен для героической борьбы с эффектами. В моём случае эти геройства неактуальны, по-крайней мере, в текущем приближении, так что прибавилось уверенности в том, что я на правильном пути.

Похоже, что при отсутствии рекурсии устранение ФВП как таковое - тривиальная задача.
Book

Автотюнинг степени параллелизма спасёт мир

Мой тезис в том, что сейчас распараллеливание как таковое - это 10-30% работы. Многие задачи вообще embarrassingly parallel. Основная работа - это тюнинг размера ворк-юнитов, степени паралеллизма, эквивалентных преобразований циклов, размера очередей, лоад балансеров, что храним в какой из памятей, что параллелим потоками, а что - векторными инструкциями, и подобных штук, под конкретный вычислительный блок/кластер.

В результате куча проблем (часть из которых рассматриваются как "нинужные", поскольку решения нет). Например, код непереносим не то что на сильно отличающиеся системы - например, при апгрейде интерконнекта приходится заново всё перетюнивать, причём не просто константы подправить. Также нельзя частично проапгрейдить кластер - в код как правило захардкожена равноценность исполнительных юнитов, и адекватный лоад балансинг гетерогенных юнитов потребует титанических усилий, "проще" (но дороже, но другого выхода _пока_ всё равно нет) выбросить старый кластер целиком, чем пытаться реюзать. Нашему кластеру уже 10 лет, и мы не можем его растить плавно, по мере появления денег, нужд и роста масштабируемости из-за переписывания кода. В клаудах так же HPC затруднён без аутотюнинга - поскольку производительность отдельных узлов и реконнектов непредсказуема и вообще плавает во времени.

Также затруднена архитектура "пайплайна", поскольку существенно усложняется лоад-балансинг. Вместо неё "проще" (опять же, _пока_ решений нет) для embarrassingly parallel делать звезду, или, если упираемся в интерконнект, звезду из звёзд. Вместе с тем, пайплайнинг в некоторых задачах (в моей) гораздо лучше в плане локальности данных и утилизации разного рода памятей и кешей.

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

ФП не так уж плохо

Моя вольная интерпретация аргументов thesz

1) Можно кооперироваться с Си для компенсации отставания, даже если оно вдруг реальное:

а) полно успешных быстрых проектов на ФЯ с сишными вставками;
б) кроме вставок, есть DSL и прочая кодогенерация Си.

2) Отставание не такое большое, как кажется на первый взгляд:

а) confirmation bias - новости о провалах ФП гораздо более популярны, чем об успехах;
б) низкая квалификация персонала - одна из причин неуспеха ФП, в том числе и в плане неспособности писать быстрый код.
Book

Легко парируемые контраргументы против медленности ФЯ в сравнении с Си

Напишу как бы каталог, чтоб не забыть. Подробный разбор каждого пункта надо будет расписать отдельно. Первоисточники:

http://nponeccop.livejournal.com/457209.html?thread=4086009#t4086009
http://nponeccop.livejournal.com/457209.html?thread=4086265#t4086265

1) сборка мусора быстрее ручного управления из-за нулевых затрат на аллокацию и амортизации затрат на деаллокацию
2) боксинг быстрее инстанцирования для реализации полиморфизма, так как меньше размер кода (в частности, меньше нагрузка на кеш инструкций и разнообразные вспомогательные кеши - блоки предсказания ветвлений и косвенных переходов и т.п.)
3) необходимость ручных деаллокаций не накладывает существенных архитектурных ограничений - в частности, в Си нет никакого особого принуждения к линейному стилю с доступом через единственный указатель
4) Наличие ФВП не затрудняет dataflow analysis и, как следствие, оптимизацию
5) Существуют схемы эффективной трансляции ФВП без дефункционализации в том или ином виде, по совокупности не уступающие сишному подходу писать без абстраций управления вообще (не считая единичных динамических диспатчей в некритичных местах)
6) Заголовки блоков памяти аллокаторов Си и Си++ по совокупности вызывают больший оверхед потребления памяти, чем боксинг, тегирование и требование значительного процента свободной памяти для эффективной работы сборщика.