Я работаю в компании Parity Technologies, которая поддерживает клиент Parity Ethereum. В этом клиенте нам нужна быстрая 256-битная арифметика, которую приходится эмулировать на программном уровне, потому что никакое оборудование не поддерживает её аппаратно.
Долгое время мы параллельно делаем две реализации арифметики: одну на Rust для стабильных сборок и одну со встроенным ассемблерным кодом (который автоматически используется nightly-версией компилятора). Мы так поступаем, потому что храним 256-битные числа как массивы 64-битных чисел, а в Rust нет никакого способа умножить два 64-битных числа, чтобы получить результат более 64 бит (так как целочисленные типы Rust только доходят до u64). Это несмотря на то, что x86_64 (наша основная целевая платформа) нативно поддерживает 128-битные результаты вычислений с 64-битными числами. Так что мы разделяем каждое 64-битное число на два 32-битных (потому что можно умножить два 32-битных числа и получить 64-битный результат).
impl U256 {
fn full_mul(self, other: Self) -> U512 {
let U256(ref me) = self;
let U256(ref you) = other;
let mut ret = [0u64; U512_SIZE];
for i in 0..U256_SIZE {
let mut carry = 0u64;
// `split` splits a 64-bit number into upper and lower halves
let (b_u, b_l) = split(you[i]);
for j in 0..U256_SIZE {
// This process is so slow that it's faster to check for 0 and skip
// it if possible.
if me[j] != 0 || carry != 0 {
let a = split(me[j]);
// `mul_u32` multiplies a 64-bit number that's been split into
// an `(upper, lower)` pair by a 32-bit number to get a 96-bit
// result. Yes, 96-bit (it returns a `(u32, u64)` pair).
let (c_l, overflow_l) = mul_u32(a, b_l, ret[i + j]);
// Since we have to multiply by a 64-bit number, we have to do
// this twice.
let (c_u, overflow_u) = mul_u32(a, b_u, c_l >> 32);
ret[i + j] = (c_l & 0xffffffff) + (c_u << 32);
// Then we have to do this complex logic to set the result. Gross.
let res = (c_u >> 32) + (overflow_u << 32);
let (res, o1) = res.overflowing_add(overflow_l + carry);
let (res, o2) = res.overflowing_add(ret[i + j + 1]);
ret[i + j + 1] = res;
carry = (o1 | o2) as u64;
}
}
}
U512(ret)
}
}
Вам даже не нужно понимать код, чтобы увидеть, насколько это неоптимально. Проверка выдачи компилятора показывает, что сгенерированный ассемблерный код крайне неоптимален. Он делает много лишней работы, по существу, просто чтобы обойти ограничения Rust. Поэтому мы написали свою версию кода на встроенном ассемблере. Важно использовать именно нашу версию ассемблерного кода, потому что x86_64 изначально поддерживает умножение двух 64-битных значений для получения 128-битного результата. Когда Rust делает
a * b, если a и b представлены в формате u64, процессор реально умножает их и получает 128-битный результат, а затем Rust просто выбрасывает верхние 64 бита. Мы хотим оставить эти 64 верхних бита, и единственный способ эффективного доступа к ним — использовать встроенный ассемблерный код.
Как несложно догадаться, наша реализация на ассемблере оказалась намного быстрее:
name u64.bench ns/iter inline_asm.bench ns/iter diff ns/iter diff % speedup u256_full_mul 243,159 197,396 -45,763 -18.82% x 1.23 u256_mul 268,750 95,843 -172,907 -64.34% x 2.80 u256_mul_small 1,608 789 -819 -50.93% x 2.04
u256_full_mul проверяет функцию выше, u256_mul перемножает два 256-битных числа с получением 256-битного результата (в Rust вы просто создаёте 512-битный результат и отбрасываете верхнюю половину, но на ассемблере у нас отдельная реализация), а u256_mul_small перемножает два маленьких 256-битных числа. Как видите, наш ассемблерный код в 2,8 раза быстрее. Это намного, намного лучше. К сожалению, он работает только в nightly-версии компилятора, и даже в нём только для платформы x86_64. Правда в том, что понадобилось много усилий и куча неудачных попыток, чтобы код Rust стал «хотя бы» вдвое быстрее ассемблера. Просто не существовало хорошего способа передать компилятору необходимые данные.
Всё изменилось в версии Rust 1.26. Теперь мы можем написать a as u128 * b as u128 — и компилятор будет использовать нативное для платформы x86_64 умножение u64-to-u128 (даже хотя вы транслируете оба числа в u128, он понимает, что они «на самом деле» всего u64, а вам просто нужен результат u128). Это значит, что наш код теперь выглядит следующим образом:
impl U256 {
fn full_mul(self, other: Self) -> U512 {
let U256(ref me) = self;
let U256(ref you) = other;
let mut ret = [0u64; U512_SIZE];
for i in 0..U256_SIZE {
let mut carry = 0u64;
let b = you[i];
for j in 0..U256_SIZE {
let a = me[j];
// This compiles down to just use x86's native 128-bit arithmetic
let (hi, low) = split_u128(a as u128 * b as u128);
let overflow = {
let existing_low = &mut ret[i + j];
let (low, o) = low.overflowing_add(*existing_low);
*existing_low = low;
o
};
carry = {
let existing_hi = &mut ret[i + j + 1];
let hi = hi + overflow as u64;
let (hi, o0) = hi.overflowing_add(carry);
let (hi, o1) = hi.overflowing_add(*existing_hi);
*existing_hi = hi;
(o0 | o1) as u64
}
}
}
U512(ret)
}
}
Хотя это почти наверняка медленнее, чем нативный для LLVM тип
i256, но скорость очень сильно выросла. Здесь мы сравниваем с оригинальной реализацией Rust:
name u64.bench ns/iter u128.bench ns/iter diff ns/iter diff % speedup u256_full_mul 243,159 73,416 -169,743 -69.81% x 3.31 u256_mul 268,750 85,797 -182,953 -68.08% x 3.13 u256_mul_small 1,608 558 -1,050 -65.30% x 2.88
Что самое замечательное, теперь повышение скорости сделано в стабильной версии компилятора. Поскольку мы компилируем бинарники клиента только стабильной версией, то раньше получить преимущество в скорости могли лишь пользователи, которые сами компилировали клиент из исходников. Поэтому нынешнее улучшение затронуло многих пользователей. Но погодите, это ещё не всё! Новый скомпилированный код со значительным отрывом превосходит и реализацию на ассемблере, даже в тесте перемножения 256-битных чисел с получением 256-битного результата. Это несмотря на то, что код Rust по-прежнему сначала выдаёт 512-битный результат, а затем отбрасывает верхнюю половину, а реализация на ассемблере этого не делает:
name inline_asm.bench ns/iter u128.bench ns/iter diff ns/iter diff % speedup u256_full_mul 197,396 73,416 -123,980 -62.81% x 2.69 u256_mul 95,843 85,797 -10,046 -10.48% x 1.12 u256_mul_small 789 558 -231 -29.28% x 1.41
Для полного умножения это очень мощное улучшение, тем более что оригинальный код использовал высокооптимизированные ассемблерные инкантации. Теперь слабонервные могут выйти, потому что я собираюсь погрузиться в сгенерированный ассемблер.
Вот написанный вручную ассемблерный код. Я представил его без комментариев, потому что хочу прокомментировать ту версию, которая фактически создаётся компилятором (поскольку, как вы увидите, макрос asm! скрывает больше, чем можно было ожидать):
impl U256 {
/// Multiplies two 256-bit integers to produce full 512-bit integer
/// No overflow possible
pub fn full_mul(self, other: U256) -> U512 {
let self_t: &[u64; 4] = &self.0;
let other_t: &[u64; 4] = &other.0;
let mut result: [u64; 8] = unsafe { ::core::mem::uninitialized() };
unsafe {
asm!("
mov $8, %rax
mulq $12
mov %rax, $0
mov %rdx, $1
mov $8, %rax
mulq $13
add %rax, $1
adc $$0, %rdx
mov %rdx, $2
mov $8, %rax
mulq $14
add %rax, $2
adc $$0, %rdx
mov %rdx, $3
mov $8, %rax
mulq $15
add %rax, $3
adc $$0, %rdx
mov %rdx, $4
mov $9, %rax
mulq $12
add %rax, $1
adc %rdx, $2
adc $$0, $3
adc $$0, $4
xor $5, $5
adc $$0, $5
xor $6, $6
adc $$0, $6
xor $7, $7
adc $$0, $7
mov $9, %rax
mulq $13
add %rax, $2
adc %rdx, $3
adc $$0, $4
adc $$0, $5
adc $$0, $6
adc $$0, $7
mov $9, %rax
mulq $14
add %rax, $3
adc %rdx, $4
adc $$0, $5
adc $$0, $6
adc $$0, $7
mov $9, %rax
mulq $15
add %rax, $4
adc %rdx, $5
adc $$0, $6
adc $$0, $7
mov $10, %rax
mulq $12
add %rax, $2
adc %rdx, $3
adc $$0, $4
adc $$0, $5
adc $$0, $6
adc $$0, $7
mov $10, %rax
mulq $13
add %rax, $3
adc %rdx, $4
adc $$0, $5
adc $$0, $6
adc $$0, $7
mov $10, %rax
mulq $14
add %rax, $4
adc %rdx, $5
adc $$0, $6
adc $$0, $7
mov $10, %rax
mulq $15
add %rax, $5
adc %rdx, $6
adc $$0, $7
mov $11, %rax
mulq $12
add %rax, $3
adc %rdx, $4
adc $$0, $5
adc $$0, $6
adc $$0, $7
mov $11, %rax
mulq $13
add %rax, $4
adc %rdx, $5
adc $$0, $6
adc $$0, $7
mov $11, %rax
mulq $14
add %rax, $5
adc %rdx, $6
adc $$0, $7
mov $11, %rax
mulq $15
add %rax, $6
adc %rdx, $7
"
: /* $0 */ "={r8}"(result[0]), /* $1 */ "={r9}"(result[1]), /* $2 */ "={r10}"(result[2]),
/* $3 */ "={r11}"(result[3]), /* $4 */ "={r12}"(result[4]), /* $5 */ "={r13}"(result[5]),
/* $6 */ "={r14}"(result[6]), /* $7 */ "={r15}"(result[7])
: /* $8 */ "m"(self_t[0]), /* $9 */ "m"(self_t[1]), /* $10 */ "m"(self_t[2]),
/* $11 */ "m"(self_t[3]), /* $12 */ "m"(other_t[0]), /* $13 */ "m"(other_t[1]),
/* $14 */ "m"(other_t[2]), /* $15 */ "m"(other_t[3])
: "rax", "rdx"
:
);
}
U512(result)
}
}
А вот что он генерирует. Я обильно прокомментировал код, чтобы вы могли понять, что происходит, даже если никогда в жизни не работали с ассемблером, но вам понадобится знание некоторых базовых понятий низкоуровневого программирования, таких как разница между памятью и регистрами. Если нужен учебник по структуре CPU, можно начать со статьи Википедии о структуре и реализации процессоров:
bigint::U256::full_mul:
/// вступление - это генерирует Rust
pushq %r15
pushq %r14
pushq %r13
pushq %r12
subq $0x40, %rsp
/// загрузка в регистры входных массивов...
movq 0x68(%rsp), %rax
movq 0x70(%rsp), %rcx
movq 0x78(%rsp), %rdx
movq 0x80(%rsp), %rsi
movq 0x88(%rsp), %r8
movq 0x90(%rsp), %r9
movq 0x98(%rsp), %r10
movq 0xa0(%rsp), %r11
/// ...и немедленно обратно в память
/// Так делает компилятор Rust. Есть способ
/// избежать этого, но вернусь к нему позже
/// Эти четыре представляют первый входной массив
movq %rax, 0x38(%rsp)
movq %rcx, 0x30(%rsp)
movq %rdx, 0x28(%rsp)
movq %rsi, 0x20(%rsp)
/// Эти четыре - выходной массив, который инициализируется
/// как второй массив на входе.
movq %r8, 0x18(%rsp)
movq %r9, 0x10(%rsp)
movq %r10, 0x8(%rsp)
movq %r11, (%rsp)
/// Этот основной цикл вы увидите много раз,
/// так что не буду всё время к нему возвращаться.
///
/// for i in 0..U256_SIZE {
/// for j in 0..U256_SIZE {
/// /* Loop body */
/// }
/// }
/// Загрузка нулевого элемента входного массива в
/// регистр "%rax". Первый элемент в реальности уже
/// в `%rax`, но его загружают всё равно.
/// Это потому что макрос `asm!` прячет много деталей,
/// о чём я расскажу позже.
movq 0x38(%rsp), %rax
/// Умножение на нулевой элемент выходного массива. Выполняется
/// в памяти, а не в регистре, и поэтому значительно медленнее.
/// Опять же, об этом позже.
mulq 0x18(%rsp)
/// `mulq` перемножает 64-битные числа и сохраняет нижние и верхние
/// 64 бита результата в `%rax` и `%rdx`, соответственно. Переносим
/// нижние биты в `%r8` (нижние 64 бита 512-битного результата),
/// а верхние в `%r9` (следующие нижние 64 бита результата).
movq %rax, %r8
movq %rdx, %r9
/// То же самое делаем для `i = 0, j = 1`
movq 0x38(%rsp), %rax
mulq 0x10(%rsp)
/// Выше мы переместили значения в выходные регистры, на этот раз
/// нужно добавить результаты в выдачу.
addq %rax, %r9
/// Здесь бы добавляем 0, потому что CPU использует "бит переноса"
/// (независимо от переполнения предыдущего сложения)
/// как дополнительный вход. Это по сути то же самое,
/// что добавить 1 к `rdx`, если предыдущее сложение переполнено.
adcq $0x0, %rdx
/// Затем переносим верхние 64 бита умножения (плюс бит переноса
/// от сложения) в третьи снизу 64 бита выдачи.
movq %rdx, %r10
/// Затем продолжаем для `j = 2` и `j = 3`
movq 0x38(%rsp), %rax
mulq 0x8(%rsp)
addq %rax, %r10
adcq $0x0, %rdx
movq %rdx, %r11
movq 0x38(%rsp), %rax
mulq (%rsp)
addq %rax, %r11
adcq $0x0, %rdx
movq %rdx, %r12
/// Делаем то же самое для `i = 1`, `i = 2` и `i = 3`
movq 0x30(%rsp), %rax
mulq 0x18(%rsp)
addq %rax, %r9
adcq %rdx, %r10
adcq $0x0, %r11
adcq $0x0, %r12
/// Эти `xor` просто для гарантии обнуления `%r13`. Снова, это
/// не оптимально (нам вообще не нужно обнулять регистры), но
/// разберёмся с этим.
xorq %r13, %r13
adcq $0x0, %r13
xorq %r14, %r14
adcq $0x0, %r14
xorq %r15, %r15
adcq $0x0, %r15
movq 0x30(%rsp), %rax
mulq 0x10(%rsp)
addq %rax, %r10
adcq %rdx, %r11
adcq $0x0, %r12
adcq $0x0, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x30(%rsp), %rax
mulq 0x8(%rsp)
addq %rax, %r11
adcq %rdx, %r12
adcq $0x0, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x30(%rsp), %rax
mulq (%rsp)
addq %rax, %r12
adcq %rdx, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x28(%rsp), %rax
mulq 0x18(%rsp)
addq %rax, %r10
adcq %rdx, %r11
adcq $0x0, %r12
adcq $0x0, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x28(%rsp), %rax
mulq 0x10(%rsp)
addq %rax, %r11
adcq %rdx, %r12
adcq $0x0, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x28(%rsp), %rax
mulq 0x8(%rsp)
addq %rax, %r12
adcq %rdx, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x28(%rsp), %rax
mulq (%rsp)
addq %rax, %r13
adcq %rdx, %r14
adcq $0x0, %r15
movq 0x20(%rsp), %rax
mulq 0x18(%rsp)
addq %rax, %r11
adcq %rdx, %r12
adcq $0x0, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x20(%rsp), %rax
mulq 0x10(%rsp)
addq %rax, %r12
adcq %rdx, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x20(%rsp), %rax
mulq 0x8(%rsp)
addq %rax, %r13
adcq %rdx, %r14
adcq $0x0, %r15
movq 0x20(%rsp), %rax
mulq (%rsp)
addq %rax, %r14
adcq %rdx, %r15
/// Наконец мы всё перенесли из регистров, так что
/// возвращаем всё на стек
movq %r8, (%rdi)
movq %r9, 0x8(%rdi)
movq %r10, 0x10(%rdi)
movq %r11, 0x18(%rdi)
movq %r12, 0x20(%rdi)
movq %r13, 0x28(%rdi)
movq %r14, 0x30(%rdi)
movq %r15, 0x38(%rdi)
movq %rdi, %rax
addq $0x40, %rsp
popq %r12
popq %r13
popq %r14
popq %r15
retq
Как видно из комментариев, в коде много недостатков. Умножение производится на переменные из памяти, а не из регистров, производятся лишние операции store и load, также и CPU вынужден производить много store и load, прежде чем получить «реальный» код (цикл умножения-сложения). Это очень важно: хотя CPU выполняет сохранения и загрузки параллельно с вычислениями, но код написан таким образом, что CPU не начинает расчёты, пока всё не загрузится. Это потому что макрос
asm скрывает много деталей. По сути, вы говорите компилятору поместить входные данные куда он хочет, а затем подставить в ваш ассемблерный код с помощью строковых манипуляций. Компилятор сохраняет всё в регистры, но затем мы командуем ему поместить входные массивы в память ("m" перед входными параметрами), чтобы он снова загрузил всё в память. Есть способ оптимизировать этот код, но это очень трудно даже для опытного профессионала. Такой код подвержен ошибкам — если вы не обнулили выходные регистры серией инструкций xor, то код будет иногда глючить, но не всегда, выдавая кажущиеся случайными значения, которые зависят от внутреннего состояния вызывающей функции. Вероятно, его можно ускорить заменой "m" на "r" (я не тестировал, потому что обнаружил это только когда начал проверять для статьи, почему старый ассемблерный код настолько медленнее), но глядя на исходники это не очевидно. Сразу поймёт только специалист с глубоким знанием синтаксиса ассемблера LLVM.
Для сравнения, код Rust с использованием u128 выглядит совершенно понятно: что написано — то и получите. Даже если вы не ставили целью оптимизацию, то вероятно напишете что-то похожее как самое простое решение. В то же время код LLVM очень качественный. Вы можете заметить, что он не слишком отличается от кода, написанного вручную, но решает некоторые проблемы (прокомментированные ниже), а также включает пару оптимизаций, о которых я бы даже не подумал. Я не смог найти никаких существенных оптимизаций, которые он пропустил.
Вот сгенерированный ассемблерный код:
bigint::U256::full_mul:
/// Вступление
pushq %rbp
movq %rsp, %rbp
pushq %r15
pushq %r14
pushq %r13
pushq %r12
pushq %rbx
subq $0x48, %rsp
movq 0x10(%rbp), %r11
movq 0x18(%rbp), %rsi
movq %rsi, -0x38(%rbp)
/// Я сначала подумал, что тут пропущена оптимизация,
/// но ему реально нужно это делать (вместо
/// `movq 0x30(%rbp), %rax`), потому что регистр `%rax` ниже
/// забивает `mulq`. Это значит, что он может умножить
/// первый элемент первого массива на любые элементы
/// без необходимости загружать его из памяти,
/// как это делает написанный вручную ассемблерный код.
movq 0x30(%rbp), %rcx
movq %rcx, %rax
/// LLVM умножает из регистра, а не из памяти
mulq %r11
/// LLVM переносит `%rdx` (верхние биты) в регистр, они
/// нам позже понадобятся. Он переносит`%rax`
/// (нижние биты) напрямую в память, потому что
/// с ними больше не будет никаких операций. Это лучше,
/// чем перенос в память и из памяти, как мы делали
/// в предыдущем коде.
movq %rdx, %r9
movq %rax, -0x70(%rbp)
movq %rcx, %rax
mulq %rsi
movq %rax, %rbx
movq %rdx, %r8
movq 0x20(%rbp), %rsi
movq %rcx, %rax
mulq %rsi
/// LLVM использует регистр `%r13` как промежуточный, потому что
/// значение в `%r13` позже всё равно понадобится.
movq %rsi, %r13
movq %r13, -0x40(%rbp)
/// Опять, нужно работать и с нижними, и с верхними битами,
/// так что LLVM переносит в регистры их обоих.
movq %rax, %r10
movq %rdx, %r14
movq 0x28(%rbp), %rdx
movq %rdx, -0x48(%rbp)
movq %rcx, %rax
mulq %rdx
movq %rax, %r12
movq %rdx, -0x58(%rbp)
movq 0x38(%rbp), %r15
movq %r15, %rax
mulq %r11
addq %r9, %rbx
adcq %r8, %r10
/// Эти две инструкции записывают флаги в регистр `%rcx`
pushfq
popq %rcx
addq %rax, %rbx
movq %rbx, -0x68(%rbp)
adcq %rdx, %r10
/// Это записывает флаги из предыдущего вычисления
/// в `%r8`.
pushfq
popq %r8
/// LLVM забирает обратно флаги из `%rcx`, а затем
/// производит сложение с флагом переноса. Это умно.
/// Так нам не нужно делать странное сложение с нулём,
/// ведь мы в одной инструкции совмещаем сложение
/// флага переноса и сложение компонент числа.
///
/// Возможно, способ LLVM и быстрее на современных
/// процессорах, но хранить это в `%rcx` необязательно,
/// потому что флаги всё равно окажутся наверху стека
/// (то есть можно удалить `popq %rcx` выше и этот
/// `pushq %rcx`, и ничего не изменится). Если это и
/// медленнее, то разница ничтожна.
pushq %rcx
popfq
adcq %r14, %r12
pushfq
popq %rax
movq %rax, -0x50(%rbp)
movq %r15, %rax
movq -0x38(%rbp), %rsi
mulq %rsi
movq %rdx, %rbx
movq %rax, %r9
addq %r10, %r9
adcq $0x0, %rbx
pushq %r8
popfq
adcq $0x0, %rbx
/// `setb` используется вместо излишнего обнуления регистров
/// с последующим добавлением бита переноса. `setb` просто
/// устанавливает байт 1 по данному адресу, если установлен
/// флаг переноса (поскольку это по сути `mov`, то такой
/// способ быстрее обнуления и последующего сложения)
setb -0x29(%rbp)
addq %r12, %rbx
setb %r10b
movq %r15, %rax
mulq %r13
movq %rax, %r12
movq %rdx, %r8
movq 0x40(%rbp), %r14
movq %r14, %rax
mulq %r11
movq %rdx, %r13
movq %rax, %rcx
movq %r14, %rax
mulq %rsi
movq %rdx, %rsi
addq %r9, %rcx
movq %rcx, -0x60(%rbp)
/// Это по сути хак для сложения `%r12` и `%rbx` и хранения
/// результата в `%rcx`. Здесь одна инструкция вместо двух,
/// которые понадобились бы в противном случае. `leaq` это
/// инструкция взятия адреса, так что строка по сути такая
/// же, как если бы вы сделали `&((void*)first)[second]` вместо
/// `first + second` на C. Но в ассемблере нет хаков. Каждый
/// грязный трюк - это честно.
leaq (%r12,%rbx), %rcx
/// В остальном коде нет никаких новых трюков, только
/// повторяются старые.
adcq %rcx, %r13
pushfq
popq %rcx
addq %rax, %r13
adcq $0x0, %rsi
pushq %rcx
popfq
adcq $0x0, %rsi
setb -0x2a(%rbp)
orb -0x29(%rbp), %r10b
addq %r12, %rbx
movzbl %r10b, %ebx
adcq %r8, %rbx
setb %al
movq -0x50(%rbp), %rcx
pushq %rcx
popfq
adcq -0x58(%rbp), %rbx
setb %r8b
orb %al, %r8b
movq %r15, %rax
mulq -0x48(%rbp)
movq %rdx, %r12
movq %rax, %rcx
addq %rbx, %rcx
movzbl %r8b, %eax
adcq %rax, %r12
addq %rsi, %rcx
setb %r10b
movq %r14, %rax
mulq -0x40(%rbp)
movq %rax, %r8
movq %rdx, %rsi
movq 0x48(%rbp), %r15
movq %r15, %rax
mulq %r11
movq %rdx, %r9
movq %rax, %r11
movq %r15, %rax
mulq -0x38(%rbp)
movq %rdx, %rbx
addq %r13, %r11
leaq (%r8,%rcx), %rdx
adcq %rdx, %r9
pushfq
popq %rdx
addq %rax, %r9
adcq $0x0, %rbx
pushq %rdx
popfq
adcq $0x0, %rbx
setb %r13b
orb -0x2a(%rbp), %r10b
addq %r8, %rcx
movzbl %r10b, %ecx
adcq %rsi, %rcx
setb %al
addq %r12, %rcx
setb %r8b
orb %al, %r8b
movq %r14, %rax
movq -0x48(%rbp), %r14
mulq %r14
movq %rdx, %r10
movq %rax, %rsi
addq %rcx, %rsi
movzbl %r8b, %eax
adcq %rax, %r10
addq %rbx, %rsi
setb %cl
orb %r13b, %cl
movq %r15, %rax
mulq -0x40(%rbp)
movq %rdx, %rbx
movq %rax, %r8
addq %rsi, %r8
movzbl %cl, %eax
adcq %rax, %rbx
setb %al
addq %r10, %rbx
setb %cl
orb %al, %cl
movq %r15, %rax
mulq %r14
addq %rbx, %rax
movzbl %cl, %ecx
adcq %rcx, %rdx
movq -0x70(%rbp), %rcx
movq %rcx, (%rdi)
movq -0x68(%rbp), %rcx
movq %rcx, 0x8(%rdi)
movq -0x60(%rbp), %rcx
movq %rcx, 0x10(%rdi)
movq %r11, 0x18(%rdi)
movq %r9, 0x20(%rdi)
movq %r8, 0x28(%rdi)
movq %rax, 0x30(%rdi)
movq %rdx, 0x38(%rdi)
movq %rdi, %rax
addq $0x48, %rsp
popq %rbx
popq %r12
popq %r13
popq %r14
popq %r15
popq %rbp
retq
Хотя в сгенерированной LLVM версии есть ещё несколько инструкций, но количество самых медленных директив (load и store) сведено к минимуму. По большей части LLVM избегает избыточной работы, а также применяет много смелых оптимизаций. В результате код выполняется значительно быстрее.
Это не первый раз, когда тщательно написанная реализация Rust превзошла наш код сборки. Несколько месяцев назад я переписал реализацию сложения и вычитания на Rust, ускорив их на 20% и 15%, соответственно, по сравнению с реализацией на ассемблере. Там чтобы превзойти ассемблерный код не требовалась 128-битная арифметика (чтобы использовать полную аппаратную поддержку на Rust следует лишь указать u64:: checked_add/ checked_sub), хотя кто знает — может, в будущем мы применим 128-битную арифметику и еще больше увеличим скорость.
Код из этого примера можно посмотреть здесь, а код реализации сложения/вычитания — здесь. Должен заметить, что, хотя последний уже показывает в бенчмарке превосходство по умножению над реализацией на ассемблере, но на самом деле это связано с тем, что бенчмарк в большинстве случаев выполнял умножение на 0. Мда. Если можно извлечь из этого какой-то урок, так что это информированная оптимизация невозможна без репрезентативных бенчмарков.
Я не считаю, что следует изучить методы оптимизации LLVM и переписать вручную свой вариант ассемблерного кода. Смысл в том, что оптимизирующие компиляторы уже по-настоящему хороши. Их пишут очень умные люди, а компьютеры действительно хороши в том типе оптимизаций (в математическом смысле), какой люди находят довольно трудным. Это работа разработчиков языка — дать нам инструменты, необходимые для максимально полного информирования оптимизатора, каковы наши истинные намерения, и бóльшие целочисленные размеры — ещё один шаг к этому. Rust проделал отличную работу для того, чтобы программисты писали программы, легко понятные и людям, и компиляторам. Именно эта сила во многом определила его успех.
Комментариев нет:
Отправить комментарий