Тру книжки

Добыл пару килограмм сокровенных знаний, будем вникать... :)

Читать дальше..

Хороший линк

Блог чувака по имени Zhanyong Wan' -- он был разработчиком в Visual Studio .net setup team, сейчас в гугле работает. (Неожиданно оказался еще и разработчиком FRP, для тех кто в теме :) Рекомендую, типа.

Улыбнуло: вот у него здоровый, со вкусом к C++ написанный пост, а-ля Александреску-Саттер "как грамотно получить размер массива в C++". Во, думаю, отличная иллюстрация к тезису о том что C++-разработчик играется с языком вместо того чтоб писать программы.

Ан нет -- через несколько месяцев продолжение, оказывается, грамотный метод тоже работает не всегда, и замечательное резюме:

I cannot believe it’s so difficult to get such a simple job (getting the number of array elements) done in C++.
What a broken language it is.

Очень понравилось :)

Читать дальше..

Динамическая оптимизация.

Узнал, что у замечательной компании Transmeta совсем плохи дела -- они уже от нечего делать подают в суд на Intel за нарушение патентов в линейке процессоров начиная с Pentium Pro. Акции за пять лет упали более чем в 10 раз..

Жалко -- компания очень интересная. Их технологии трансляции на лету команд x86 в систему команд процессора Transmeta Crusoe и динамической оптимизации кода в свое время на меня произвели большое впечатление -- в плане производительности интерпретируемых языков.

До того как я почитал про HP Dynamo, я смеялся над тестами в которых C# рвал C++ и думал что это невозможно в принципе. (TM наняла кучу народа, работавшего над этим проектом). Однако Dynamo впечатлило -- софтверный интерпретатор команд (виртуальная машина) для процессора PA-8000, работающий на этом же самом процессоре -- обгоняет в тестах нативный код сгенеренный мощным компилятором C++.

Вот что называется just-in-time compilng и динамическая оптимизация, которая может ускорять вещи, в принципе недоступные классическому компилятору.

В качестве примера -- оптимизация виртуальных вызовов. Классический пример -- CObject с чисто виртуальной функцией draw и унаследованные от него CPoint и CLine, реализующие эту функцию.

Как известно, в C++ для реализации этого у объекта есть указатель на vtable в которой лежат указатели на виртуальные функции. Соответственно чтоб вызвать draw() имея указатель на CObject, надо залезть в vtable по указателю, взять из vtable адрес функции и сделать переход туда (либо на CPoint::draw либо на CLine::draw).
..что довольно хреново с точки зрения процессора: он заранее не может понять, куда мы собираемся сделать переход, и поэтому не может сделать prefetch в кэш для кода. Но если мы используем JIT(компиляцию на лету, как в C#), то JIT-компилятор способен определить, что в 99% случаев реальный тип объекта один и тот же (допустим CPoint), и адрес функции практически всегда один и тот же(CPoint::draw), он сгенерит следующий код:

если (тип_объекта == CPoint)
    переход на CPoint::draw
иначе
   разруливаем дела с vtable

Соответственно вызовы CPoint::draw будут замечательно соптимизированы, процессор сможет сделать заранее прочитать начало функции из памяти¹.

Благодаря подобным штукам JIT-компилируемый код может работать быстрее нативного, ведь JIT компилятор -- по сути профайлер и компилятор в одном флаконе, и оптимизирует он именно для той платформы на которой запущено приложение.

Возвращаясь к истории с Transmeta -- у них в процессорах Crusoe подобные вещи использовались для исполнения x86-кода. Оптимизирующий интерпретатор прошит в специальной памяти (типа флэша в биосе, кажется), но реально -- он 100% софтверный. Судя по прессе, к этим вещам также имели непосредственное отношение разработчики "Эльбруса", в котором также широко используются подобные вещи. Зарулить intel по скорости не очень удалось, но зато по потреблению мощности -- чуть ли не в десятки раз, поскольку сам процессор получился намного проще, транзисторов меньше.

---

1.Реально тут есть еще много тонкостей, связанных с наличием reflection, случаев, когда мы сначала много вызываем CPoint::draw а потом много CLine::draw и пр. Интересная дискуссия на эту тему тут.

Читать дальше..

call/cc

Единственный оператор языка программирования, который вполне заслуживает звания "культового" -- это замечательный оператор call/cc, впервые появившийся в диалекте лиспа, scheme в середине 80-х годов. call/cc -- это call with current continuation. То бишь вызов функции (обычно -- лямбда-функции) с параметром, содержащим как бы контекст выполнения программы в точке вызова, который называется словом continuation. Проще показать :) Пример на ruby, где тоже есть call/cc:

def foo
for i = 1..100
    c = nil #сюда мы будем сохранять continuation
    callcc {def |x| c = x} # (**) 
                           # в фигурных скобках -
                           # лямбда-функция 
                           # сохраняет переданный 
                           # ей continuation в 
                           # переменную c
    puts i 
    return c if (i % 3) == 0 # прерываем выполнение 
                             # функции и возвращаем 
                             # continuation каждые 
                             # три итерации
end
end

Это обычная функция, печатающая числа от 1 до 100, но каждые три итерации она возвращает управление тому кто ее вызвал, а потом может продолжать работу с места где ее остановили. т.е. работает это вот так:

> t = foo()
1
2
3
> t.call # вызываем continuation, и выполнение 
         # продолжается с (**)
4
5
6
> t.call # еще разок
7
8
9

Если есть call/cc, то можно легко реализовать выходы из середины циклов, исключения, да и сами циклы. Еще стоит упомянуть про Continuation Passing Style, когда функции в качестве аргумента передается некоторый continuation в который она должна по завершении передать результат. Если функциональные языки вам не очень близки, то call/cc это суть coroutines, то бишь функции, которые возвращают значение много раз по ходу выполнения. А coroutines сейчас есть в большинстве мейнстримных языков: итераторы в C# (см. оператор yield), coroutines в lua и python. (А с точки зрения computer science оператор call/cc тесно связан с такой фундаментальной вещью как рекурсивные функции, точнее, с понятнием fixed point combinator). Линки по теме:

• Взгляд с современной такой, прикладной точки зрения (для web-приложений), must read: Crossing borders: Continuations, Web development, and Java programming
• Про call/cc вообще: A page about call/cc
• Связь call/cc и исключений Exceptions Are Strictly More Powerful Than Call/CC (осторожно: жестокая теоретическая computer science)
• Эквивалентность call/cc и fixed point combinator: Self-application as the fixpoint of call/cc (осторожно: жестокая теоретическая computer science)

Читать дальше..