Rust круче C++? Часть 1: скорость

Привет, Хабр!

Спор «Rust или C++» идёт с 2015 года, с выхода Rust 1.0, и за одиннадцать лет превратился в отдельный жанр со своими приколами. «В Rust на каждом индексе проверка, вот он и тормозит». «В плюсах проверок нет, значит, быстрее». «Ага, а у Rust ссылки не пересекаются, так что быстрее как раз он». «Паника дорогая», «исключения дорогие», «абстракции бесплатные». Каждая сторона уверена в своём, а в ассемблер почти никто не смотрит, хотя ответ лежит прямо там (и местами он неприятный для обеих сторон).

В одну статью вопрос «круче ли Rust, чем C++» не влез, так что это первая часть, и она про скорость. Безопасность и прочие поводы поругаться ждут своей очереди.

Две ссылки, которые точно не пересекаются

Первым идёт аргумент про ссылки, и тут сразу важный нюансик. Rust и clang оба отдают код в LLVM, хоть и разных версий, так что главные разницы в ассемблере я дальше проверяю с двух сторон: если она пропадает, когда меняешь одну подсказку компилятору, значит, дело было в подсказке. g++ позовём третьим, у него свой оптимизатор и свои привычки. Начнём с крошечного примера, на нём всё видно сразу:

pub fn add_twice(a: &mut i32, b: &i32) {
    *a += *b;
    *a += *b;
}

На C++ то же самое пишется через int& и const int&, тело один в один. А ассемблер разный:

; Rust
add_twice:
    mov   eax, dword ptr [rsi]
    add   eax, eax
    add   dword ptr [rdi], eax
    ret

; clang -O3 (у g++ то же самое, только операнды в другом порядке)
add_twice:
    mov   eax, dword ptr [rdi]
    add   eax, dword ptr [rsi]
    mov   dword ptr [rdi], eax
    add   eax, dword ptr [rsi]
    mov   dword ptr [rdi], eax
    ret

Rust прочитал b один раз, удвоил и прибавил к a. C++ записал a и снова полез за b в память, и по-другому он не может: a и b вполне могут смотреть на одно и то же число, вызов add_twice(x, x) в C++ законный и обязан учетверить x. В Rust такой вызов даже не соберётся, на add_twice(&mut x, &x) компилятор ответит error[E0502]: cannot borrow x as immutable because it is also borrowed as mutable. Раз пересечься ссылки не могут, rustc честно сообщает об этом LLVM атрибутом noalias. То есть мы получаем такое обещание, пока функция работает, эту память либо вообще никто не меняет, либо меняют только через эту ссылку. В промежуточном представлении его видно прямо в объявлении функции:

define void @add_twice(ptr noalias ... %a, ptr noalias ... readonly ... %b)

Почему общая ссылка & на тип с UnsafeCell внутри этот noalias не получает (у &mut он остаётся) и к чему это приводит, мы подробно разбирали в статье про UnsafeCell и noalias, так что здесь пропущу.

Самое забавно, что фокус всё это работает в обе стороны. Пометьте аргументы в C++ как __restrict, и clang выдаст те же четыре инструкции, что и Rust. Перепишите Rust-версию на сырые указатели mut i32 и const i32, и rustc выдаст шесть инструкций, как C++, инструкция в инструкцию. То есть всё это живёт в типе ссылки, а язык просто передаёт её дальше.

На одном сложении разницу не намеришь, нужен цикл:

pub fn sum_into(total: &mut u64, v: &[u64]) {
    for x in v {
        *total += *x;
    }
}

Rust держит сумму в регистре, складывает по четыре числа за проход векторными командами (это и есть векторизация, когда одна инструкция обрабатывает сразу несколько чисел) и пишет total в память один раз, в самом конце. g++ же боится, что total смотрит куда-то внутрь v, и тогда любая запись в total может поменять элемент, до которого цикл ещё не дошёл. Поэтому он пишет сумму в память на каждом шаге и про векторы даже не думает:

; g++ -O3, внутренний цикл sum_into(uint64_t& total, const uint64_t* v, size_t n)
.L6:
    add   rax, QWORD PTR [rsi]
    add   rsi, 8
    mov   QWORD PTR [rdi], rax
    cmp   rdx, rsi
    jne   .L6

clang похитрее и проверяет пересечение прямо во время работы. Не пересекаются, значит, прыгаем в быстрый векторный цикл, пересекаются, значит, идём медленным путём с записью на каждом шаге:

; clang -O3, проверка пересечения в sum_into
    ...
    lea   rcx, [rdi + 8]          ; конец total
    lea   r8, [rsi + 8*rdx]       ; конец массива
    cmp   rdi, r8
    setb  r8b
    cmp   rsi, rcx
    setb  cl
    test  r8b, cl                 ; пересекаются?
    je    .LBB2_8                 ; нет, значит векторный цикл

Мерил на массиве из 4096 u64 (32 КБ, всё лежит в кэше), 50 тысяч повторов:

По скорости clang идёт вровень с Rust, медиана у него даже чуть ниже, но прогоны перекрываются. Догоняет он по сути за счёт той проверки и платит за неё размером: 63 инструкции против 37 у Rust. g++ без подсказки отстаёт от Rust в 2,5 раза, от clang почти в 2,8. С __restrict он векторизует, но складывает в одну цепочку вместо двух, как Rust и clang, и, похоже, его 0,159 растут отсюда. Фанаты плюсов в комментах скажут, что сумму надо копить в локальной переменной, и будут правы, так g++ тоже векторизует. Только это такая же подсказка компилятору, просто написанная руками.

Короче, первый раунд за Rust по очкам: скорость как у clang, но без проверки на пересечение и при коде в 1,7 раза короче, а g++ он обгоняет в 2,5 раза. Компилятор просто знает про его ссылки больше. Зато у Rust есть небольшой налог, которого у C++ по умолчанию нет.

«Проверки границ убивают векторизацию»

Пожалуй, главный аргумент против Rust в любом споре про скорость. Каждый v[i] проверяет, не вылез ли индекс за массив, и если вылез, программа паникует. А раз внутри цикла сидит развилка «упасть или нет», складывать по несколько чисел за раз нельзя. Звучит логично, так что берём функцию, где компилятор заранее не знает, влезет индекс или нет:

pub fn sum_n(v: &[u32], n: usize) -> u32 {
    let mut s = 0u32;
    for i in 0..n {
        s = s.wrapping_add(v[i]);
    }
    s
}

n никак не связано с длиной v, и проверка тут нужна. Но LLVM просто вытащил её из цикла:

sum_n:
    test   rdx, rdx
    je     .LBB3_1
    lea    rax, [rdx - 1]          ; последний индекс, n - 1
    cmp    rsi, rax                ; длина <= n - 1?
    jbe    .LBB3_11                ; тогда сразу паника
    ...
.LBB3_7:                           ; обычный векторный цикл без проверок
    movdqu xmm2, xmmword ptr [rdi + 4*rax]
    paddd  xmm1, xmm2
    movdqu xmm2, xmmword ptr [rdi + 4*rax + 16]
    paddd  xmm0, xmm2
    add    rax, 8
    cmp    rcx, rax
    jne    .LBB3_7
    ...
.LBB3_11:
    ...
    mov    rdi, rsi                ; индекс для сообщения равен длине
    call   core::panicking::panic_bounds_check

Но почему так вообще можно? Если n больше длины, исходный цикл всё равно упадёт, когда доберётся до индекса len, а до этого момента снаружи ничего не видно: сумма живёт в регистре и пропадёт вместе с паникой. Раз так, можно упасть сразу и с тем же индексом, сообщение выйдет слово в слово как у честного цикла: index out of bounds: the len is 5 but the index is 5.

Если цикл пишет в память, такая тема уже не прокатит, ведь первые элементы обязаны записаться до падения:

pub fn scale_n(dst: &mut [u32], src: &[u32], n: usize) {
    for i in 0..n {
        dst[i] = src[i] * 3;
    }
}

Здесь LLVM сначала считает, докуда точно безопасно, гонит до этого места быстрый векторный цикл без проверок, а остаток добивает поштучно, уже с проверками. Интереснее всего сравнить начало функции с тем, что делает clang на C++ с обычными указателями:

; Rust: k = min(dst.len(), src.len(), n - 1)
    lea    r9, [r8 - 1]
    cmp    rcx, rsi
    mov    rax, rsi
    cmovb  rax, rcx
    cmp    rax, r9
    cmovae rax, r9

