Вчера собрался ускорить работу(получилось достаточно ощутимо) и загрузку системы(30 секунд, против полутора минут), почитал многие how-to.
Опишу что и где я улучшал. Итак о способах, по порядку.

В последнее время обсуждения языка PHP на хабре сводятся больше к возможностям проектировать сложные системы, что не может не радовать. Однако, просмотрев с десяток самых признаваемых веб-фреймворков (Zend Framework, Adept, CakePHP, CodeIgniter, LIMB, Symfony, MZZ и другие) я с искренним удивлением обнаружил в некоторых существенные недочеты с точки зрения элементарной оптимизации.

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

Вот тут подымался вопрос о том, как определить, есть ли у объекта атрибут и как это сделать максимально быстро, однако достаточно глубоко тема исследована не была.

Недавно, во время разбора кода одной программы я заметил метод, который выглядел примерно так:

public void Foo<T>(IEnumerable<T> items)
{
 if(items == null || items.Count() == 0)
 {
  // Оповестить о пустом перечислении
 }
}


Метод принимает дженерик-перечисление и проверяет, пустое ли оно. Видите ли вы тут потенциальную проблему? Я намекну, проблема в этой строчке:

items.Count() == 0

И в чем же тут проблема? Проблема в том, что эта строчка может оказаться очень неэффективной.

Введение

Новый набор SIMD инструкций для x86-процессоров Intel AVX был представлен публике ещё в марте 2008 года. И хотя реализации этих инструкций в железе ждать ещё полгода, спецификацию AVX уже можно считать устоявшейся, а поддержка набора инструкций AVX добавлена в новые версии компиляторов и ассемблеров. В данной статье рассмотрены практические вопросы оптимизации для Intel AVX подпрограмм на языках C/C++ и ассемблер.

Интерес к холсту (<canvas>), а равно и к мобильным приложениям, приводит к возрождению прежней художественной школы восьмибитных изображений. Joe Huckaby из Effect Games поигрался с зацикливанием цвета, что привело к несколько ошеломляющим результатам.

Помнит ли кто-нибудь зацикливание цвета в девяностых годах? Эта технология часто использовалась восьмибитными видеоиграми той эпохи для достижения интересных зрелищных эффектов методом зацикленного сдвига цветовой палитры. Тогда видеокарты могли показывать только 256 цветов за раз, так что использовалась палитра подобранных цветов. Но программист мог переменять эту палитру по своему усмотрению, и цвета на экране тотчас переменялись, подстраиваясь под неё. Это происходило быстро, и не требовало буквально никакой дополнительной памяти.

Здесь также происходит искусная оптимизация — вместо того, чтобы очищать и перерисовывать всю сцену в каждом кадре, Джо обновляет только те пикселы, которые изменяются:

Чтобы достигнуть во браузере быстрой смены кадров, мне пришлось устроить слегка безумную оптимизацию движка. Отображение картинки 640×480 с индексированным цветом на тридцатидвухбитном RGB-холсте означало бы обход и прорисовку 307200 пикселов в каждом кадре джаваскриптом. Это обход обширного массива, так что некоторые браузеры просто не в состоянии справиться с этим. Я преодолел их медлительность предварительной обработкою изображений, когда они впервые загружаются, и сбором тех пикселов, которые ссылаются на анимируемые цвета (то есть на цвета, входящие в зацикливаемые подмножества палитры). Координаты этих пикселов хранятся в отдельном (меньшем) массиве, и оттого одни только изменяемые пикселы обновляются на экране. Этот финт оптимизации сработал настолько превосходно, что анимация действительно крутится на весьма неплохой скорости в моём iPhone 3GS и iPad!

Решил посмотреть на новый Intel VTune Amplifier XE 2011 beta и написать статью о примере использования. Правда, в процессе написания акцент частично сместился от использования Amplifier к его тестированию. Но это тоже хорошо, надеюсь, разработчики в Intel учтут пожелания и внесут изменения в следующую версию инструмента. И вообще буду критиковать и себя, и всех. :)

