Я недавно давал интервью на Amazon. Во время сеанса кодирования интервьюер спросил, почему я объявил переменную в методе. Я объяснил свой процесс, и он предложил мне решить ту же проблему с меньшим количеством переменных. Например (это было не из интервью), я начал с метода A, а затем улучшил его до метода B, удалив int s
. Он был рад и сказал, что это уменьшит использование памяти этим методом.
Я понимаю логику, стоящую за этим, но мой вопрос:
Когда целесообразно использовать метод A против метода B, и наоборот?
Вы можете видеть , что метод А будет иметь более высокое использование памяти, так как int s
декларируется, но он имеет только выполнить один расчет, то есть a + b
. С другой стороны, метод B использует меньше памяти, но должен выполнить два вычисления, то есть a + b
дважды. Когда я использую одну технику над другой? Или один из методов всегда предпочтительнее другого? Что нужно учитывать при оценке двух методов?
Метод А:
private bool IsSumInRange(int a, int b)
{
int s = a + b;
if (s > 1000 || s < -1000) return false;
else return true;
}
Метод Б:
private bool IsSumInRange(int a, int b)
{
if (a + b > 1000 || a + b < -1000) return false;
else return true;
}
int s
то время как они полностью в порядке с этими магическими числами для верхних и нижних границ?Ответы:
Вместо того, чтобы рассуждать о том, что может или не может произойти, давайте просто посмотрим, не так ли? Мне придется использовать C ++, поскольку у меня нет удобного компилятора C # (хотя см. Пример C # от VisualMelon ), но я уверен, что одни и те же принципы применяются независимо.
Мы включим две альтернативы, с которыми вы столкнулись в интервью. Мы также включим версию, которая использует,
abs
как предлагается в некоторых ответах.Теперь скомпилируйте его без какой-либо оптимизации:
g++ -c -o test.o test.cpp
Теперь мы можем точно видеть, что это генерирует:
objdump -d test.o
Мы можем видеть из стековых адресов (например,
-0x4
inmov %edi,-0x4(%rbp)
против-0x14
inmov %edi,-0x14(%rbp)
), которыеIsSumInRangeWithVar()
используют 16 дополнительных байтов в стеке.Поскольку
IsSumInRangeWithoutVar()
в стеке не выделяется место для хранения промежуточного значения,s
оно должно пересчитать его, в результате чего эта реализация будет на 2 инструкции длиннее.Забавно,
IsSumInRangeSuperOptimized()
выглядит очень похожеIsSumInRangeWithoutVar()
, за исключением того, что сначала сравнивают -1000 и 1000 секунд.Теперь давайте компилировать только самые основные оптимизации:
g++ -O1 -c -o test.o test.cpp
. Результат:Вы посмотрите на это: каждый вариант идентичен . Компилятор может сделать что-то очень умное:
abs(a + b) <= 1000
эквивалентно тому, чтоa + b + 1000 <= 2000
анализsetbe
выполняет сравнение без знака, поэтому отрицательное число становится очень большим положительным числом.lea
Инструкция может фактически выполнять все эти дополнения в одной команде, и устранить все условные переходы.Чтобы ответить на ваш вопрос, почти всегда нужно оптимизировать не память или скорость, а читабельность . Чтение кода намного сложнее, чем его написание, а чтение кода, который был искажен для «оптимизации», намного сложнее, чем чтение кода, написанного для ясности. Чаще всего эти «оптимизации» оказываются незначительными, или, как в данном случае , практически нулевым фактическим влиянием на производительность.
Давайте измерим! Я переписал примеры на Python:
Запустите с Python 3.5.2, это приведет к выводу:
Разборка в Python не очень интересна, так как «компилятор» байт-кода мало что дает для оптимизации.
Производительность трех функций практически одинакова. Мы могли бы соблазниться,
IsSumInRangeWithVar()
потому что это незначительное увеличение скорости. Хотя я добавляю, когда я пробовал разные параметрыtimeit
, иногдаIsSumInRangeSuperOptimized()
получаюсь быстрее, поэтому я подозреваю, что причиной разницы могут быть внешние факторы, а не какое-либо внутреннее преимущество какой-либо реализации.Если это действительно критичный к производительности код, интерпретируемый язык просто очень плохой выбор. Запустив ту же программу с Pypy, я получаю:
Простое использование pypy, использующего JIT-компиляцию для устранения многих накладных расходов интерпретатора, привело к улучшению производительности на 1 или 2 порядка. Я был довольно шокирован, увидев, что
IsSumInRangeWithVar()
это на порядок быстрее, чем другие. Поэтому я изменил порядок тестов и снова запустил:Таким образом, кажется, что на самом деле это не что-то, что делает его быстрым, а порядок, в котором я делаю сравнительный анализ!
Я хотел бы углубиться в это, потому что, честно говоря, я не знаю, почему это происходит. Но я считаю, что суть была достигнута: микрооптимизации, такие как объявление промежуточного значения в качестве переменной или нет, редко актуальны. При использовании интерпретируемого языка или высоко оптимизированного компилятора первая цель по-прежнему заключается в написании понятного кода.
Если может потребоваться дальнейшая оптимизация, сравните результаты . Помните, что лучшая оптимизация получается не из мелких деталей, а из большей алгоритмической картины: pypy будет на порядок быстрее для повторной оценки той же функции, чем cpython, потому что он использует более быстрые алгоритмы (JIT-компилятор против интерпретации) для оценки программа. И есть также закодированный алгоритм: поиск по B-дереву будет быстрее, чем связанный список.
Убедившись , что вы используете правильные инструменты и алгоритмы для работы, быть готовым к погружению глубоко в детали системы. Результаты могут быть очень удивительными, даже для опытных разработчиков, и поэтому у вас должен быть эталон для количественной оценки изменений.
источник
Чтобы ответить на поставленный вопрос:
Есть две вещи, которые вы должны установить:
Чтобы ответить на первый вопрос, вы должны знать, каковы требования к производительности для вашего приложения. Если нет требований к производительности, то нет причин для оптимизации тем или иным способом. Требования к производительности помогут вам добраться до места «достаточно хорошо».
Метод, который вы предоставили сам по себе, не вызовет каких-либо проблем с производительностью сам по себе, но, возможно, в рамках цикла и обработки большого количества данных вам придется начать думать немного иначе о том, как вы подходите к проблеме.
Обнаружение того, что ограничивает приложение
Начните смотреть на поведение вашего приложения с монитором производительности. Следите за использованием процессора, диска, сети и памяти во время работы. Один или несколько предметов будут максимально использованы, в то время как все остальное используется умеренно - если только вы не достигнете идеального баланса, но это почти никогда не происходит).
Когда вам нужно посмотреть глубже, обычно вы используете профилировщик . Есть профайлеры памяти и процесс профайлеры , и они измеряют разные вещи. Процесс профилирования оказывает существенное влияние на производительность, но вы используете свой код, чтобы выяснить, в чем дело.
Допустим, вы видите, что ваш процессор и использование диска достигли пика Сначала вы должны проверить «горячие точки» или код, который либо вызывается чаще, чем остальные, либо занимает значительно более длительный процент обработки.
Если вы не можете найти какие-либо горячие точки, вы бы начали смотреть на память. Возможно, вы создаете больше объектов, чем необходимо, и ваша сборка мусора работает сверхурочно.
Восстановление производительности
Думай критически. Ниже приведен список изменений в порядке окупаемости инвестиций:
В подобных ситуациях вы должны применять научный метод. Придумайте гипотезу, внесите изменения и проверьте ее. Если вы достигаете своих целей производительности, все готово. Если нет, перейдите к следующей вещи в списке.
Отвечая на вопрос, выделенный жирным шрифтом:
Честно говоря, это последний шаг в попытке справиться с проблемами производительности или памяти. Влияние метода A против метода B будет действительно различным в зависимости от языка и платформы (в некоторых случаях).
Почти любой скомпилированный язык с наполовину приличным оптимизатором будет генерировать аналогичный код с любой из этих структур. Однако эти предположения не обязательно остаются верными в проприетарных и игрушечных языках, в которых нет оптимизатора.
То, что будет иметь лучшее влияние, зависит от того,
sum
является ли переменная стека или переменной кучи. Это выбор языковой реализации. Например, в C, C ++ и Java числовые примитивы, такие как a,int
являются переменными стека по умолчанию. Ваш код не оказывает большего влияния на память при назначении переменной стека, чем при полностью встроенном коде.Другие оптимизации, которые вы можете найти в библиотеках C (особенно в старых), где вы можете выбрать между копированием 2-мерного массива вниз или первым - это оптимизация, зависящая от платформы. Это требует определенных знаний о том, как выбранный вами чипсет лучше всего оптимизирует доступ к памяти. Есть тонкие различия между архитектурами.
Суть в том, что оптимизация - это сочетание искусства и науки. Это требует некоторого критического мышления, а также определенной гибкости в подходе к проблеме. Ищите большие вещи, прежде чем винить маленькие вещи.
источник
«это уменьшит память» - эм, нет. Даже если это будет правдой (а для любого приличного компилятора это не так), разница, скорее всего, будет незначительной для любой реальной ситуации.
Однако я бы рекомендовал использовать метод A * (метод A с небольшим изменением):
но по двум совершенно другим причинам:
давая переменной
s
объясняющее имя, код становится более понятнымв коде не используется дважды одна и та же логика суммирования, поэтому код становится более СУХИМЫМ, что означает меньше ошибок, подверженных изменениям.
источник
sum
переменной, что приведет к нулевому использованию памяти. И даже если нет, это всего лишь одно слово памяти в «листовом» методе. Учитывая, насколько невероятно бесполезной может быть потеря Java или C # из-за их ГХ и объектной модели, локальнаяint
переменная буквально не использует заметную память. Это бессмысленная микрооптимизация.sum
бы деталь реализации , и я сомневаюсь , что кто -то мог бы сделать убедительные доводы в отношении того или нет глупый трюк , как избежать один местныйint
приведет к тому или это количество использования памяти в долгосрочной перспективе. ИМО читабельность важнее. Читаемость может быть субъективной, но, FWIW, лично я бы предпочел, чтобы вы никогда не делали одни и те же вычисления дважды, не для использования процессора, а потому, что мне нужно проверять ваше добавление только один раз, когда я ищу ошибку.Вы можете сделать лучше, чем оба
Большинство процессоров (и, следовательно, компиляторов) могут выполнять abs () за одну операцию. У вас не только меньше сумм, но и меньше сравнений, которые, как правило, требуют больших вычислительных ресурсов. Он также удаляет разветвления, что намного хуже на большинстве процессоров, поскольку прекращает конвейерную обработку.
Интервьюер, как и другие ответы, говорит, что это растительная жизнь, и он не имеет никакого дела, проводящего техническое интервью.
Тем не менее, его вопрос действителен. И ответ на вопрос, когда вы оптимизируете и как, когда вы доказали, что это необходимо, и вы профилировали его, чтобы точно доказать, какие части нуждаются в этом . Известно, что Кнут говорит, что преждевременная оптимизация - это корень всего зла, потому что слишком легко попытаться найти ненужные разделы или внести изменения (как, например, ваш интервьюер), которые не имеют никакого эффекта, и при этом упустить места, которые действительно в этом нуждаются. Пока у вас нет веских доказательств, что это действительно необходимо, ясность кода является более важной целью.
Править FabioTurati правильно указывает, что это логический смысл, противоположный оригиналу (моя ошибка!), И что это иллюстрирует дальнейшее влияние цитаты Кнута, где мы рискуем взломать код, пытаясь его оптимизировать.
источник
a+b
вif
и делать это дважды. Вы понимаете это неправильно: «Он был доволен и сказал, что это уменьшит использование памяти этим методом», - он был добр к вам, скрывая свое разочарование этим бессмысленным объяснением памяти. Вы не должны относиться к этому серьезно, чтобы задать вопрос здесь. Вы получили работу? Я думаю, вы этого не сделали :-(abs()
, и у вас также есть одноreturn
, вместо одного, когда условие истинно ("if ветвь"), и еще одно, когда оно ложно ( "еще ветка"). Когда вы меняете код таким образом, будьте осторожны: есть риск непреднамеренного написания функции, которая возвращает true, когда она должна возвращать false, и наоборот. Что именно здесь и произошло. Я знаю, что вы сосредоточены на другом, и вы хорошо поработали над этим. Тем неadds
, и ARM имеет предикат reverse-sub (rsblt
= reverse-sub, если меньше), но все остальное требует нескольких дополнительных инструкций для реализацииabs(a+b)
илиabs(a)
. godbolt.org/z/Ok_Con показывает выходные данные asm для x86, ARM, AArch64, PowerPC, MIPS и RISC-V. Только преобразовав сравнение в проверку диапазона(unsigned)(a+b+999) <= 1998U
, gcc может оптимизировать его, как в ответе Фила.IsSumInRange(INT_MIN, 0)
. Исходный код возвращаетсяfalse
потому чтоINT_MIN+0 > 1000 || INT_MIN+0 < -1000
; но «новый и улучшенный» код возвращаетсяtrue
потому чтоabs(INT_MIN+0) < 1000
. (Или, в некоторых языках, онОборудование дешевое; Программисты стоят дорого . Так что затраты времени, потраченного вами на этот вопрос, вероятно, намного хуже, чем любой из ответов.
Несмотря на это, большинство современных компиляторов найдут способ оптимизировать локальную переменную в регистр (вместо выделения стекового пространства), поэтому методы, вероятно, идентичны с точки зрения исполняемого кода. По этой причине большинство разработчиков выбирают вариант, который наиболее четко передает намерение (см. Написание действительно очевидного кода (ROC) ). На мой взгляд, это будет метод А.
С другой стороны, если это чисто академическое упражнение, вы можете получить лучшее из обоих миров с помощью метода C:
источник
a+=b
это хитрый трюк, но я должен упомянуть (на случай, если это не подразумевается из остальной части ответа), из моих методов опыта, которые связываются с параметрами, может быть очень трудно отлаживать и поддерживать.if
проверку, но забыли отменить результат сравнения; Ваша функция теперь возвращается,true
когда неa + b
находится в диапазоне. Либо добавьте a к внешнему виду условия ( ), либо распределите инвертирующие тесты, чтобы получить Или для!
return !(a > 1000 || a < -1000)
!
return a <= 1000 && a >= -1000;
return -1000 <= a && a <= 1000;
<=
/>=
, а не<
/>
(с<
/>
, 1000 и -1000 рассматриваются как выходящие за пределы диапазона, исходный код обрабатывает их как находящиеся в диапазоне).Я бы оптимизировал для удобочитаемости. Метод X:
Небольшие методы, которые делают только одну вещь, но о которых легко рассуждать.
(Это личное предпочтение, мне нравится положительное тестирование вместо отрицательного, ваш исходный код фактически проверяет, находится ли значение за пределами диапазона.)
источник
a
иb
кnumber1
иnumber2
пособия читаемость в любом случае. Кроме того, ваше именование функций противоречиво: зачемIsSumInRange
жестко кодировать диапазон, еслиIsValueInRange
он принимает его в качестве аргументов?Короче говоря, я не думаю, что этот вопрос имеет большое значение в современных вычислениях, но с исторической точки зрения это интересное упражнение.
Ваш интервьюер, скорее всего, фанат Мистического Месяца Человека. В книге Фред Брукс утверждает, что программистам обычно нужны две версии ключевых функций в их наборе инструментов: версия, оптимизированная для памяти, и версия, оптимизированная для процессора. Фред основал это на своем опыте, связанном с разработкой операционной системы IBM System / 360, где машины могут иметь всего 8 килобайт оперативной памяти. В таких машинах память, необходимая для локальных переменных в функциях, потенциально может быть важной, особенно если компилятор не оптимизировал их эффективно (или если код был написан непосредственно на языке ассемблера).
В нынешнюю эпоху, я думаю, вам будет трудно найти систему, в которой наличие или отсутствие локальной переменной в методе будет иметь заметное значение. Чтобы значение переменной имело значение, метод должен быть рекурсивным с ожидаемой глубокой рекурсией. Даже тогда вполне вероятно, что глубина стека будет превышена, вызывая исключения переполнения стека до того, как сама переменная вызовет проблему. Единственный реальный сценарий, в котором это может быть проблемой, - это очень большие массивы, выделенные в стеке рекурсивным методом. Но это также маловероятно, так как я думаю, что большинство разработчиков дважды подумают о ненужных копиях больших массивов.
источник
После присваивания s = a + b; переменные a и b больше не используются. Следовательно, для s не используется память, если вы не используете полностью поврежденный компилятор; память, которая так или иначе использовалась для a и b, используется повторно.
Но оптимизация этой функции - полная чушь. Если бы вы могли сэкономить место, было бы, возможно, 8 байт во время работы функции (которая восстанавливается, когда функция возвращается), так что это абсолютно бессмысленно. Если бы вы могли сэкономить время, это были бы отдельные числа наносекунд. Оптимизация этого - пустая трата времени.
источник
Переменные типа локальных значений размещаются в стеке или (более вероятно, для таких небольших кусков кода) используют регистры в процессоре и никогда не видят ОЗУ. В любом случае они недолговечны и не о чем беспокоиться. Вы начинаете рассматривать использование памяти, когда вам нужно буферизовать или поставить в очередь элементы данных в коллекциях, которые могут быть как большими, так и долгосрочными.
Тогда это зависит от того, что вам нужно больше всего для вашего приложения. Скорость обработки? Время отклика? След памяти? Ремонтопригодность? Согласованность в дизайне? Все зависит от вас.
источник
stackalloc
и сейчасSpan<T>
. Возможно полезно в горячей точке, после профилирования. Кроме того, некоторые из документов вокруг структур подразумевают, что типы значений могут быть в стеке, в то время как ссылочные типы не будут. Во всяком случае, в лучшем случае вы могли бы избежать немного GC.Как уже говорили другие ответы, вам нужно подумать, для чего вы оптимизируете.
В этом примере я подозреваю, что любой приличный компилятор сгенерирует эквивалентный код для обоих методов, поэтому решение не повлияет на время выполнения или память!
Что же влияет на это читаемость кода. (Код предназначен для чтения людьми, а не только компьютерами.) Между этими двумя примерами нет большой разницы; когда все остальные вещи равны, я считаю краткость добродетелью, поэтому я, вероятно, выберу метод B. Но все остальные вещи редко бывают равными, и в более сложном случае в реальном мире это может иметь большой эффект.
Что нужно учитывать:
источник
Как указывалось во многих ответах, попытка настроить эту функцию с помощью современных компиляторов не будет иметь никакого значения. Оптимизатор, скорее всего, может найти лучшее решение (голосование за ответ, который показал код на ассемблере, чтобы доказать это!). Вы заявили, что код в интервью не совсем тот код, который вас просили сравнить, поэтому, возможно, реальный пример имеет немного больше смысла.
Но давайте еще раз посмотрим на этот вопрос: это вопрос интервью. Итак, реальная проблема в том, как вы должны ответить на это, если вы хотите попытаться получить работу?
Давайте также предположим, что интервьюер знает, о чем он говорит, и он просто пытается увидеть то, что вы знаете.
Я хотел бы отметить, что, игнорируя оптимизатор, первый может создать временную переменную в стеке, тогда как второй не будет, но будет выполнять вычисления дважды. Поэтому первый использует больше памяти, но работает быстрее.
Вы могли бы упомянуть, что в любом случае для вычисления результата может потребоваться временная переменная, чтобы сохранить результат (чтобы его можно было сравнивать), поэтому независимо от того, назовете ли вы эту переменную или нет, разница не будет.
Затем я бы упомянул, что в действительности код будет оптимизирован и, скорее всего, будет создан эквивалентный машинный код, поскольку все переменные являются локальными. Тем не менее, это зависит от того, какой компилятор вы используете (не так давно я смог получить полезное улучшение производительности, объявив локальную переменную как "final" в Java).
Вы могли бы упомянуть, что стек в любом случае живет на своей собственной странице памяти, поэтому, если ваша дополнительная переменная не вызвала переполнение стека страницей, в действительности она не будет выделять больше памяти. Если это действительно переполняет, это хотело бы полностью новую страницу все же.
Я хотел бы упомянуть, что более реалистичным примером может быть выбор - использовать ли кэш для хранения результатов многих вычислений или нет, и это подняло бы вопрос о процессоре против памяти.
Все это показывает, что вы знаете, о чем говорите.
Я бы оставил это до конца, чтобы сказать, что было бы лучше сосредоточиться на читабельности вместо этого. Хотя в данном случае это правда, в контексте интервью это можно интерпретировать как «я не знаю о производительности, но мой код читается как история Джанет и Джона ».
Чего вам не следует делать, так это выдвигать обычные мягкие заявления о том, что оптимизация кода не нужна, не оптимизируйте, пока вы не профилируете код (это просто означает, что вы не видите плохой код для себя), аппаратные средства стоят дешевле, чем программисты и, пожалуйста, пожалуйста, не цитируйте Кнута "преждевременно бла-бла ...".
Производительность кода является серьезной проблемой во многих организациях, и многим организациям нужны программисты, которые понимают это.
В частности, в таких организациях, как Amazon, часть кода имеет огромное влияние. Фрагмент кода может быть развернут на тысячах серверов или миллионах устройств и может вызываться миллиарды раз в день каждый день в году. Там могут быть тысячи подобных фрагментов. Разница между плохим и хорошим алгоритмом может легко быть в тысячу раз больше. Сделайте числа и умножьте все это: это имеет значение. Потенциальные затраты на организацию неработающего кода могут быть очень значительными или даже фатальными, если система исчерпает свои ресурсы.
Кроме того, многие из этих организаций работают в конкурентной среде. Таким образом, вы не можете просто сказать своим клиентам, чтобы они покупали больший компьютер, если программное обеспечение вашего конкурента уже работает нормально на оборудовании, которое у них есть, или если программное обеспечение работает на мобильном телефоне, и его невозможно обновить. Некоторые приложения особенно критичны по производительности (на ум приходят игры и мобильные приложения) и могут жить или умирать в зависимости от их скорости отклика или скорости.
Лично я более двух десятилетий работал над многими проектами, в которых системы выходили из строя или не могли работать из-за проблем с производительностью, и меня вызвали для оптимизации этих систем, и во всех случаях это было из-за плохого кода, написанного программистами, которые не понимали влияние того, что они писали. Более того, это никогда не один кусок кода, это всегда везде. Когда я появляюсь, уже поздно думать о производительности: ущерб уже нанесен.
Понимание производительности кода - это хороший навык, который нужно иметь так же, как понимание правильности кода и стиля кода. Это выходит из практики. Сбои производительности могут быть такими же плохими, как и функциональные сбои. Если система не работает, она не работает. Неважно, почему. Точно так же производительность и функции, которые никогда не используются, являются плохими.
Поэтому, если интервьюер спрашивает вас об эффективности, я бы порекомендовал попробовать и продемонстрировать как можно больше знаний. Если вопрос кажется плохим, вежливо укажите, почему вы считаете, что в этом случае это не будет проблемой. Не цитируйте Кнута.
источник
Вы должны сначала оптимизировать для правильности.
Ваша функция не работает для входных значений, близких к Int.MaxValue:
Это возвращает истину, потому что сумма переполняется до -400. Функция также не работает для a = int.MinValue + 200. (неверно добавляет до «400»)
Мы не узнаем, что искал интервьюер, пока он или она не вмешаются, но «переполнение реально» .
В ситуации интервью задайте вопросы, чтобы прояснить суть проблемы: каковы допустимые максимальные и минимальные входные значения? Если у вас есть такие данные, вы можете выдать исключение, если вызывающая сторона отправляет значения за пределы диапазона. Или (в C #) вы можете использовать проверенный раздел {}, который может вызвать исключение при переполнении. Да, это сложнее и сложнее, но иногда это то, что нужно.
источник
Ваш вопрос должен был звучать так: «Нужно ли вообще это оптимизировать?».
Версии A и B отличаются одной важной деталью, которая делает A предпочтительным, но это не связано с оптимизацией: вы не повторяете код.
Фактическая «оптимизация» называется устранением общих подвыражений, что делает почти каждый компилятор. Некоторые выполняют эту базовую оптимизацию, даже когда оптимизации отключены. Так что это не совсем оптимизация (сгенерированный код почти наверняка будет одинаковым в любом случае).
Но если это не оптимизация, то почему это предпочтительнее? Хорошо, вы не повторяете код, кого это волнует!
Ну, во-первых, у вас нет риска случайно получить половину условного предложения неправильно. Но что еще более важно, кто-то, читающий этот код, может сразу поймать то, что вы пытаетесь сделать, вместо
if((((wtf||is||this||longexpression))))
опыта. Читатель увидитif(one || theother)
, что это хорошо. Не редко случается так, что вы - тот человек, который читает ваш собственный код три года спустя и думает: «WTF это значит?». В этом случае всегда полезно, если ваш код немедленно сообщает о намерении. При правильном названии общего подвыражения это так.Кроме того, если в любое время в будущем вы решите, что, например, вам нужно перейти
a+b
наa-b
, вы должны изменить одинместо, а не два. И нет никакого риска (снова) ошибиться с ошибкой второго.Что касается вашего фактического вопроса, что вы должны оптимизировать, прежде всего ваш код должен быть правильным . Это абсолютно самая важная вещь. Неправильный код - это плохой код, тем более, что, несмотря на то, что он некорректен, он «работает нормально» или, по крайней мере, выглядит так, как будто он работает нормально. После этого код должен быть читаемым (читаемым кем-то незнакомым с ним).
Что касается оптимизации ... никто, конечно, не должен намеренно писать антиоптимизированный код, и, конечно, я не говорю, что вам не следует задумываться над дизайном, прежде чем начать (например, выбор правильного алгоритма для задачи, не менее эффективный).
Но для большинства приложений большую часть времени производительность, которую вы получаете после выполнения корректного, читаемого кода с использованием разумного алгоритма с помощью оптимизирующего компилятора, просто прекрасна, и в этом нет особой необходимости беспокоиться.
Если это не так, т. Е. Если производительность приложения действительно не соответствует требованиям, и только в этом случае вам следует беспокоиться о такой локальной оптимизации, как та, которую вы пытались выполнить. Предпочтительно, однако, вы бы пересмотрели алгоритм верхнего уровня. Если вы вызываете функцию 500 раз вместо 50 000 раз из-за лучшего алгоритма, это оказывает большее влияние, чем сохранение трех тактов на микрооптимизацию. Если вы не останавливаетесь в течение нескольких сотен циклов при произвольном доступе к памяти все время, это имеет большее влияние, чем выполнение нескольких дешевых дополнительных вычислений и т. Д. И т. Д.
Оптимизация - это сложный вопрос (вы можете написать об этом целые книги и не дойти до конца), и тратить время на слепую оптимизацию определенного места (даже не зная, является ли это узким местом вообще!), Обычно зря. Без профилирования очень трудно получить правильную оптимизацию.
Но, как правило, когда вы летите вслепую и просто хотите / хотите что- то сделать , или в качестве общей стратегии по умолчанию, я бы предложил оптимизировать для «памяти».
Оптимизация под «память» (в частности, пространственную локальность и шаблоны доступа) обычно дает преимущество, потому что в отличие от когда-то, когда все было «примерно одинаково», в настоящее время доступ к ОЗУ является одной из самых дорогих вещей (не считая чтения с диска!) что вы в принципе можете сделать. В то время как ALU, с другой стороны, дешев и становится быстрее с каждой неделей. Пропускная способность и задержка памяти улучшаются не так быстро. Хорошая локальность и хорошие шаблоны доступа могут легко изменить 5-кратную разницу (20-кратное в экстремальных, надуманных примерах) во время выполнения по сравнению с плохими шаблонами доступа в приложениях с большим объемом данных. Будьте добры к своим тайникам, и вы станете счастливым человеком.
Чтобы рассмотреть предыдущий абзац в перспективе, подумайте, сколько стоят разные вещи, которые вы можете сделать. Выполнение чего-то подобного
a+b
занимает (если не оптимизировано) один или два цикла, но ЦП обычно может запускать несколько инструкций за цикл и может передавать независимые инструкции, так что более реалистично это будет стоить вам примерно половину цикла или меньше. В идеале, если компилятор хорош в планировании и в зависимости от ситуации, он может стоить ноль.Извлечение данных («память») обходится вам либо в 4-5 циклов, если вам повезет, и это в L1, и примерно в 15 циклов, если вам не так повезло (попадание в L2). Если данные вообще не находятся в кэше, это занимает несколько сотен циклов. Если ваш шаблон случайного доступа превышает возможности TLB (это легко сделать всего за ~ 50 записей), добавьте еще несколько сотен циклов. Если ваш шаблон случайного доступа действительно вызывает ошибку страницы, в лучшем случае это будет стоить вам несколько десятков тысяч циклов, а в худшем - несколько миллионов.
Теперь подумайте, что вы хотите избежать срочно?
источник
После получения функциональности право первого . Тогда избирательность касается микрооптимизаций.
В качестве вопроса об оптимизации кода код вызывает обычную дискуссию, но не достигает цели более высокого уровня: является ли код функционально правильным?
И C ++, и C, и другие считают
int
переполнение проблемой изa + b
. Это не очень хорошо определено, и C называет это неопределенным поведением . Не указывается «обтекание» - хотя это обычное поведение.IsSumInRange()
Ожидается, что такая вызываемая функция будет хорошо определена и будет работать правильно для всехint
значенийa,b
. Сырьеa + b
нет. Решение переменного тока может использовать:Выше код может быть оптимизирован с помощью более широкого , чем целочисленный тип
int
, если таковые имеются, как показано ниже , или распределяяsum > N
,sum < -N
тесты в пределахif (a >= 0)
логики. Тем не менее, такая оптимизация может не привести к «более быстрому» испускаемому коду при использовании умного компилятора, и не стоит того, чтобы быть умным.Даже использование
abs(sum)
склонно к проблемам, когдаsum == INT_MIN
.источник
О каких компиляторах идет речь, и что за «память»? Потому что в вашем примере, при условии разумного оптимизатора, выражение
a+b
должно обычно храниться в регистре (форме памяти) перед выполнением такой арифметики.Так что, если мы говорим о тупом компиляторе, который встречается
a+b
дважды, он выделит больше регистров (памяти) во втором примере, потому что ваш первый пример может просто сохранить это выражение один раз в одном регистре, сопоставленном с локальной переменной, но мы Сейчас мы говорим об очень глупых компиляторах ... если только вы не работаете с другим типом глупых компиляторов, стек которых разливает каждую переменную повсеместно, и в этом случае, возможно, первая из них приведет к большему сожалению для оптимизации, чем секунда*.Все это чрезвычайно спекулятивно, довольно глупо, без измерений / разборки и даже в худшем случае, это не случай «память против производительности» (потому что даже среди худших оптимизаторов, о которых я могу думать, мы не говорим о чем угодно, кроме временной памяти, такой как стек / регистр), это в лучшем случае чисто «производительность», и среди любого разумного оптимизатора два эквивалентны, и если один не использует разумный оптимизатор, почему так мало внимания уделяется оптимизации, которая носит микроскопический характер и особенно отсутствуют измерения? Это похоже на фокус на уровне ассемблера выбора инструкций / выделения регистров, который я бы никогда не ожидал, что кто-то, желающий оставаться продуктивным, будет иметь, например, использование интерпретатора, стек которого проливает все.
Что касается этого вопроса, если я могу заняться этим более широко, часто я не нахожу два диаметрально противоположных. Особенно, если ваши шаблоны доступа являются последовательными и с учетом скорости кэш-памяти ЦП, часто уменьшение количества байтов, обрабатываемых последовательно для нетривиальных входных данных, приводит (до некоторой степени) к более быстрой обработке этих данных. Конечно, существуют переломные моменты, когда, если данные намного, намного меньше в обмен на путь, куда больше инструкций, может быть быстрее обрабатывать последовательно в более крупной форме в обмен на меньшее количество инструкций.
Но я обнаружил, что многие разработчики склонны недооценивать, насколько сокращение использования памяти в таких случаях может привести к пропорциональному сокращению времени, затрачиваемого на обработку. Очень по-человечески интуитивно понятно переводить затраты на производительность в инструкции, а не в доступ к памяти до точки достижения больших LUT в какой-то тщетной попытке ускорить некоторые небольшие вычисления, только чтобы обнаружить, что производительность снижается при дополнительном доступе к памяти.
Для случаев последовательного доступа через некоторый огромный массив (не говоря о локальных скалярных переменных, как в вашем примере), я придерживаюсь правила, что меньшее количество памяти для последовательной передачи данных преобразуется в более высокую производительность, особенно когда результирующий код проще, чем иначе, до тех пор, пока он не До тех пор, пока мои измерения и профилировщик не скажут мне иначе, и это имеет значение, точно так же, как я предполагаю, что последовательное чтение меньшего двоичного файла на диске будет быстрее проходить, чем больший (даже если меньший требует больше инструкций до тех пор, пока это предположение не будет больше применяться в моих измерениях.
источник