Pull to refresh

Как обновление Rust 1.26 ускорило мой код в три с лишним раза

Reading time 13 min
Views 21K
Original author: Parity Technologies
Хочу поделиться небольшой историей о мощи LLVM и преимуществах языков высокого уровня над ассемблером.

Я работаю в компании 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 проделал отличную работу для того, чтобы программисты писали программы, легко понятные и людям, и компиляторам. Именно эта сила во многом определила его успех.
Tags:
Hubs:
+46
Comments 33
Comments Comments 33

Articles