Начну, пожалуй, с очевидного (слева от этого текста). Изображение, приведенное здесь, довольно известно. Оно показывает, что сотрудники Интел обычно носят на пальцах вместо колец процессоры Atom и рисовые зерна.
Оно демонстрирует размер процессора Intel Atom в сравнении с рисовым зерном. А я продемонстрирую вам буквально «на пальцах» простые и, надеюсь, полезные для программистов на С\С++ советы по оптимизации софта для Intel Atom.

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

Но вот насколько эта рекомендация актуальна в наше время? В стародавние времена, например, советовали не повторять вычисления. Считалось хорошим тоном вместо:

X = A + 10 + B;
Y = A + 10 + C;

написать так:

TMP = A + 10;
X = TMP + B;
Y = TMP + C;

Большая часть времени исполнения программы приходится на циклы: это могут быть вычисления, прием и обработка информации и т.д. Правильное применение техник оптимизации циклов позволит увеличить скорость работы программы. Но прежде, чем приступать к оптимизациям необходимо выделить «узкие» места программы и попытаться найти причины падения быстродействия.

Это — вольный перевод моего недавнего поста на английской версии Intel Software Network. Так что те, кому Victoria Zhislina нравится больше vikky13, кто уже видел этот пост, могут сразу прочесть первый и последний абзацы, отсутствующие в оригинале.

— Всем здрасьте, мне нужен транслятор с русского языка в код программы на C++. Ну то есть, я пишу задачу, а транслятор реализует ее решение на языке С++. Где можно такой найти? Если для Cи нету, может быть, есть для других языков?

— Есть, называется начальник отдела разработки. Пишешь задачу на русском — отдаешь подчиненным и все, код готов! Хоть на Си, хоть на Дельфи, хоть на Яве. Я проверял, работает!

Говорят, что это не анекдот, а реальный вопрос на программистском форуме. Также говорят, что человек гораздо умнее машины, а значит, может ей помочь — поделиться умом. Но есть немало случаев, когда делать этого точно не стоит. Результат будет обратный ожидаемому.

С Новым годом! Опишу классический сюжет — оптимизацию длинной арифметики в C++ при помощи ассемблерных вставок. Однако, на Хабре его еще не было, поэтому после некоторых колебаний решил запостить сюда, вы уж простите, если сами когда-то писали то же самое и продвинулись дальше меня :-)

Как-то раз возникла необходимость написать транслитерацию на Python — из кириллицы в латиницу. Из слова «ситх» получается «sith», а из «шелест» выходит «shelest».

Казалось бы, чего тут вообще писать — задача едва сложнее print "Hello world". И это отчасти так — но не совсем.

Дело в том, что некоторые буквы в русском языке при транслитерации преобразуются не в одну, а сразу несколько латинских букв: это Ж, Ц, Ч, Ш, Щ, Ю и Я. По сути, если бы правилами транслитерации предполагалось преобразовывать их в одну латинскую букву, то транслитерация русского в английский действительно была бы не намного сложнее той самой простейшей программы.

Но, поскольку правила транслитерации мы менять точно не собираемся, то посмотрим, что получится при использовании обычной транслитерации.

К примеру, фраза «ШАПКА и Юля» преобразуется в «SHAPKA и YUlya», либо в «ShAPKA и Yulya» — в зависимости от того, что задано в таблице транслитерации для «Ш» и «Ю» (иногда задаётся «SH» и «YU», а иногда «Sh» и «Yu»).

То есть регистр следующей буквы в стандартных функциях транслитерации не учитывается, и все буквы в верхнем регистре заменяются по общим правилам. Поэтому в ходе транслитерации для слов «ЧАША» и «Щи» легко получается что-то вроде «ChAShA» или «SCHi», когда реально мы скорее хотели получить «CHASHA» и «Schi».

Тем не менее, все найденные реализации транслитерации из кириллицы в латиницу на Python, как выяснилось, эту особенность не учитывали. Это и многочисленные решения, приведённые на форумах, и библиотека pytils, реализующая транслитерацию в одном из своих модулей.

