Эффекты предсказания ветвлений на производительности?
Вам не нужно проверять на 0 или 1 при запуске (поскольку цикл for уже имеет условие i<len и будет ложным как для 0, так и для 1), но вам нужно переместить return true из петля. Вы не знаете, что он отсортирован, пока не сравните все элементы:
for(int i=1; i<len; ++i) {
if(sArr[i-1] > sArr[i]) return false;
}
return true;
6 ответов
Если мы - вне "ранней оптимизации" фаза, то, конечно, мы вне, "Я могу измерить ту" фазу также? С сумасшедшими сложностями современной архитектуры ЦП единственный способ знать наверняка состоит в том, чтобы попробовать его и мера. Конечно, не может быть то, что много обстоятельств, где у Вас будет выбор двух способов реализовать что-то, один из которых требует ответвления и того, которое не делает.
Предсказание ветвлений довольно чинят хорошее в эти дни. Но это не означает, что штраф ответвлений может быть устранен.
В типичном коде, Вы, вероятно, выздоравливаете более чем 99%-е корректные прогнозы, и все же хит производительности может все еще быть значительным. Существует несколько факторов в действии в этом.
Каждый - простая задержка ответвления. На общем ПК ЦП, который мог бы быть в порядке 12 циклов для mispredict или 1 цикла для правильно предсказанного ответвления. Ради аргумента давайте предположим, что все Ваши ответвления правильно предсказаны, затем Вы дома свободные, правильно? Не совсем.
простое существование ответвления запрещает большую оптимизацию. Компилятор не может переупорядочить код эффективно через ответвления. В базисном блоке (то есть, блок кода, который выполняется последовательно, без ответвлений, одной точки входа и одного выхода), это может переупорядочить инструкции, как этому нравится, пока значение кода сохраняется, потому что они будут все выполняться рано или поздно. Через ответвления это становится более хитрым. Мы могли спустить эти инструкции выполниться после этого ответвления, но затем как мы гарантируем, что они выполняются? Поместите их в оба ответвления? Это - дополнительный размер кода, это грязно также, и он не масштабируется, если мы хотим переупорядочить больше чем через одно ответвление.
Ответвления могут все еще быть дорогими, даже с лучшим предсказанием ветвлений. Не только из-за mispredicts, но и потому что планирование инструкции становится настолько более трудным.
Это также подразумевает, что, а не количество ответвлений, важный фактор - то, сколько кода входит в блок между ними. Ответвление по любой строке плохо, но если можно получить дюжину строк в блок между ответвлениями, вероятно, возможно запланировать те инструкции обоснованно хорошо, таким образом, ответвление не ограничит ЦП или компилятор слишком много.
, Но в типичном коде, ответвления являются чрезвычайно бесплатными. В типичном коде, нет что много ответвлений, кластеризируемых тесно вместе в критическом по отношению к производительности коде.
" (Ради обсуждения, предположите, что я вне "ранней оптимизации, корень всей злой" фазы)",
Превосходный. Затем можно представить производительность приложения, использовать теги gcc, чтобы сделать прогноз и профиль снова, использовать теги gcc для создания противоположного прогноза и профиля снова.
Теперь воображают теоретически ЦП, который выбирает оба пути ответвления с упреждением. И для последующего, если операторы в обоих путях, это выберет четыре пути с упреждением, и т.д. ЦП волшебно не выращивает четыре раза пространство кэша, таким образом, это собирается выбрать более короткую часть с упреждением каждого пути, чем это сделало бы для единственного пути.
при нахождении половины упреждающих выборок потраченной впустую потеря говорит, что 5% процессорного времени, затем Вы действительно хотите искать решение, которое не переходит.
Не точно ответ, но можно найти здесь , апплет демонстрирует конечный автомат, часто используемый для основанного на таблице предсказания ветвлений в современных микропроцессорах .
, Это иллюстрирует использование дополнительная логика для генерации быстрого (но возможно неправильно) оценка для условия ответвления и целевого адреса.
процессор выбирает и выполняет предсказанные инструкции в полной скорости, но должен вернуться все промежуточные результаты, когда прогноз складывается к тому, чтобы быть неправильно.
Мой ответ:
причина AMD был столь же быстрым или лучше, чем Intel в некоторых точках является прошлым, просто, что у них было лучшее предсказание ветвлений.
, Если Ваш код не имеет никакого предсказания ветвлений, (Значение его не имеет никаких ответвлений), затем он, как могут ожидать, будет работать быстрее.
Так, заключение: избегайте ответвлений, если они не необходимы. Если они, попытайтесь сделать его так, чтобы одно ответвление было оценено 95% времени.
Одна вещь, которую я недавно нашел (на DSP TI), это, стараясь избегать ответвлений может иногда генерировать больше кода, чем стоимость предсказания ветвлений.
у меня было что-то как следующее в жестком цикле:
if (var >= limit) { otherVar = 0;}
я хотел избавиться от потенциального ответвления и пытался изменить его на:
otherVar *= (var<limit)&1;
, Но 'оптимизация' генерировал вдвое больше блока и был на самом деле медленнее.