Ако смятате, че това е шега, то тази история е за вас
Съвсем наскоро публикувах нов плъгин за JS свързванията на GDAL, който в момента поддържам за импортиране и експортиране на N-измерни масиви към scijs. scijs, макар и все още далеч зад съименника си Python, в момента набира все по-голяма популярност, воден от общия успех на JavaScript и V8.
Винаги съм знаел, че I/O производителността на 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 CPU чрез ръчно изработени вътрешни цикли на сглобяване. Със сигурност, когато работи с много големи матрици, Eigen щеше да изпуши ndarray. Очаквах поне коефициент 10, може би дори повече.
Оказва се, че не винаги е толкова просто.
Моят тест се състои от добавяне на две матрици 10 000x10 000 Float32 (TYPE) (размер 400 MB). Това е донякъде необичаен тест, който изисква много висока честотна лента на паметта.
Първият ми метод е „наивният 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. Още веднъж, Eigen използва вътрешен 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, използвайки подреждане, успях да намаля времето за изпълнение с порядък, вижте бележката в края. Само за точката, 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 CPU, но това е всичко. Не е много по-лошо от това, което ще получите от 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 се покрива от модерния CPU - оптимизирането на регистъра не е толкова важно, колкото беше преди 20 или 30 години. Използваните инструкции не винаги са оптимални — cvtss2ssdможеше да бъде избегнат и добавянето можеше да е на място — особено след като JS прави добавяне на място. Проверката на границите и изключенията определено е забележително добра — едва ли можеше да бъде по-добра.
Също така прехвърлянето от ndarray-ops вероятно може ръчно да елиминира променливата на итератора — спестявайки няколко цикъла на итерация. Уви, тъй като няма аритметика на указателя, изчисляването на отместването на масива трябва да бъде оставено на V8 — и това носи значителна цена на производителността.
И така, да обобщим:
- На първо място, алгоритмите са по-важни от оптимизацията на ниско ниво и езикът на по-високо ниво улеснява прилагането на по-добрия
- Не предполагайте, че имате нужда от C++, за да сте бързи, V8 JavaScript има почти компилирана производителност
- Текущото ниво на производителност на произведеното от V8 асемблиране е малко под това на g++ -O0— и с порядък по-високо от всеки друг „интерпретиран“ език
- Ръчното управление на паметта и аритметиката на указателя, които правят C++ толкова труден за научаване, вероятно е последната му голяма сила срещу езиците, управлявани от паметта - докато JIT-компилаторите узряват, разликата в необработената производителност продължава да се стеснява
- Все още е възможно да получите 10-кратно увеличение на производителността чрез извършване на ръчно оптимизирано сглобяване — но това е много времеемък процес и дори малки детайли могат лесно да съсипят вашата производителност — и вашата инвестиция
- В конкретния случай на V8 JavaScript, C++ също остава единственият начин да се възползвате от наличието на множество ядра за тежки изчислителни задачи
- SIMD би било много добре дошло допълнение към V8 — особено след като е доста лесно да се направи в обикновен цикъл от типа на този в ndarray-ops thunk
Актуализация: Това изглежда, че има съвсем скорошна библиотека SIMD WebAssembly в github: https://github.com/CrimsonCodes0/SIMD.ts
От 9 юли v128 SIMD е предложение за фаза 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)
Със специални благодарности на mikolalysenko и puzpuzpuz за техните предложения
