Рубрика «оптимизация кода»

Это небольшое подведение итогов на пост “Быстрее, чем C++; медленнее, чем PHP”

Неблагодарное дело — «спорить» в комментариях, поэтому формулирую несколько мыслей в отдельный пост. Автор утверждал тут, тут, и еще много где, что у него большой стаж и богатый опыт в программировании на С++.
Читать полностью »

Итак, вы оптимизировали самые очевидные части своей игры. Однако на самом деле это не так. Вы упустили хитрый, не совсем заметный момент: оптимизацию иерархии сцены Unity.

А что не так с иерархией? Позвольте вам кое-что показать.

Запустите Unity и откройте проект своей игры. Затем запустите игру на целевом устройстве
и подключите к ней Unity Profiler. Запишите несколько кадров во время игрового процесса.

В Unity Profiler поищите следующие неприятные маркеры профайлера:

Оптимизация Unity: как вас обкрадывает иерархия сцен - 1

Не нашли? Продолжайте искать, уверен, найдётся хотя бы один.

Это могут быть UpdateRendererBoundingVolumes, Physics.SyncColliderTransform или TransformChangedDispatch.

Они появятся, когда вы уже будете готовы сдаться. Они возникнут, когда вы уже наведёте курсор мыши на кнопку закрытия Profiler.

Нашли? Если да, то вам повезло. Я тоже нашёл их в одном из своих предыдущих проектов и узнал, как полностью избавиться от них. Я понял, какое зло в них скрыто…

Хотите узнать секреты производительности иерархий сцен Unity?
Читать полностью »

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

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

image

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

Для меня очень важно подбирать хорошие заголовки для своих постов, но я сразу же вспомнил, что подходящее название «48 процессора заблокированы девятью инструкциями» уже занято [перевод на Хабре] постом, написанным меньше месяца назад. Количество заблокированных процессоров отличается, а цикл немного длиннее, но на самом деле всё это заставляет испытывать дежавю. Поэтому пока я объясняю новую найденную проблему, мне был хотелось поразмыслить над тем, почему это случается постоянно.

Почему это происходит?

Грубо говоря, такие проблемы возникают вследствие наблюдения, которое я назову Первым законом Доусона о вычислениях: O(n2) — это магнит для алгоритмов, которые плохо масштабируются: они достаточно быстры, чтобы попасть в продакшен, но достаточно медленны, чтобы всё портить, когда туда попадут.

Как линейное время превращается в Windows в O(n²) - 2

O(n2) в действии — данные взяты из моего случая
Читать полностью »

Скачать файл с кодом и данные можно в оригинале поста в моем блоге

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

Мне довелось работать с Wolfram Language начиная с (уже довольно далекого) 2005 года (тогда еще была версия Mathematica 5.2, сейчас уже 12-я). За эти почти 15 лет произошло очень много: добавились тысячи новых встроенных функций и областей, в которых они работают (машинное обучение, точная геометрия, работа с аудио, работа в вебе, облачные возможности, глубокая поддержка единиц измерения, интеграция с базами данных Wolfram|Alpha, географические вычисления, поддержка работы с CUDA, Python, распараллеливание операций и многое многое другое), появились новые сервисы — облако Wolfram Cloud, широко известная система вычислительных значeний Wolfram|Alpha, репозиторий функций, репозиторий нейросетей и пр.
Читать полностью »

image

Деление — одна из самых дорогих операций в современных процессорах. За доказательством далеко ходить не нужно: Agner Fog[1] вещает, что на процессорах Intel / AMD мы легко можем получить Latency в 25-119 clock cycles, а reciprocal throughput — 25-120. В переводе на Русский — МЕДЛЕННО! Тем не менее, возможность избежать инструкции деления в вашем коде — есть. И в этой статье, я расскажу как это работает, в частности в современных компиляторах(они то, умеют так уже лет 20 как), а также, расскажу как полученное знание можно использовать для того чтобы сделать код лучше, быстрее, мощнее.
Читать полностью »

Почему для открытия меню Windows читает один файл сто тысяч раз? - 1

