Проверка условного значения и установка переменной несколько раз; низкоуровневая оптимизация

Question

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

Например (псевдо-код):

bool found = false; 
for(particle in literallyAHaystack) { 
    bool isNeedle = particle == "needle"; 

    if(isNeedle) { 
     found = true; 
    } 

    // [some code that uses the 'found' variable] 

    if(isNeedle) { 
     found = false; 
    } 
} 

против

bool found = false; 
for(particle in literallyAHaystack) { 
    bool isNeedle = particle == "needle"; 

    if(isNeedle) { 
     found = true; 
    } 

    // [some code that uses the 'found' variable] 

    found = false; // a conditional no longer surrounds this statement 
} 

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

Answer 1

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

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

---

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

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

Более подробную информацию о такого рода вещи на x86 см http://agner.org/optimize/ и другие ссылки в x86 тегов вики.

Чтобы увидеть, как ваш код компилируется, поставить его на http://gcc.godbolt.org/ (и использовать O3 -march=haswell -ffast-math или что-то.)

---

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

Я представляю флаг, который является частью общей структуры состояния (используется кодом в критическом разделе, защищенном блокировкой), который могут использовать разные потоки.(Это был бы ужасный дизайн в этом случае, однако, поскольку found всегда остается false после использования, поэтому нет постоянного состояния, поэтому оно должно быть локальным.)

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

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

например. при векторизации иногда бывает полезно дублировать хранилища для адресата, если вы хотите записать 3 элемента вектора вместо всех 4, и это нормально писать за пределами того, что вы храните. например в this code.

Answer 2

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

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