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

10

При написании чувствительного к производительности кода в Javascript, который работает с большими числовыми массивами (например, пакет линейной алгебры, работающий с целыми числами или числами с плавающей запятой), всегда требуется, чтобы JIT помогал как можно больше. Примерно это означает:

  1. Мы всегда хотим, чтобы наши массивы были упакованными SMI (маленькими целыми числами) или упакованными двойными числами, в зависимости от того, выполняем ли мы вычисления целых чисел или с плавающей точкой.
  2. Мы всегда хотим передавать функции одного и того же типа функциям, чтобы они не были помечены как «мегаморфные» и деоптимизированы. Например, мы всегда хотим звонить vec.add(x, y)с обоими xи yбыть упакованными массивами SMI или с обоими упакованными двойными массивами.
  3. Мы хотим, чтобы функции были максимально встроены.

Когда кто-то выходит за пределы этих случаев, происходит внезапное и резкое снижение производительности. Это может произойти по разным безобидным причинам:

  1. Вы можете превратить упакованный массив SMI в упакованный массив Double с помощью, казалось бы, безобидной операции, например, эквивалента myArray.map(x => -x). На самом деле это «лучший» плохой случай, поскольку упакованные двойные массивы все еще очень быстры.
  2. Вы можете превратить упакованный массив в универсальный штучный массив, например, сопоставив массив с функцией, которая (неожиданно) вернула nullили undefined. Этого плохого случая довольно легко избежать.
  3. Вы можете деоптимизировать целую функцию, например vec.add(), передав слишком много типов вещей и превратив ее в мегаморфную. Это может произойти, если вы хотите сделать «общее программирование», гдеvec.add() это используется как в случаях, когда вы не проявляете осторожность с типами (поэтому он видит много типов, приходящих), так и в случаях, когда вы хотите добиться максимальной производительности. (например, он должен получать только двойные числа в штучной упаковке).

Мой вопрос является более мягким вопросом о том, как написать высокопроизводительный код Javascript в свете вышеизложенных соображений, при этом сохраняя код приятным и читабельным. Некоторые конкретные подвопросы, чтобы вы знали, к какому ответу я стремлюсь:

  • Есть ли где-нибудь набор руководящих принципов, как программировать, оставаясь в мире упакованных массивов SMI (например)?
  • Возможно сделать общее высокопроизводительное программирование в Javascript, не используя что-то вроде системы макросов, чтобы встроить такие вещи, как vec.add() в места вызова?
  • Как объединить высокопроизводительный код в библиотеки в свете таких вещей, как мегаморфные сайты вызовов и деоптимизация? Например, если я счастливо использую пакет линейной алгебры Aна высокой скорости, а затем я импортирую пакет, Bкоторый зависит от A, ноB вызывает его с другими типами и деоптимизирует его, внезапно (без изменения кода) мой код работает медленнее.
  • Есть ли хорошие удобные инструменты измерения для проверки того, что движок Javascript делает с типами внутри?
