Что касается эффективности, логическое сравнение с избыточной манипуляцией с памятью

Question

Что больше налогов? Является ли более эффективным включение в массив обмена элементами с условным оператором if для предотвращения избыточных обменов, например, обмена с самим собой?

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

Допустим, вы разрабатываете алгоритм и пытаетесь проверить эффективность: сравнивает или обменивается (например, сортировка вставкой).

if(condition)
   exchange two elements

Answer 1

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

По сути, если ваш ЦП сильно страдает от непредвиденного предсказания ветвлений, а перестановка элементов тривиальна, то имеет смысл отказаться от условного. однако, если ваша целевая архитектура ЦП может поддерживать достаточное количество предсказаний ошибок ветвления с слишком большой задержкой или стоимость замены элементов составляет , а не , то вы можете повысить производительность в зависимости от размера указанного массив. Вы также можете извлечь выгоду из использования инструкций, таких как MOVcc / CMPXCHG, или их аналогов, отличных от x86 (хотя в этой ситуации вам все равно потребуется чтение + сравнение, но при этом удаляется ветвление).

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

Answer 2

Полезный способ взглянуть на любой код оценки состояния, чтобы спросить: «Какова вероятность каждого результата?»

Например, есть тестовое выражение test, и вероятность егоЗначение true равно 1/100, тогда в среднем оно говорит вам очень мало для ваших вложений в процессорные циклы.

Фактически вы можете определить это количественно.Если это правда, то объем информации, которую вы узнали, довольно хорош.Примерно log2 (100/1) = 6,6 бит, но это происходит только 1 раз из 100.В остальных 99 раз объем информации, которую вы изучаете, составляет log2 (100/99) = 0,014 бит.Практически ничего.Так что такое состояние в среднем говорит вам очень мало.Это не «работает» очень усердно.

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

Это 6,6 * 1/100 + .014 * 99/100 = .066 + .014 = .08 бит, что очень плохо,(Это число называется энтропией решения.)

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

Так что, если вы беспокоитесь о выполнении условного теста (вы можете и не быть), попробуйте заставить его заработать свои циклы.