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

http://troubles.md/posts/the-power-of-compilers/
  • Перевод
Хочу поделиться небольшой историей о мощи 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 проделал отличную работу для того, чтобы программисты писали программы, легко понятные и людям, и компиляторам. Именно эта сила во многом определила его успех.
Поделиться публикацией
Комментарии 33
    +5
    Два фразы из всей статьи, который сразу показывают, о чём идёт речь:

    Оригинальный код использовал высокооптимизированные ассемблерные инкантации

    Вероятно, его можно ускорить заменой «m» на «r» (я не тестировал, потому что обнаружил это только когда начал проверять для статьи, почему старый ассемблерный код настолько медленнее), но глядя на исходники это не очевидно.

    То есть вставки на ассемблере не то, что никто не попрофайлил — никто даже не заглянул в тот код, который генерирует компилятор на самом деле! О каких «высокооптимизированных ассемблерные инкантациях» может идти речь?

    Вместо того, чтобы сделать несколько простых ассемблерных вставок, которые делают то, что «руками» из-за ограничений языка сделать нельзя порождена здоровенная простыня… и никто даже не удосужился посмотреть — во что она выливается после компиляции… Типичный карго-культ: ассмеблер == очень-очень быстро, думать не надо, главное — что ассемблер…

    А потом делается «открытие»: надо же — и на ассемблере можно написать плохо и медленно! Это таки так… но причём тут rust???
      +1
      Представьте что будет, когда они узнают что почти как 30 лет сопроцессор у всех из коробки есть, и 128 битную арифметику давно подвезли.
        +4

        Расскажите поподробнее пожалуйста про 128-битную арифметику на x86

          +2
          Причём тут сопроцессор?

          128 битную арифметику давно подвезли.

          Кому подвезли?
            –4
            SSE — расширение команд сопроцессора? Так вот в SSE2 (Pentium 4) есть целочисленная SIMD арифметика, да не совсем 128, а 2x64, но это лучше чем считать на CPU.
            Далее, не трогал, но знаю что есть AVX, там как раз расширение до 128 бит, 2011 год, не сказать что что то супер новое и редкое.
              +5
              Какое имеет отношение SIMD к 128-битной/256-битной арифметике? Вот прямо из названия «одиночный поток команд, множественный поток данных» очевидно же, что ни о какой 128-битной/256-битной арифметике там речь не идёт, всё сводится к независимым наборами чисел! И даже понятно почему: чем более длинный у вас сумматор или мультипликатор… тем сложнее заставить его работать на высокой частоте! Потому ничего похожего на то, что требуется для обсуждаемой в статье задачи в SSE/AVX нет и быть не может. Даже всякие SSSE3 и SSE4 с их «горизонтальными» сложениями/умножениями базовый принцип «сумматоры и мультипликаторы должны быть короткими» блюдут строго… против физики не попрёшь, однако.

              P.S. Тем грустные видеть кучу плюсов, которые набрал ваш комментарий… Когда-то на Хабре собиралась публика, которая подобных элементарных ошибок не допускала… Но чем дальше в лес, тем ближе уровень фишек.нет или дёрти.ру… грустно…
                0
                SIMD дает нам возможность производить некоторые операции (сложение/умножение) сразу над несколькими парами операндов. И да, есть досадное ограничение, большинство этих операции carry-less, старшую часть результата мы теряем. Но мы можем делать вычисления над числами разрядностью меньшей разрядности регистров (например для сложения/вычитания 63 бита вместо 64), тогда после операции нам надо будет довычислять эти переносы. С умножением сложнее, но принцип тот же, понижаем разрядность что бы не потерять перенос и используем на свой вкус алгоритм Штрассена или Фюрера, которое хорошо ложатся ни SIMD. Да это не прям готовая реализация в виде одной команды add/mul, но SSE/AVX дают сильное ускорение если подумать.
                Да, моя ошибка выше что арифметика не 128 битная, а скажем так над 128 битами одновременно, а то и больше, давно не использовал ассемблер да и особенности технологий подзабыл за ненадобностью в повседневной работе.
                  –1
                  Какое отношение алгоритм Штрассена имеет к длинной арифметике?
                    +1
                    Прям как на экзамене )) Ok, алгоритм Шёнхаге-Штрассена
                    0
                    Но мы можем делать вычисления над числами разрядностью меньшей разрядности регистров (например для сложения/вычитания 63 бита вместо 64), тогда после операции нам надо будет довычислять эти переносы.
                    Как вы это себе представляете? В SIMD не операций для работы с 63-разрядными числами. Либо 64бита, либо 32. Если вы начинаете работать с 32 битами, то вы получаете вдвое больше операций и, соответсвенно смысла в SSE нет никакого (мы будем вместо пару 64битных чисел складывать две пары 32-битных, что явно никакого ускорения не даст). AVX вроде как может, в теории, дать какое-то ускорение, так как можно складывать 4 32-битных числа одновременно (получая 4 64-битных числа с точки зрения процессора, а практически — 33битных), но к этому добавятся инструкции перемешивания, и в результате, скорее всего, вычисления будут происходить дольше.

                    С умножением сложнее, но принцип тот же, понижаем разрядность что бы не потерять перенос и используем на свой вкус алгоритм Штрассена или Фюрера, которое хорошо ложатся ни SIMD.
                    Плохо они ложатся на SIMD, очень плохо. Дело в том, что, как я уже писал, мультипликатора 64бит на 64бита в 128бит в SIMD нету, всё что есть — это «обрезанные» мультипликаторы 32бит на 32бита в 64бит. Дальше — у нас получается в 4 раза больше операций, что, опять-таки, немедленно делает SSE бессмысленным, а AVX — почти бессмысленным (вместо одного умножения 64бит на 64бита в 128бит мы вроде как могли бы использовать 4 умножения 32бит на 32бита в 64бит — но у нас появлятся дополнительные инструкции для «разреживания» и прочего).

                    Да это не прям готовая реализация в виде одной команды add/mul, но SSE/AVX дают сильное ускорение если подумать.
                    Не в случае с арифметикой длинных чисел. Теориетически разве что AVX512 мог бы дать ускорение, но во-первых он мало где есть, а во-вторых — это использование снижает частоту процессора, так что не факт что в результате будет выигрыш.

                    Да, моя ошибка выше что арифметика не 128 битная, а скажем так над 128 битами одновременно, а то и больше, давно не использовал ассемблер да и особенности технологий подзабыл за ненадобностью в повседневной работе.
                    Если вы «подзабыли особенности технологий за ненадобностью», то откуда такая уверенность, что они, в данном конкретном случае, вообще дадут выигрыш?
                      –1
                      Как вы это себе представляете? В SIMD не операций для работы с 63-разрядными числами.

                      Разбиваете 128 бит число на четыре 32битных (или 8x16бит, тогда далее делим разрядность на два). Расширяете их до 64 бит старшими нулевыми битами. Далее при умножении этих 64битных чисел, результат тоже будет не более 64 бит, и отсечение старшей части результат вам уже не страшно. Ну и с этим подходом используете упомянутые выше алгоритмы.
                        0
                        Вы вообще хоть иногда читаете комментарии, на который отвечаете? Там, вообще-то, описан и ваш «гениальнй» алгоритм и объяснено, почему толку от него — никакого (за исключением обфускации кода, но для этого есть много других способов).

                        Если вы не знаете как работает та или иная технология, то не стоит их тащить в дискуссию. Ну пожалйста. Хабр был одним из немногих мест в сети, где собеседники умели-таки думать и считать. Не нужно его в фишки.нет превращать…
                          0
                          Почему вы считаете, что хитрое 32х-битное умножение будет работать быстрее чем обычное 64х-битное?
                            +1
                            На всякий случай напишу подробнее имею в виду. Вот у нас есть два 128-битных числа, и их надо перемножить.

                            Если использовать 64х-битное умножение, то методом «в лоб» будет достаточно 4х умножений и 4х сложений. Методом Карацубы число умножений удастся уменьшить до 3х, но число сложений вырастет и появятся логические операции, так что не рискну оценивать что из этого лучше.

                            Вы же предлагаете сделать два FFT-преобразования и параллельное умножение на SIMD-инструкциях. Будет ли это быстрее чем 4 обычных умножения и 4 сложения?
                              +1
                              Почему вы считаете
                              С чего вы решили, что Ghost_nsk вообще хоть чего-то считал? Если бы он считал, то сразу понял бы, что SSE — будет только замедлять, так как там только два умножителя 32бит на 32бита в 64бит, что однозначно медленнее, чем один умножитель 64бита на 64бита в 128бит.

                              В случае с AVX'ом 32бит на 32бита в 64бит умножителей у нас уже 4 штуки, но что-то выиграть мы сможем только если использовать что-то типа Карацубы — а тут мы упрёмся в сложения (так как аналога скалярного ADC в AVX нету).

                              То есть если где-то и можно получить выигрыш — то лишь начиная с AVX512. Что, в принципе, не так плохо согласуется с тем, что нам нужна 256-битная арифметика (как раз после расширения вдвое всё влазит в один регистр). Но тут надо считать особенно тщательно, так как использование AVX512 автоматически понижает частоту ядра, так что вопрос — будет ли в итоге выигрыш… он далеко неочевиден даже для AVX512.

                              Но посмотрите с чего мы начали:
                              Представьте что будет, когда они узнают что почти как 30 лет сопроцессор у всех из коробки есть, и 128 битную арифметику давно подвезли.

                              Это явно было замечание не про AVX512, появившийся чуть больше года назад в Skylake-SP (то есть только на серверах), а о чём-то другом.
                +16
                Я предлагаю взглянуть чуть с другой стороны.

                Был код на языке высокого уровня. Прошлись профайлером, нашли узкое место: широкая арифметика. Решили переписать с использованием ассемблерных вставок. Человек переписал, получили значимое ускорение. Обрадовались, выкатили.
                Компилятор языка высокого уровня обновился, появилась поддержка 128-битной арифметики. Решили проверить, на сколько её использование оправдано. Выяснили, что новая реализация быстрее той, что была с вставками. Обрадовались, выкатили.

                Нашли проблему, замерили, нашли решение, замерили. Решение устроило — пользуемся и радуемся.
                Изменились внешние обстоятельства, касающиеся данной задачи. Проверили новое решение, которое проще в поддержке и при этом оказалось быстрее использующегося. Задача решена.

                Выводы:
                0) Люди не идеальны. Что-то не знают, о чем-то забывают.
                1) Во многих случаях компиляторы способны генерировать весьма хороший код.
                2) Хорошо, когда в языке высокого уровня дают спуститься на низкий.
                3) И да, Rust тут весьма вторичен. Хотя родная поддержка 128-битных целых мне что-то весьма не часто попадалась.
                  +2

                  Вот дельное замечание. А позиция некоторых, дескать "автор сам дурак и нечего тут рассуждать" — неконструктивна.

                    +2

                    Это все понятно. Но я бы не стал написанный на шаге "переписал, получили значимое ускорение" код называть "высокооптимизированным". Прилагательное "высокооптимизированный" все-таки подразумевает кучу итераций оптимизации с изучением кода на всех уровнях, чего тут сделано не было.

                      0
                      3) И да, Rust тут весьма вторичен. Хотя родная поддержка 128-битных целых мне что-то весьма не часто попадалась.
                      В gcc (и, соответственно, в clang'е) оно уже давно есть.

                      Или вы думали их кто-то в LLVM специально для rust'а добавил? И оптимизации сделал?

                      Прошлись профайлером, нашли узкое место: широкая арифметика. Решили переписать с использованием ассемблерных вставок. Человек переписал, получили значимое ускорение. Обрадовались, выкатили.
                      И даже не попробовали взглянуть в сгенерированный код?

                      Понимаете, я ж не против. «Метод тяп-ляп и в подакшн» — очень часть самый выгодный. Но когда мне заливают в уши про «highly-optimised assembly incantations from our resident cycle wizard» (переводчик перевёл это просто как «высокооптимизированные ассемблерные инкантации», чтобы не так пафосно выглядело), а потом выясняется, что его вкрутили так, что все данные через память гоняются… это даже не смешно.
                        0

                        Про реализации в gcc и llvm знаю. Я про язык. Хотя тут Rust'у с его единственной, по сути, реализацией просто говорить.


                        Про пафос согласен, тут они сильно перегнули и, я бы даже сказал, напросились.

                    0
                    я подумал в новом расте появилась какая-то могучая оптимизация, ан нет, просто поддержка старого доброго нового типа…
                      0
                      Есть же libgmp, очень оптимальная и всеми используемая. Зачем велосипеды изобретать?
                        +3
                        лицензия GPL подходит далеко не всем
                          0
                          Она еще и под LGPL лицензирована, если очень хочется можно у разработчика исключения линковки попросить.
                            0

                            Все-таки LGPL так себе сочетается со статической линковкой, которую очень любит раст. Всем просить исключение такое себе занятие.


                            Но при этом для желающих есть несколько готовых пакетов с привязками


                              0

                              Если нельзя использовать динамическую линковку, то можно задействовать dlopen().

                          +1
                          она офигенно медленная по сравнению с кастомными решениями
                          +1
                          Надо было еще ссылки на скомпилированный результат на play.rust-lang.org оставить. Там и IR и ассемблер можно посмотреть
                            0
                            mulx, adcx, adox… не, не слыхали)
                              +2
                              Broadwell+, Ryzen+. Не уверен, что они могу себе такое позволить.
                              0
                              В С++ 20 может быть приедут шаблонные wide_integers произвольной длины. Очень жаль, что в Rust все еще не приехали дженерики с аргументами-не типами, и аналогичную штуку не сделать :(
                                0

                                https://github.com/rust-lang/rust/issues/44580#issuecomment-373858405 — дела потихоньку, но таки ползут в эту сторону (RFC — https://github.com/rust-lang/rfcs/pull/2000)

                                  0
                                  Да, я знаю; примерно раз в полгода открываю этот тред.
                                  Грустно, что очень многих вещей, которые уже есть в С++ (или в D), ждать еще очень очень долго. Многих, подозреваю, вообще можно не дождаться, типа static if, поскольку их изначально не закладывали.
                                  Ле вздох.

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое