64-битная арифметика в браузере и WebAssembly

WebAssembly активно разрабатывается и уже достиг состояния, когда собранный модуль можно попробовать в Chrome Canary и Firefox Nightly, включив флажок в настройках.

Сравним производительность арифметических вычислений с 64-битными числами в WebAssembly, asm.js, PNaCl и native-коде. Посмотрим на инструменты, которые есть для WebAssembly сейчас, и заглянем в недалёкое будущее.

Disclaimer

WebAssembly сейчас в стадии разработки, уже через месяц статья может устареть. Цель статьи — рассказать о положении дел, для тех, кто интересуется.

TL;DR

демо, графики

Алгоритм

В качестве бенчмарка возьмём Argon2, который мне недавно понадобилось вычислять в браузере.
Argon2 (github, хабр) — это сравнительно новая криптографическая функция формирования ключа (key derivation function, KDF), победившая на Password Hashing Competition.

Она основана на 64-битной арифметике, вот функции, за одну итерацию выполняющиеся около 60M раз:

uint64_t fBlaMka(uint64_t x, uint64_t y) {
    const uint64_t m = UINT64_C(0xFFFFFFFF);
    const uint64_t xy = (x & m) * (y & m);
    return x + y + 2 * xy;
}

uint64_t rotr64(const uint64_t w, const unsigned c) {
    return (w >> c) | (w << (64 - c));
}

Сложности реализации на asm.js

Казалось бы, всё просто: взять да перемножить два 64-битных числа, как это и сделано в native-коде argon2, например, вызвав sse-инструкцию. Но только не в браузере.

В V8, как известно, нет 64-битных integer-ов, поэтому вся арифметика за неимением лучшего эмулируется 31-битными smi (small integer). Что очень медленно. Настолько медленно и настолько безобразно, что это неоднократно упоминали разработчики Unity, и 64-битные типы включили в WebAssembly MVP, хотя сначала хотели отложить на потом.

Посмотрим на код, сгенерированный asm.js для функции умножения двух int64, это функция из compiler-rt:

function ___muldsi3($a, $b) {
    $a = $a | 0;
    $b = $b | 0;
    var $1 = 0, $2 = 0, $3 = 0, $6 = 0, $8 = 0, $11 = 0, $12 = 0;
    $1 = $a & 65535;
    $2 = $b & 65535;
    $3 = Math_imul($2, $1) | 0;
    $6 = $a >>> 16;
    $8 = ($3 >>> 16) + (Math_imul($2, $6) | 0) | 0;
    $11 = $b >>> 16;
    $12 = Math_imul($11, $1) | 0;
    return (tempRet0 = (($8 >>> 16) + (Math_imul($11, $6) | 0) | 0) + ((($8 & 65535) + $12 | 0) >>> 16) | 0, 0 | ($8 + $12 << 16 | $3 & 65535)) | 0;
}

Вот она, и вот она же на JavaScript. Реализация кстати очень хорошая, не вызывающая deopt-ов в V8. Проверим это на всякий случай:

Скомпилируем asm.js, отключив переименование переменных, чтобы имена функций в коде были читабельными, и запустим с флагами, позволяющими открыть артефакты в IR Hydra (можно просто установить npm i -g node-irhydra):

Как видим, V8 даже заинлайнил функцию __muldsi3 в __muldi3. Там же можно посмотреть на ассемблерный код этой функции.

