Перейти к основному содержимому

Добавление BigInts в V8

· 8 мин. чтения
Якоб Куммеров, арбитр точности

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

Суть​

Как программист JavaScript, теперь1 у вас в арсенале есть целые числа с произвольной2 точностью:

const a = 2172141653n;
const b = 15346349309n;
a * b;
// → 33334444555566667777n     // Ура!
Number(a) * Number(b);
// → 33334444555566670000      // Увы!
const such_many = 2n ** 222n;
// → 6739986666787659948666753771754907668409286105635143120275902562304n

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

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

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

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

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

Вернёмся в школу и к Кнуту​

Работа с целыми числами, хранимыми в регистрах процессора, действительно проста: например, чтобы умножить два из них, есть машинная инструкция, которую программное обеспечение может использовать, чтобы сказать процессору «умножь содержимое этих двух регистров!», и процессор выполнит это. Для арифметики 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 умножает BigInts: одна цифра за раз, складывая промежуточные результаты. Алгоритм работает так же хорошо для 0 до 9, как и для гораздо больших цифр BigInt.

Дональд Кнут опубликовал конкретную реализацию умножения и деления больших чисел, составленных из меньших частей, в Том 2 своего классического труда Искусство программирования, ещё в далёком 1969 году. Реализация V8 следует этой книге, что показывает, что это действительно классический пример компьютерной науки.

«Меньше упрощений» == больше сладостей?​

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

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

Немного веселья с побитовыми операциями​

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

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

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

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

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

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

> const big_array = new BigInt64Array(1);
> big_array[0] = 123n;  // OK
> big_array[0]
123n
> big_array[0] = 456;
TypeError: Невозможно преобразовать 456 в 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, по электронной почте [email protected] или @v8js в Twitter.

Footnotes​

  1. Теперь, если вы используете Chrome Beta, Dev или Canary либо предварительную версию Node.js; в противном случае скоро (Chrome 67, Node.js tip-of-tree, вероятно, примерно в то же время). ↩

  2. Произвольная до определённого ограничения на реализацию. К сожалению, мы пока не придумали, как поместить бесконечное количество данных в конечное количество памяти вашего компьютера. ↩

  3. На 64-битных машинах используются 64-битные цифры, т.е. от 0 до 18446744073709551615 (т.е. 2n**64n-1n). ↩

  4. Смешивание типов операндов BigInt и Number обычно не допускается. Это относительно необычно для JavaScript, но есть объяснение данного решения. ↩