Стратегии оптимизации производительности последней инстанции [закрыто]

Брось больше оборудования на это!

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

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

Несколько примеров:

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

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

Сказать невозможно. Это зависит от того, как выглядит код. Если мы можем предположить, что код уже существует, то мы можем просто взглянуть на него и выяснить, как его оптимизировать.

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

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

Ну, и «Покажите код на SO и попросите совета по оптимизации для этого конкретного фрагмента кода».

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

Если лучшее оборудование - вариант, то определенно сделайте это. В противном случае

• Убедитесь, что вы используете лучшие параметры компилятора и компоновщика.
• Если подпрограмма точки доступа находится в библиотеке, отличной от часто вызывающей, подумайте о перемещении или клонировании ее в модуль вызывающих абонентов. Устраняет часть накладных расходов на вызовы и может улучшить попадание в кеш (см., Как AIX статически связывает strcpy () с отдельно связанными общими объектами). Это, конечно, может также уменьшить попадание в кэш, поэтому стоит принять одну меру.
• Посмотрите, есть ли возможность использовать специализированную версию подпрограммы точки доступа. Обратной стороной является необходимость поддержки нескольких версий.
• Посмотрите на ассемблер. Если вы думаете, что это может быть лучше, подумайте, почему компилятор не понял этого, и как вы могли бы помочь компилятору.
• Подумайте: вы действительно используете лучший алгоритм? Это лучший алгоритм для вашего входного размера?

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

• Когда доходит до того, что вы используете эффективные алгоритмы, возникает вопрос, что вам нужно больше скорости или памяти . Используйте кэширование, чтобы «заплатить» за память за большую скорость, или используйте вычисления, чтобы уменьшить объем памяти.
• Если возможно (и более рентабельно), решите проблему с помощью оборудования - более быстрый процессор, больше памяти или HD может решить проблему быстрее, чем пытаться ее кодировать.
• Используйте распараллеливание , если возможно - запустите часть кода в нескольких потоках.
• Используйте правильный инструмент для задания . некоторые языки программирования создают более эффективный код, используя управляемый код (например, Java /. NET) ускоряют разработку, но собственные языки программирования создают более быстрый код.
• Микрооптимизация . Только тогда, когда можно было использовать оптимизированную сборку для ускорения небольших фрагментов кода, использование SSE / векторной оптимизации в нужных местах может значительно повысить производительность.

• Встроенные подпрограммы (исключение вызова / возврата и нажатия параметров)
• Попробуйте исключить тесты / переключатели с помощью поиска в таблице (если они быстрее)
• Разверните циклы (устройство Даффа) до точки, в которой они просто поместятся в кеш-память ЦП
• Локализуйте доступ к памяти, чтобы не взорвать ваш кеш
• Локализовать связанные вычисления, если оптимизатор этого еще не делает.
• Исключить инварианты цикла, если оптимизатор еще этого не делает

Вам, вероятно, следует рассмотреть «перспективу Google», то есть определить, как ваше приложение может стать в значительной степени распараллеленным и параллельным, что неизбежно в какой-то момент также будет означать, что вам нужно будет рассмотреть возможность распределения вашего приложения на разных машинах и сети, так что он может идеально масштабироваться почти линейно с оборудованием, которое вы ему используете.

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

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

Я думаю, это уже было сказано по-другому. Но когда вы имеете дело с алгоритмом, интенсивно использующим процессор, вам следует упростить все внутри самого внутреннего цикла за счет всего остального.

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

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

Предложения:

• Предварительное вычисление, а не повторное вычисление : любые циклы или повторяющиеся вызовы, которые содержат вычисления с относительно ограниченным диапазоном входных данных, рассмотрите возможность поиска (массив или словарь), который содержит результат этого вычисления для всех значений в допустимом диапазоне входных данных. Затем используйте вместо этого простой поиск внутри алгоритма.
  Недостатки : если на самом деле используется несколько предварительно вычисленных значений, это может усугубить ситуацию, также поиск может занять значительную часть памяти.
• Дон ' • использовать библиотечные методы : необходимо написать большинство библиотек для правильной работы в широком диапазоне сценариев и выполнения нулевых проверок параметров и т. д. Повторно реализовав метод, вы сможете избавиться от большого количества логики это не относится к конкретным обстоятельствам, в которых вы его используете.
  Минусы : написание дополнительного кода означает большую поверхность для ошибок.