; clang: можно ли вектором, если dst и src пересекаются?
    mov    rcx, rdi
    sub    rcx, rsi                ; dst - src
    cmp    rcx, 32
    setb   cl                      ; ближе 32 байт, тогда поштучно

Rust перед циклом проверяет длины, C++ перед циклом проверяет пересечение, и это довольно смешная симметрия. Внутри быстрого цикла проверок нет ни у того, ни у другого, а по размеру выходит 52 инструкции у Rust против 60 у clang и 56 у g++. Если в начале функции сразу обрезать срезы через let (dst, src) = (&mut dst[..n], &src[..n]);, паники из цикла уйдут совсем и останется 47 инструкций. Вариант через zip вообще обходится без паник и укладывается в 34 инструкции, правда n он не принимает и идёт до конца более короткого среза. И ещё в копилку C++: тот же цикл на std::vector с проверяющим .at() clang векторизует, а g++ нет.

Проверка в цикле остаётся там, где вынести её некуда, например при выборке по случайным индексам:

pub fn gather(v: &[u32], idx: &[usize]) -> u32 {
    let mut s = 0u32;
    for &i in idx {
        s = s.wrapping_add(v[i]);
    }
    s
}

Каждый индекс свой, и в цикле сидят сравнение cmp и переход jae на панику:

.LBB0_3:
    mov   r8, qword ptr [rdx + r9]
    cmp   r8, rsi                 ; i < len?
    jae   .LBB0_6                 ; нет, паника
    add   eax, dword ptr [rdi + 4*r8]
    add   r9, 8
    cmp   rcx, r9
    jne   .LBB0_3

Без проверки, через get_unchecked, LLVM разворачивает этот цикл по восемь элементов за проход, и выглядит это бодрее. Казалось бы, вот тут-то проверка и должна выстрелить, но нет. Когда всё лежит в кэше (4096 элементов), медианы такие: с проверкой 0,35 нс на элемент, без неё 0,36, clang 0,33, g++ 0,32, а по отдельным прогонам всё гуляет от 0,25 у g++ до 0,59 у Rust с проверкой (прогонов тут шесть). Когда индексов на 32 МБ, они уже не лезут ни в L1, ни в L2 и в лучшем случае читаются из L3 (у процессора, на котором я мерил, он на 260 МБ). Тут меня чуть не развёл сам бенчмарк, в общем прогоне вариант с проверкой выходил медленнее, 0,7–1,6 против 0,6–1,0, но мерился он всегда первым в процессе. Перемерил каждый вариант в отдельном процессе, чередуя порядок, по 12 запусков, и получил медиану 0,70 нс на элемент с проверкой и 0,71 без неё. Процессор заранее угадывает, что паники не будет, а сам цикл, похоже, и так упирается в загрузки: сначала индекс, потом число по нему. Так что проверку в замере я не поймал, ассемблер тут просто выглядит страшнее, чем работает.

Раз zip выкинул все проверки, напрашивается вывод, что итераторы всегда быстрее индексов. Не торопимся.

Итератор или индекс?

На простой сумме разницы нет вообще. for i in 0..v.len() { s += v[i] } и v.iter().fold(...) дают один и тот же ассемблер, отличается только место, где обнуляется регистр. Индекс, который бегает до длины самого среза, LLVM видит насквозь.

Забавнее с итераторами, которые что-то считают. Задачка: сколько чисел от 0 до n с шагом 4. Два варианта на одном и том же итераторе:

fn by_count(n: i32) -> usize { (0..n).step_by(4).count() }
fn by_len(n: i32) -> usize { (0..n).step_by(4).len() }\

Ответ одинаковый, а время нет.

На n = 2_000_000_000 вариант с count() работает 173–194 мс, вариант с len() укладывается в 53–58 нс, и это уже порог самого таймера, в функции десяток инструкций и никакого цикла. Больше чем в миллион раз разницы на одном итераторе лол.

len() спрашивает у итератора размер, а StepBy над диапазоном считает его формулой. Своего count() у StepBy нет, он по умолчанию сводится к fold с прибавлением единички, а fold у StepBy честно перебирает выданные элементы по одному, прыгая через nth. Такую конструкцию LLVM в формулу уже не свернул.

Поменяйте i32 на u32, и тот же count() схлопнется в четыре инструкции:

