Около шестнадцати лет назад вышла первая версия Hotspot – реализация JVM, впоследствии ставшая стандартной виртуальной машиной, поставляемой в комплекте JRE от Sun.

Основным отличием этой реализации стал JIT-компилятор, благодаря которому заявления про медленную Джаву во-многих случаях стали совсем несостоятельными.
Сейчас почти все интерпретируемые платформы, такие как CLR, Python, Ruby, Perl, и даже замечательный язык программирования R, обзавелись своими реализациями JIT-трансляторов.

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

Таким образом вам может быть интересно под катом, если:

• Вы принципиально не понимаете, что такое JIT-компилятор, или у вас есть легкое непонимание, чем такой подход существенно лучше интерпретации.
• Вы хотели бы написать простой JIT для своего интерпретируемого языка.
• Вы преподаете курс «Языки программирования и компиляторы», и не против сделать практическое задание для студентов еще интересней.
• Вам интересно, как нарисована эта картинка.

В посте про «новшества» Parallel Studio XE 2015 я обещал написать про интересную технологию от Intel — Graphics Technology. Собственно, это я и собираюсь сделать сейчас. Суть Intel Graphics Technology заключается в использовании интегрированного в процессор графического ядра для выполнения вычислений на нем. Это оффлоад (offload) на графику, что, естественно, дает прирост производительности. Неужели интегрированная графика настолько мощна, что этот прирост будет действительно велик?
Давайте посмотрим на семейство новых графических ядер GT1, GT2 и GT3/GT3e, интегрированных в процессоры 4-го поколения Intel Core.

Высокоуровневые языки программирования содержат в себе много абстрактных программистских конструкций, таких как функции, условные операторы и циклы — они делают нас удивительно продуктивными. Однако одним из недостатков написания кода на высокоуровневом языке является потенциальное значительное снижение скорости работы программы. Поэтому компиляторы стараются автоматически оптимизировать код и увеличить скорость работы. В наши дни логика оптимизации стала очень сложной: компиляторы преобразуют циклы, условные выражения и рекурсивные функции; удаляют целые блоки кода. Они оптимизируют код под процессорную архитектуру, чтобы сделать его действительно быстрым и компактным. И это очень здорово, ведь лучше фокусироваться на написании читабельного кода, чем заниматься ручными оптимизациями, которые будет сложно понимать и поддерживать. Кроме того, ручные оптимизации могут помешать компилятору выполнить дополнительные и более эффективные автоматические оптимизации. Вместо того чтобы писать оптимизации руками, лучше бы сосредоточиться на дизайне архитектуры и на эффективных алгоритмах, включая параллелизм и использование особенностей библиотек.

Данная статья посвящена оптимизациям компилятора Visual C++. Я собираюсь обсудить наиболее важные техники оптимизаций и решения, которые приходится применить компилятору, чтобы правильно их применить. Моя цель не в том, чтобы рассказать вам как вручную оптимизировать код, а в том, чтобы показать, почему стоит доверять компилятору оптимизировать ваш код самостоятельно.

Эта публикация для тех, кто вынужден по долгу службы пользоваться pgcpp компилятором или поддерживать совместимость кода с этим компилятором.

На днях я получил баг репорт, что мой код неправильно работает, если его скомпилировать при помощи pgcpp.

Начав разбираться, я нашел место, где происходит ошибка. Оказалось, что если код компилируется с O2 или O3 оптимизацией, то std::sort может начать дублировать часть вектора и заменять этими дубликатами другие части.

Вот простой C++ код, который поможет воссоздать это ужасное поведение (обратите внимание на число 3193 в выводе):

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

Процесс поиска конкретной функции по указателю на объект называется поздним связыванием и выполняется во время работы программы. Позднее связывание не только увеличивает накладные расходы на вызов, но и препятствует оптимизации кода компилятором. Из-за этого сами виртуальные функции принято считать замедляющими работу.