• Действительно используйте библиотечные методы : чтобы противоречить себе, языковые библиотеки пишут люди, которые намного умнее вас или меня ; скорее всего, они сделали это лучше и быстрее. Не выполняйте его самостоятельно, если вы не можете сделать это быстрее (например: всегда измерять!)
• Чит : в некоторых случаях, хотя для вашей проблемы может существовать точный расчет, вам может не понадобиться «точное», иногда приближение может быть «достаточно хорошим» и намного быстрее в сделке. Спросите себя, действительно ли имеет значение, если ответ отклоняется на 1%? 5%? даже 10%?
  Минусы : Ну ... ответ не будет точным.

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

• Cache misses . Кэш данных - источник остановок №1 в большинстве программ. Повышение коэффициента попадания в кэш за счет реорганизации структур данных, вызывающих нарушение, для обеспечения лучшей локализации; упаковать структуры и числовые типы, чтобы исключить потраченные впустую байты (и, следовательно, бесполезные выборки кеша); по возможности предварительно выбирайте данные для уменьшения простоев.
• Загрузка-попадание-хранилище . Предположения компилятора о псевдониме указателя и случаи, когда данные перемещаются между отключенными наборами регистров через память, могут вызвать определенное патологическое поведение, которое приводит к очистке всего конвейера ЦП при операции загрузки. Найдите места, где поплавки, векторы и целые числа сбрасываются друг с другом, и устраните их. Используйте __ restrict , чтобы пообещать компилятору использовать псевдонимы.
• Микрокодированные операции . У большинства процессоров есть некоторые операции, которые нельзя конвейерно обработать, вместо этого они запускают крошечную подпрограмму, хранящуюся в ПЗУ. Примеры на PowerPC: целочисленное умножение, деление и сдвиг на величину переменной. Проблема в том, что весь конвейер останавливается во время выполнения этой операции. Постарайтесь исключить использование этих операций или, по крайней мере, разбить их на составляющие конвейерные операции, чтобы вы могли воспользоваться преимуществами суперскалярной диспетчеризации независимо от того, что делает остальная часть вашей программы.
• Ветвь неверно предсказывает . Они тоже опустошают трубопровод. Найдите случаи, когда ЦП тратит много времени на перезаправку канала после разветвления, и используйте подсказку ветвления, если она доступна, чтобы заставить его чаще предсказывать правильно. Или еще лучше, замените ветки условными перемещениями везде, где это возможно, особенно после операций с плавающей запятой, потому что их канал обычно глубже и чтение флагов условий после fcmp может вызвать остановку.
• Последовательные операции с плавающей запятой . Сделайте эти SIMD.

И еще кое-что, что мне нравится делать:

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

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

Избегайте курсоров в большинстве баз данных. Также избегайте зацикливания. В большинстве случаев доступ к данным должен быть основан на наборах, а не на записи путем обработки записей. Это включает в себя отказ от повторного использования одной хранимой процедуры, если вы хотите вставить 1 000 000 записей за один раз.

Никогда не используйте select *, возвращайте только те поля, которые вам действительно нужны. Это особенно верно, если есть какие-либо соединения, так как поля соединения будут повторяться и, таким образом, вызывать ненужную нагрузку как на сервер, так и на сеть.

Избегайте использования коррелированных подзапросов. Используйте объединения (включая соединения с производными таблицами, где это возможно) (я знаю, что это верно для Microsoft SQL Server, но проверьте совет при использовании другой серверной части).

Index, index, index. И обновите эту статистику, если применимо к вашей базе данных.

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

Используйте правильные типы данных. Быстрее выполнять математические вычисления даты в поле даты, чем пытаться преобразовать строковый тип данных в тип данных даты, а затем производить вычисления.

Никогда не помещайте какой-либо цикл в триггер!

Большинство баз данных есть способ проверить, как будет выполняться запрос. В Microsoft SQL Server это называется планом выполнения. Сначала проверьте их, чтобы увидеть, где находятся проблемные места.

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

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

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

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

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

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

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

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

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

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

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

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

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

• What hardware are you running on? Can you use platform-specific optimizations (like vectorization)?
• Can you get a better compiler? E.g. switch from GCC to Intel?
• Can you make your algorithm run in parallel?
• Can you reduce cache misses by reorganizing data?
• Can you disable asserts?
• Micro-optimize for your compiler and platform. In the style of, "at an if/else, put the most common statement first"

Дополнительные предложения:

• Избегайте ввода-вывода : Любой ввод-вывод (диск, сеть, порты и т. Д.) всегда будет намного медленнее, чем любой другой выполнение вычислений, поэтому избавьтесь от любых операций ввода-вывода, которые вы делаете не обязательно.