cnt_u32:                          ; (0..n).step_by(4).count() для n: u32
    mov   eax, edi
    add   rax, 3
    shr   rax, 2
    ret

За это спасибо std. В core/src/iter/adapters/step_by.rs для диапазонов есть отдельная быстрая версия, которая заранее считает количество шагов, и включена она только для беззнаковых типов: spec_int_ranges!(Range; u8 u16 u32 u64 usize). Знаковые идут общим путём. А (0..=n).step_by(4).count() на i32 даёт около 300–400 мс, и .len() на нём уже не соберётся, потому что RangeInclusive<i32> не реализует ExactSizeIterator, компилятор ответит ошибкой E0599.

Выходит, вся эта бесплатность итератора иногда держится на том, постаралась ли под него std. Кстати, ручной while на i32 из той же задачки отрабатывает за 20 мс, а C++ на том же цикле выдаёт ответ за наносекунды, и это уже следующий раунд.

Где C++ отыгрывается

Начнём с классики про переполнение:

pub fn always(x: i32) -> bool {
    x + 1 > x
}

На C++ clang превращает return x + 1 > x; в mov al, 1 и ret, g++ в mov eax, 1 и ret, то есть оба просто возвращают true и ничего не считают. Rust сравнивает: cmp edi, 2147483647 и setne al. Для Rust переполнение числа со знаком это ошибка программиста, но с заранее прописанным результатом: в релизной сборке значение просто заворачивается по кругу.

Для i32::MAX выражение x + 1 станет самым маленьким отрицательным числом, ответ будет false, и компилятор обязан это учесть. В C++ знаковое переполнение считается неопределённым поведением, тем самым UB. Стандарт про такие места говорит «делать так нельзя, а что выйдет, не моя забота», и компилятор вправе считать, что такого никогда не случится.

Пример:

pub fn count_step(n: i32) -> i32 {
    let mut c = 0;
    let mut i = 0;
    while i <= n {
        c += 1;
        i += 4;
    }
    c
}

C++ версию с for (int i = 0; i <= n; i += 4) clang и g++ превращают в формулу на семь инструкций без всякого цикла:

; clang -O3
count_step:
    mov    ecx, edi
    shr    ecx, 2
    inc    ecx                    ; n / 4 + 1
    xor    eax, eax
    test   edi, edi
    cmovns eax, ecx               ; для отрицательного n ноль
    ret

Rust на том же коде векторизует сам счётчик: прибавляет вектор из двоек и проходит восемь итераций за раз. Старается изо всех сил, но от цикла так и не избавляется. На n = 2_000_000_000 выходит 20,5–23,8 мс у Rust против 28 нс у C++, и эти 28 нс почти целиком уходят на сам замер времени, на функцию из семи инструкций приходятся считанные наносекунды.

Почему LLVM не может свернуть Rust-версию в формулу? Если n от i32::MAX - 3 и выше, то i += 4 переполнится раньше, чем условие станет ложным, в релизном Rust i завернётся в минус, и цикл станет бесконечным. Результат такого переполнения в Rust прописан заранее, компилятор обязан его сохранить, поэтому в ассемблере есть отдельная проверка как раз на такие n. Я проверил: на i32::MAX релизная сборка висит, пока её не прибьёт timeout, а отладочная падает с attempt to add with overflow. C++ с -O3 на INT_MAX спокойно возвращает 536870912, а тот же код с -O0 висит. Одна программа ведёт себя по-разному в зависимости от флага компиляции.

Можно взять счётчик пошире, let mut i: i64 с условием while i <= n as i64, тогда переполняться просто нечему, и ассемблер совпадает с clang-овским до инструкции. А можно сказать компилятору то же, что C++ говорит по умолчанию, через unsafe { i.unchecked_add(4) }. Тут LLVM выдает: обе функции у него получились одинаковыми, и вместо второй в ассемблере осталась одна строчка count_step_unchecked = count_step_i64, то есть он просто сделал её вторым именем первой.

C++ получает скорость, потому что разрешает себе додумывать, а Rust меняет её на предсказуемость и даёт unchecked_add для мест, где вы готовы поручиться сами. Но если у вас горячий цикл на i32 с хитрым условием выхода, загляните в ассемблер, мало ли что там.

Отыграться Rust может на памяти.

Восемь байт против шестнадцати