Джоппи
источник
1
Это очень интересная тема и очень хорошо написанный пост, который показывает, что вы правильно сделали свою часть исследования. Однако я боюсь, что вопрос (ы) слишком широк для формата SO, а также что он неизбежно привлечет больше мнений, чем фактов. Оптимизация кода - очень сложный вопрос, и две версии движка могут вести себя не одинаково. Я думаю, что есть один из людей, ответственных за V8 JIT, который иногда зависает, так что, возможно, они могли бы дать правильный ответ для своего двигателя, но даже для них, я думаю, это было бы слишком широким предметом для одного Q / A ,
Кайидо
«Мой вопрос - скорее мягкий вопрос о том, как написать высокопроизводительный код Javascript ...» Кроме того, обратите внимание, что javascript обеспечивает порождение фоновых процессов (веб-работников), и есть также библиотеки, которые подключаются к GPU (tenorflow.js и gpu.js) предлагает иные средства, кроме как полагаться только на компиляцию для повышения вычислительной пропускной способности приложения на основе JavaScript ...
Джон Трент
@JonTrent На самом деле я немного соврал в своем посте, меня не волнуют классические приложения линейной алгебры, а больше компьютерная алгебра над целыми числами. Это означает, что многие существующие числовые пакеты немедленно исключаются, поскольку (например) при сокращении строки матрицы они могут делиться на 2, что «не разрешено» в мире, в котором я работаю, поскольку (1/2) не является целым числом Я рассматривал веб-работников (особенно для нескольких длительных вычислений, которые я хочу отменить), но проблема, которую я здесь рассматриваю, заключается в том, чтобы снизить задержку настолько, чтобы реагировать на взаимодействие.
Джоппи
Что касается целочисленной арифметики в JavaScript, вы, вероятно, смотрите на код в стиле asm.js, грубо говоря «оставляя |0позади каждую операцию». Это не красиво, но лучшее, что вы можете сделать на языке, который не имеет правильных целых чисел. Вы также можете использовать BigInts, но на сегодняшний день они не очень быстрые в любом из распространенных движков (в основном из-за отсутствия спроса).
jmrk

Ответы:

8

Разработчик V8 здесь. Учитывая интерес к этому вопросу и отсутствие других ответов, я могу дать этому шанс; Боюсь, это будет не тот ответ, на который вы надеялись.

Есть ли где-нибудь набор руководящих принципов, как программировать, оставаясь в мире упакованных массивов SMI (например)?

Краткий ответ: это прямо здесь const guidelines = ["keep your integers small enough"].

Более длинный ответ: дать комплексный набор рекомендаций сложно по разным причинам. В целом, мы считаем, что разработчики JavaScript должны писать код, который имеет смысл для них и их варианта использования, а разработчики движка JavaScript должны выяснить, как быстро запустить этот код на своих движках. С другой стороны, у этого идеала есть некоторые ограничения в том смысле, что некоторые шаблоны кодирования всегда будут иметь более высокие затраты производительности, чем другие, независимо от выбора реализации движка и усилий по оптимизации.

Когда мы говорим о рекомендациях по производительности, мы стараемся помнить об этом и тщательно оценивать, какие рекомендации имеют высокую вероятность того, что они останутся действительными для многих механизмов и в течение многих лет, а также являются достаточно идиоматичными / ненавязчивыми.

Возвращаясь к рассматриваемому примеру: внутреннее использование Smis должно быть деталью реализации, о которой пользовательский код не должен знать. Это сделает некоторые случаи более эффективными, и в других случаях это не должно повредить. Не все движки используют Smis (например, AFAIK Firefox / Spidermonkey исторически нет; я слышал, что в некоторых случаях они используют Smis в наши дни; но я не знаю никаких деталей и не могу говорить с какими-либо полномочиями по причина). В V8 размер Smis - это внутренняя деталь, которая на самом деле менялась с течением времени и в разных версиях. На 32-битных платформах, которые использовались в большинстве случаев, Smis всегда были 31-битными целыми числами со знаком; на 64-битных платформах они были 32-битными целыми числами со знаком, что в последнее время казалось наиболее распространенным случаем, пока в Chrome 80 мы не выпустили «сжатие указателей» для 64-битных архитектур, которые требовали уменьшения размера Smi до 31 бита, известного на 32-битных платформах. Если бы вы основали реализацию на предположении, что Smis, как правило, 32-битные, вы получите такие неудачные ситуации, какэто .

К счастью, как вы заметили, двойные массивы все еще очень быстрые. Для числового кода, вероятно, имеет смысл предполагать / предназначаться для двойных массивов. Учитывая преобладание двойников в JavaScript, разумно предположить, что все движки имеют хорошую поддержку для двойников и двойных массивов.

Можно ли выполнять общее высокопроизводительное программирование в Javascript, не используя что-то вроде системы макросов для встраивания таких вещей, как vec.add () в места вызова?

«универсальный» обычно расходится с «высокопроизводительным». Это не связано с JavaScript или конкретными реализациями движка.

