Уже немало лет прошло, как я познакомился с инструкциями MMX, SSE, а позже и AVX на процессорах Intel. В своё время они казались какой-то магией на фоне x86 ассемблера, который уже давно стал чем-то обыденным. Они меня настолько зацепили, что пару лет назад у меня появилась идея написать свой собственный софт рендерер для одной известной игры. Сподвигло меня на это то, какую производительность обещали эти инструкции. В какой-то момент я даже думал об этом написать. Но писать текст оказалось куда сложнее кода.

В то время я хотел избежать проблем с поддержкой на разных процессорах. Хотелось иметь возможность проверить мой рендерер на максимально доступном количестве. У меня до сих пор остались знакомые со старыми AMD процессорами, и их потолок был SSE3. Поэтому на тот момент я решил ограничиться максимум SSE3. Так появилась векторная математическая библиотека, чуть менее, чем полностью реализованная на SSE, с редким включением до SSE3. Однако в какой-то момент мне стало интересно, какую максимальную производительность я смогу выжать из процессора для ряда критичных операций векторной математики. Одной из таких операций является умножение матриц float 4 на 4.

Введение:

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

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

Возникает необходимость использовать численные методы, наиболее известным из которых является метод Рунге — Кутты [1]. Что касается Python, то в публикациях по численным методам, например [2,3], данных по применение Рунге — Кутты крайне мало, а по его модификации — методу Рунге-Кутта-Фельберга вообще нет.

В настоящее время, благодаря простому интерфейсу, наибольшее распространение в Python имеет функцию odeint из модуля scipy.integrate. Вторая функция ode из этого модуля реализует несколько методов, в том числе и упомянутый пятиранговый метод Рунге-Кутта-Фельберга, но, вследствие универсальности, имеет ограниченное быстродействие.

Целью настоящей публикации является сравнительный анализ перечисленных средств численного решения систем дифференциальных уравнений с модифицированным автором под Python методом Рунге-Кутта-Фельберга. В публикации так же приведены решения по краевым задачам для систем дифференциальных уравнений (СДУ).

Занимаясь программированием рендеринга графики, мы живём в мире, в котором обязательны низкоуровневые оптимизации, чтобы добиться GPU-фреймов длиной 30 мс. Для этого мы используем различные методики и разработанные с нуля новые проходы рендеринга с повышенной производительностью (атрибуты геометрии, текстурный кеш, экспорт и так далее), GPR-сжатие, скрывание задержки (latency hiding), ROP…

В сфере повышения производительности CPU в своё время применялись разные трюки, и примечательно то, что сегодня они используются для современных видеокарт ради ускорения вычислений ALU (Низкоуровневая оптимизация для AMD GCN, Быстрый обратный квадратный корень в Quake).


Быстрый обратный квадратный корень в Quake

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

Эта статья — не исчерпывающее хардкорное руководство по железу. Это всего лишь введение, напоминание, свод базовых принципов написания эффективного кода для CPU. Я хочу «показать, что низкоуровневое мышление сегодня всё ещё полезно», даже если речь пойдёт о процессорах, которые я мог бы добавить.

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

Около месяца свободного времени я уделил чтению исходного кода Quake II. Это был удивительный и поучительный опыт, потому что в движок idTech3 внесено большое изменение: Quake 1, Quake World и QuakeGL объединены в одну красивую архитектуру кода. Особенно был интересен способ, которым достигли модульности, несмотря на то, что язык программирования C не обеспечивает полиморфизма.

Quake II во многих отношениях является блестящим образцом программного обеспечения, потому что это был самый популярный (по количеству лицензий) трёхмерный движок всех времён. На его основе было создано более 30 игр. Кроме того, он ознаменовал переход игровой индустрии от программной/8-битной системы цветов к аппаратной/24-битной. Этот переход произошёл примерно в 1997 году.

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

Процесс «подчистки» меня сильно увлёк: в статье теперь более 40 мегабайт видео, скриншотов и иллюстраций. Сейчас я не знаю, стоили ли мои труды того, и нужно ли публиковать в будущем необработанные заметки в ASCII, выскажите своё мнение.

Если вы используете в своей игре спрайты с прозрачностью (а обычно так и бывает, как минимум для UI), то вам, вероятно, стоит уделить внимание к полностью прозрачным пикселям текстур (или «текселам»).

