внедряем bigint в v8 [перевод]

Вольный перевод статьи Jakob Kummerow "Adding BigInts to V8"

Внедряем BigInt в V8

За последние пару месяцев мы внедрили поддержку BigInts в V8, которая указана в этом предложении для включения в будущую версию ECMAScript. А пост расскажет о наших приключениях.

TL;DR

Теперь[1], среди прочих инструментов, JavaScript программисту доступны целые числа с произвольной[2] точностью:

const a = 2172141653n;
const b = 15346349309n;
a * b;
// → 33334444555566667777n     // Вау!
Number(a) * Number(b);
// → 33334444555566670000      // Бу!
const such_many = 2n ** 222n;
// → 6739986666787659948666753771754907668409286105635143120275902562304n

Подробности о новой функциональности и её использовании описаны в нашей углубленной статье по BigInt. Мы с нетерпением ждем крутых вещей, которые вы создадите с её помощью!

Представление BigInts в памяти

Как правило, компьютеры хранят целые числа в регистрах CPU (которые, в настоящее время, 32 или 64-битной архитектуры) или чанках памяти размера регистра. Это приводит нас к минимальным и максимальным значениям, с которыми вы уже можете быть знакомы. например, 32-битное целое число может хранить значения от -2,147,483,648 до 2,147,483,647. Однако, идея BigInts в том, чтобы не ограничиваться такими пределами.

И так, как же мы может хранить BigInt с сотней, или тысячью, или миллионом битов? Такое не поместится в регистр, потому мы разместим в памяти объект и сделаем его достаточно большим для хранения всех BigInt битов в виде последовательности чанков, которые мы называем “цифрами” — потому что концептуально это очень схоже с тем, как мы можем написать большие числа, чем "9", использую больше цифр, как в "10"; кроме случаев, когда десятичная система использует цифры от 0 до 9, наша BigInt использует цифры от 0 до 4294967295 (т.е. 2**32-1). Это диапазон значений 32-битного CPU регистра[3] без знакового бита, который мы храним отдельно. Опишем BigInt объект с 3*32 = 96 битами с помощью псевдокода:

{
  type: 'BigInt',
  sign: 0,
  num_digits: 3,
  digits: [0x12…, 0x34…, 0x56…],
}

Снова в школу и снова к Кнуту

Работать с целыми числами, хранящимися в CPU регистрах, очень просто: например, перемножьте два из них, и CPU сделать это, используя машинную инструкцию, которую ПО может использовать для того, чтобы сказать CPU перемножить содержимое этих двух регистров. Для BigInt арифметики нам придется придумать собственное решение.К счастью, это как раз то задание, которое решал буквально каждый ребенок: помните, что вы делали в школе, когда приходилось умножать 345 * 678 без использования калькулятора?

345 * 678
---------
     30    //   5 * 6
+   24     //  4  * 6
+  18      // 3   * 6
+     35   //   5 *  7
+    28    //  4  *  7
+   21     // 3   *  7
+      40  //   5 *   8
+     32   //  4  *   8
+    24    // 3   *   8
=========
   233910

Именно так V8 перемножает BigIntы: одна цифра за раз, добавляя промежуточные результаты. С тем же успехом, что и для BigInt, алгоритм работает для значений от 0 до 9.

Дональд Кнут опубликовал конкретную реализацию умножения и деления больших чисел, собранных из более мелких чанков, во втором томе своей книги "The Art of Computer Programming" еще в 1969 году. Имплементация V8 следует этой книге, что наглядно демонстрирует вневременной кусок информатики.

“Меньше дешугаринга” == больше сладостей?

Удивительно, но нам пришлось потратить много времени, чтобы заработали унарные операции вроде -x. До сих пор -x делал то же самое, что и x * (-1), поэтому, для упрощения, V8 применяет эту замену как можно раньше при обработке JavaScript, а именно в парсере. Этот подход называется “дешугаринг”, потому что расценивает выражение, вроде -x, как “синтаксический сахар” для x * (-1). Другим инструментам (интерпретатору, компилятору, всей runtime системе) даже и знать о том, что такое унарная операция, не нужно, потому что видят они только умножение, которое они, конечно, должны поддерживать в любом случае.

Однако, с BigInt эта реализация становится нерабочей, поскольку перемножение BigInt и числа (вроде -1) должно выбросить TypeError[4]. Парсеру придется дешугарировать -x к виду x * (-1n), если x типа BigInt — но парсер никаким образом не знает, какое значение будет иметь x. Поэтому нам пришлось перестать полагаться на ранний дешугаринг и внедрить должную поддержку для унарных операций в Numbers и BigInts.

Повеселимся с побитовыми операциями

