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. Там же можно посмотреть на ассемблерный код этой функции.


    IR
    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  

    Assembler

    140 andl r8,0xffff
    ;; <@43,#72> gap
    147 movq r9,rdx
    ;; <@44,#76> bit-i
    150 andl r9,0xffff
    ;; <@48,#79> load-context-slot
    170 movq r11,[r11+0x77]
    ;; <@50,#82> check-value
    174 movq r10,0x3d78a90c3b59 ;; object: 0x3d78a90c3b59 <JS Function imul (SharedFunctionInfo 0x3d78a9058f91)>
    184 cmpq r11,r10
    187 jnz 968
    ;; <@51,#82> gap
    193 movq rdi,r9
    ;; <@52,#83> mul-i
    196 imull rdi,r8
    ;; <@53,#83> gap
    200 movq r11,rax
    ;; <@54,#89> shift-i
    203 shrl r11, 16
    ;; <@55,#89> gap
    207 movq r12,rdi
    ;; <@56,#94> shift-i
    210 shrl r12, 16
    ;; <@58,#100> mul-i
    214 imull r9,r11
    ;; <@60,#104> add-i
    218 addl r9,r12
    ;; <@61,#104> gap
    221 movq r12,rdx
    ;; <@62,#111> shift-i
    224 shrl r12, 16
    ;; <@63,#111> gap
    228 movq r14,r12
    ;; <@64,#118> mul-i
    231 imull r14,r8
    ;; <@65,#118> gap
    235 movq r8,r9
    ;; <@66,#125> shift-i
    238 shrl r8, 16
    ;; <@68,#131> mul-i
    242 imull r12,r11
    ;; <@70,#135> add-i
    246 addl r12,r8
    ;; <@71,#135> gap
    249 movq r8,r9
    ;; <@72,#142> bit-i
    252 andl r8,0xffff
    ;; <@74,#145> add-i
    259 addl r8,r14
    ;; <@76,#151> shift-i
    262 shrl r8, 16
    ;; <@78,#153> add-i
    266 addl r8,r12
    ;; <@80,#238> smi-tag
    269 movl r12,r8
    272 shlq r12, 32
    ;; <@84,#158> store-context-slot
    289 movq [r11+0x6f],r12
    ;; <@86,#163> add-i
    293 leal r8,[r9+r14*1]
    ;; <@88,#166> shift-i
    297 shll r8, 16
    ;; <@90,#170> bit-i
    301 andl rdi,0xffff
    ;; <@92,#172> bit-i
    307 orl rdi,r8


    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 сек.


    Графики


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



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



    Размер кода


    Code size, KiB Комментарий
    asm.js 109 полностью весь js-ник
    WebAssembly 43 только .wasm, без обёртки
    PNaCl 112 .pexe

    А что насчёт 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.


    Ссылки


    Поделиться публикацией

    Комментарии 11

      0
      Спасибо за исследование.
      Только как-то очень хаотично написан раздел про llvm. Что получилось собрать, а что нет? В графики попала wasm версия полученная через asm.js, а упрощённый тест был просто для проверки, что 64 бита возможны? Тогда можно ожидать, что когда всё заработает wasm версия будет в несколько раз быстрее?
        +1

        Собрать получилось только тестовую версию с двумя функциями, что-то более сложное (например, функция с возвратом строки) уже не работает никакими спомобами через генерацию wasm backend в LLVM, пока только ⇒ asm.js ⇒ wasm. Да, должно стать в несколько раз быстрее, когда пофиксят.

        0
        Жаль pnacl не взлетел, по моему с точки зрения производительности это наиболее оптимальный вариант. Если первый запуск кажется долгим можно поставлять nacl-версию.
          +1

          NaCl запрещён по умолчанию для веб-приложений, просить его включить в настройках некомильфо, т.е. сделать этого, можно сказать, что и нельзя.
          Вот почему у PNaCl так плохо с инцииализацией при 100-килобайтном .pexe, мне непонятно, время jit-а должно быть несколько мс. Так что тоже не всё гладко… У wasm уже сейчас время старта стабильно, это хорошо.

            0
            Некомильфо, но насколько я знаю nacl можно включать в приложения которые ставятся через Chrome Web Store, т.е. нельзя загружать nexe с сайта.
              +1

              Из Chrome Web Store можно, да. Но сейчас уже хочется чего-то, что не требовало бы инсталляции, особенно из модерируемого гуглом стора.

            0
            Про PNaCL в википедии пишту, что mozilla отказалась от его поддержки из-за отсутствия полной спецификации. Так что может и правильно, что не взлетел. Производительность — это конечно хорошо, но кучу проблем с совместимостью на разных браузерах она вряд ли перекрывает.
            0
            Antelle А не знаете случайно они asm совсем забросили или будут развивать параллельно с wasm? Сейчас довольно удобно критические по производительности вещи оборачивать в asm, но не хватает i64 и прочих радостей, да и asm -> wasm достаточно удачная компиляция, в отличии от c -> wasm создает намного меньше мусора (без i64 конечно). Опять же типизация рано или поздно появится и тогда asm сможет выглядет по приличнее, так что интересна его судьба.
              +1

              Вы про нотацию use asm и процедуру валидации-компиляции-выполнения asm.js js subset, или про fastcomp, форк llvm, который используется в emscripten? Поддержку asm.js скорее всего уберут, когда все браузеры поддержат wasm. Может быть, какой-то переходный период будет, когда asm.js будет компилироваться браузером в wasm, но вообще его нет смысла тащить дальше, когда есть бинарный формат. C → wasm работает плоховато, потому что поддержкой компиляторов пока что ещё не очень и занимаются по-хорошему. Я думаю, приведут в порядок тоже. Компиляторов скорее всего вообще много будет, Microsoft наверное тоже что-то сделает.

                0
                Я про первое (понятно, что это работает только в ФФ, но в принципе и в других браузерах этот код оптимизируется лучше js).

                Поддержку asm.js скорее всего уберут, когда все браузеры поддержат wasm.

                А какой смысл убирать то, что уже добавлено. В ФФ — это отдельная прекомпиляция, а в других браузерах это ведь выполняется силами штатного компилятора, как это вообще можно убрать?

                asm.js будет компилироваться браузером в wasm

                А сейчас разве не так происходит? То есть не учитывая поддержку 64-разрядных целых разве wasm не просто бинарное представление asm?

                но вообще его нет смысла тащить дальше, когда есть бинарный формат

                Ну как сказать нет смысла — сейчас можно быстренько в asm критичные вещи завернуть и даже ничего не компилировать или на продакшн компилировать asmjs -> wasm. А если его уберут — прийдется на С писать и обязательно компилировать даже в стадии разработки.
                В идеале было бы хорошо, чтоб asm развивался как один из языков которые компилируются в wasm. Опять же поддержка int64 в js совсем не помешает, эмуляция на int32 и правда медленная.

                C → wasm работает плоховато, потому что поддержкой компиляторов пока что ещё не очень и занимаются

                Ну не только по этому, рукописный код всегда аккуратнее сгенерированного, потому в случае asmjs -> wasm мы получим именно то, что написали, а вот c -> wasm иногда генерирует кучу ненужного мусора, нужно за этим следить. Но да, компиляторы и правда становятся лучше.

                В целом asmjs сейчас очень помогает исправлять косяки в реализации браузерных API к примеру DataView и помогает писать критичные участки кода без предварительной компиляции. Очень хотелось бы, чтоб его развитие продолжилось и нововведения vm для wasm были портированы в asmjs и js.
                  +1

                  Всмысле, что убрать могут анализ типов в коде, аннотации, специальную поддержку asm.js браузером… — потому что их достатчно сложно держать в актуальном состоянии. Тот же Firefox периодически отламвывает валидацию. Или просто перестанут развивать, оставив что работает. А может быть и нет, посмотрим, но пока я где-то читал, что его не планируют развивать, asm.js это переходный этап.

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

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