Даже если значение альфа-канала равно 0, с пикселем всё равно связано значение цвета. Этот цвет ни на что не влияет, так ведь? В конце концов, пиксель полностью прозрачен, кому есть дело до его цвета…

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

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

От создания нового проекта в Юнити до публикации бета-версии в Стиме прошло 10 месяцев. 90% времени ушло на создание, оптимизацию и вылизывание физической модели, остальное — на геймплей.

Цель была в том, чтобы создать полностью физический мир. Но подход, реализованный в Red Faction показался слишком громоздким и не слишком реалистичным. В той игре меши при взрыве разбивались на куски, на которые натягивались физические коллайдеры. Я решил не мучаться с сопроматом и множеством частных случаев разрушений, а сделать простую систему, работающую во всех случаях.

Сделал всё из взаимодействующих частиц: землю, здания, танки игроков, врагов, снаряды и бонусы — всё. Взаимодействия между частицами реализовал на видеокарте, поскольку для параллельных вычислений она в 50-100 раз производительней процессора.

Получившаяся из частиц материя сначала выглядела странно, и напоминала то ли жидкость, то ли газ:



А для игры нужно было что-то прочное, способное держать форму. Испробовав разные способы взаимодействия частиц, я нашёл, что сила Леннарда-Джонса даёт самую прочную субстанцию. Получилось что-то вроде манной каши. Для экспериментов я добавил взрывы по клику мыши.

В этих 3-ех статьях я детально расскажу об атомарных операциях, барьерах памяти и о быстром обмене данными между потоками, а так же о «sequence-points» на примере «execute-around-idiom», а заодно постараемся вместе сделать что-нибудь полезное — умный указатель, который делает любой объект потоко-безопасным для любых операций с его членами переменными или функциями. А затем покажем как используя его достичь производительности высоко-оптимизированных lock-free алгоритмов на 8 — 64 ядрах.

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

→ Часть 0
→ Часть 1, общие оптимизации

В прошлый раз мы получили ускорение в среднем в 2,5 раза без изменения подхода. В этот раз я покажу, как применять SIMD-подход и получить ускорение еще в 3,5 раза. Конечно, применение SIMD для обработки графики не является ноу-хау, можно даже сказать, что SIMD был придуман для этого. Но на практике очень мало разработчиков используют его даже в задачах обработки изображений. Например, довольно известные и распространенные библиотеки ImageMagick и LibGD написаны без использования SIMD. Отчасти так происходит потому, что SIMD-подход объективно сложнее и не кроссплатформенный, а отчасти потому, что по нему мало информации. Довольно просто найти азы, но мало детальных материалов и разбора реальных задач. От этого на Stack Overflow очень много вопросов буквально о каждой мелочи: как загрузить данные, как распаковать, запаковать. Видно, что всем приходится набивать шишки самостоятельно.

Недавно познакомился со структурами C/C++ — struct. Господи, да «что же с ними знакомиться» скажете вы? Тем самым вы допустите сразу 2 ошибки: во-первых я не Господи, а во вторых я тоже думал что структуры — они и в Африке структуры. А вот как оказалось и — нет. Я расскажу о нескольких жизненно-важных подробностях, которые кого-нибудь из читателей избавят от часовой отладки…

Городская библиотека Стокгольма. Фото minotauria.

В этой статье я хочу рассказать о том, что оценивать время обращения к памяти как O(1) — это очень плохая идея, и вместо этого мы должны использовать O(√N). Вначале мы рассмотрим практическую сторону вопроса, потом математическую, на основе теоретической физики, а потом рассмотрим последствия и выводы.

Введение

Если вы изучали информатику и анализ алгоритмической сложности, то знаете, что проход по связному списку это O(N), двоичный поиск это O(log(N)), а поиск элемента в хеш-таблице это O(1). Что, если я скажу вам, что все это неправда? Что, если проход по связному списку на самом деле O(N√N), а поиск в хеш-таблице это O(√N)?

Не верите? Я вас сейчас буду убеждать. Я покажу, что доступ к памяти это не O(1), а O(√N). Этот результат справедлив и в теории, и на практике. Давайте начнем с практики.

Измеряем