В тексте выше ключевое слово «если». Что, если компилятор знает, какую функцию на самом деле надо вызывать?

Мы все сталкивались с проблемами, возникающими при неправильной работе с указателями: выход за пределы массива и переполнение буфера, случайная запись в неизвестный кусок памяти, с последующим чтением этого «мусора» в другом месте, а в некоторых отдельных случаях и просто падение всей системы. Иногда это просто «дичь», господа! И нужно уметь обходится с этой «дичью» правильно – вовремя находить и исправлять подобные ошибки и проблемы. Именно этим занялись в «плюсовом» компиляторе Intel ещё несколько релизов тому назад. Кроме того, многие идеи пошли дальше и будут реализованы в «железе» через технологию Intel Memory Protection Extensions. Давайте-ка посмотрим, как всё это работает в компиляторе.

Данный пост продолжает серию из трех статей об оптимизациях для x86 в GCC 5.0. В предыдущей статье речь шла о векторизации. Напомню, что GCC 5.0 находится сейчас в фазе stage3, то есть внедрение новых оптимизаций уже фактически заверешено и уровень производительности за редким исключением останется прежним и в продуктовом релизе. Сегодня речь пойдет об ускорениях позиционно-независимого кода или position independent code (PIC) в 32-битном режиме для x86.

Здравствуйте. Хочу представить свой проект – компилятор .NET/Mono в Java. Целью проекта является создание компилятора, и набора стандартных библиотек позволяющих переносить написанные приложения и библиотеки на платформу Java, версии 1.6 и выше. Из аналогичных проектов мне известен лишь проект dot42. Но он заточен под Android и имеет собственную стандартную библиотеку не совсем совместимую с .NET/Mono.

Пока есть только альфа версия, и поэтому для реального использования компилятор пока не годится, однако уже частично работоспособен, генерирует валидный код Java и поддерживает часть стандарта ECMA-335.

Исходные коды на github.com: https://github.com/zebraxxl/CIL2Java

Часто программисты полагаются на компилятор в вопросе векторизации циклов. Но компилятор не всесилен, ему зачастую тоже требуется помощь при разборе трудных участков. В данной статье есть ответ на вопрос: как узнать, где компилятор испытывает сложности с векторизацией и как помочь ему их преодолеть?

Язык Julia не поддерживает такую технику программирования, хорошо зарекомендовавшую себя в языках Haskell, Prolog, Erlang, Scala, Mathematica, как pattern matching. Но разрешает писать макросы, которые позволяют исправить этот фатальный недостаток. Выглядит это примерно так:

julia> immutable X a end

julia> immutable Y a ; b end

julia> @case(Y(X(9),2),  Y(4,3)-> 55, Y(X(k),2)->1+k)
10

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

Комбинаторные (монадические) парсеры достаточно хорошо известны (wikibooks). Они представляют из себя библиотеку маленьких парсеров, которые распознают простые элементы грамматики, и способы объединять несколько парсеров в один (комбинировать — от сюда и название). Монадические они потому что один из способов комбинирования, порождения парсера остатка текста на основе результата разбора начала, удовлетворяет условиям, накладываемым на математический объект «монада». В языке Haskell это позволяет воспользоваться мощным сервисом, предоставляемым языком и библиотеками. В других языках название «монадические» можно смело игнорировать — это не будет мешать их реализации и использованию, включая упомянутую выше операцию «bind».

Проще всего комбинаторные парсеры реализуются в языках с поддержкой замыканий, но можно воспользоваться и классическим ООП (пример описан Rebecca Parsons в книге Мартина Фаулера «Предметно-ориентированные языки»).
К преимуществам комбинаторных парсеров относится простота использования (запись на языке программирования практически не отличается от обычного описания грамматики), независимость от препроцессора (как yacc/bison, happy или ocamlyacc), возможность реализовать некоторые элементы, плохо укладывающиеся в контекстно-свободную грамматику, прямо на языке программирования общего назначения.