Option<&T> в Rust весит ровно столько же, сколько сама ссылка. Нулевой ссылка не бывает, поэтому ноль свободен, и в нём хранят None. Такое свободное значение внутри типа называют нишей. В C++ std::optional<T*> хранит указатель плюс отдельный флаг «есть значение или нет», и с выравниванием выходит 16 байт. Вот что показали size_of в Rust и sizeof на обеих стандартных библиотеках C++:

Option<u32> без ниши в Rust тоже весит 8 байт, ровно как в C++, а NonZeroU32 по смыслу уже, чем uint32_t, ноль в нём не положишь. И std::string в libc++ такой же компактный, как String, 24 байта, просто optional поверх него всё равно докидывает восемь.

В регистрах та же история. Функция «разыменуй, если есть, иначе верни ноль» в Rust получает Option<&u64> в одном регистре и проверяет его на ноль, как обычный указатель, а C++ получает optional<uint64_t*> в двух:

; Rust, Option<&u64>
    test  rdi, rdi                ; None это просто ноль
    je    .LBB0_1
    mov   rax, qword ptr [rdi]

; clang, std::optional<uint64_t*>
    test  sil, 1                  ; флаг приехал отдельным регистром
    je    .LBB1_1
    mov   rax, qword ptr [rdi]

По инструкциям одно и то же, зато на большом массиве разница уже заметная. Беру 50 млн значений от 0 до 3, где ноль значит «пусто», и суммирую через if let Some(n) = x в Rust и через if (v[i]) s += *v[i] в C++:

Вариант с if в C++ входит в развилку: пустой в среднем каждый четвёртый элемент, порядок случайный, и процессор часто не угадывает, куда пойдёт код. С value_or(0) clang обходится без развилки, а g++ её оставляет, поэтому у него разницы почти нет. В Rust же if let из ассемблера пропал совсем. None хранится как ноль, прибавить ноль это всё равно что ничего не прибавить, и LLVM просто складывает всё подряд векторами. Вдвое меньше памяти плюс векторы дают те самые 2,2–2,3 раза против лучших C++ вариантов с value_or.

Справедливости ради, опытный плюсовик в такой задаче обойдётся без optional. Он возьмёт обычный uint32_t и договорится, что ноль значит «нет значения», а для указателей сделает то же самое через nullptr. Я домерил и этот вариант: те же 200 МБ, clang 28,6 мс, g++ 30,4 мс по медианам, прогоны C++ гуляют в 27–33 мс, у Rust в 25–28. clang собирает ровно тот же векторный цикл, что и Rust, g++ тоже векторизует без развилки, только по-своему, с одной цепочкой сложений. Выходит ничья, а небольшой перевес Rust в такой шум укладывается.

Паника и исключение идут через один и тот же код

По логике холиваров тут всё должно быть по-разному: в C++ исключения, в Rust паники и Result. Берём функцию, которая создаёт вектор, отдаёт его во внешнюю функцию work и возвращает длину. Если work упадёт, вектор надо освободить, пока ошибка летит выше, и для этого компилятор в обоих языках добавляет посадочную площадку, маленький кусок кода, который прибирается после упавшего вызова. Выглядят эти площадки как близнецы:

; Rust: work(&mut v) запаниковала, освобождаем v и летим дальше
.Ltmp2:
    mov   rbx, rax                ; объект исключения
    mov   rsi, qword ptr [rsp]    ; capacity
    test  rsi, rsi
    je    .LBB0_12
    mov   rdi, qword ptr [rsp + 8]
    mov   edx, 1
    call  __rust_dealloc
.LBB0_12:
    mov   rdi, rbx
    call  _Unwind_Resume@PLT

; clang: work(v) бросила исключение, тот же сценарий для std::vector
.Ltmp2:
    mov   rbx, rax
    mov   rdi, qword ptr [rsp]
    test  rdi, rdi
    je    .LBB0_12
    mov   rsi, qword ptr [rsp + 16]
    sub   rsi, rdi
    call  _ZdlPvm@PLT             ; operator delete
.LBB0_12:
    mov   rdi, rbx
    call  _Unwind_Resume@PLT

