Комментарии 23
Ммм, а про какие процессоры в этой статье идет речь? Если в процессоре есть предикатные регистры, результаты же будут совсем другие, разве нет?
В данной статье рассматривались только обычные промышленные Intel'ы.
В самом конце сделано не очень явное замечание, что есть случаи, когда на специальном железе существуют специальные инструкции, сильно меняющие поведение.
На обычных промышленных Intel есть маски в AVX512 - для рассматриваемого примера они, конечно, не очень годятся, но попробовать использовать можно.
Но на ARM давно уже вовсю используются предикатные регистры, это же не специальное железо. И ARM-овские десктопы тоже стали обыденностью.
Я согласен, что зря не указал явно Intel-специфичность описываемых наблюдений.
И согласен с тем, что ARM это действительно не специальное железо, а обыденность в индустрии, как и те же видеокарты.
Спасибо, что сделали это важное замечание.
В качестве забавного наблюдения могу отметить, что мы в команде изучали возможность применения ARM'а для нашего проекта (кластер большой, интересовались в том числе и с экономической точки зрения). И оказалось, что ещё десятилетие назад в коде были сделаны неявные завязки на Intel-специфику. В итоге, в том числе новые Mac-и на ARM-ах использовать в нашей команде пока что не выйдет :)
А чем второй пузырёк от сортировки вставкой отличается?
В данной статье эти алгоритмы рассматриваются исключительно с точки зрения демонстрации эффекта от branch prediction. Алгоритмы намеренно очень похожи, чтобы выполнять "одинаковое число практически одинаковых инструкций". Исходя из этого, совершенно не важно, на что они похожи.
Иначе можно начать придираться к тому, что даже в рамках текущей complexity можно сделать ещё кучу оптимизаций.
Или можно начать погружаться в огромную и очень интересную тему сортировок :)
сортировка вставкой — это когда находят нужное место, а потом обменивают. В пузырьке всегда обменивают два соседних.
TTTTTTT....TTTFFF...FFFFFFF
А разве не TFTFTFTF...?
Нет, в статье числа отсортированы по критерию четности, а не по возрастанию/убыванию, так что сначала будут идти все четные числа, а потом все нечетные.
Хотя судя по статье на которую регулярно ссылается автор, вариант TFTFTFTF… тоже будет оптимизирован
В видеокартах стоит не проблема предсказателя переходов, а проблема низкой утилизации варпов. Насколько я понимаю, там, вообще, предсказателя переходов нет, вместо него толстый SMT с десятками потоков на ядро (именно настоящими потоками — варпами, каждый из которых состоит из 32/64 суб-потоков, которые по сути элементы SIMD вектора). Не известно, какую инструкцию делать следующей, — не беда, в очереди на исполнение стоит еще десяток потоков, можно исполнить инструкцию того, у которого все известно. Проблема с ветвлениями на GPU связана с тем, что это SIMD архитектуры и процессор физически не может исполнить разные инструкции для разных частей варпа, поэтому выполняет обе ветки if по очереди.
Да, в целом как то так
не беда, в очереди на исполнение стоит еще десяток потоков
Вы пишете как будто проблем вообще нет - реально всё таки есть компромисс между числом SMT потоков и размером регистрового файла на поток. Но да, SMT на GPU - основная техника борьбы c latency, заменяющая предсказание переходов и OoO.
"реализация GetEvensCount без if всё-таки чуть-чуть медленнее, чем с if'ами"
Хотя это и несколько оффтоп, но попиарю в очередной раз компилятор Clang:
https://gcc.godbolt.org/z/WoMbrx8zx
SIMD, развёртка, считаем 32 числа за итерацию - эта версия уж точно не медленнее.
Значит, в общем случае избавляться от if выгоднее.
Ясно, что в первом случае автор хотел продемонстрировать работу предсказателя переходов, но в данном случае задача решается ещё проще: надо посчитать количество нечётных и вычесть это число из длины массива. У нечётных установлен последний бит, так что просто суммируем эти биты:
int oddCount = 0;
for (int i = 0; i < array.Length; ++i) oddCount += (array[i] & 1);
return array.Length - oddCount
Наверняка, это ещё и компилятором в SIMD'ы какие-нибудь свернутся.
Сказка про Branch prediction