Давайте сначала определимся с определениями. Нотация “О” большое применима ко многим вещам, от использования памяти до запущенных инструкций. В рамках этой статьи мы O(f(N)) будет означать, что f(N) — это верхняя граница (худший случай) по времени, которое необходимо для получения доступа к N байтов памяти (или, соответственно, N одинаковых по размеру элементов). Я использую Big O для анализа времени, но не операций, и это важно. Мы увидим, что центральный процессор подолгу ждет медленную память. Лично меня не волнует, что делает процессор пока ждет. Меня волнует лишь время, как долго выполняется та или иная задача, поэтому я ограничиваюсь определением выше.

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


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

В работе над сайтом «Я люблю ИП» мы используем разные сервисы, которые облегчают жизнь предпринимателям. В этой статье мы собрали самые полезные государственные сервисы для ИП. Они помогут вам зарегистрировать бизнес, рассчитаться с налогами и страховыми взносами, сдать отчётность или узнать о возможных штрафах.

В чем разница между двумя этими определениями инициализированных локальных переменных С/С++?

char buffer[32] = { 0 };
char buffer[32] = {};

Одно отличие состоит в том, что первое допустимо в языках С и С++, а второе — только в С++.

Что ж, давайте тогда сосредоточимся на С++. Что означают эти два определения?

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

Эти определения несколько различаются, но по факту результат один — весь массив должен быть инициализирован нулями. Поэтому согласно правилу «as-if» в С++ они одинаковы. То есть любой достаточно современный оптимизатор должен генерировать идентичный код для каждого из этих фрагментов. Верно?

В этом обзоре мы рассмотрим популярные в 2016 году игровые движки и проголосуем за лучшие из них.

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

Изображения и текст принадлежат их авторам.

Анимация элементов в мобильных приложениях — это просто. Правильная анимация тоже может быть простой… если вы последуете представленным в статье советам.

Сегодня кто только не использует CSS 3 анимацию в своих проектах, тем не менее не только лишь все, но мало кто может делать это правильно. Даже описаны так называемые «лучшие практики», но люди продолжают делать всё по-своему. Скорее всего потому, что просто не понимают, почему всё устроено именно так, а не иначе.

Я уверен, что многим программистам знакома формула:


А уж тот, кто плотно работал с графикой, знает эти цифры буквально наизусть — как в былые времена эникейщики запоминали серийники Windows. Иногда коэффициенты округляют до второго знака, иногда уточняют до четвертого, но каноническая форма именно такая.

Вычисляет она относительную яркость цвета (relative luminance или в некоторых контекстах luma; не путать с lightness и brightness) и широко применяется для преобразования цветного RGB-изображения в Grayscale и связанных с этим задач.

Формула растиражирована и процитирована в тысячах статей, форумных обсуждений и ответов на StackOverflow… Но дело в том, что единственно-правильное её место — на свалке истории. Использовать её нельзя. Однако же используют.

Но почему нельзя? И откуда же взялись именно такие коэффициенты?

В этой серии из двух статей говорится о том, как структура данных и памяти влияет на производительность. Предлагаются определенные действия для повышения производительности программного обеспечения. Даже простейшие действия, показанные в этих статьях, позволят добиться существенного прироста производительности. Многие статьи, посвященные оптимизации производительности программ, рассматривают распараллеливание нагрузки в следующих областях: распределенная память (например, MPI), общая память или набор команд SIMD (векторизация), но на самом деле распараллеливание необходимо применять во всех трех областях. Эти элементы очень важны, но память также важна, а про нее часто забывают. Изменения архитектуры программ и применение параллельной обработки влияют на память и на производительность.

На хабре то и дело мелькают статьи об успешном опыте использования Qt для разработки под Android, а также под iOS и WP. Статьи наполнены достаточно большим энтузиазмом — ведь это так здорово: пишешь и тестируешь UI на десктопе, а потом просто собираешь с помощью нехитрых команд под Android, iOS, WP, заливаешь в сторы и готово. В этой же статье я хочу поделиться опытом «собирания грабель» преимущественно при разработке под Android.

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

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

Можно самостоятельно анимировать различные элементы страницы или же воспользоваться Motion UI. Это библиотека для создания плавных переходов и анимаций на Sass, вышедшая из семейства Foundation.