Это одна и та же схема из Itanium ABI. Ошибка летит вверх по цепочке вызовов, и по пути специальный код, раскрутчик, заходит во все такие площадки. Какая площадка отвечает за какой вызов, записано в таблице в секции .gcc_except_table, её читает personality routine, а сам раскрутчик у обоих общий. Rust-бинарник берёт UnwindRaiseException@GCC_3.0 из libgcc_s, C++ бросает через __cxa_throw в libstdc++ и попадает в ту же libgcc_s. Пока ошибок нет, всё это ничего не стоит: с -C panic=abort в Rust и -fno-exceptions в C++ площадка и таблица исчезают, а инструкции обычного пути не меняются. Как паника раскручивает стек по шагам, мы разбирали в статье про панику и раскрутку.

Замерил 200 тысяч вызовов, в каждом либо успех, либо ошибка, время на один вызов в наносекундах:

В Rust «раскрутка с числом» сделана через resume_unwind(Box::new(x)), «со строкой» через обычный panic! с пустым хуком, в C++ через throw x и throw std::runtime_error. Раскрутка везде стоит микросекунды, это в тысячи раз дороже, чем вернуть число, и в 60–200 раз дороже, чем вернуть строку. Rust тут почти вровень с clang, по медианам медленнее на 4–6%. g++ на той же libgcc_s заметно шустрее. А сборка с libc++ ходит в LLVMвыйlibunwind и оказалась самой медленной.

Самая интересная строчка та, где ошибка строкой: Rust там проигрывает в два раза, и, похоже, из-за мелочи. Строка вида "bad -123" в libstdc++ помещается в буфер прямо внутри std::string, короткие строки до 15 символов в кучу не ходят. А непустой String в Rust всегда лежит в куче, так что format! на каждой ошибке выделяет память. Сколько тут от выделения памяти, а сколько от самого форматирования, я отдельно не разбирал.

Пока счёт почти ровный, и остался последний раунд, сортировка.

Сортировка

10 млн u64, четыре набора: случайные, уже отсортированные, отсортированные наоборот и случайные всего с 16 разными значениями. С одной стороны sort_unstable и sort из Rust, с другой std::sort и std::stable_sort. Сначала только libstdc++, время в миллисекундах:

В 3,3–3,5 раза на случайных и в 15–16 раз на уже отсортированных. По такой таблице прям чешутся руки написать «Rust сортирует в 16 раз быстрее C++!!!!!!!!!!!», но пересоберём тот же бенчмарк clang-ом с -stdlib=libc++:

Тот же clang, тот же код бенчмарка, другая стандартная библиотека, и std::sort ускорился в 2,4 раза на случайных и почти в 8 раз на отсортированных. Rust всё ещё впереди, но теперь уже в 1,3–2,3 раза.

Всё упирается в алгоритмы. sort_unstable в Rust построен на ipnsort, sort на driftsort, оба от Лукаса Бергдолла и Орсона Питерса, так прямо и написано в документации std. ipnsort первым делом проверяет, не отсортирован ли массив уже, и если да, просто выходит:

// core/src/slice/sort/unstable/mod.rs, начало ipnsort
let (run_len, was_reversed) = find_existing_run(v, is_less);
// ...

if run_len == len {
    if was_reversed {
        v.reverse();
    }
    return;
}

Отсюда 9 мс на отсортированных и 15 на обратных, это один проход по массиву плюс разворот. В libstdc++ std::sort устроен как классический интросорт (std::__introsort_loop в bits/stl_algo.h, в GCC 16 он такой же), такую проверку он не делает и отсортированный массив всё равно рекурсивно режет на части, как и случайный. А std::sort в libc++ сделан по мотивам pdqsort того же Орсона Питерса, соавтора ipnsort, об этом сказано в комментарии к introsort. Если очередное разбиение ничего не переставило, libc++ пробует добить обе половины сортировкой вставками и на уже отсортированном массиве справляется почти за линейное время, отсюда 19 мс вместо 148. На случайном массиве у libc++ в запасе ещё и разбиение без развилок, блоками по 64 элемента с битовыми масками. Включается оно для чисел со стандартным сравнением, условие видно прямо в algorithm/sort.h:

template <class _Compare, class _Iter, class _Tp = typename iterator_traits<_Iter>::value_type>
inline const bool __use_branchless_sort =
    __libcpp_is_contiguous_iterator<_Iter>::value && __is_cheap_to_copy<_Tp> && is_arithmetic<_Tp>::value &&
    (__desugars_to_v<__less_tag, __remove_cvref_t<_Compare>, _Tp, _Tp> ||
     __desugars_to_v<__greater_tag, __remove_cvref_t<_Compare>, _Tp, _Tp>);

