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

13

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

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

Аллан П. Энгсиг-Каруп
источник
Программы, которые пишут ученые, часто работают очень долго (например, симуляции). Время программиста и время работы компьютера могут быть сопоставимы. Это сильно отличается от сегодняшней «обычной» работы программиста. Как и на заре вычислительной техники, часто стоит потратить некоторые усилия (и время программиста), чтобы ускорить процесс моделирования, быстрее завершить его и выполнить работу быстрее.
Сабольч

Ответы:

15

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

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

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

Джед браун
источник
1
Совсем недавно я получил улучшение в 10 000 раз (для наших самых больших событий) во время выполнения ограничительного шага нашего анализа, просто заменяя алгоритм, который был O (n ^ 2) во времени и пространстве, на один O (n log n). ) в обоих. Имейте в виду, это означало еще одну зависимость и некоторую дополнительную сложность, но иногда это того стоит ...
dmckee --- котенок экс-модератора
1
Факторы ускорения (относящиеся к чему-либо) не слишком стоят того, чтобы иметь четкую ссылку на то, с чем вы сравнивались. Если вы сравните с плохой реализацией, основанной на неподходящем алгоритме, а затем измените, то, очевидно, было бы неоправданно ожидать больших относительных выгод.
Аллан П. Энгсиг-Каруп
1
@Allan: Если в одном изменении было в 10 000 раз больше, то, очевидно, это была неправильно выбранная реализация. Предыдущий код был поврежден как ненужным пространством, так и сложностью времени: производительность кэширования была ужасной. Но в том-то и дело, не так ли?
dmckee --- котенок экс-модератора
8

Как бы вы определили «оптимизировать»? Существует целый спектр от разработки лучших алгоритмов или вычислительных моделей до использования вручную настроенного ассемблера.

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

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

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

Pedro
источник
4

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

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

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

Пол
источник
4

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

Эмпирическое правило, как всегда, является известным правилом 80/20. В какой-то момент это просто не значит больше тратить все больше и больше времени на получение нескольких процентов (или меньше) времени работы. Но вам придется проанализировать.

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

Цитировать Дональда Кнута: «преждевременная оптимизация - корень всего зла». Так что профилируйте свой код, но не слишком скоро.

GertVdE
источник
Вы имеете в виду правило принципа Парето (80/20)? Если да, то имеете ли вы в виду, что мы должны сосредоточить усилия на оптимизации на 20% кода, который дает 80% замедления? Или вы имеете в виду, что если вы ожидаете ускорения только на 20%, то оптимизировать не стоит?
Павел
Нет, я использовал это только как принцип, а не 80/20. В какой-то момент времени вы потратите столько усилий, чтобы набрать всего несколько процентов, и это больше не стоит усилий.
GertVdE
3

Несколько дополнительных советов:

  1. Прежде чем выполнять какую-либо оптимизацию работающей программы, убедитесь, что у вас есть хороший набор тестовых примеров, которые помогают поддерживать целостность кода. Нет смысла быстрее получать неправильные результаты.
  2. Если ваша оптимизация делает код менее читабельным, сохраняйте исходную версию, по крайней мере, в форме комментария, но лучше в качестве альтернативной версии, которая будет выбрана во время компиляции и выполнения. Ваши потребности в оптимизации могут изменяться по мере развития ваших проблем и ваших машин, и исходный код может стать лучшей отправной точкой для оптимизации, которую вы будете выполнять через пять лет.
  3. Если ваша оптимизированная версия оказывает минимальное влияние, но делает код менее читабельным, менее универсальным или менее стабильным, вернитесь к исходной версии. Вы теряете больше, чем вы получаете.
khinsen
источник