Сегодня большинство компьютерных систем хранят целые числа со знаком с помощью изящного трюка “дополнения двух”, который обладает хорошими свойствами, заключающимися в том, что первый бит указывает знак, а добавление 1 к битовой комбинации всегда увеличивает число на 1, заботясь о знаке бита автоматически. Например, для 8-битных целых чисел:

10000000 это -128, наименьшее представимое число,
10000001 это -127,
11111111 это -1,
00000000 это 0,
00000001 это 1,
01111111 это 127, наибольшее представимое число.

Эта кодировка настолько распространена, что многие программисты на нее полагаются, и спецификация BigInt отражает этот факт, предписывая, что BigInt должен действовать так, как если бы они использовали представление "дополнения двух". Но, как описано выше, BigInt от V8 так не действуют!

Поэтому, следуя спецификации, для выполнения побитовых операций, наши BigInt должны делать вид, что используют "дополнение двух" под капотом. Для значений больше нуля это не играет роли, но значениям меньше нуля придется выполнить дополнительную работу. Это имеет несколько неожиданный эффект: a & b, если a и b оба имеют отрицательные значения BigInt, на самом деле выполняет четыре шага (в отличие от одного, если б они оба были положительными): оба входа преобразуются в формат "фейковых двоих", после фактическая операция выполняется, а за ней результат преобразуется обратно в наше реальное представление. Вы можете спросить, почему так? А потому, что все непобитовые операции таким образом выполняются намного проще.

Два новых типа TypedArrays

Предложение BigInt включает два новых варианта TypedArray: BigInt64Array и BigUint64Array. Мы можем создать TypedArray с 64-битными целыми числами, поскольку BigInt предоставляет естественный способ чтения и записи всех битов в этих элементах, тогда как если попытаться использовать для этого Number, некоторые биты могут быть потеряны. Потому новые массивы не совсем похожи на уже существующие 8/16/32-битные целочисленные TypedArray: доступ к их элементам всегда осуществляется с помощью BigInt, а попытка использовать Numbers выбросит исключение.

> const big_array = new BigInt64Array(1);
> big_array[0] = 123n;  // OK
> big_array[0]
123n
> big_array[0] = 456;
TypeError: Cannot convert 456 to a BigInt
> big_array[0] = BigInt(456);  // OK

Подобно тому, как работающий с этими типами массивов JavaScript код, выглядит и работает несколько иначе, чем традиционный код TypedArray, нам пришлось обобщить нашу имплементацию TypedArray, чтобы те вели себя отлично от двух новичков.

Соображения об оптимизации

На данный момент мы отправляем базовую реализацию BigInt. Она функционально завершена и должна обеспечивать стабильную производительность (немного быстрее, чем существующие библиотеки), но оптимизирована она не детально. Причина в том, что, в соответствии с нашей целью установить приоритеты реальных приложений над искусственными тестами, мы сначала хотим посмотреть, как вы будете использовать BigInt, чтобы потом мы могли оптимизировать именно те случаи, которые вас интересуют!

Например, если мы увидим, что относительно небольшие BigInt (до 64 бит) являются важным юзкейсом, мы могли бы сделать их более эффективными в использовании памяти, используя для них специальное представление:

{
  type: 'BigInt-Int64',
  value: 0x12…,
}

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

Другая история - поддержка BigInt в оптимизирующем компиляторе. Для приложений с высокой вычислительной мощностью, работающих на 64-битных значениях и работающих на 64-битном оборудовании, хранение этих значений в регистрах будет гораздо более эффективным, чем выделение их в виде объектов в куче, как мы делаем в настоящее время. У нас есть планы относительно того, как мы будем реализовывать такую поддержку, но это другой случай, когда мы сначала хотели бы выяснить, действительно ли это то, что вас, наших пользователей, волнует больше всего; или мы должны потратить наше время на что-то другое вместо этого.

Пожалуйста, присылайте нам свой фидбэк о том, как и для чего вы используете BigInt, а также проблемы, с которыми вы сталкиваетесь! Написать нам можно в нашем баг-трекере crbug.com/v8/new, через почту v8-users@googlegroups.com, или твиттер-аккаунт @v8js.

Если запустите версии Chrome Beta/Dev/Canary или предварительную версию Node.js, в противном случае, в ближайших версиях (Chrome 67, Node.js).
Произвольной до предела, определенного реализацией. Извиняемся, но мы еще не выяснили, как втиснуть бесконечный объем данных в ограниченный объем памяти вашего компьютера.
В 64-битных машинах мы используем 64-битные цифры, т.е. от 0 до 18446744073709551615 (т.е. 2n**64n-1n).
Смешивание типов операндов BigInt и Number обычно не допускается. Это несколько необычно для JavaScript, но такому решению есть объяснение.