Значит, напишем свою функцию транслитерации, с блэкджеком и^W^W^W^H^H. :)

На всех CPU операция деления выполняется сравнительно медленно, с этим ничего поделать нельзя. Но если делитель константа, то деление можно заменить на умножение на какую-то другую константу (обратное число, которое вычисляется во время компиляции). Тогда код будет чуть быстрее работать (и потреблять меньше энергии). Такую оптимизацию делают многие компиляторы (gcc, MSVC), но оказывается, многие разработчики не знают, как вычисляется сомножитель, а это не тривиально.

Дальше будет рассказано, как вычисляется сомножитель.

Эрик Липперт — ветеран Microsoft, проработавший в компании 16 лет и стоящий за разработкой VBScript, JScript и C#.

На прошлой неделе в комментариях к одной из статей разгорелся спор о роли низкоуровневой оптимизации в программировании, и я вспомнил относящуюся к этому статью Эрика. Она была написана в конце 2003, и хотя реалии с тех пор несколько изменились — принципы остались теми же самыми. Можете мысленно заменить ASP и VBScript на PHP, JavaScript, или на другой скриптовый язык по вашему вкусу.

Эту статью я уже пытался перевести в 2005, но русский текст тогда получился неуклюжий, так что этот перевод — новый и ранее не публиковался, в соответствии с требованиями НЛО. В Переводе блога Эрика Липперта этого текста тоже нет — наверное, для них он слишком стар.

---

Я уже много писал о быстродействии скриптов, но до сих пор я не высказывался по поводу того, что многие советы об их оптимизации я считаю как минимум бестолковыми, а то и откровенно вредными.

Например, за семь лет в Microsoft я получил десятки вопросов, аналогичных по своей сути этому, заданному в конце 1990-х:

У нас есть код на VBScript, и в одной часто вызываемой функции мы определяем оператором Dim несколько переменных, которые нигде в функции не используются. Не замедляется ли каждый вызов функции из-за объявления этих переменных?

Какой интересный вопрос! В компилируемом языке, таком как Си, объявление локальных переменных общим размером n байт всего лишь вычитает n из указателя стека при входе в функцию. Если n будет чуть больше или чуть меньше, затраты времени на вычитание никак не изменятся. Наверное, в VBScript точно так же? Оказалось, что нет! Вот что я написал автору вопроса:

asm.js — необыкновенно оптимизируемое, низкоуровневое подмножество JavaScript. — asmjs.org

asm.js — новый язык?

Нет, это просто подмножество JavaScript. Программа на asm.js одинаково поведёт себя и в существующих движках JavaScript, и в движке с предварительной (ahead-of-time, AOT) компиляцией, способном распознавать и оптимизировать asm.js; различаться будет её скорость, разумеется!

Какой выигрыш в производительности можно ожидать от asm.js?

Сейчас ещё рано утверждать. Однако наши предварительные измерения производительности программ, скомпилированных из Си в asm.js, показывают не более чем двукратное замедление по сравнению с компилированными в машинный код посредством clang. Мы опубликуем дальнейшие измерения, когда насобираем их.

Как я могу следить за ходом реализации?

Мозилла работает над первой реализацией оптимизирующего компилятора asm.js для SpiderMonkey. В вики Фонда Мозиллы также опубликован план разработки дальнейших выпусков и оптимизаций. Если авторы других движков JavaScript опубликуют собственные планы реализации компиляторов asm.js, мы их здесь упомянем.

Почему бы вам не разработать синтаксис байткода вместо необычного диалекта джаваскрипта?

Для компиляторов наподобие Emscripten или Mandreel синтаксис байткодового языка попросту не особенно значим. Притом большинство байткодов и вообще машинных языков имеют двоичный формат, не читаемый людьми. Однако мы можем создать на уровне asm.js более человеко-читаемый синтаксис, который будет и удобным в дизассемблировании, и пригодным для чтения и записи людьми.

То обстоятельство, что asm.js — это JavaScript, не обернётся ли непредсказуемым выполнением кода?

Предварительная (ahead-of-time, AOT) компиляция asm.js может генерировать код, выполнение которого весьма предсказуемо, потому что валидный код asm.js ограничен крайне небольшим подмножеством JavaScript, состоящим только из строго типизированных целых чисел, чисел с плавающей точкою, арифметических операций, вызовов функций и обращения к куче.

Почему бы тогда не NaCl или PNaCl вместо этого? Вы просто упорствуете насчёт JavaScript?

Принципиальным достоинством asm.js по сравнению с новыми технологиями вроде NaCl и PNaCl является то, что asm.js работает сегодня: существующие движки JavaScript ужé неплохо оптимизируют код, написанный в таком стиле. Что означает, что разработчики могут выпускать код на asm.js сегодня, а со временем его работа будет ускоряться. Другою важною пользою является заметно бóльшая простота реализации, для которой потребуется совсем немного дополнительных механизмов поверх существующих движков JavaScript — и не понадобится слой совместимости API.

При оптимизации времени выполнения алгоритма, использующего LDPC декодер, профайлер привел к функции, вычисляющей следующее значение:

где a и b — целые числа. Количество вызовов шло на миллионы, а реализация ее была достаточно

SIMD и обработка изображений

Обработка изображений (здесь мы сознательно ограничиваем в себя только растровыми картинками и опускаем широкий класс векторных изображений), как правило, представляет собой набор простых операций, которые применяются к каждой точке изображения. Если учесть, что цветовые каналы, из которых состоит точка изображения (пиксель) обычно представлены в виде целых чисел небольшой размерности, то обработка изображения сводится к огромному числу однотипных операций над 1-2 байтными целыми числами.

Введение

Ранее во вступительной статье я поднимал список проблем, с которыми придется столкнуться разработчику, если он захочет оптимизировать оптимизацию обработки изображения при помощи SIMD инструкций. Теперь пришло время на конкретном примере показать, как указанные выше проблемы можно решить. Я долго думал, какой алгоритм выбрать для первого примера, и решил остановиться на медианной фильтрации. Медианная фильтрация является эффективным способом подавления шумов, которые неизбежно появляются на цифровых камерах в условиях малого освещения сцены. Алгоритм этот достаточно ресурсоемок – так например, при обработке серого изображения медианным фильтром 3х3 требуется порядка 50 операций на одну точку изображения. Но в тоже время он оперирует только с 8-битными числами и ему для работы требуется сравнительно не много входных данных. Эти обстоятельства делают алгоритм достаточно простым для SIMD оптимизации и в тоже время позволяют получить из нее весьма существенное ускорение.

На носу было придумывание темы для диплома, на кафедре популярностью пользовались различные варианты идей связанных с генетическими алгоритмами, а мне самому хотелось сделать что-нибудь этакое. Так и родилась идея, давшая начало данному проекту, а именно генетическому оптимизатору программного кода.



Цель была довольно амбициозной — в идеале сделать такую штуку, которой на вход подается программа, а дальше она ее крутит так и сяк и пытается всячески ускорить отдельные ее фрагменты без участия человека, попутно собирая себе базу для последующих оптимизаций. Сразу скажу что хотя в целом задача была решена, практической пользы я из нее извлечь не смог. Однако некоторые полученные в процессе результаты показались мне достаточно интересными чтобы ими поделиться.

Например вот такая забавная оптимизация набора арифметических инструкций (взятых из какой-то подвернувшейся под руку математической библиотеки), соответствующих формулам: , которая на 6 джаве с выключенным JIT у меня давала около 10% ускорения, при этом на первый взгляд даже не очевидно что эти формулы эквивалентны (ОТКУДА ТУТ OR? ЭТО ВООБЩЕ ЗАКОННО?!), хотя это так. Под катом я расскажу, как именно получались такие результаты и каким образом компьютер придумывал лучший код чем тот, который мог написать я сам.