- @jorpic: *haskell *jobВ жежешечке обосрали вакансию, запощу здесь ещё: ru-declarative.livejournal.com Да, денег мало. 30 часов — перебор, согласен. Но совсем бездельники не нужны. Пусть будет 20.5 months ago; 20 replies
- @jorpic:Я в Москву вернулся, а тут, оказывается, в эти выходные hackday будет. Хочу сходить, посмотреть на людей.
Только что зафайлил проект (js in jail в самом конце hackday.ru
Идея в формальной верификации жаваскрипта на соответствие спецификации. Жаваскрипт совсем не тривиальная штука, да и формальные методы для динамических языков я как-то не встречал. Если к этому прибавить что я даже в теории плохо представляю как это делается, получается что эпик фейл гарантирован.
Вобщем, если кому-то вдруг интересно — присоединяйтесь.
Можно заранее встретиться, я расскажу то немногое что знаю про why, separation logic и shape analysis (правда не уверен, что до этого дело дойдёт).
Там пишут что нужно технологии M$ использовать, у нас будет GHC и Z3 smt solver.
Btw, там ещё какие-то чуваки проект на хаскеле и эрланге делают.7 months ago - @jorpic:в копилку RWH: всю прошлую неделю торчал в конторе, готовили к сертификации устройство, в котором хаскель отправляет через спутник координаты и показания датчиков. скоро будет ездить по сибири в технических поездах и карьерных самосвалах.7 months ago; 32 replies
- @jorpic:Отсутствие интернета — великая штука. Я прочитал "Маятник Фуко", "Уллиса" и по паре книжек Пиаже и Выготского.
Это при том, что за пару прошедших лет я прочёл не более десятка нетехнических книжек.
Маятник и Уллис — наикрутейшие книжки. Обе довольно толстые и читать их нужно быстро, чтобы полностью погрузиться.
Уверен, если прочитаю Маятник ещё раз — обязательно сойду с ума и превращусь в одного из его героев. - @jorpic:Узнал про новые утилиты:
mtr — заменитель traceroute (собирает больше статистики, можно запросто понять, что какой-то маршрутизатор перегружен)
ip — заменитель ifconfig
Это я перебираю ведро брусники и чтобы не скучать смотрю лекции яндекса: video.yandex.ru
Ещё недавно сталь пользовать tig — это такая консольная обётрка над git'ом. Для просмотра истории и каких-то простых операций довольно удобно получается. - @jorpic:Есть такая забавная штука, называется Inverse Symbolic Calcualtor (isc.carma.newcastle.edu.au).
Ещё по почте товарищ прислал красивую картинку wolframalpha.com
Кто знает, почему так получается?9 months ago; 14 replies - @jorpic: *загадкаЕсть алфавит из двух символов и скобок A={a,b,(,)}.
Над этим алфавитом есть язык, в котором все скобки парные.
Вопрос 1. Как перенумеровать все слова этого языка? Чтобы по заданному n быстро получить соответствующее слово (без перебора предыдущих слов).
Вопрос 2. Как перенумеровать все слова заданной длины?
Вопрос 3. Кажется есть какой-то томик кнута про перечисление деревьев, имеет смысл в нём искать ответы? - @jorpic: *jitЕщё одна отвлечённая мысль. Считается, что whole-program optimization делает возможными какие-то нелокальные преобразования и это очень хорошо. С другой стороны, та же самая trace-based компиляция (или проход вверх по стеку, как в #1478860) это и есть те самые глобальные оптимизации, не доступные обычному не whole-program компилятору.9 months ago
- @jorpic: *jitВ больших программах на C++ в пять раз больше вызовов функций, чем в программах на C.
Средний размер виртуальных функций в C++ всего 30 инструкций — в 6 раз меньше чем средняя функция на C.
Т.е. выгода от правильно заинлайненых методов может быть значительной.
В функциональных языках, думаю, функции ещё меньше. Но, в случае, например, хаскеля, само понятние вызова размазано во времени и пространстве. - @jorpic: *jitЕщё про adaptive recompilation.
В динамической компиляции есть два важных вопроса:
— when: как долго ждать пока соберётся достаточно статистики о выполнении программы;
— what: какой код больше выиграет от компиляции.
Про when я уже слегка упоминал в самом начале: у каждого метода есть счётчик вызовов и когда он достигает какого-то предела, принимается решение, есть ли смысл этот метод оптимизировать. Можно придумать более интересные эвристики, но как оказалось, важнее правильно определять что оптимизировать. Поэтому простые и быстрые счётчики лучше хитрых.
Например, если переполняется счётчик метода возвращающего константу, то, очевидно, что такой метод нисколько не выиграет от оптимизации, зато если заинлайнить его в вызывающем методе, то будет польза. Т.е. нужно пройтись вверх по стеку (чаще всего на один-два вызова).
В общем случае, лучше оптимизировать маленькие методы (меньше затрат на компиляцию), с замыканиями (которые можно заинлайнить) и содержащие вызовы других маленьких методов (которых тоже заинлайнить можно).
Поэтому, в заголовке каждого метода хранится дополнительная информация:
— size: размер метода в инструкциях
— count: сколько раз вызывался
— sends: сколько в нём вызовов других методов
— version: сколько раз метод уже компилировался (если много, то видимо, выгоды от ещё одной перекомпиляции будет не много).9 months ago - @jorpic:С первого августа я поменял половину зарплаты на возможность работать меньше и удалённо.
Сижу сейчас в Балабаново (где делают спички и нет интернета) и бездельничаю.
У меня жена не работает, ребёнок и кредит. А получать я буду чуть больше чем среднюю зарплату по Москве.
Чего и вам желаю.9 months ago; 19 replies - @jorpic: *jitdynamically dispatched calls это один из(??) способов сделать инкапсуляцию и полиморфизм. К сожалению, даже без позднего связывания dynamic dispatch довольно накладная операция (как минимум сброс кэша инструкций и конвейера).
Пусть у нас есть два класса:
class CartesianPoint:
def getX (self): return self._x
class PolarPoint:
def getX (self): return self._rho * cos (self._theta)
...
x = p.getX () # вызов метода где-то в программе
...
Собрав во время выполнения программы статистику о том, какая из реализаций метода getX чаще всего вызывается в данной строчке, можно перекомпилировать кусок кода и заинлайнить этот метод в место вызова.
Например, вместо p.getX() будет:
...
if p.__class == CartesianPoint:
x = p._x
else:
x = p.getX()
...
Получается adaptive recompilation.
Если в polymorphic inline cache добавить счётчик вызовов для каждого из методов, то у компилятора будет вся необходимая информация, чтобы проделать такой трюк. Собственно это и есть type feedback.
Btw, это один из тех случаев, когда динамический компилятор генерит более эффективный код чем статический.9 months ago - @jorpic: *jitИтак, 95% вызовов мономорфны, однако оставшиеся 5% могут давать значительный вклад в производительность программы.
Например, если в списке лежат объекты разных типов, и мы в цикле для каждого объекта вызываем какой-то метод:
foreach w in widgets: w.draw ()
В этом случае inline cache малоэффективен. Сплошные промахи будут: в начале каждого метода стоит проверка, что тип объекта для которого он вызван действительно такой как ожидается. Если это не так, происходит поиск нужного метода (через lookup) и ссылка на него подставляется в место вызова.
Urs Hölzle решил, что для по-настоящему полиморфных вызовов было бы неплохо кэшировать сразу несколько ссылок на методы, для этого придумал после первого промаха подставлять в место вызова ссылку на специальный кусок кода polymorphic inline cache. Т.е. как-то так:
...
% push args
push obj
call pic_123
...
pic_123:
switch (obj.type) {
case Window: jump to draw_window
case Button: jump to draw_button
default:
method_ref = lookup (method_name)
update_pic (obj.type, method_name)
jump to method_ref
}
Если при следующем вызове окажется, что obj это не Window и не Button, то в switch добавится новый кейс.
Размер кэша ограничен десятком записей.
Прирост производительности типичной программы от PIC в пределах 5-10%. Не так много, но, в качестве побочного эффекта, PIC предоставляет компилятору type feedback, правильное использование которого вроде как ещё десяток процентов добавляет.9 months ago - @jorpic: *haskellсходил на лекцию Хоара в Политехнический музей. На какой-то вопрос про функциональные языки он ответил, что это интересно, но он не испытывает такого же энтузиазма, как люди, которые "продают" ФП. В качестве аргумента сказал, что любой ФЯ содержит в себе процедурный кусок, например, монады. Ещё он сказал, что в последнее время больше занимается философией, чем CS. Так что фейл с монадами ему можно простить.10 months ago; 25 replies
- @jorpic: *jitпродолжаю читать что пишет Urs Hölzle.
Всякие петоны [имхо] популярны, в числе прочего, из-за позднего связывания (late binding).
Идея в том, что узнать какие у объекта есть методы (и где они реализованы) мы можем только в рантайме: у каждого объекта есть ссылочка на класс от которого он инстанцирован (или на прототип), пройдя по ссылочке можно поискать в описании класса нужный метод по имени. Таким образом получается duck typing и полиморфизм.
Late binding штука накладная (особенно если иерархия наследования развесистая), поэтому компилятору полезно как-то полиморфные вызовы оптимизировать.
Lookup cache. После того как обошли родительские классы и таки нашли нужный метод можно результат поиска запомнить в хэше (ключом будет имя метода и вышеуказанная ссылочка на класс объекта, а значением — адрес реализации метода).
В Berkeley Smalltalk'е lookup cache даёт 37% производительности. Но, всё равно, даже поиск в кэше — это оверхед по сравнению с простым вызовом метода по адресу.
К счастью, оказалось, что вызовы методов преимущественно мономорфные. Т.е. если в конкретном методе в переменной win лежит экземпляр класса Window, то в 95% последующих вызовов этого метода там будет тоже Window (объект может быть другим, но тоже экземпляр окна).
In-line cache. Т.е. лучше всего кэшировать в месте вызова, подменяя вызов lookup'а на вызов самого метода.
После компиляции win.draw (...) выглядит как-то так:
...
% push аргументы всякие
push win
push "draw"
call lookup % получаем на стеке адрес нужной реализации draw
call [esp]
...
Когда lookup нашёл нужный метод, он может вместо вызова себя поставить непосредственно вызов draw:
...
% push аргументы
push win
nop
nop
call draw
..
Естественно, никто не может гарантировать что вызов действительно мономорфный и в следующий раз в win не будет лежать экземпляр другого класса (например, дочернего для Window). Поэтому в начале draw должна быть проверка: если объект другого класса, то вызываем старый добрый lookup.
Btw, in-line cache не отменяет lookup caсhe (который прячется внутри функции lookup).10 months ago - @jorpic:Читаю эпик тред lambda-the-ultimate.org по рекомендации @tum.
По ссылке там отличная мысль, что архитектура браузеров и веба во многих смыслах неверна, и чтобы получить представление о том как могло бы быть лучше, достаточно посмотреть в сторону Smalltalk'а.
Кто не знает, поясню: Smalltalk — это exploratorial programming environment доведённая до предела настолько, что можноне останавливая не только саму программу поправить, но и пофиксить баги в компиляторе и отладчике, и потом продолжить выполнение.
На другом конце спектра гугловский Native Client.10 months ago - @jorpic:Btw, нужно читать блог товарища Edward Z. Yang: blog.ezyang.com
Из интересного:
— Denotational semantics в картинках
— Внутренности GHC в картинках - @jorpic: *jitНесколько тезисов по мотивам вводной части.
Как работает компилятор Self.
Сначала исходники очень простым компилятором (NIC — Non Inlining Compiler) транслируются в нейтивкод.
В каждом методе ставятся заглушки считающие число вызовов метода.
Когда счётчик достигает какого-то предела, метод перекомпилируется более умным компилятором.
Если появляется дополнительная информация (например, что метод не полиморфный и есть возможность его специализировать), метод может перекомпилироваться заново.
Если возникает исключительная ситуация (например, если арифметическое переполнение, то результатом будет уже не просто int, а double или Integer какой-нибудь) или программу пытаются дебагером тыкать, то оптимизированный метод может перекомпилироваться обратно без оптимизации (deoptimization).
Счётчик на самом деле затухает со временем (counter decay): раз в пару секунд все счётчики делятся на константу.
Т.е. если программа работает неделю, то методы, доля которых в общем числе вызовов невелика, всё равно не будут оптимизироваться.
(Кстати, как я понял, trace based компиляция так и не выстрелила из-за своей сложности по сравнению с простыми счётчиками.)
Btw, есть версия, что исходники — наиболее компактное представление программы (т.е. байткод и ast хранить не надо).
А неоптимизированный нейтивкод может быть побочным продуктом интерпретации (это вроде в Smalltalk'е каком-то было).
Поскольку ничего нового я пока не написал, пара вопросов.
Какие бенефиты от jit:
— быстрая компиляция;
— у оптимизирующего компилятора больше информации (от рантайма);
— сам компилятор проще (без сложных статических анализов);
— edit-run вместо edit-compile-link-run;
— редактирование кода в рантайме без перезапуска программы (через deoptimization).
— что ещё?
Какие недостатки:
— тормозит;
— сложно сделать whole program optimization, т.е. все оптимизации преимущественно локальные;
— что ещё? - @jorpic: *jitСлучайно распечатал диссертацию товарища Urs Hölzle (cs.ucsb.edu).
Пишет про трюки, которые он в 1994 году реализовал для jit-компилятора языка self.
Читается очень легко, постараюсь сюда конспект накидать.
Внимание, вопрос! Что можно почитать про современное состояние дел в динамической компиляции (например про javascript)?