«Проводник тратит 700 мс на то, чтобы открыть контекстное меню панели задач. 75% этого времени он выполняет 114 801 операцию считывания из одного файла, средний объём считываемых данных 68 байт.

Мне стоит написать пост об этом, или достаточно саркастичного твита?»

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

Это напрягало меня уже давно, но я проявлял нехарактерный мне самоконтроль и удерживался от раздражения. Так было до сегодняшнего дня, когда я наконец сорвался и схватился за трассировщик ETW.

Этот пост написан как проверка скоростного блогинга. От момента нахождения проблемы и саркастичного твита о ней до публикации поста прошло примерно 90 минут.

Читать полностью »

image

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

Уровень производительности: чего мы хотели достичь

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

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

Мы твёрдо были уверены, что игра должна работать в 1080p с приличной частотой кадров даже на интегрированных графических картах, и саму по себе эту цель достичь было не так трудно: основным ограничивающим фактором является ЦП, особенно при увеличении объёмов больницы. Современные интегрированные видеокарты начинают испытывать проблемы только при разрешениях примерно от 2560 x 1440.

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

image

Пару месяцев назад мне наконец пришлось признать, что я недостаточно умён, чтобы пройти некоторые уровни головоломки Snakebird. Единственным способом вернуть себе часть самоуважения было написание солвера. Так я мог бы притвориться, что создать программу для решения головоломки — это почти то же самое, что и решить её самому. Код получившейся программы на C++ выложен на Github. Основная часть рассматриваемого в статье кода реализована в search.h и compress.h. В этом посте я в основном буду рассказывать об оптимизации поиска в ширину, который бы потребовал 50-100 ГБ памяти, чтобы он уместился в 4 ГБ.

Позже я напишу ещё один пост, в котором будет описана специфика игры. В этом посте вам нужно знать, что мне не удалось найти никаких хороших альтернатив грубому перебору (brute force), потому что ни один из привычных трюков не сработал. В игре множество состояний, потому что есть куча подвижных или толкаемых объектов, при этом важна форма некоторых из них, которая может меняться со временем. Не было никакой пригодной консервативной эвристики для алгоритмов наподобие A*, позволяющих сузить пространство поиска. Граф поиска был ориентированным и заданным неявно, поэтому одновременный поиск в прямом и обратном направлении оказался невозможным. Единственный ход мог изменить состояние множеством несвязанных друг с другом способов, поэтому не могло пригодиться ничего наподобие хеширования Зобриста.

Приблизительные подсчёты показали, что в самой большой головоломке после устранения всех симметричных положений будет порядка 10 миллиардов состояний. Даже после упаковки описания состояний с максимальной плотностью размер состояния составлял 8-10 байт. При 100 ГБ памяти задача оказалась бы тривиальной, но не для моей домашней машины с 16 ГБ памяти. А поскольку Chrome нужно из них 12 ГБ, мой настоящий запас памяти ближе к 4 ГБ. Всё, что будет превышать этот объём, придётся сохранять на диск (старый и ржавый винчестер).
Читать полностью »

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

… расходовать память или такты процессора на элементы в миллиардных объёмах — это нехорошо…

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

Немного контекста

Приложение iFunny имеет дело с колоссальным объёмом графического и видеоконтента, а нечёткий поиск дубликатов является одной из очень важных задач. Сама по себе это большая тема, заслуживающая отдельной статьи, но сегодня я просто немного расскажу о некоторых подходах к обсчёту очень больших массивов чисел, применительно к этому поиску. Конечно же, у всех разное понимание «очень больших массивов», и тягаться с Адронным коллайдером было бы глупо, но всё же. :)

Если совсем коротко про алгоритм, то для каждого изображения создаётся его цифровая подпись (сигнатура) из 968 целых чисел, а сравнение производится путем нахождения «расстояния» между двумя сигнатурами. Учитывая, что объём контента только за два последних месяца составил порядка 10 миллионов изображений, то, как легко прикинет в уме внимательный читатель, — это как раз те самые «элементы в миллиардных объёмах». Кому интересно — добро пожаловать под кат.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js