Так что в этом раунде дерутся стандартные библиотеки, а язык стоит в сторонке. Плюсовик может взять стороннюю сортировку посвежее (такой вариант я не мерил), и в самом языке ничего этому не мешает. Плюс Rust в другом: хороший алгоритм лежит прямо в std и достаётся всем, кто написал .sort_unstable(), без выбора между библиотеками.

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

Как повторить у себя

Компиляторы обожают посчитать ответ заранее и выкинуть весь бенчмарк, поэтому функции в Rust помечены #[inline(never)], а входы и выходы прогнаны через std::hint::black_box. В C++ функции лежат в отдельном .cpp без LTO, и бенчмарк их внутренностей не видит. Если не сказано иначе, каждое число в статье это медиана из трёх прогонов, а внутри прогона медиана из пяти–девяти замеров. Самые показательные примеры я прогнал и на самых свежих GCC 16.2 и clang 23.1 через Compiler Explorer, картина там та же, но отдельные цифры на других компиляторах и железе, конечно, могут сдвинуться. В листингах вырезаны служебные директивы, сокращены длинные имена символов, а косвенные вызовы через GOT показаны как прямые.

Целиком ассемблер смотрится так:

# ассемблер Rust в синтаксисе Intel, рядом появится f.s
rustc --edition 2024 -C opt-level=3 --crate-type=lib --emit=asm \
      -C llvm-args=-x86-asm-syntax=intel f.rs
# pub fn без атрибутов в f.s может не попасть вовсе, даже с циклом, как sum_n:
# вешайте #[unsafe(no_mangle)] или #[inline(never)]

# то же для крейта, файл ищите в target/release/deps/<крейт>-<хеш>.s
cargo rustc --release -- --emit=asm -C llvm-args=-x86-asm-syntax=intel

# повесил ли rustc noalias на аргументы
rustc --edition 2024 -C opt-level=3 --crate-type=lib --emit=llvm-ir f.rs
grep '^define' f.ll

# C++ для сравнения (если clang стоит в нескольких версиях, зовите нужную с номером)
clang++-20 -std=c++20 -O3 -S -masm=intel f.cpp -o f_clang.s
g++ -std=c++20 -O3 -S -masm=intel f.cpp -o f_gcc.s
# libc++ вместо libstdc++, нужны пакеты libc++ и libc++abi под вашу версию clang
clang++-20 -stdlib=libc++ -std=c++20 -O3 f.cpp

# посадочные площадки уходят, обычный путь не меняется
rustc --edition 2024 -C opt-level=3 -C panic=abort --crate-type=lib --emit=asm f.rs -o f_abort.s
clang++-20 -std=c++20 -O3 -fno-exceptions -S f.cpp -o f_noexc.s

Если вам роднее синтаксис AT&T, просто уберите -masm=intel и -C llvm-args=-x86-asm-syntax=intel, по умолчанию и rustc, и clang, и g++ выдают именно его. Ну а теперь можно и подвести счёт.

Так кто быстрее?

Короче, по скорости на одинаковом коде Rust выигрывает там, где знает про код больше: его &mut ни с чем не пересекается, а в ссылке и в NonZero не бывает нуля. C++ догоняет его тут ручными фичами вроде __restrict и договорённости «ноль значит пусто», а в циклах clang догоняет и сам, ценой проверки во время работы и лишнего кода. C++ выигрывает там, где ему разрешено не думать о переполнении. Проверки границ на этих примерах выходят почти вничью, а с ошибками картина интерснее: раскрутка у Rust идёт вровень с clang, g++ раскручивает примерно в 1,7 раза быстрее, а ошибку строкой Rust возвращает вдвое дольше, чем C++ с libstdc++, похоже, из-за выделения памяти. В сортировке же меряются библиотеки. Так что в споре «кто быстрее» правы обе стороны, каждая в своём раунде, и узнать, чей раунд у вас в коде, можно только ассемблером и замером.

Спасибо.

Размещайте облачную инфраструктуру и масштабируйте сервисы с надежным облачным провайдером Beget.
Эксклюзивно для читателей Хабра мы даем бонус 10% при первом пополнении.