• Переместить ввод-вывод вперед : загрузить все данные, которые вы собираетесь для предварительного расчета, чтобы вы не повторялись ожидания ввода-вывода в ядре критического алгоритма (и, возможно, в результате повторных поисков диска, когда загрузка всех данных в одно обращение может избежать поиска).

• Delay I / O : не записывайте свои результаты, пока расчет окончен, сохраните их в структуре данных и затем выбросьте это за один присест в конце, когда тяжелая работа готово.

• Потоковый ввод-вывод : Для тех, кто достаточно смел, объедините "ввод-вывод" up-front 'или' Delay I / O 'с фактическим вычислением перевод загрузки в параллельный поток, так что пока вы загружаете больше данных, над которыми можете работать данные, которые у вас уже есть, или пока вы рассчитываете следующий пакет данных вы можете одновременно выписывать результаты из последней партии.

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

Это эффекты, которыми вам нужно управлять. Иногда с помощью микроуправления вашим кодом, но иногда с помощью внимательного рассмотрения и рефакторинга.

Во многих комментариях уже упоминается код, дружественный к кешу. У этого есть как минимум два различных варианта:

• Избегать задержек при выборке из памяти.
• Снижение нагрузки на шину памяти (пропускная способность).

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

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

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

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

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

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

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

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

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

Последние несколько% очень сильно зависят от процессора и приложений ....

• Архитектура кеша различается, некоторые чипы имеют встроенную оперативную память вы можете отображать напрямую, ARM (иногда) имеют вектор unit, SH4 - полезный матричный код операции. Есть ли графический процессор - возможно, шейдер - это лучший вариант. TMS320 очень чувствительны к ветвям внутри петель (поэтому отдельные петли и переместите условия на улицу, если возможно).

Список можно продолжить ... Но такие вещи действительно последнее средство ...

Выполните сборку для x86 и запустите Valgrind / Cachegrind против кода. для правильного профилирования производительности. Или Texas Instruments ' CCStudio имеет прекрасный профилировщик. Тогда вы действительно узнаете, где сфокусироваться ...

Настройка ОС и фреймворка.

Это может показаться излишним, но подумайте об этом так: операционные системы и фреймворки предназначены для многих вещей . Ваше приложение делает только очень специфические вещи. Если бы вы могли заставить ОС выполнять именно то, что нужно вашему приложению, и ваше приложение понимало, как работает фреймворк (php, .net, java), вы могли бы намного лучше использовать свое оборудование.

Facebook, например, изменил некоторые элементы уровня ядра в Linux, изменил принцип работы memcached (например, они написали прокси-сервер memcached, а использовали udp вместо tcp ).

Другой пример - Window2008. У Win2K8 есть версия, в которой вы можете установить только базовую ОС, необходимую для запуска X-приложений (например, веб-приложений, серверных приложений). Это снижает значительную часть накладных расходов, которые ОС несет на запущенных процессах, и дает вам лучшую производительность.

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

Кэширование! Дешевый способ (с точки зрения программиста) сделать что-либо быстрее - это добавить уровень абстракции кэширования в любую область перемещения данных вашей программы. Будь то ввод / вывод или просто передача / создание объектов или структур. Часто легко добавить кеши к заводским классам и читателям / писателям.

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

The google way is one option "Cache it.. Whenever possible don't touch the disk"

Разделяй и властвуй

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

Такой общий оператор невозможен, это зависит от проблемной области. Некоторые возможности:

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

• Найдите вызовы, которые блокируют (база данных, сетевой жесткий диск, обновление дисплея), и изолируйте их и / или поместите в поток.

Если вы использовали базу данных, и это был Microsoft SQL Server:

• изучите директивы nolock и rowlock. (На этом форуме есть темы.)

ЕСЛИ ваше приложение является чисто вычислительным, вы можете посмотреть на этот мой вопрос об оптимизации кеша для поворота больших изображений. Увеличение скорости ошеломило меня.

Это долгий путь, но, возможно, он дает представление, особенно если ваша проблема связана с визуализацией: Rotating-bitmap-in-code

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

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

На языке с шаблонами (C ++ / D) вы можете попробовать распространять значения констант через аргументы шаблона. Вы можете сделать это даже для небольших наборов не совсем постоянных значений с помощью переключателя.

Foo(i, j); // i always in 0-4.

становится

switch(i)
{
    case 0: Foo<0>(j); break;
    case 1: Foo<1>(j); break;
    case 2: Foo<2>(j); break;
    case 3: Foo<3>(j); break;
    case 4: Foo<4>(j); break;
}

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