«Общий» код означает, что решения должны приниматься во время выполнения. Каждый раз, когда вы выполняете функцию, код должен запускаться, чтобы определить, скажем, «является xцелым числом? Если да, взять этот путь кода. Является xли строка? Затем перепрыгнуть сюда. Это объект? Имеет ли он .valueOf? Нет? Тогда возможно .toString()? Может быть, в цепочке прототипов? Назовите это и перезапустите с самого начала с его результатом ". «Высокопроизводительный» оптимизированный код по существу основан на идее отбросить все эти динамические проверки; это возможно только в том случае, если у движка / компилятора есть какой-то способ заранее выводить типы: если он может доказать (или предположить с достаточно высокой вероятностью), что xвсегда будет целым числом, тогда ему нужно только сгенерировать код для этого случая ( охраняется проверкой типа, если были задействованы недоказанные предположения).

Подкладка ортогональна всему этому. «Универсальная» функция все еще может быть встроенной. В некоторых случаях компилятор может распространять информацию о типе во встроенную функцию, чтобы уменьшить там полиморфизм.

(Для сравнения: C ++, будучи статически скомпилированным языком, имеет шаблоны для решения связанной проблемы. Короче говоря, они позволяют программисту явно указывать компилятору создавать специализированные копии функций (или целых классов), параметризованных для заданных типов. Хорошее решение для некоторых случаев, но не без собственного набора недостатков, например, большого времени компиляции и больших двоичных файлов. В JavaScript, конечно, нет такой вещи, как шаблоны. Вы можете использовать evalдля создания системы, которая чем-то похожа, но тогда вы столкнулись бы с подобными недостатками: вам пришлось бы делать эквивалент работы компилятора C ++ во время выполнения, и вам нужно было бы беспокоиться об огромном количестве кода, который вы генерируете.)

Как объединить высокопроизводительный код в библиотеки в свете таких вещей, как мегаморфные сайты вызовов и деоптимизация? Например, если я с удовольствием использую пакет линейной алгебры A на высокой скорости, а затем я импортирую пакет B, который зависит от A, но B вызывает его другими типами и деоптимизирует его, внезапно (без изменения кода) мой код работает медленнее ,

Да, это общая проблема с JavaScript. V8 использовался для реализации некоторых встроенных функций (например, Array.sort) в JavaScript, и эта проблема (которую мы называем «загрязнением типа обратной связи») была одной из основных причин, почему мы полностью отошли от этой техники.

Тем не менее, для числового кода не так уж много типов (только Smis и double), и, как вы заметили, они должны иметь аналогичную производительность на практике, поэтому, хотя загрязнение с обратной связью типов действительно является теоретической проблемой, а в некоторых случаях может оказывают существенное влияние, также вполне вероятно, что в сценариях линейной алгебры вы не увидите ощутимых различий.

Кроме того, внутри движка существует гораздо больше ситуаций, чем «один тип == быстрый» и «более одного типа == медленный». Если данная операция видела и Смиса, и двойников, это совершенно нормально. Загрузка элементов из двух видов массивов тоже подойдет. Мы используем термин «мегаморфный» для ситуации, когда нагрузка видела так много разных типов, что она отказывается от отслеживания их по отдельности, а вместо этого использует более общий механизм, который лучше масштабируется для большого количества типов - функция, содержащая такие нагрузки, может по-прежнему оптимизировать. «Деоптимизация» - это очень специфический акт необходимости выбрасывать оптимизированный код для функции, потому что виден новый тип, который ранее не был виден, и поэтому оптимизированный код не приспособлен для обработки. Но даже это хорошо просто вернитесь к неоптимизированному коду, чтобы собрать больше отзывов о типах, и повторите оптимизацию позже. Если это случится пару раз, тогда не о чем беспокоиться; это становится проблемой только в патологически плохих случаях.

