Если вы думаете, что это шутка, то эта история для вас
Совсем недавно я опубликовал новый плагин для привязок JS к GDAL, который я поддерживаю в настоящее время для импорта и экспорта N-мерных массивов в scijs. scijs, хотя и далеко отстающий от своего тезки на Python, в настоящее время набирает все большую популярность благодаря общему успеху JavaScript и V8.
Я всегда знал, что производительность ввода-вывода Node.js непревзойденная по сравнению с другими языками сценариев. Затем, в прошлом году, я полностью отказался от использования Python год назад после того, как я не смог превзойти мою собственную однопоточную JS-реализацию алгоритма линейной оптимизации в многопоточном Python.
Тем не менее, используется модель node-gdal-async, где многопоточная реализация C ++ управляется однопоточной, но асинхронной суперструктурой JS, которая в настоящее время является ведущей высокопроизводительной модель в экосистеме Node.js - я, естественно, предположил, что хорошая реализация многомерных массивов в scijs должна работать точно так же:
Поэтому я решил провести некоторое тестирование, чтобы увидеть, чего можно было бы достичь, выполнив прямую замену некоторых основных операций в ndarray-ops, а именно сравнения, сложения и умножения матриц.
Эта история не об основных операциях с матрицами, так как это очень хорошо изученная проблема. Речь идет об использовании JavaScript для выполнения тяжелой работы, связанной с процессором.
Когда дело доходит до матриц, вам редко приходится изобретать велосипед, особенно если ваш целевой язык - C ++. Поэтому я решил сравнить Eigen, одну из ведущих библиотек линейной алгебры для C ++, с ndarray. Eigen, реализованный в виде шаблонов C ++, поддерживает использование инструкций SIMD - SSE и AVX - на современных процессорах x86 через внутренние циклы сборки вручную. Конечно, при работе с очень большими матрицами Eigen собирался курить ndarray. Я ожидал, что по крайней мере в 10 раз больше, а может, и больше.
Оказывается, не всегда все так просто.
Мой тест состоит из добавления двух матриц 10 000x10 000 Float32 (TYPE) (размером 400 МБ). Это несколько необычный тест, требующий очень большой пропускной способности памяти.
Мой первый метод - это «наивный JS», который просто делал:
const a = ndarray(new TYPE(size * size), [size, size], [1, size]); const b = ndarray(new TYPE(size * size), [size, size], [1, size]); for (int i = 0; i < size*size; i++) a[i] += b[i];
Это не сработает ни для чего, кроме простого добавления матриц с одинаковыми шагами в памяти. Я планировал использовать в качестве основы для проверки накладных расходов ndarray-ops.
Один ndarray-ops:
const a = ndarray(new TYPE(size * size), [size, size], [1, size]); const b = ndarray(new TYPE(size * size), [size, size], [1, size]); ops.addeq(a, b);
что в основном то же самое, за исключением того, что ndarray на самом деле не знает, что пункт назначения совпадает с одним из операндов.
И, наконец, матрицы Eigen C ++:
Matrix<TYPE, Dynamic, Dynamic> a(SIZE, SIZE); Matrix<TYPE, Dynamic, Dynamic> b(SIZE, SIZE); a += b;
который тоже выполняет добавление на месте.
Матрицы инициализируются (здесь для краткости опущены), чтобы предотвратить возможное отложенное выделение памяти.
Итак, первый тур:
----------------------------------------------------- trivial | ndarray-ops | Eigen | Eigen w/SIMD ----------------------------------------------------- 130ms 224ms 46ms 33ms AVX512 (recent Intel) 434ms 579ms 152ms 126ms SSE2 (older Athlon)
Не так уж и плохо с V8. И снова Эйген использует внутренний SSE2 / AVX в оптимизированном вручную цикле сборки. Я ожидал большей разницы.
Теперь давайте попробуем еще один тест - тот, который мне действительно был нужен - две матрицы имеют разные шаги - одна в порядке строк, а другая - в порядке столбцов. На этот раз банальная реализация не сработает. Для каждой библиотеки a - это библиотека, использующая свой шаг по умолчанию.
Второй раунд:
------------------------------- ndarray-ops | Eigen | Eigen SIMD ------------------------------- 363ms 533ms 533ms AVX512 (recent Intel i7) 1131ms 3032ms 3032ms SSE2 (older Athlon Phenom II BE)
Хм?
К этому моменту я потратил более трех часов, возясь с различными вариантами компиляции, когда столкнулся с таким результатом.
Я просто отказывался верить в это. В какой-то момент я даже подозревал, что под рукой есть некая черная магия и V8 тайно выполнял параллельную работу на нескольких ядрах.
Я закончил дизассемблирование кода, и именно в этот момент я решил написать эту историю, поскольку это был ценный урок (а также найти способ оправдать все потраченное мной время).
(Оказывается, ответ был очень простым - в этой конкретной операции Eigen не использовал тайлинг и обрабатывал кеш L1. Eigen - очень хорошая библиотека с очень хорошей репутацией производительности, но в этой конкретной операции она просто выполняла небрежная работа - нет другого способа выразить это. Характер операции, которая используется в качестве примера, делает ее очень зависимой от пропускной способности памяти, что является причиной того, что SIMD имеет только очень незначительное влияние - это в основном конкуренция кеш-памяти L1 и порядок обхода матриц действительно важен. Когда я повторно реализовал добавление Eigen, используя тайлинг, я смог уменьшить время выполнения на порядок, см. примечание в конце. Просто для этого Эйген использует тайлинг при умножении - просто попал в слабое место.)
Прежде всего, несколько слов о ndarray-ops: он построен на идее создания пользовательских функций для любой заданной формы и шага массива. Если вы пришли из современного структурированного языка, идея создания функции путем написания кода в строке и последующей передачи его интерпретатору может показаться крайним святотатством, но это обычное и очень полезное (даже если не всегда очень безопасное) ) парадигма программирования в мире JavaScript. Вот внутренний преобразователь, который он сгенерировал по этому поводу:
for(i1 = 0; i1 < s0; ++i1) {
for(i0 = 0; i0 < s1; ++i0) {
a0[p0] += a1[p1]
p0 += d0s0
p1 += d1s0
}
}
Кроме того, для новичков в V8 - V8 работает как в режиме интерпретатора, так и в режиме JIT-компилятора. Обычно первые несколько итераций выполняются интерпретатором, затем, когда функция становится «горячее», будет несколько раундов JIT-компиляции, начиная с наиболее часто встречающегося пути кода, а затем до полной оптимизированной компиляции этих частей, чем это возможно. быть скомпилированным - поскольку JavaScript, в общем случае, не может быть полностью скомпилирован. Обычно даже в окончательной версии будет один или два обработчика случайных исключений для путей кода, которые никогда не запускаются. Итак, вот этот окончательный оптимизированный вывод внутреннего цикла этой функции, созданный V8:
0x00003f738f8c5860: mov %rcx,%r12 # Not great 0x00003f738f8c5863: mov %r11,%r8 # register 0x00003f738f8c5866: mov %r14,%rbx # optimization 0x00003f738f8c5869: cmp -0x158(%rbp),%r12d # i0 < s1 0x00003f738f8c5870: jge 0x3f738f8c58f7 # loop exit 0x00003f738f8c5876: movslq %r8d,%r11 # array 1 start 0x00003f738f8c5879: cmp %rdx,%r11 # rdx = array 1 size 0x00003f738f8c587c: jae 0x3f738f8c6419 # exception handler 0x00003f738f8c5882: lea (%r9,%rsi,1),%rcx # array 1 offset 0x00003f738f8c5886: movslq %ebx,%r14 # array 2 start 0x00003f738f8c5889: movss (%rcx,%r11,4),%xmm0 # load float 1 0x00003f738f8c588f: cmp %rdi,%r14 # rdi = array 2 size 0x00003f738f8c5892: jae 0x3f738f8c6425 # exception handler 0x00003f738f8c5898: lea (%r15,%rax,1),%rcx # array 2 offset 0x00003f738f8c589c: movss (%rcx,%r14,4),%xmm1 # load float 2 0x00003f738f8c58a2: cvtss2sd %xmm1,%xmm1 # somewhat archaic 0x00003f738f8c58a6: cvtss2sd %xmm0,%xmm0 # method 0x00003f738f8c58aa: addsd %xmm1,%xmm0 # add float 0x00003f738f8c58ae: lea (%r9,%rsi,1),%rcx # dst array offset! 0x00003f738f8c58b2: cvtsd2ss %xmm0,%xmm0 # why? useless! 0x00003f738f8c58b6: movss %xmm0,(%rcx,%r11,4) # store 0x00003f738f8c58bc: mov -0x120(%rbp),%r11 # p0 0x00003f738f8c58c3: add %r8d,%r11d # d0s0 0x00003f738f8c58c6: jo 0x3f738f8c6431 # exception handler 0x00003f738f8c58cc: mov -0x118(%rbp),%r14 # p1 0x00003f738f8c58d3: add %ebx,%r14d # d0s1 0x00003f738f8c58d6: jo 0x3f738f8c643d # exception handler 0x00003f738f8c58dc: mov %r12,%rcx # i0 0x00003f738f8c58df: add $0x1,%ecx # ++ 0x00003f738f8c58e2: jo 0x3f738f8c6449 # exception handler 0x00003f738f8c58e8: cmp -0x20(%r13),%rsp # JIT handler? 0x00003f738f8c58ec: ja 0x3f738f8c5860 # loop
Он не совсем идеален, но все же замечательно чистый. Он имеет множество проверок границ и обработки исключений, но вы получите их на любом современном «безопасном» языке. У него на несколько обращений к памяти больше, чем следовало бы, добавление не на месте, оптимизация регистров ужасна, а числа с плавающей запятой загружаются не самым эффективным способом для современного процессора x86, но это все. Это не намного хуже, чем то, что вы получите от g ++ -O0.
Небольшое примечание: в этом конкретном случае V8 легко выигрывает в сравнении с g ++ -O0, потому что Eigen, реализованный как шаблоны C ++, имеет очень тяжелую среду отладки. Но в остальном он, как правило, немного медленнее, чем неоптимизирующий компилятор C ++ в общем случае.
Что действительно поразительно для любого начинающего читателя сборки V8 (меня), так это то, что все индексы массива являются целыми числами. Как вы знаете, в JavaScript нет натуральных целых чисел. Тем не менее, V8 превратил их в целые числа с проверкой границ. Замечательно.
Вот теперь высокопроизводительный внутренний цикл, созданный g ++ с AVX512 при использовании матриц с одинаковыми шагами (первый раунд):
0x00000000000014e8 <+56>: vmovaps (%rsi,%rcx,4),%ymm1 0x00000000000014ed <+61>: vaddps (%r8,%rcx,4),%ymm1,%ymm0 0x00000000000014f3 <+67>: vmovaps %ymm0,(%rsi,%rcx,4) 0x00000000000014f8 <+72>: add $0x8,%rcx # 2 floats per 0x00000000000014fc <+76>: cmp %rcx,%rax # iteration 0x00000000000014ff <+79>: jg 0x14e8
Я не буду вам лгать - в любом случае это будет сложно, но этот явно лучше. Это результат 30-летнего опыта оптимизации компиляторов. Во-первых, он делает 2 числа за цикл (почему не 4, для меня остается загадкой). Он также делает гораздо меньше обращений к памяти. Он не выполняет проверку границ, поэтому код кажется намного короче, но, опять же, способ, которым V8 выполняет проверку границ, очень эффективен и не слишком дорог. Также добавление на месте - экономия нескольких циклов.
Если вам интересно - внутренний ассемблерный код поступает непосредственно от самого Eigen через встроенные функции компилятора, но логика цикла вокруг него создается компилятором.
Это цикл g ++, добавляющий матрицы с разными шагами (в этом случае AVX невозможен):
0x00000000000014c0 <+80>: movss (%rax),%xmm0 # load 0x00000000000014c4 <+84>: addss (%rsi),%xmm0 # add 0x00000000000014c8 <+88>: add $0x4,%rax # increment on X 0x00000000000014cc <+92>: add %r11,%rsi # increment on Y 0x00000000000014cf <+95>: movss %xmm0,-0x4(%rax) # store 0x00000000000014d4 <+100>: cmp %r9,%rax # loop exit? 0x00000000000014d7 <+103>: jne 0x14c0 # loop
Это почти идеально - это должно быть нашей базой для кода V8. Первое приращение - константа, второе - регистр. Сложение двух чисел происходит на месте. Вместо вычисления смещения массива на каждой итерации, оно просто увеличивается и используется как итератор цикла - это, вероятно, проблема производительности номер один в ассемблерном коде V8.
Тем не менее, V8 на удивление близок. Приходится признать некоторую неуклюжесть, когда речь идет о выпуске сборки. К некоторым переменным, которые могли быть в регистрах, доступ осуществляется из памяти - но поскольку они наверняка будут в кешах L1, это не такая уж большая проблема - на данный момент недостаток сложности V8 покрывается современным процессором - Оптимизация реестра не так важна, как это было 20 или 30 лет назад. Используемые инструкции не всегда оптимальны - cvtss2ssd можно было бы избежать, и можно было бы добавить добавление, особенно потому, что JS выполняет добавление на месте. Проверка границ и исключений определенно на удивление хороша - вряд ли могло быть лучше.
Также преобразователь из ndarray-ops, вероятно, мог бы вручную удалить переменную итератора, сэкономив несколько циклов на итерацию. Увы, поскольку здесь нет арифметики с указателями, вычисление смещения массива должно быть оставлено на V8 - а это влечет за собой значительную цену производительности.
Итак, резюмируем:
- Прежде всего, алгоритмы более важны, чем оптимизация низкого уровня, а язык более высокого уровня упрощает реализацию лучшего.
- Не думайте, что вам нужен C ++, чтобы быть быстрым, V8 JavaScript имеет почти скомпилированную производительность
- Текущий уровень производительности сборки V8 немного ниже, чем у g ++ -O0 - и на порядок выше, чем у любого другого «интерпретируемого» языка.
- Ручное управление памятью и арифметика указателей, которые затрудняют изучение C ++, вероятно, являются его последней сильной стороной против языков с управлением памятью - по мере развития JIT-компиляторов разрыв в чистой производительности продолжает сокращаться.
- По-прежнему можно увеличить производительность в 10 раз, оптимизировав сборку вручную, но это очень трудоемкий процесс, и даже мелкие детали могут легко испортить вашу производительность и ваши вложения.
- В конкретном случае JavaScript V8, C ++ также остается единственным способом воспользоваться преимуществом наличия нескольких ядер для сложных вычислительных задач
- SIMD было бы очень желанным дополнением к V8 - особенно потому, что это довольно легко сделать в простом цикле, подобном тому, который указан в преобразователе ndarray-ops
Обновление: он Похоже, что на github есть совсем недавняя библиотека SIMD WebAssembly: https://github.com/CrimsonCodes0/SIMD.ts
По состоянию на 9 июля SIMD v128 является предложением фазы 4 с работающей реализацией в V8. начиная с 9.1.269.36 и Node.js с 16.4.0
Это означает, что возможная версия ndarray_ops в ближайшем будущем, вероятно, будет иметь почти нативную однопоточную производительность
В заключение, после переопределения суммы в Eigen с использованием тайлинга (второй круговой тест), я получил следующие результаты:
----------------------------------------- ndarray-ops | Eigen a+b | Eigen tiled a+b ----------------------------------------- 425ms 533ms 45ms AVX512 (recent Intel i7) 1273ms 3032ms 175ms SSE2 (older Athlon Phenom II BE)
Особая благодарность миколалысенко и пузпузпуз за их предложения.
