Хабр Курсы для бэкендеров
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 35
Закреплённые комментарии
Я не настоящий сварщик и на rust только поглядываю со стороны. Погуглил - похоже, дело в том, что rust трепетно относится к точности операций (см. здесь) и глобально задать fast-math (без которого clang тоже отказывается векторизовать аналогичный цикл, поскольку векторизация меняет порядок сложений и может влиять на результат) нельзя. Советуют явно использовать интринсики . С ними работает, и из кода
#![feature(core_intrinsics)]
use rand::prelude::*;
use std::intrinsics::fadd_fast;
const N: usize = 1024 * 1024;
fn main() {
let mut rng = rand::rng();
let data: Vec<f32> = (0..N).map(|_| rng.random()).collect();
let mut sum: f32 = 0.;
for val in data {
sum = unsafe {fadd_fast(sum, val)};
}
println!("sum = {}", sum);
}через RUSTFLAGS=‘-C target-feature=+avx2’ cargo build --release генерируется нормальный векторный вариант c vaddps и ymm регистрами. Можно ли заставить sum() использовать быструю математику - не знаю, но в любом случае так попроще, чем вручную писать на ассемблере.
Вот ещё более быстрый и более точный вариант и без unsafe из одноимённого блога.
#![allow(internal_features)]
#![feature(core_intrinsics)]
use std::intrinsics::fadd_algebraic;
fn sum_block(arr: &[f32]) -> f32 {
arr.iter().fold(0.0, |x, y| fadd_algebraic(x, *y))
}
pub fn sum_orlp(arr: &[f32]) -> f32 {
let mut chunks = arr.chunks_exact(256);
let mut sum = 0.0;
let mut c = 0.0;
for chunk in &mut chunks {
let y = sum_block(chunk) - c;
let t = sum + y;
c = (t - sum) - y;
sum = t;
}
sum + (sum_block(chunks.remainder()) - c)
}
Avx512 не разворачивали сильнее? Всё-таки больше регистров, должно снизить влияние задержки на чтение.
Хотя возможно спекулятивное исполнение уже использует дополнительные регистры.
Нет, там в таблице для версии assembly был 4х разворот, а SIMD 8x. Надо будет попробовать на тачке с быстрой памятью. Я пару лет назад делал алгоритм Offset/Gain коррекции изображений (он ещё Flat Field Correction называется), там одно вычитание и одно умножение по двумерным массивам и пришёл к выводу, что для эффективного использования AVX512 нужно некоторое значимое количество инструкций только на регистрах, а так когда просто читаем из памяти, просто вычитаем или складываем и тут же пишем обратно, то выигрыш очень невелик. Вот когда начинаются свёртки или умножения матриц или матрицы на вектор, где FMA инструкции используются то да. В основном тут был интерес проверить, понимает ли встроенный ассемблер Раста и библиотека интрисинков эти инструкции, и всё вроде норм.
для эффективного использования AVX512 нужно некоторое значимое количество инструкций только на регистрах
С ним было совсем плохо на Skylake (серверном) - заметно снижалась частота (что замедляло другие операции), выигрыш был действительно только если 90+% операций на zmm регистрах (скажем, в оптимизированном умножении матриц). На современных процессорах получше. И в любом случае на клиентских процессорах, даже там где AVX512 поддерживается, выигрыша оно не даёт - отдельного исполнительного устройства нет, работает на 256битном.
Там же у SIMD инструкций load сильно ограничен (меньше 4 одновременно, т.е. простой большой, если нет доп. операций для исполнения пока оно там крутится) по кол-ву одновременных.
Максимум можно предварительно в L1d подгрузить, если оно ещё не там.
Из L1 грузить будет вроде бы 4-5 циклов. Потом fused load+add. А т.к. там больше ничего не происходит одновременно (хотя бы тот же prefetch - т.к. цикл не очень предсказуемая вещь и можно начать тянуть память для след. итерации цикла в L1), то просто простой конвеера скорее всего происходит пока load порты заняты.
можно предварительно в L1d подгрузить
Сколько бы я не пробовал набросать вменяемый и воспроизводимый пример с префетчем (если вы его имеете ввиду) — у меня это ни разу не получилось, даже на чистом асме. На SO тоже пытались и пришли к выводу, что на современных процессорах это уже неактуально (а лет 20-25 назад на старых процесорах вполне работало). Причём я пробовал как разные упреждения предзагрузки в кэш, ht 0 1 2, так и на данных, которые читаются непоследовательно. Вот я добавил Rust Playground + Prefetch - попробуйте сами, если есть желание поковыряться. Бенчмарк я там тоже чуть поправил, чтобы он 256 раз код гонял и минимум выбирал.
Префетч явными инструкциями имеет смысл только при рандомном доступе (и при этом в начале итерации цикла можно легко получить адрес данных для следующей и иницировать префетч). С регулярным доступом хардварный префетч сам справляется.
В теории, да, конечно, но на практике хотелось бы иметь на руках живой код, который бы явно это демонстрировал. Надо будет попробовать почитать память с шагом, бòльшим чем размер L3 и случайно (я пробовал только с фиксированным), на досуге сделаю ещё один подход к снаряду.
Если можно гарантировать невытеснение кеш линий, то программно можно предзагрузить хоть половину L1d. Зная кол-во параллельных предзагрузок можно начередовать их с другими инструкциями оптимальным образом (ещё нужно помнить про выравнивание инструкций и пр. специфику, о которой я скорее всего ещё не знаю...).
При наличии других прожорливых потоков смысл от программной предзагрузки теряется, т.е. предзагружать много линий не имеет смысла, т.к. вероятность их вытеснения до использования сильно возрастает.
Для bare metal под одну задачу такой проблемы нет и программная предзагрузка/освобождение блоков памяти надёжнее и выгоднее (известно когда и сколько предзагружать, когда и сколько освобождать - т.е. не нужно заниматься предсказаниями и лишними оптимистичными инструкциями) надежды на железо.
то программно можно предзагрузить хоть половину L1d
На первые несколько десятков килобайт хватит, а дальше что?
А дальше на скорости памяти. L3 и L2 предзагрузку заранее никто не отменял по аналогичным приципам, поэтому там скорее на пару MiB хватит сразу, а потом смешанная предзагрузка блоков кеш линий по мере исчерпания текущих. Если надеятся на железо, то можно поймать DRAM refresh прям во время обработки и почти 1us куковать периодически.
Смысл префетча - не в том, чтобы заранее загрузить в кеш побольше (это можно и явными чтениями сделать), а чтобы в процессе обработки больших массивов подкачка из памяти в кеш шла параллельно с вычислениями на ядре.
Если данных мало и они влезают в кеш - есть технология, позволяющая гарантированно запретить их вытеснение другими потоками (работает только в kernel mode).
а, оно и правда работает:
префетчинг на рандоме
use rand::prelude::*;
use std::arch::asm;
use std::mem::size_of;
const LARGE_MEM: usize = 1024 * 1024 * 1024; //512 и выше в Playground не фурычит
const F32S_IN: usize = LARGE_MEM / 4;
const DIST_BYTES: usize = 28 * 1024 * 1024; //I have 26 MB L3
const DIST_ELEMS: usize = DIST_BYTES / 4;
const ITERS: usize = 10_000_000;
const M: usize = 100_000; // Benchmark reps
const DUMMY_ITERS: usize = 8;
macro_rules! dummy_payload {
() => {
".rept {dummy}\n\
addss xmm0, xmm2\n\
mulss xmm0, xmm1\n\
.endr\n"
};
}
fn random_load_prefetch(data: *const f32, idx: &[usize]) -> f32 {
let mut acc: f32 = 0.0;
for w in idx.windows(2) {
let cur = w[0];
let next = w[1];
unsafe {
asm!(
// prefetch NEXT random element (>=L3 away)
"prefetcht0 [{ptr} + {next} * 4]",
// load CURRENT element
"movss xmm0, [{ptr} + {cur} * 4]",
// ---- dummy compute to overlap memory latency ----
dummy_payload!(),
ptr = in(reg) data,
cur = in(reg) cur,
next = in(reg) next,
// constants
dummy = const DUMMY_ITERS,
in("xmm1") 1.000123_f32,
in("xmm2") 0.999877_f32,
out("xmm0") _,
options(nostack, preserves_flags),
);
}
acc += cur as f32;
}
acc
}
fn random_load_no_prefetch(data: *const f32, idx: &[usize]) -> f32 {
let mut acc: f32 = 0.0;
for &i in idx {
unsafe {
asm!(
"movss xmm0, [{ptr} + {idx} * 4]",
// ---- same dummy ----
dummy_payload!(),
ptr = in(reg) data,
idx = in(reg) i,
// constants
dummy = const DUMMY_ITERS,
in("xmm1") 1.000123_f32,
in("xmm2") 0.999877_f32,
out("xmm0") _,
options(nostack, preserves_flags),
);
}
acc += i as f32;
}
acc
}
#[inline(always)]
fn rdtsc_start() -> u64 {
let lo: u32;
let hi: u32;
unsafe {
asm!(
"lfence",
"rdtsc",
out("eax") lo,
out("edx") hi,
options(nomem, nostack, preserves_flags),
);
}
((hi as u64) << 32) | lo as u64
}
#[inline(always)]
fn rdtsc_end() -> u64 {
let lo: u32;
let hi: u32;
unsafe {
asm!(
"rdtscp",
"lfence",
out("eax") lo,
out("edx") hi,
out("ecx") _, // IA32_TSC_AUX
options(nomem, nostack, preserves_flags),
);
}
((hi as u64) << 32) | lo as u64
}
fn bench_min<F: Fn()>(f: F) -> u64 {
let mut best: u64 = u64::MAX;
for _ in 0..M {
let t0 = rdtsc_start();
f();
let t1 = rdtsc_end();
let dt = t1 - t0;
if dt < best {
best = dt;
}
}
best
}
fn make_random_indices(len: usize) -> Vec<usize> {
let mut rng = rand::rng();
let mut idx = Vec::with_capacity(len);
// Divide memory into 32MB pages and shuffle pages
let pages = F32S_IN / DIST_ELEMS;
let mut order: Vec<usize> = (0..pages).collect();
order.shuffle(&mut rng);
for p in order {
let base = p * DIST_ELEMS;
let offset = rng.random_range(0..DIST_ELEMS);
idx.push(base + offset);
}
idx
}
fn main() {
let bytes = F32S_IN * size_of::<f32>();
let gb = bytes as f64 / (1024.0 * 1024.0 * 1024.0);
println!("Allocating {:.2} GB...", gb);
let data: Vec<f32> = vec![1.0f32; F32S_IN];
println!("Generating random indices...");
let idx = make_random_indices(ITERS);
let t1 = bench_min(|| {
let _ = random_load_no_prefetch(data.as_ptr(), &idx);
});
let t2 = bench_min(|| {
let _ = random_load_prefetch(data.as_ptr(), &idx);
});
println!("Random load NO prefetch : {} cycles", t1);
println!("Random load WITH prefetch: {} cycles", t2);
let improvement = (t1 as f64 - t2 as f64) / t1 as f64 * 100.0;
println!("Improvement: {:+.2} %", improvement);
}Или на Playground.
Из хорошего - походу асм пробрасывается дальше "как есть", то есть можно и директивы макроассемблера использовать типа .rept / .endr, чтобы без копипастинга нафигачить "бесполезной" вычислительной нагрузки, ассемблер это честно развернёт перед кодогенерацией, но и это не всё — до кучи это можно оформить стандартным макросом Раста:
macro_rules! dummy_payload {
() => {
".rept {dummy}\n\
addss xmm0, xmm2\n\
mulss xmm0, xmm1\n\
.endr\n"
};
}и вкорячить его вот прямо в ассемблер в обе функции с префетчингом и без:
asm!(
// prefetch NEXT random element (>=L3 away)
"prefetcht0 [{ptr} + {next} * 4]",
// load CURRENT element
"movss xmm0, [{ptr} + {cur} * 4]",
// ---- dummy compute to overlap memory latency ----
dummy_payload!(),
ptr = in(reg) data,
...Еще разрешения QueryPerformanceCounter тут недостаточно, так что замер времени теперь по феншую через rdtsc/rdtscp и на Xeon, что у меня, можно и 20% получить (это вроде норм для данного сценария):
Running `target\release\r-prefetch2.exe`
Allocating 1.00 GB...
Generating random indices...
Random load NO prefetch : 305 cycles
Random load WITH prefetch: 241 cycles
Improvement: +20.98 %Там, конечно, можно покрутить количество вычислений, или стратегию чтения памяти, бенчмарк всё ещё швыряет от 5 до 25%, но префетчинг версия стабильно лучше, если мы с копилотом нигде не налажали (там версия без префетчинга короче, но я пробовал копипастить один-в-один, просто комментируя перфетчинг, местами я их тоже менял на всякий случай, результат тот же), по-хорошему надо бы прибить поток к одному ядру, но принцип уже понятен.
Я просто счастлив сегодня.
Предзагрузка - чтобы работать как конвеер из стиралок и сушилок, а не как стиралка-сушилка (железный вариант обязателен для старого софта, а так - часто мешает, вспомнить хотя бы мусорные кеш линии для ограждения данных потоков). Задача - скрыть время доступа к внешней памяти.
Сомневаюсь, что железный предзагрузчик может скрыть почти 1us DRAM refresh (некоторые работы в этой области намекают, что точно не может и все решения memory bound задач просто живут с этими непредсказуемыми задержками), т.к. типичный доступ к памяти не занимает много сотен наносекунд. Если взять доступ L1d за 4-5 циклов, то на 5GHz ядре один DRAM refresh это провал по времени почти в 1000000 кеш линий (почти 64KiB, если обработка <1 цикла на кеш линию), а т.к. там нужна синхронизация на это время все полученные параллельно из памяти кеш линии для ядра будут ждать "неудачную" (попала в банку с DRAM refresh) предзагрузку кеш линии. И если нет предзагруженного буфера почти в 64KiB хотя бы в L3 работа будет просто останавливаться на сотни наносекунд.
Будем мы их сразу использовать или нет не имеет значения. Там LRU, поэтому при нагрузке на кеш предзагрузка теряет свою эффективность настолько, что предзагружать много кеш линий задолго до их обработки становится вредно (т.к. железная предзагрузка ещё добавит нагрузки на кеш).
Запрет вытеснения это хорошо, но что-то всё равно будет вытеснено, а магия это плохо.
чтобы работать как конвеер
Вот именно - как конвейер, обычно интересно общее время обработки гигабайтного массива, а не поведение на старте.
И если нет предзагруженного буфера почти в 64KiB хотя бы в L3
Даже если в начале что-то предзагрузить - всё равно в процессе вытеснится своими же данными.
Тогда `prefetchnta` (и положить в регистр) и просто не мусорить в кеш. Это намного быстрее, чем мусорить в кеш с помощью железки.
Но также как и железка этот вариант будет добавлять DRAM refresh задержки в общую обработку случайным образом, т.к. окно (только понял, что это основное, что хотел донести изначально) предзагрузки слишком маленькое, чтобы оно не влияло на результат.
Тогда
prefetchnta(и положить в регистр) и просто не мусорить в кеш
Если применяли loop tiling - то к элементу массива вполне возможны повторные обращения (до того, как перейдём к следующему куску) и в кеше он нужен.
этот вариант будет добавлять DRAM refresh задержки в общую обработку случайным образом
Да, какой то процент замедления от этого будет, ничего не поделаешь.
Возможно нужно clflushopt всех кеш линий массива сделать перед каждым прогоном (пока не знаю, как в расте это правильно сделать). Ещё есть вопросы к среде исполнения т.к. разница в 1мс вне зависимости от подхода выглядит очень странно. Возможно нужно проводить бенч на bare metal, чтобы исключить постороннее влияние.
Поменял местами бенчи, увеличил размер массива до 16MiB, поменял код в перфетче на (смешанный prefetch кеш линий начала след. двух циклов [там 2-3 порта для загрузки ymm, поэтому после каждых двух загрузок из памяти поставил prefetch]): "2:",
// ---- PREFETCH 2 iterations ahead (256 bytes) ----
// ---- Main loads ----
"vaddps ymm0, ymm0, [rdi + r10*4]",
"vaddps ymm1, ymm1, [rdi + r10*4 + 32]",
"prefetcht0 [rdi + r10*4 + 128]",
"vaddps ymm2, ymm2, [rdi + r10*4 + 64]",
"vaddps ymm3, ymm3, [rdi + r10*4 + 96]",
"prefetcht0 [rdi + r10*4 + 256]",
и получаю такое:AVX2 prefetch assembly sum: Sum=8387048.000; best time = 3.43813ms
AVX2 normal assembly sum: Sum=8387048.000; best time = 4.428003msAVX2 prefetch assembly sum: Sum=8388720.000; best time = 3.4316ms
AVX2 normal assembly sum: Sum=8388720.000; best time = 3.44306msAVX2 prefetch assembly sum: Sum=8389057.000; best time = 3.506484ms
AVX2 normal assembly sum: Sum=8389057.000; best time = 3.44506msAVX2 prefetch assembly sum: Sum=8388825.000; best time = 3.545974ms
AVX2 normal assembly sum: Sum=8388825.000; best time = 4.455999ms
при смене порядка бенчей к оригинальному, но со всеми изменениями выше:AVX2 normal assembly sum: Sum=8388928.000; best time = 3.761652ms
AVX2 prefetch assembly sum: Sum=8388928.000; best time = 3.715009msAVX2 normal assembly sum: Sum=8389341.000; best time = 3.425933ms
AVX2 prefetch assembly sum: Sum=8389341.000; best time = 3.466136msAVX2 normal assembly sum: Sum=8390126.000; best time = 3.712881ms
AVX2 prefetch assembly sum: Sum=8390126.000; best time = 3.749143msAVX2 normal assembly sum: Sum=8389072.000; best time = 4.363928ms
AVX2 prefetch assembly sum: Sum=8389072.000; best time = 4.551079msAVX2 normal assembly sum: Sum=8387146.000; best time = 4.432056ms
AVX2 prefetch assembly sum: Sum=8387146.000; best time = 3.523452msAVX2 normal assembly sum: Sum=8388622.000; best time = 3.360004ms
AVX2 prefetch assembly sum: Sum=8388622.000; best time = 4.496095ms
ещё лучше можно сделать так (можно до 8+ [нужно смотреть по процу, сколько у него их] линий держать некешируемых), т.к. мы только читаем (проблема с доп. задержкой в 1мс остаётся, но происходит гораздо реже для prefetchnta варианта): "2:",
// ---- PREFETCH 2 iterations ahead (256 bytes) ----
// ---- Main loads ----
"vaddps ymm0, ymm0, [rdi + r10*4]",
"vaddps ymm1, ymm1, [rdi + r10*4 + 32]",
"prefetchnta [rdi + r10*4 + 128]",
"prefetchnta [rdi + r10*4 + 256]",
"vaddps ymm2, ymm2, [rdi + r10*4 + 64]",
"vaddps ymm3, ymm3, [rdi + r10*4 + 96]",
"prefetchnta [rdi + r10*4 + 192]",
"prefetchnta [rdi + r10*4 + 320]",
AVX2 normal assembly sum: Sum=8388643.000; best time = 3.431242ms
AVX2 prefetch assembly sum: Sum=8388643.000; best time = 3.271411ms
Спасибо за эксперимент! И вот ещё вариант на рандоме комментом выше. У вас, кстати, какой процессор? Копилот пишет, что на Intel (Skylake+) будет "Prefetch helps slightly (5–15%)" - это я и наблюдаю, правда на Sappjire Rapids, но игогда и 25%, а вот AMD Zen 3/4 не всё так шоколадно - Often no benefit or regression. Но у меня нет AMD что б проверить.
7 1800X (старый обычный Zen).
256MiB (со всем, что я там наделал. с prefetcht0 на 0.2-0.35ms дольше исполняется чем с prefetchnta, а так стабильно предзагрузка лучше)
AVX2 normal assembly sum: Sum=134216776.000; best time = 57.612553ms
AVX2 prefetch assembly sum: Sum=134216776.000; best time = 56.600445ms
цикл развёрнут на все 16 регистров (предзагрузке чуть хуже становится, обычному варианту на % лучше):
AVX2 normal assembly sum: Sum=134225120.000; best time = 57.081848ms
AVX2 prefetch assembly sum: Sum=134225120.000; best time = 56.624981ms
Рандом (одинаково или так):
Random load NO prefetch : 216 cycles
Random load WITH prefetch: 180 cycles
Improvement: +16.67 %
Раз уж вы стали разбирать нативные оптимизации под конкретный процессоh, то почему бы не прокинуть заодно target-cpu=native, чтоб llvm сам всё сделал
Я пробовал, конечно, но на данном примере эффект на обнаружил (хотя мог и ошибиться, указав опцию неверно или не там). Тут ещё многое зависит от того, как именно реализован тот же Vec, так что llvm работает с тем, что ему Раст выдал. Я не случайно интеловский компилятор взял, вот он под нативный процессор хоста, но котором компилируется очень хорошо отрабатывает. Вообще я хотел именно упор на интеграцию ассемблера в статье сделать, а что касается оптимизаций, то тут надо взять кусочек кода на Расте, скомпилять так и сяк и сравнить. Я на досуге про это в статью возможно добавлю, чтобы вопросов меньше было.
Это флаг компилятора. Обычно либо скармливается с флагом -C в rustc либо указывается в toml в качестве дополнительных флагов либо через RUSTFLAGS как в комментарии в закрепе. По сути это избавляет вас от ручного выбора нужного процессора и его фич при оптимизации. Так что если без старых флагов, но с target=native получились примерно те же цифры, то поздравляю - флаг заработал как надо.
А для бенчмарков у Rust есть довольно приятный набор инструментов. Хоть бы тот же criterion попользовали, а то всё ручками да ручками, ещё и статистика небось неравномерная получается.
Да, я как интернеты учат, вставил опцию в .cargo\config.toml, это включает и AVX2 и FMA и всё остальное:
[build]
rustflags = ["-C", "target-cpu=native"]и в Cargo.toml до кучи
[profile.release]
codegen-units = 1
lto = true
opt-level = 3В принципе оно работает, я вижу AVX2 в выдаче, но не везде.
Про criterion я знаю, но он добавит свою "обвязку", просто хотелось оставить "минимальный" ассемблер.
Но вообще оптимизирует он местами приятно. Вот сегодня поиграл с бинарным поиском — известный в узких кругах Даниель запостил You can beat the binary search, я взял оттуда код, перекинул его на AVX2, затем в Раст, получилось как-то так:
бинарный поиск на расте AVX2 - сотня строк
#[target_feature(enable = "avx2")]
#[inline] // allowed
unsafe fn simd_quad_branchless_avx2_raw(ptr: *const u16, size: usize, pos: u16) -> bool {
const GAP: usize = 16;
// Small case
if size < GAP {
let mut p = ptr;
let end = ptr.add(size);
while p < end {
if *p == pos {
return true;
}
p = p.add(1);
}
return false;
}
let num_blocks = size / GAP;
let mut base = 0usize;
let mut n = num_blocks;
// -------------------------------
// Quad branchless search
// -------------------------------
while n > 3 {
let quarter = n >> 2;
let k1 = *ptr.add((base + quarter + 1) * GAP - 1);
let k2 = *ptr.add((base + 2 * quarter + 1) * GAP - 1);
let k3 = *ptr.add((base + 3 * quarter + 1) * GAP - 1);
let c1 = (k1 < pos) as usize;
let c2 = (k2 < pos) as usize;
let c3 = (k3 < pos) as usize;
base += (c1 + c2 + c3) * quarter;
n -= 3 * quarter;
}
// -------------------------------
// Binary refinement
// -------------------------------
while n > 1 {
let half = n >> 1;
let key = *ptr.add((base + half + 1) * GAP - 1);
let cmp = (key < pos) as usize;
base += cmp * half;
n -= half;
}
// -------------------------------
// Final block selection
// -------------------------------
let key = *ptr.add((base + 1) * GAP - 1);
let cmp = (key < pos) as usize;
let lo = base + cmp;
// -------------------------------
// SIMD AVX2 block equality check
// -------------------------------
mark!("begin avx2");
if lo < num_blocks {
let blk = ptr.add(lo * GAP);
let needle = _mm256_set1_epi16(pos as i16);
let v = _mm256_loadu_si256(blk as *const __m256i);
let hit = _mm256_cmpeq_epi16(v, needle);
return _mm256_movemask_epi8(hit) != 0;
}
mark!("end avx2");
// -------------------------------
// Tail
// -------------------------------
let mut p = ptr.add(num_blocks * GAP);
let end = ptr.add(size);
while p < end {
let v = *p;
if v >= pos {
return v == pos;
}
p = p.add(1);
}
false
}
и к удивлению на простом бенчмарке Раст своим стандартным .binary_search() его даже чуть обогнал, потому что по массиву фиксированного и заранее известного размера решил "в лоб" и на серии cmov (это contidional move) без всяких бранчей практически обскакал AVX2:
ассемблер из Растаманского binary_search
# === begin arr.binary_search ===
#NO_APP
xor edx, edx
cmp si, cx
setbe dl
shl edx, 11
cmp word ptr [r9 + 2*rdx + 2048], cx
lea r8, [rdx + 1024]
cmova r8, rdx
cmp word ptr [r9 + 2*r8 + 1024], cx
lea rdx, [r8 + 512]
cmova rdx, r8
cmp word ptr [r9 + 2*rdx + 512], cx
lea r8, [rdx + 256]
cmova r8, rdx
cmp word ptr [r9 + 2*r8 + 256], cx
lea rdx, [r8 + 128]
cmova rdx, r8
cmp word ptr [r9 + 2*rdx + 128], cx
lea r8, [rdx + 64]
cmova r8, rdx
cmp word ptr [r9 + 2*r8 + 64], cx
lea rdx, [r8 + 32]
cmova rdx, r8
cmp word ptr [r9 + 2*rdx + 32], cx
lea r8, [rdx + 16]
cmova r8, rdx
cmp word ptr [r9 + 2*r8 + 16], cx
lea rdx, [r8 + 8]
cmova rdx, r8
cmp word ptr [r9 + 2*rdx + 8], cx
lea r8, [rdx + 4]
cmova r8, rdx
cmp word ptr [r9 + 2*r8 + 4], cx
lea rdx, [r8 + 2]
cmova rdx, r8
lea r8, [rdx + 1]
cmp word ptr [r9 + 2*rdx + 2], cx
cmova r8, rdx
xor edx, edx
cmp cx, word ptr [r9 + 2*r8]
lea ecx, [rcx + 1]
sete dl
add rax, rdx
#APP
# === end arr.binary_search ===
Ну то есть по такой оптимизации и бенчмаркингу можно отдельную статью замутить, надо только хороших примеров набрать. А так меня просто более низкий уровень интересует, как например вот в этом комменте.
Про criterion я знаю, но он добавит свою "обвязку", просто хотелось оставить "минимальный" ассемблер.
На производительность влияет не только эффективность ассемблера, но и "фазы луны" - температура процессора, прогрев кэшей, работа соседних процессов и т.п. В этом плане criterion позволяет все это дело митигировать и собирать чуть более честную статистику. Ну и если делать именно бенчмарки для запуска cargo bench, а не самому крафтить всю эту инфраструктуру, то код для расчёта не будет мешать коду бенчмарков. То бишь ассемблер будет чище.
Не оставим Расту никаких шансов, включив кодогенерацию AVX2 и оптимизацию под наш конкретный процессор:
А почему расту этого не сказали?
Сказали конечно, ведь всё это время мы работали с [build] rustflags = ["-C", "target-feature=+avx512f"], +avx2 я пробовал в том числе, но оптимизация работает до определённого "предела", у Интеловского компилятора в общем тоже самое, если ему заказать AVX512, то он не будет повально везде его использовать, вот и у Раста оптимизация и векторизация не так хорошо работают. Опцию я включал в .cargo\config.toml, но я мог и ошибиться, если вы сможете заставить его сгенерировать более оптимальный код для сложения, то напишите пожалуйста.
Я не настоящий сварщик и на rust только поглядываю со стороны. Погуглил - похоже, дело в том, что rust трепетно относится к точности операций (см. здесь) и глобально задать fast-math (без которого clang тоже отказывается векторизовать аналогичный цикл, поскольку векторизация меняет порядок сложений и может влиять на результат) нельзя. Советуют явно использовать интринсики . С ними работает, и из кода
#![feature(core_intrinsics)]
use rand::prelude::*;
use std::intrinsics::fadd_fast;
const N: usize = 1024 * 1024;
fn main() {
let mut rng = rand::rng();
let data: Vec<f32> = (0..N).map(|_| rng.random()).collect();
let mut sum: f32 = 0.;
for val in data {
sum = unsafe {fadd_fast(sum, val)};
}
println!("sum = {}", sum);
}через RUSTFLAGS=‘-C target-feature=+avx2’ cargo build --release генерируется нормальный векторный вариант c vaddps и ymm регистрами. Можно ли заставить sum() использовать быструю математику - не знаю, но в любом случае так попроще, чем вручную писать на ассемблере.
Класс, спасибо, вот ради таких комментов я и пишу статьи. Про fadd_fast() я не знал. На самом деле было бы, конечно здорово, чтобы он выгонял AVX2 код и из "plain" for цикла, как это интеловский компилятор делает, но этого мне добиться не удалось.
Но с core_intrinsics и fadd_fast() есть нюанс:
Так что компилировать придётся с nightly
cargo +nightly rustc -r -- --emit=asm -C "llvm-args=-x86-asm-syntax=intel"И да, тогда цикл вот так выглядит:
.LBB4_13:
vaddps ymm0, ymm0, ymmword ptr [rax + 4*rcx - 224]
vaddps ymm1, ymm1, ymmword ptr [rax + 4*rcx - 192]
vaddps ymm2, ymm2, ymmword ptr [rax + 4*rcx - 160]
vaddps ymm3, ymm3, ymmword ptr [rax + 4*rcx - 128]
vaddps ymm0, ymm0, ymmword ptr [rax + 4*rcx - 96]
vaddps ymm1, ymm1, ymmword ptr [rax + 4*rcx - 64]
vaddps ymm2, ymm2, ymmword ptr [rax + 4*rcx - 32]
vaddps ymm3, ymm3, ymmword ptr [rax + 4*rcx]
add rcx, 64
cmp rcx, 1048632
jne .LBB4_13Но хотелось бы остаться в рамках stable.
Вот ещё более быстрый и более точный вариант и без unsafe из одноимённого блога.
#![allow(internal_features)]
#![feature(core_intrinsics)]
use std::intrinsics::fadd_algebraic;
fn sum_block(arr: &[f32]) -> f32 {
arr.iter().fold(0.0, |x, y| fadd_algebraic(x, *y))
}
pub fn sum_orlp(arr: &[f32]) -> f32 {
let mut chunks = arr.chunks_exact(256);
let mut sum = 0.0;
let mut c = 0.0;
for chunk in &mut chunks {
let y = sum_block(chunk) - c;
let t = sum + y;
c = (t - sum) - y;
sum = t;
}
sum + (sum_block(chunks.remainder()) - c)
}
Тут ещё и борьба с накоплением ошибок. И да, fadd_algebraic безопасен, но компилируется в тот же vaddps, так что выглядит предпочтительнее.
Вот ещё более быстрый и более точный вариант и без unsafe из одноимённого блога.
Да, это алгоритм суммирования Кэхэна. В принципе компенсированное суммирование не было основной целью статьи, но это безусловно отличное дополнение.
Этот пример чуть больше проливает свет на причину происходящего, А то у неподготовленного читателя может появится мысль, что компиляторы тупые, или ещё более крамольная мысль - что Rust не блейзенгли =)
Да, борьба с накоплением ошибки происходит в основном за счёт этого куска:
let t = sum + y;
c = (t - sum) - y;
И если бы мы разрешили ассоциативность для float, то компилятор посмотрел бы и такой “бро, ща я оптимизирую твой код”:
c = (sum + y - sum) - y; // c = 0 <- компилятор выкидывает "с" и ломает нашу задумку.
И чтобы компиляторы не портили наш численно устойчивый код им запрещено его неявно оптимизировать.
Тут раскрывается, что упор раста на безопасность - это не только про владение памятью.
Да, там есть возможности, а уж вкупе с тем, что мы легко (но без фанатизма) можем инлайнить ассемблер в код в 64-бит окружении (и легко контролировать получаемый код), чего без плясок с бубном в C++ / MSVC не достичь, то просто класс, зтакий "швейцарский ножик". Кому как, а мне он нравится всё больше и больше.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Ржавый ассемблер