Итак, краткое содержание всего этого: не беспокойтесь об этом . Просто напишите разумный код, пусть двигатель справится с этим. Под «разумным» я подразумеваю: то, что имеет смысл для вашего варианта использования, является читабельным, обслуживаемым, использует эффективные алгоритмы, не содержит ошибок, таких как чтение, за пределами длины массивов. В идеале это все, что вам нужно, и вам не нужно больше ничего делать. Если вам легче что- то делать и / или если вы действительно наблюдаете проблемы с производительностью, я могу предложить две идеи:

Использование TypeScript может помочь. Большое полное предупреждение: типы TypeScript нацелены на производительность разработчика, а не на производительность выполнения (и, как выясняется, эти две точки зрения предъявляют очень разные требования к системе типов). Тем не менее, есть некоторые совпадения: например, если вы последовательно аннотируете вещи как number, то компилятор TS предупредит вас, если вы случайно поместите nullв массив или функцию, которая должна содержать / работать только с числами. Конечно, дисциплина все еще необходима: один number_func(random_object as number)аварийный люк может молча подорвать все, потому что правильность аннотаций типов нигде не соблюдается.

Использование TypedArrays также может помочь. Они имеют немного больше накладных расходов (потребление памяти и скорость выделения) на массив по сравнению с обычными массивами JavaScript (поэтому, если вам нужно много маленьких массивов, то обычные массивы, вероятно, более эффективны), и они менее гибки, потому что не могут расти или уменьшить после выделения, но они гарантируют, что все элементы имеют ровно один тип.

Есть ли хорошие удобные инструменты измерения для проверки того, что движок Javascript делает с типами внутри?

Нет, и это намеренно. Как объяснялось выше, мы не хотим, чтобы вы специально адаптировали свой код к тем шаблонам, которые V8 может оптимизировать особенно хорошо сегодня, и мы не верим, что вы действительно хотите это сделать. Этот набор вещей может измениться в любом направлении: если есть шаблон, который вы хотели бы использовать, мы могли бы оптимизировать его для будущей версии (ранее мы играли с идеей хранения неупакованных 32-разрядных целых чисел в качестве элементов массива). ... но работа над этим еще не началась, так что никаких обещаний); и иногда, если есть шаблон, который мы использовали для оптимизации в прошлом, мы могли бы отказаться от него, если он помешает другим, более важным / действенным оптимизациям. Кроме того, такие вещи, как встроенная эвристика, как известно, трудно понять правильно, поэтому принятие правильного решения в нужное время является областью текущих исследований и соответствующих изменений в поведении движка / компилятора; что делает это еще один случай, когда это будет неудачно для всех (выи мы) если вы потратили много времени на настройку своего кода, пока какой-то набор текущих версий браузеров не примет приблизительно встроенные решения, которые вы считаете (или знаете?) наилучшими, только чтобы вернуться через полгода, чтобы понять, что тогдашние браузеры изменили свою эвристику.

Конечно, вы всегда можете измерить производительность вашего приложения в целом - это то, что в конечном итоге имеет значение, а не то, какой выбор конкретно сделан внутренним движком. Остерегайтесь микробенчмарков, поскольку они вводят в заблуждение: если вы извлекаете только две строки кода и сравниваете их, то есть вероятность, что сценарий будет достаточно разным (например, обратная связь другого типа), что механизм будет принимать совершенно разные решения.

jmrk
источник
2
Спасибо за этот прекрасный ответ, это подтверждает , что многие из моих подозрений о том , как работают вещи, и , что важно , как они предназначены для работы. Кстати, есть ли в блоге и т. Д. Сообщения о проблеме «обратной связи по типу», о которой вы упоминали Array.sort()? Я хотел бы прочитать немного больше об этом.
Джоппи
Я не думаю, что мы писали об этом конкретном аспекте. По сути, это то, что вы сами описали в своем вопросе: когда встроенные функции реализованы в JavaScript, они «похожи на библиотеку» в том смысле, что если разные куски кода вызывают их с разными типами, производительность может пострадать, иногда совсем немного, иногда больше. Это была не единственная и, возможно, даже не самая большая проблема с этой техникой; В основном я просто хотел сказать, что я знаком с общим вопросом.
jmrk