Comments 89
Выглядит как натягивание совы на глобус. Да, в ассемблере есть удобная инструкция SETLE очень хорошо подходящая именно под этот случай. Ну а если надо не посчитать числа меньше 500, а просуммировать? А если что-то другое, для чего нет подходящей инструкции в ассемблере?
если надо просуммировать, то где то на хабре был пост о том, как компиляторы оптимизируют ваш код и там примерно такой алгоритм выходил: (n * (n + 1)) / 2. сумма от 1 до n включительно
Не о том речь.
Весьма локальное решение представляют как панацею. Я не могу представить много вариантов, где подобный трюк будет полезен.
Как академическое исследование - любопытно, но не полно. Будет ли такой же эффект на других процессорах и процессорных архитектурах? А в случае байткода? А на интерпретируемых языках?
Весьма локальное решение
применение branchless в принципе довольно локальная история, да. иногда полезно, но обычно пайплайн ни разу не настолько линейный и скорость появляется при превращении в filter-map-reduce пайплайн - чисто за счёт cache locality.
Сам приём в среднем вроде не привязан к архитектуре процессоров, поэтому в теории может везде работать. В случае байткода - как повезёт. Java/С#/Swift наверняка запрятали это где-нибудь в JIT-оптимизациях, CPython или Lua - может быть, но с большим шансом только в каких-нибудь более мажорных версиях.
А будет ли так же работать в Java и Swift? Там нет прямого приведения булево к целому. Толь через ?:
?: оптимизируется лучше чем if?
?: оптимизируется лучше чем if?
Зависит от компилятора/JITа, но на уровне команд процессоров Интела, вполне может компилироваться как бранчлесс.
Однако тут есть нюанс: сначала оба операнда читаются из памяти, потом один из них выбирается. Если чтение не из кешей - то бранч может оказаться выгоднее.
Я не настолько силён в этих языках. Выбрал как представителей использующих виртуальные машины с собственными инструкциями. Робот уточняет
Swift - благодаря llvm бэкэнду снативится до setle.
Go - есть поддержка на уровне IR, и соотвественно нативно.
Wasm - поддерживает типизированные варианты инструкции, так что зависит от оптимизатора. Рантайм Node, deno, bun и браузеры вполне могут их использовать, если JIT соизволит.
C# - может соптимизировать нативно, в CIL нет прямой поддержки,
JVM - kotlin, java - не могёт.
OCaml, Haskell - оба имеют и на уровне байткода и при компиляции в натив.
Nim - зависит от бэкэнда для транспиляции - для си понятно дело заведётся, для JS - зависит от финального рантайма.
Lua и Luajit - оба имеют на уровне байткода
Cpython - не умеет, PyPi - если JIT соизволит.
Для C# набросал бенчмарк, вот результаты
Результаты
Код методов на C#
public int NaiveLoop()
{
var smlen = 0;
for (int i = 0; i < numbers.Length; i++)
{
if (numbers[i] < 500)
{
small_numbers[smlen] = numbers[i];
smlen += 1;
}
}
return smlen;
}
public int LoopWithoutBranch()
{
var smlen = 0;
for (int i = 0; i < numbers.Length; i++)
{
var num = numbers[i];
var isSmall = num < 500 ? 1 : 0;
small_numbers[smlen] = num;
smlen += isSmall;
}
return smlen;
}Так что да, тернарный оператор var isSmall = num < 500 ? 1 : 0; действительно не будет использовать прыжки, вот asm код:
mov r10d,[r10+rdx*4+10] ; Load numbers[i]
cmp r10d,1F4 ; Compare with 500
setl r9b ; Set r9b = 1 if < 500, else 0
movzx r9d,r9b ; Zero-extend to 32-bit
mov [r11+rbx*4+10],r10d ; Unconditionally write value
add eax,r9d ; Conditionally increment (0 or 1)
Будет ли такой же эффект на других процессорах и процессорных архитектурах?
можно потыкать тут другие архитектуры https://godbolt.org/z/9frdYccb4
Ну а если надо не посчитать числа меньше 500, а просуммировать?
for (int i = 0; i < 1000; i++)
{
smlen += (numbers[i] < 500) * numbers[i];
}
Вообще был один интересный вопрос на Stackoverflow - почему обработка с if отсортированного массива куда быстрей? И шикарный ответ.
Вкратце - если последовательность данных упорядочена, то предиктор процессора работает как по маслу в таких случаях. Фактически if убирают за вас.
Можно возразить "Так а если у меня неотсортированная последовательность?". Однако если мы говорим не про лабораторный эксперимент с использованием ГСЧ, как правило, эти последовательности не берутся из воздуха. Они хранятся в какой-нибудь базе и уже упорядочены.
Однако если мы говорим не про лабораторный эксперимент с использованием ГСЧ, как правило, эти последовательности не берутся из воздуха. Они хранятся в какой-нибудь базе и уже упорядочены.
Далеко не всегда хранятся, далеко не всегда в базе, и даже если и упорядочены - далеко не всегда по тому критерию(ям), по которому(ым) у нас условие(я).
Для условного перемещения есть cmovcc (csel в ARM). Как вариант:
setle al
movzx eax,al
neg eax
and eax,edx
add [count],eaxНо это хуже, конечно, больше зависимостей и лишних операций.
Не проверял, но надеюсь, компилятор догадается (и тут нужно переделать без UB):
sum += (a <= b ? UINT_MAX : 0) & addend;
Суть примера понятна, спасибо! Но разве примеры с ветвлением и без ветвления всегда дадут одинаковый результат? В примере с ветвлением массив `small_numbers` никогда не будет содержать числа, больше 499, в вот пример без ветвления может, если последний элемент в исходном массиве будет больше 499. А значит у них разная логика и их производительность нельзя сравнивать.
С одной стороны я согласен. С другой: а нам не без разницы что там лежит? Всё что за заполненным размером - мусор.
Мой посыл был в том, что сравнивать производительность алгоритмов корректно только в случае равенства их результатов. Если после одного из алгоритмов нужно делать какие-то дополнительные вычисления, то их сравнение уже не корректно. Можете считать это занудством.
P.S. Просто отбросить хвост, считая его мусором, не получится. Нужно проверять, что лежит в последнем индексе массива, что уже усложнит читабельность кода.
А что за вычисления?
В итоговом массиве small_numbers последним элементом может казаться число, больше 499, чего быть не должно. А может и не оказаться, если в исходном массиве значений последнее число меньше 500. А следовательно нужно проверить, что последний элемент не больше 499 и убрать его, если мы собираемся использовать массив small_numbers где-то дальше. Или я ошибаюсь?
Я исхожу из того, что у массива есть длина в отдельной переменной и мы никогда не обращаемся за пределы этой длины. Число большее 499 - это не последний элемент, а элемент за пределами массива.
Например, если мы нашли одно маленькое число, то оно будет лежать по индексу 0, а по индексу 1 может лежать что угодно.
Пример на шарпах
![Во втором массиве отличается второй элемент, но это всё-равно, т.к. smlen==1 и мы нигде не должны обращаться к small_numbers[1]](https://habrastorage.org/getpro/habr/upload_files/594/158/e35/594158e3531ce03407b079c8b7bd1dc4.png "Во втором массиве отличается второй элемент, но это всё-равно, т.к. smlen==1 и мы нигде не должны обращаться к small_numbers[1]")
Если в таком смысле, то все верно. Но в реальной практике эти алгоритмы ведь должны быть для каких-то целей и обычно внутри функций. И результаты их вычислений также нужны не просто так, а где-то должны использоваться, и скорее всего должны быть переданы в другую функцию, которая уже не ожидает значения больше 499. Вот и получается, что первый алгоритм в качестве результата может вернуть готовый чистый массив small_numbers, в котором точно нет значений, больше 499. А branchless алгоритм должен либо подчистить массив small_numbers (для чего потребуется хоть и незначительная, но доп. логика), либо должен возвращать грязный массив small_numbers и индекс для "отсечения хвоста", и тогда доп. логику придется реализовывать позже.
либо подчистить массив
small_numbers(для чего потребуется хоть и незначительная, но доп. логика)
Согласен. Но это ни на что не влияет, т.к. 1 действие. К тому же я не могу представить, зачем нам результат без количества. Что-то очень специфичное.
Для этого в алгоритме есть переменная smlen. Никто не должен читать данные начиная с этого индекса.
Если в конце добавить проверку последнего элемента и корректирующие действия, это изменит сложность на константу. При измерении вычислительной сложности константами обычно пренебрегают.
Интеловский компилятор, кстати, генерирует из прямолинейной реализации векторизованный код без ветвлений внутри цикла (используя VPCOMPRESS).
В статье счётчик и данные - глобальные переменные, у вас же счётчик существует только в области видимости функции, и данные передаются в аргументы. Если повторить окружение как в статье, то векторный код рассосётся и не появится даже для branchless версии. Забавно конечно, что автор вообще не думает за локальность данных, которая чаще будет давать больше профита, нежели branchless.
Да, похоже он тогда боится, что запись в small_numbers может перекрыться с smlen (хотя по идее это UB и изменение поведения в такой ситуации можно проигнорировать ради оптимизации). Но да, в любом случае использование локальных переменных и restrict может отсечь потенциальные побочные эффекты, из за которых приходится генерировать странный код.
векторный код рассосётся
Не, вроде не рассосётся, я вернул счётчик наружу, код замедлился, но векторизация осталась, вот коммент ниже со скриншотом.
Как минимум результат выполнения кода из примеров может быть разный. Преждевременная оптимизация или более понятный код - выбор очевиден.
устранение ошибочного предсказания ветвления — ключевой способ повышения скорости программ.
оно конечно повышает скорость программы, но вот к ключевым способам я бы это не отнёс. Применение кода без ветвлений - довольно нетривиальная задача и имеет довольно узкую область применимости. И упоминание quicksort особенно забавно, ибо branchless вариант нашёл не человек, а робот, что ещё раз подчёркивает нетривиальность этой методики в большинстве реального кода.
Большим профитом было бы показать, как локальность данных помогла бы в этой ситуации больше, нежели сэкономить на ветвлениях.
(numbers[i] < 500) Вот не могу вспомнить - стандарт языка нам точно и всегда гарантирует что результат операции 1, а не любое отличное от 0 ?
Хоть в этой версии добавляется безусловное сохранение (запись в память, даже если условие не выполняется), её затраты обычно гораздо меньше, чем огромная цена ошибочного предсказания ветвления.
Это было безусловно верно 40 лет назад. Сегодня цена ошибки предсказания ветвления — пара тактов, а лишний доступ в память (даже в кэш второго уровня, даже на чтение) — десятки и сотни тактов. Через это, подобные оптимизации имеют смысл только для очень маленьких и горячих циклов, либо из академического интереса.
Кстати, для пущего улучшения, можно циклы перевернуть, чтоб шли от тысячи к нулю. На RISC-платформах сэкономится регистр.
цена ошибки предсказания ветвления — пара тактов
Скорее десяток, можно глянуть скажем в исходниках компиляторов - хотя там некое "среднее по больнице", реальное влияние зависит от кода вокруг.
а лишний доступ в память (даже в кэш второго уровня, даже на чтение)
Примерно столько же (даже если важна именно latency доступа). В интеловском мануале цифры в районе 10-15.
Скорее десяток
зависит от длины конвейера, но для современных х86 систем, вы пожалуй правы.
Примерно столько же (даже если важна именно latency доступа). В интеловском мануале цифры в районе 10-15.
Опять же зависит от архитектуры, но это если действительно повезло попасть в L2-кэш. А если нужных данных нет ни в одном кэше?
справедливости ради в этом примере оба массива практически с гарантией окажутся в кешах.
Понятно, что latency доступа в DRAM будет заметно больше. Тут уже общее правило - перед тем, как оптимизировать, сначала определить узкое место в коде, потом - узкое место в железе, из за которого тормозит этот код, и потом целенаправленно бить в нужную точку.
Кстати, для пущего улучшения, можно циклы перевернуть, чтоб шли от тысячи к нулю. На RISC-платформах сэкономится регистр
На х86/64 тоже, чего бы ему не сэкономить.
там в коде ассемблера сравнение с константой. Не уверен, есть ли какая-то разница между сравнением с константой и сравнением с нулём.
Есть. Даже c# код под Интел экономит регистр на обратных циклах.
Типа такого будет:
L0027 dec r8d
L002a jns short L0020
а обратный цикл -- не сломает кеш предсказуемость?
Отличный вопрос, меня он тоже тревожит. По опыту - нет, хотя объяснить я себе этого не могу.
Но: с обратным циклом и пойнтер-арифметикой (ref var curr + MemoryMarshal + Unsafe.Add) можно и от регистра для exit condition избавиться, и доступ прямой последовательный сохранить. И JIT именно так и делает, когда решает, что может поменять направление счётчика.
Сегодня цена ошибки предсказания ветвления — пара тактов
Citation needed для временной эпохи наставшей после класса уязвимостей Spectre.
а лишний доступ в память (даже в кэш второго уровня, даже на чтение)
Здесь вы путаетесь, в тексте, даже цитате, стоит: "в этой версии добавляется безусловное сохранение". Безусловное сохранение - это не чтение (благодаря write-back cache). Во-вторых, здесь безусловно используется L1D cache, даже с того же самого lane. Где такой оппортунизм станет дорогим - на много-много ядер и дорогой синхронизацией кэша из-за постоянной модификации памяти. Решение? Устранить конкуренцию между потоками.
Citation needed для временной эпохи наставшей после класса уязвимостей Spectre.
Предсказание ветвления заключается в том, что процессор пытается угадать с какого места в памяти заполнять конвейер после того, как туда попала команда ветвления (спекулятивное заполнение). Потому что точный адрес ветвления выяснится в блоке исполнения ближе к концу конвейера. Соответственно, цена ошибки — время затраченное на заполнение конвейера командами с неправильного адреса. Очевидно, такая цена не может быть выше длины конвейера (в тактах). В зависимости от архитектуры она будет болтаться где-то возле половины длины. Скажем, тактов 10-15
Здесь вы путаетесь, в тексте, даже цитате, стоит: "в этой версии добавляется безусловное сохранение". Безусловное сохранение - это не чтение (благодаря write-back cache)
Производительность приложения предложенного в статье интересна исключительно с академической точки зрения. Автор демонстрирует некий принцип. Теоретически верный сам по себе. Но, при современном уровне развития вычислительной техники (скорость процессора на порядок выше скорости памяти) намного важнее, как программа обращается с памятью. Лишнее обращение может запросто перекрыть все выгоды от оптимизированных ветвлений
Про misprediction понял, где ошибся, пока читал текст.
The average misprediction penalty was measured to approximately 18 clock cycles for Zen 1-3. The misprediction penalty varies from 15 - 18 in Zen 4 and 15 - 25 in Zen 5.
https://agner.org/optimize/microarchitecture.pdf стр 35
дел
По своей природе очень похоже на написание кода для GPU, где обычно условия не приветствуются :)
Можно всю итерацию вычислять цвет пикселя, а затем в самом конце происходит умножение на ноль и все вычисления коту под хвост
Да, довольно таки ужасно, но зато без ветвлений + предсказуемо...
с ифами много приколов связано. С тем, как процессор реагирует на ветвления.
Допустим, у нас есть структура Кот {цвет, вес}. И надо посчитать суммарный вес всех чёрных котов.
Казалось бы, надо так:
пусть сумма = 0;
Для каждого кота в массиве: {
если (кот.цвет == чёрный) { сумма += кот.вес; }
}Но вот фигуёки. Если компилятор только за вас не перепишет. Потому что вот так будет в разы быстрее.
пусть сумма = 0;
Для каждого кота в массиве: {
пусть временная_сумма = сумма + кот.вес;
если (кот.цвет == чёрный) { сумма = временная_сумма; }
}Во первых, вычисление предсказуемо и процессор в очереди может его оптимизировать. Во вторых, это ещё и векторизуется проще.
Хммм. Сейчас на LLMил пример, и что-то у меня улучшение не такое сильное, как в прошлый раз. 35 ms против 42. Но всё равно есть. Может, LLVM улучшили?
Короче, вот кот код.
Вот
use std::time::Instant;
use rand::prelude::*;
// The Cat struct with two fields.
#[derive(Debug, Clone)]
struct Cat {
is_black: bool,
weight: f32,
}
/// Sum the weights of black cats using a plain `for` loop.
fn sum_black_cats_for(cats: &[Cat]) -> f32 {
let mut total = 0.0;
for cat in cats {
if cat.is_black {
total += cat.weight;
}
}
total
}
/// Sum the weights with unconditional sum.
fn sum_black_cats_for2(cats: &[Cat]) -> f32 {
let mut total = 0.0;
for cat in cats {
let temp_total = total + cat.weight;
if cat.is_black {
total = temp_total;
}
}
total
}
/// Sum the weights of black cats using iterator adapters.
fn sum_black_cats_iter(cats: &[Cat]) -> f32 {
cats.iter()
.filter(|cat| cat.is_black)
.map(|cat| cat.weight)
.sum()
}
fn main() {
let mut rng = rand::rng();
let n = 10_000_000;
// Generate a vector of one million random cats.
let cats: Vec<Cat> = (0..n)
.map(|_| Cat {
is_black: rng.random(), // 50% chance of being black
weight: rng.random_range(3.0..10.0), // random weight between 0 and 100
})
.collect();
// ---- Time the for-loop version ----
let start = Instant::now();
let sum_for = sum_black_cats_for(&cats);
let duration_for = start.elapsed();
println!("For-loop sum: {:.2}", sum_for);
println!("For-loop time: {:?}", duration_for);
// ---- Time the always sum version ----
let start = Instant::now();
let sum_for = sum_black_cats_for2(&cats);
let duration_for = start.elapsed();
println!("Always sum sum: {:.2}", sum_for);
println!("Always sum time: {:?}", duration_for);
// ---- Time the iterator version ----
let start = Instant::now();
let sum_iter = sum_black_cats_iter(&cats);
let duration_iter = start.elapsed();
println!("Iterator sum: {:.2}", sum_iter);
println!("Iterator time: {:?}", duration_iter);
}
Ещё поэкспериментировал. Абсолютный чемпион с отрывом
fn sum_black_cats_for2(cats: &[Cat]) -> u64 {
let mut total = 0;
for cat in cats {
total += cat.weight * cat.is_black as u64;
}
total
}Что и следовало ожидать. Просто в реальном коде так красиво редко свернётся.
IF-ы не бесплатны. Сильно не бесплатны. Арифметика намного дешевле. Не надо добавлять if-ы, чтобы избежать немного арифметики. Вот главное, что нужно
Не надо добавлять if-ы, чтобы избежать немного арифметики. Вот главное, что нужно
Даже не вспоминаем о возможном "лишнем" обращении к незакешированной памяти для обеспечения чистой арифметики, с этим и так понятно.
Но вот у меня есть живой пример, в котором с помощью ИФа можно ИНОГДА избавиться от простого int64 idiv над операндами, гарантированно лежащими в регистре и кеш-линии. И оно того стоит - любые бенчмарки и реальность это подтверждают.
Так что не всякая арифметика одинаково полезна.
Не очень понятно, что именно умножается в данном варианте. (Cat::weight у Вас объявлена как f32. На u64 она не умножается.) Похоже, Вы не всё описали, что сделали. От этого быстродействие может изменяться.
А так, ещё можно вместо умножения попробовать делать - (отрицание) и & (побитовое И).
Умножается оно здесь на 1 (удовлетворяет условию) или на 0 (не удовлетворяет), таким образом получаем сумму весов котов, удовлетворяющих условию.
А так, ещё можно вместо умножения попробовать делать - (отрицание) и & (побитовое И).
Можно, и даже побитовое NOT. Всё это можно сделать без ветвлений, парой-тройкой арифметических/битовых операций. Иногда ОЧЕНЬ ускоряет, иногда - нет.
Тут ещё стоит не забывать про буферы декодера и блока обработки циклов (как его там) - там сдвиг команд на пару байтов туда-сюда может СИЛЬНО влиять на производительность.
Нет, Вы не поняли мой вопрос. Rust не даст умножить f32 на u64. Соответственно, MountainGoat что-то сделал с Cat::weight - то ли сделал его u64, то ли ещё чего-то...
А когда я говорил "можно попробовать делать" - я это так ненавязчиво намекал, чтобы MountainGoat попробовал сделать и поэкспериментировать, хех!
А про буферы - ну, да, действительно, ещё куча разных мелочей, влияющих на быстродействие...
Что, не приведёт имплицитно инт в флоту?
Я не специалист, на с# приводит и результат ожидаемо лучший.
...побитовые операции с флотом тоже вполне себе существуют.
Нет, Rust не любит имплицитные операции из соображений уменьшения возможностей (вероятности) выстрелов в собственную ногу. Там выбор дизайна в большинстве мест тяготеет к тому, чтобы пишущий и читающий код программист хорошо осознавал, что происходит.
Если хочется f32, так и надо прямо писать as f32, а не as u64.
(Извините, не уловил, что автором реплики был MountainGoat, а не Вы - поправил свою реплику.)
Раст принципиально ничего не приводит. Даже f32 к f64. Только литералы подбирает по типу, и то 10.0 в u64 класть низя.
Да я просто во всей программе тип несколько раз поменял и забыл, какой оставил. Было интересно, соотношение скоростей поменяется при смене типа или нет. Ответ: поменяется. При переходе с 32 на 64 бит разница в скорости между разными методами уменьшилась вдвое. При переходе с f на u ничего не изменилось.
Побитовые операции ничего не дадут потому, что компилятор и так их вставляет, где может. То же самое касается и векторизации вручную. Это очень вымороченный случай, когда руками что-то можно так сделать, что компилятор не сможет.
Это вы заблуждаетесь. Компилятор VS2026 создает одинаковый код за одним исключением: во втором варианте он все суммирует в один регистр, а потом копирует его значение в регистр результата.
То есть вторая функция медленнеe на одно копирование из регистра в регистр (это сарказм, если чо). В разы, да.
Для этого этот цикл надо хотя бы на 4 линии заunrollить. Я предпочитаю пользоваться оператором ? при этом.
А здесь говорится ровно о противоположном, и разбирается до боли похожий пример:
Дел
Если вы возьмёте нормальный современный оптимизирующий компилятор, скажем Intel OneAPI (да, я в курсе, что вы на Apple M1, но тем не менее), то будете приятно удивлены, потому что вот это:
Превратится вот в это:
Это под профилировщиком VTune запущено. И нет никаких бранчей и SIMD на месте.
Разница между if и bl есть, но не драматическая. Кодом bl утомлять не буду, его там больше. Зато разница между Intel и Visual Studio впечатляющая:
100000 итераций (for (int i = 0; i < 100000; i++) ret = small_**();)
Интел:
Time if: 0.195534
Time bl: 0.124896
Студия
Time if: 35.107267
Time bl: 5.962277Синтетические примеры хороши для понимания, но в реальной жизни они могут быть чуть другие. А так интеловский компилятор в общем неплохо справляется, вот, к примеру, тернарный оператор он сам на cmove заменяет, надо просто в ассемблер поглядывать и ему иногда немножко помогать, зато это даёт возможность не отказываясь от удобного представления искодников с "if" получать тем не менее "branchless" машинный код.
В смысле у автора оригинала, я только сейчас плашку перевода заметил
А флаги какие (и нет ли изменений в исходнике, номера строчек смущают)? У меня на godbolt отказался:
Begin optimization report for: small_if()
LOOP BEGIN at <source> (26, 5)
remark #15344: Loop was not vectorized: vector dependence prevents vectorization
remark #15346: vector dependence: assumed FLOW dependence between [ <source> (29, 19) ] and [ <source> (28, 13) ]
remark #15346: vector dependence: assumed FLOW dependence between [ <source> (29, 19) ] and [ <source> (29, 19) ]
remark #25438: Loop unrolled without remainder by 8
LOOP END
При выносе в независимую функцию без использования глобальных переменных векторизует, ссылку кидал выше.
Флаги по умолчанию, включена скорость и повальный AVX2 на Haswell (я упражняюсь на i7-4800MQ):
и вот
Но, кстати, когда я перебрасываю код в библиотечную функцию (я ещё и на Расте покрутил), то там не всё так шоколадно, хотя интел всё равно в лидерах.
А, и не то, чтобя я годболту не доверяю, но я привык верить исключительно собственным глазам, поэтому только декомпиляция/анализ листингов компиляции или анализ под отладчиком или профилировщиком именно у меня, там, где оно запускается. Все версии самые свежие 2026, что интел, что MSVC.
Кстати, меня в этом ассемблерном коде несколько смущает отсутствие записи в выходной массив.
Студия Time if: 35.107267
А по мнению VTune, куда здесь время уходит? Есть подозрение, что не на branch prediction.
О таких вещах должен думать разработчик компилятора. Чтобы у миллиона программистов не болела голова. Нереально при создании программы анализировать каждый маленький участок кода, и предсказывать как он будет исполняться в железе. Такое нормально только если пишешь вирусы и софт для взлома, и нужно использовать особенности работы железа, которые можно использовать как уязвимость.
smlen = 0;for(inti = 0; i < 1000; i++) {if(numbers[i] < 500) { small_numbers[smlen] = numbers[i]; smlen += 1; }}
А о чём конкретно в случае изначального примера должен думать разработчик компилятора?
И что в нём такого, что его нужно прям анализировать и предсказывать [особенно Инженеру встраиваемых систем (младшему)]?
Как уже показали выше, компилятор вполне может векторизовать такой код, заменяя бранчи на другие инструкции, дающие такой же результат. То есть его разработчики подумали о том, как использовать подходящие инструкции процессора для некоторых характерных паттернов исходного кода. Другое дело, что это срабатывает не всегда - тогда см. ответ рядом про профилировку.
Векторизировать условное поэлементное копирование?
Я не так просто поинтересовался об изначальном примере. Там компилятору вообще нечего решать, кроме как счётчик заменить на обратный (думаю, что многие компиляторы так и делают, JIT .NETa - точно) и, возможно, цикл развернуть - всё остальное до самого времени исполнения неясно.
То есть, здесь только разработчик может знать, что значения. к примеру, отсортированы - и тогда нужен ИФ с ранним выходом, или "почти отсортированы", и тогда код как в примере будет оптимальным, или вообще непредсказуемые, и тогда нужен оптимизированный вариант из примера.
Тут только JIT PGO мог бы по ходу дела переписывать асм, вопрос - не было бы это дороже, чем прогонять цикл как написано.
А так-то да, "его разработчики подумали" о многом. иной раз читаешь релиз ноутс и диву даёшься. Но всего на их уровне не придумаешь.
Векторизировать условное поэлементное копирование?
Именно так. Загрузили вектор в регистр, одной инструкцией сравниваем значения с заранее подговленным вектором с размноженной константой, другой копируем подходящие в выходной массив (подряд).
только разработчик может знать, что значения. к примеру, отсортированы
Понятно, что про входные данные компилятор не знает.
Именно так. Загрузили вектор в регистр, одной инструкцией сравниваем значения с заранее подговленным вектором с размноженной константой, другой копируем подходящие в выходной массив (подряд).
Можно по-подробнее, псевдокод?
Уже кидал ссылку на годболт, вот основные инструкции
vmovdqu ymm1, ymmword ptr [rdi + 4*r9]
vpcmpgtd k1, ymm0, ymm1 // ymm0 - размноженная константа
vpcompressd ymmword ptr [rsi + 4*rdx] {k1}, ymm1
vpcompressd
Да, пропустил, спасибо за науку.
Жаль, что нарочно на такое .NET JIT (пока) не спровоцировать, мне бы пригодилось кое-где.
но vpcompressd — это вроде AVX512, если я туда, куда надо смотрю. Но и на чистом AVX2 можно тоже сделать, что б восемь значений за итерацию, там через свою LUT можно выкрутиться, вроде.
Вопрос же не в этом! Вопрос в том, что здесь очень значительная зависимость от неизвестных данных.
Ну, а так, естественно, вдумчиво оптимизировать нужно с профайлером и, соответственно, горячие пути.
Но и это будет всё больше автоматизироваться с применением нейросетей, я уверен. Типа AlphaDev, но в более общем виде.
Не факт, что пишущий подобный код программист сам знает что-то о данных (скажем, если это библиотечная функция, вызываемая из тысяч мест). Если профилировка показала, что больше всего времени приходится на конкретный вызов и по коду верхнего уровня можно делать какие-то предположения - можно и написать кастомную версию.
Нереально при создании программы анализировать каждый маленький участок кода, и предсказывать как он будет исполняться в железе.
Не надо ничего предсказывать. После того, как написан работающий вариант программы, запускаем профилировщик, смотрим, какие проблемы со стороны железа испытывают наиболее часто исполняемые участки и думаем, что с ними делать.
Если if вас замедляют, откажитесь от них