v50 EnterInlined ___muldsi3 Tagged  
i71 Constant 65535  Smi  
i72 Bitwise BIT_AND i234 i71 TaggedNumber  
i76 Bitwise BIT_AND i236 i71 TaggedNumber  
t79 LoadContextSlot t47[13] Tagged  
t82 CheckValue t79 0x3d78a90c3b59 <JS Function imul (SharedFunctionInfo 0x3d78a9058f91)> Tagged  
i83 Mul i76 i72 TaggedNumber  
i88 Constant 16  Smi  
i89 Shr i234 i88 TaggedNumber  
i94 Shr i83 i88 TaggedNumber  
i100 Mul i76 i89 TaggedNumber  
i104 Add i94 i100 TaggedNumber  
i111 Shr i236 i88 TaggedNumber  
i118 Mul i111 i72 TaggedNumber  
i125 Shr i104 i88 TaggedNumber  
i131 Mul i111 i89 TaggedNumber  
i135 Add i125 i131 TaggedNumber  
i142 Bitwise BIT_AND i104 i71 TaggedNumber  
i145 Add i142 i118 TaggedNumber  
i151 Shr i145 i88 TaggedNumber  
i153 Add i135 i151 TaggedNumber  
t238 Change i153 i to t  
v158 StoreContextSlot t47[12] = t238 changes[ContextSlots] Tagged  
v159 Simulate id=319 var[3] = t47, var[1] = i234, var[2] = i236, var[6] = i83, var[5] = t6, var[8] = i104, var[4] = t6, var[10] = i118, var[9] = t6, var[7] = t6, push i153 Tagged  
i163 Add i104 i118 TaggedNumber  
i166 Shl i163 i88 TaggedNumber  
i170 Bitwise BIT_AND i83 i71 TaggedNumber  
i172 Bitwise BIT_OR i166 i170 TaggedNumber  
v179 LeaveInlined Tagged  
v180 Simulate id=172 pop 1 / push i172 Tagged  
v181 Goto B3 Tagged  

Chrome генерирует не такой оптимальный код, как можно было бы сделать, имея аннотации типов, разработчики V8 принципиально не хотят поддерживать asm.js js subset, и вобщем-то, правильно. В отличие от этого Firefox, видя "use asm", в случае если код проходит валидацию, выкидывает некоторые проверки, в результате чего получившийся код быстрее где-то в 3..4 раза.

По сравнению с native-кодом, Chrome и Safari медленнее в 50 раз, Firefox — в 12.
IE11 достаточно медленный, а вот Edge с включённым в настройках asm.js где-то посередине между Chrome и Firefox:

WebAssembly

Скомпилируем этот код в WebAssembly. Сделать это можно несколькими способами, для начала попробуем C/C++ Source ⇒ asm2wasm ⇒ WebAssembly (некоторые параметры исключены для краткости):

cmake 
    -DCMAKE_TOOLCHAIN_FILE=~/emsdk_portable/emscripten/incoming/cmake/Modules/Platform/Emscripten.cmake 
    -DCMAKE_C_FLAGS="-O3" 
    -DCMAKE_EXE_LINKER_FLAGS="-O3 -g0 -s 'EXPORTED_FUNCTIONS=["_argon2_hash"]' -s BINARYEN=1" && cmake --build .

Можно использовать тот же toolchain, что и для сборки asm.js, указав, что мы хотим использовать binaryen (-s BINARYEN=1).
На выходе мы получим:

• wast-файл: текстовое представление WebAssembly, S-Expressions.
• mappedGlobals: json с функциями, экспортируемыми из модуля и доступными JavaScript, там будут runtime-функции и то, что мы указали в EXPORTED_FUNCTIONS.
• js-обёртка, которая управляет wasm-модулем или может выполнить код другими способами, если wasm не поддерживается.
• asm.js-код, который будет использован как fallback, на случай, когда нет поддержки wasm.

Преобразуем wast-файл в бинарный формат wasm:

~/binaryen/bin/wasm-as argon2.wast > argon2.wasm

Используем модуль в браузере

Что же умеет делать js-обёртка, кроме вызова wasm-модуля, и как её использовать?

• загрузить бинарный wasm-модуль
• создать объект Module с настройками
• любым способом импортировать скрипт в браузер

global.Module = {
    print: log,
    printErr: log,
    setStatus: log,
    wasmBinary: loadedWasmBinaryAsArrayBuffer,
    wasmJSMethod: 'native-wasm,',
    asmjsCodeFile: 'dist/argon2.asm.js',
    wasmBinaryFile: 'dist/argon2.wasm',
    wasmTextFile: 'dist/argon2.wast'
};
var xhr = new XMLHttpRequest();
xhr.open('GET', 'dist/argon2.wasm', true);
xhr.responseType = 'arraybuffer';
xhr.onload = function() {
    global.Module.wasmBinary = xhr.response;
    // load script
};
xhr.send(null);

Здесь мы указваем на расположение скомпилированных артефактов, подключаем свои логи и определяем метод, которым будем выполнять код. Из методов можно выбрать:

• native-wasm: использовать поддержку wasm в браузере;
• interpret-s-expr: загрузить текстовое представление .wast и интерпретировать его;
• interpret-binary: интерпретировать бинарный формат .wasm;
• interpret-asm2wasm: загрузить asm.js-код, скомпилировать его в .wasm и выполнить;
• asmjs: выполнить asm.js-код.

Можно перечислить несколько методов через запятую, тогда будет выполнен первый успешный из них. По умолчанию берётся метод native-wasm,interpret-binary, то есть попробовать, нет ли wasm, если нет, то интерпретировать бинарный модуль.

После успешной загрузки в объекте Module появляются все экспортированные методы.

Пример использования (полностью):

var pwd = Module.allocate(Module.intArrayFromString('password'), 'i8', Module.ALLOC_NORMAL);
// ...
var res = Module._argon2_hash(t_cost, m_cost, parallelism, pwd, pwdlen, salt, saltlen,
    hash, hashlen, encoded, encodedlen, argon2_type, version);
var encodedStr = Module.Pointer_stringify(encoded);

Firefox Nightly позволяет заглянуть внутрь wasm-модуля:

В Chrome пока нет инструментов для просмотра wasm, модуль даже не отображается в редакторе. Но к релизу тоже обещают сделать view source.

Интерпретатор из Binaryen

Binaryen генерирует интерпретатор, который умеет выполнять текстовый .wast и бинарный .wasm форматы. Попробовать его можно, выставив method в interpret-s-expr или interpret-binary. Пока что интерпретатор настолько медленный, что подсчёта хэша я не дождался, а оценил по меньшему числу итераций. Оно составило бы полчаса, в то время как в Chrome было 7 сек и даже в IE11 45 сек.

Качество кода

Посмотрим, какой же код у нас получился. Я написал простой тест, чтобы .wast был предельно маленьким, вот он:

uint64_t fBlaMka(uint64_t x, uint64_t y) {
    const uint64_t m = UINT64_C(0xFFFFFFFF);
    const uint64_t xy = (x & m) * (y & m);
    return x + y + 2 * xy;
}

int exp_fBlaMka() {
    for (unsigned i = 0; i < 100000000; i++) {
        if (fBlaMka(i, i) == i - 1) {
            return 1;
        }
    }
    return 0;
}

Заглянем в .wast и найдём нашу функцию:

(func $_exp_fBlaMka (result i32)
  (local $0 i32)
  (set_local $0
    (i32.const 0)
  )
  (loop $while-out$0 $while-in$1
    (if                                       # код цикла, куда заинлайнена наша функция
      (i32.and
        (i32.eq
          (call $___muldi3                    # начало функции
            (call $_i64Add
              (call $_bitshift64Shl
                (get_local $0)
                (i32.const 0)
                (i32.const 1)
              )
              (i32.load
                (i32.const 168)
              )
              (i32.const 2)
              (i32.const 0)
            )
            (i32.load
              (i32.const 168)
            )
            (get_local $0)
            (i32.const 0)
          )
          (i32.add
            (get_local $0)
            (i32.const -1)
          )
        )
# ...

Снова i32? Почему так получается? Вспомним, что мы получили wasm-код, скомпилировав asm.js, поэтому i64 мы здесь и не увидим. Неудивительно, что такой код тоже выполняется долго.

Однако же, теперь скорость выполнения в Chrome получилась такой же, как в Firefox, и чуть быстрее, чем asm.js в Firefox.

LLVM WebAssembly Backend

Теперь попробуем более сложный способ, C/C++ Source ⇒ WebAssembly LLVM backend ⇒ s2wasm ⇒ WebAssembly.

LLVM научился генерировать WebAssembly, делая это без emscripten. Но делает он это пока очень плохо, получившийся модуль не всегда работает.

Собираем LLVM с поддержкой WebAssembly:

cmake -G Ninja -DLLVM_EXPERIMENTAL_TARGETS_TO_BUILD=WebAssembly .. && ninja

Включаем её в компиляции:

export EMCC_WASM_BACKEND=1
-DCMAKE_EXE_LINKER_FLAGS="-s WASM_BACKEND=1"

Чтобы попробовать разные версии LLVM в emscripten, указаываем путь к нему в ~/.emscripten, LLVM_ROOT. И… получаем ошибку при загрузке модуля в браузер.

Можно ещё собрать не форком fastcomp, используемом в emcc, а ванильным LLVM из апстрима, как-то так:

clang -emit-llvm --target=wasm32 -S perf-test.c
llc perf-test.ll -march=wasm32
~/binaryen/bin/s2wasm perf-test.s > perf-test.wast
~/binaryen/bin/wasm-as perf-test.wast > perf-test.wasm

Тоже падает. Возможно, wasm из wast для V8 надо собирать sexpr-wasm-prototype, а не binaryen, но это всё равно не помогает.

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

(func $fBlaMka (param $0 i64) (param $1 i64) (result i64)
  (i64.add
    (i64.add
      (get_local $1)
      (get_local $0)
    )
    (i64.mul
      (i64.and
        (i64.shl
          (get_local $0)
          (i64.const 1)
        )
        (i64.const 8589934590)
      )
      (i64.and
        (get_local $1)
        (i64.const 4294967295)
      )
    )
  )
)

Ура, i64! Загрузим его в браузер и оценим время, в сравнении с прошлым вариантом:

console.time('i64');
Module._exp_fBlaMka();
console.timeEnd('i64');

i32: 1851.5ms
i64: 414.49ms

В светлом будущем скорость 64-битной арифметики лучше в несколько раз.

Threading

В MVP WebAssembly не включены pthreads, они появятся только потом. Пока сложно сказать, что будет, вобщем, на ближайший год — ответ нет. Но зато WebAssembly можно без проблем использовать в web worker-ах без какой-либо деградации производительности, в чём вы можете убедиться сами на демо-страничке.

PNaCl

Теперь сравним производительность с PNaCl. PNaCl — это тоже формат бинарного кода, разработанный в Google для Chrome и даже включённый по умолчанию. Когда-то предполагалось поддержать его и в других браузерах, но Mozilla отвергла предложение, а другие и не задумывались. Не взлетело.

Итак, PNaCl — это .pexe, который jit-ится в рантайме, сделаем простой модуль для него:

class Argon2Instance : public pp::Instance {
 public:
  virtual void HandleMessage(const pp::Var& msg) {
    pp::VarDictionary req(msg); // получаем параметры из сообщения
    int t_cost = req.Get(pp::Var("time")).AsInt();
    // ...
    int res = argon2_hash(t_cost, m_cost, parallelism, pwd, pwdlen, salt, saltlen,
                    hash, hashlen, encoded, encodedlen,
                    argon2_type == 1 ? Argon2_i : Argon2_d, version);
    pp::VarDictionary reply;
    reply.Set(pp::Var("res"), res);
    PostMessage(reply); // отправляем ответ
  }
};

Вызвать это можно, внедрив .pexe на страничку в <embed> и отправив ему сообщение:

// подписываемся на сообщение с результатом
listener.addEventListener('message', e => console.log(e.data));
// отправляем задачу
moduleEl.postMessage({ pwd: 'password', ... });

В отличие от WASM, в PNaCl уже сейчас поддерживает и 64-битные типы и pthreads, поэтому работает намного быстрее, по скорости, время работы в 1.5..2 раза больше native-кода. Но это только хром. Грустно тут только время загрузки, которое составляет несколько секунд, а в случае вообще первого использования PNaCl пользователем может вырасти до невменяемых цифр порядка 30 сек.

Графики

Среднее время выполнения кода в разных средах:

Время загрузки и первого выполнения:

Размер кода

А что насчёт node.js?

В node.js скомпилировать native-код очень просто уже сейчас, достаточно добавить пару binding-ов. Когда V8 обновится до какой-то версии, node.js можно будет запустить с флагом --expose-wasm (пока его поддержка в экспериментальной стадии) и использовать wasm и в ноде. Пока он не загружается, потому что V8 достаточно старый.

Выводы

Сейчас разумно использовать asm.js в Firefox и PNaCl в Chrome. WASM уже сейчас достаточно хорош, ко времени MVP, компиляцию в LLVM, скорее всего, доведут до ума, но использовать его, конечно же, рано, даже в nightly-билдах по умолчанию он выключен. Однако производительность wasm уже сейчас показательна и превышает скорость работы asm.js, даже без поддержки i64.

Ссылки

• демо: github
• код примеров из статьи: github
• argon2: github, хабр, для нердов
• страничка new llvm wasm backend: github/binaryen

Автор: Antelle

Источник