К недостаткам — сложность составления сообщений об ошибке, неспособность работать с леворекурсивной грамматикой (приводит к зацикливанию), а так же то, что очень легко сделать этот парсер не эффективным по быстродействию и памяти. (Одна из причин — компилятор не может произвести оптимизацию в терминах грамматики, так как работает на уровне языка программирования. Но есть и другие тонкости, требующие внимания, если требуется эффективность.)
Как альтернативу можно рассмотреть реализации в виде макросов (например OCaml streams parsers). В Perl6 поддержка грамматик встроена в язык.

Наследование

Персер конкретного языка состоит из множества более специализированных парсеров, ссылающихся друг на друга. В этом отношении парсеры напоминают методы некого объекта. Возникает желание порождать парсеры новых версий языков, подменяя отдельные подпарсеры (как это делается в паттерне проектирования «шаблонный метод» из ООП). Для экспериментов с этим подходом (а так же в порядке изучения очередного языка) я выбрал язык Julia — динамически-типизированном с особым подходом к наследованию (подобному CLOS из Common Lisp и R).
В отличие от обычных комбинаторных парсеров, подход с наследованием является экспериментальным (хотя в некотором виде поддерживается библиотекой макросов OCaml и языком Perl6). Пока он порождает не очень читабельный код. Исходный код доступен на Github.

Думаю, многим, также, как и мне, книга «Getting Started with LLVM Core Libraries» покажется интересной. Это первая книга, посвященная целиком и полностью LLVM. В основном, как следует из названия, ориентирована на новичков, которые только обратили свое внимание на LLVM, но уже имеют опыт программирования на C++.

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

Продолжаю тему межпроцедурных оптимизаций, введение в которую можно найти в предыдущем посте. Сегодня хочется немного порассуждать о подстановке функции (inlining) и о том, как подстановка влияет на производительность приложения.

Уважаемые читатели! Хочу поделиться с вами своим open-source проектом, над которым я работаю в своё свободное время уже достаточно давно, TeaVM. TeaVM представляет собой транслятор из байткода Java в JavaScript. Существует несколько попыток создать JVM на JavaScript, одна из самых удачных — Doppio. Однако, кроме академической, никакой ценности они не представляют, так как скорость интерпретации байт-кода оставляет желать лучшего. Более того, для интерпретации байткода необходимо как минимум загрузить этот байткод в браузер, а это вырождается в загрузку десятков мегабайт class-файлов.

В отличие от них, TeaVM не интерпретирует байткод, а генерирует JavaScript, который выполняет ровно то, что делал бы байткод, будь он запущен в реальной JVM. Проще говоря, TeaVM декомпилирует байткод Java, но не обратно в Java, а в JavaScript. Разумеется, всё это верно до определённых пределов. Во-первых, в JavaScript попросту отсутствуют некоторые вещи, привычные Java-разработчикам, такие как потоки, полноценная поддержка Юникода (например, поддержка классов символов, регулярные выражения), блокирующий ввод-вывод. Во-вторых, это обусловлено требованиями, которые я предъявлял к компилятору. Например, в TeaVM очень ограничена поддержка reflection. Это следствие одного из преимуществ TeaVM — сравнительно небольшой размер генерируемого файла. Нет, TeaVM не генерирует минимально возможный JavaScript, однако и не станет генерировать огромные многомегабайтные скрипты на каждый чих. Reflection делает невозможным какой-либо статический анализ, поэтому было принято решение от него отказаться.

Прежде чем я продолжу, я хочу для начала показать, на что способен TeaVM. Во-первых, он способен в реальном времени симулировать физику. Во-вторых, он ещё способен по этой физике рисовать красивые картинки в Canvas. Можно увидеть, что JavaScript-файлы сравнительно небольшие. Кстати, обсчёт физики я сам не реализовывал, я всего лишь взял имеющуюся библиотеку JBox2D.

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

Хотя на самом-то деле, если вспомнить историю Си, всё достаточно очевидно и, главное, логично. А все жалобы людей, «обжёгшихся» на неопределённом поведении для людей не забывших что такое Си и зачем он вообще существует звучат примерно как: «я тут гвозди бензопилой забивал… забивал и забивал, всё было хорошо, а потом я дёрнул за ручку и у неё коготки как забегают, задёргаются, мне руку оттяпало и полноги… ну кто так строит?».

Люди, которые знают что такое бензопила пытаются, конечно, объяснить, что за если за эту рукоятку дёрнуть, то так, в общем-то, и должно быть, но люди, считающие, что у них у руках такой себе молоток говорят «мимо» них, и, в результате, все остаются при своих.

Отличные новости ждут пользователей gcc при переходе на версию 4.9.0 – новые оптимизации с использованием неопределенного поведения могут «сломать» (на самом деле — доломать) существующий код, который, например, сравнивает с нулем указатели, ранее переданные в memmove() и ряд других функций стандартной библиотеки.

Например, утверждается, что в таком коде:

int wtf( int* to, int* from, size_t count ) {
    memmove( to, from, count );
    if( from != 0 )
        return *from;
    return 0;
}

новый gcc может удалить сравнение указателя с нулем и в результате вызов wtf( 0, 0, 0 ) будет приводить к разыменованию нулевого указателя (и аварийному завершению программы).

Да, да. Вы не ослышались. В этот раз статья «наоборот». Не мы проверяем какой-то проект, а проверили наш анализатор с помощью другого инструмента. На самом деле, подобное делали мы и раньше. Например, проверяли PVS-Studio с помощью Cppcheck, с помощью анализатора, встроенного в Visual Studio, смотрели на предупреждения Intel C++. Но раньше не было повода написать статью. Ничего интересного не находилось. А вот Clang смог заинтересовать своими диагностическими сообщениями.

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

В процессе подготовки очередного релиз-кандидата в ядре Linux 3.16 выяснилось совершенно непредсказуемое поведение функции балансировки нагрузки в Linux 3.16-rc6. В списке рассылки для разработчиков ядра двое авторов прислали сообщения о разных багах, хотя у них могла быть общая природа.

Линус Торвальдс внимательно разобрался в вопросе и ёмко ответил одному из сообщивших о баге: «Ok, я посмотрел на генерацию кода, и твой компилятор — чистое и полное дерьмо».

В соответствии со стандартами C и C++, если выполнение программы приводит к переполнению знаковой целой переменной, или к любому из сотен других «неопределённых действий» (undefined behaviour, UB), то результат выполнения программы может быть любым: она может запостить на Твиттер непристойности, может отформатировать вам диск…
Увы, в действительности «пасхальные яйца», которые бы заставляли программу в случае UB делать что-то из ряда вон выходящее, не встречались со времён GCC 1.17 — та запускала nethack, когда встречала в коде программы неизвестные #pragma. Обычно же результат UB намного скучнее: компилятор просто оптимизирует код для тех случаев, когда UB не происходит, не придавая ни малейшего значения тому, что этот код будет делать в случае UB — ведь стандарт разрешает сделать в этом случае что угодно!
В качестве иллюстрации того, как изобилие UB в стандарте позволяет компилятору выполнять неочевидные оптимизации, Реймонд Чен приводит такой пример кода:

int table[4];
bool exists_in_table(int v)
{
    for (int i = 0; i <= 4; i++) {
        if (table[i] == v) return true;
    }
    return false;
}

В условии цикла мы ошиблись на единицу, поставив <= вместо <. В итоге exists_in_table() либо должна вернуть true на одной из первых четырёх итераций, либо она прочтёт table[4], что является UB, и в этом случае exists_in_table() может сделать всё что угодно — в том числе, вернуть true! В полном соответствии со стандартом, компилятор может соптимизировать код exists_in_table() до

int table[4];
bool exists_in_table(int v)
{
    return true;
}

Такие оптимизации иногда застают программистов врасплох.