본문으로 건너뛰기

V8에 BigInt 추가

· 약 7분
정밀성을 담당하는 Jakob Kummerow

지난 몇 달 동안, 향후 ECMAScript 버전에 포함될 예정인 이 제안서에 따라 V8에서 BigInt를 지원하는 기능을 구현했습니다. 아래 글에서 우리의 모험 이야기를 들어보세요.

요약​

이제 여러분은 JavaScript 프로그래머로서 임의1 정밀도를 가진 정수를 도구로 사용할 수 있습니다2:

const a = 2172141653n;
const b = 15346349309n;
a * b;
// → 33334444555566667777n     // 야호!
Number(a) * Number(b);
// → 33334444555566670000      // 앗!
const such_many = 2n ** 222n;
// → 6739986666787659948666753771754907668409286105635143120275902562304n

새로운 기능과 이를 어떻게 사용할 수 있는지에 대한 자세한 정보는 우리의 BigInt에 대한 심층적인 기사를 참조하세요. 여러분이 이것으로 멋진 것들을 만들어내는 것을 기대합니다!

메모리에서 BigInt 표현하기​

일반적으로 컴퓨터는 정수를 CPU의 레지스터(요즘은 보통 32 또는 64비트 크기)나 레지스터 크기의 메모리 조각으로 저장합니다. 이는 여러분이 익숙할 최소 및 최대 값으로 이어집니다. 예를 들어, 32비트 부호 있는 정수는 -2,147,483,648에서 2,147,483,647까지 값을 가질 수 있습니다. 하지만 BigInt의 아이디어는 이러한 제한에 국한되지 않는 것입니다.

그렇다면 어떻게 백, 천 또는 백만 비트를 가진 BigInt를 저장할 수 있을까요? 이는 레지스터에 들어갈 수 없으므로 메모리에 객체를 할당합니다. 우리는 BigInt의 비트를 모두 보유할 수 있도록 충분히 큰 크기로 메모리를 할당하고 이를 여러 조각(우리는 이것을 'digit'라 부르기로 합니다)으로 나눕니다. 이는 십진법에서 0부터 9까지 숫자를 사용하는 것과 비슷하지만, 우리의 BigInt는 0에서 4294967295(2**32-1의 값)까지 숫자를 사용합니다. 이는 부호 비트를 제외한 32비트 CPU 레지스터3의 값 범위입니다. 부호 비트는 별도로 저장합니다. 다음은 96비트를 가진 BigInt 객체를 표현하는 예제입니다:

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

다시 학교로, 그리고 다시 Knuth로​

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 곱하기는 바로 이렇게 작동합니다: 한 번에 한 자리씩 중간 결과를 더해가는 것입니다. 이 알고리즘은 0에서 9까지뿐만 아니라 BigInt의 훨씬 더 큰 숫자에 대해서도 동일하게 잘 동작합니다.

Donald Knuth는 1969년에 고전 컴퓨터 과학 서적인 The Art of Computer Programming 2권에서 작은 조각으로 이루어진 대규모 숫자의 곱셈과 나눗셈에 대한 특정 구현을 게시했습니다. V8의 구현은 이 책을 따르며, 이는 시간이 지나도 유효한 컴퓨터 과학의 멋진 사례임을 보여줍니다.

“적은 문법 설탕” == 더 많은 단 것?​

놀랍게도, 우리는 -x와 같은 간단한 단항 연산 명령을 처리하기 위해 많은 노력을 기울여야 했습니다. 지금까지 -x는 정확히 x * (-1)과 같았으며, 이를 간소화하기 위해 V8은 가급적 빠르게, 즉 자바스크립트를 처리하는 파서 단계에서 정확히 이 교체를 적용했습니다. 이 접근방식을 “문법 설탕 해체”라고 부릅니다. 왜냐하면 이는 -x와 같은 표현을 x * (-1)에 대한 “문법 설탕”으로 간주하기 때문입니다. 다른 구성 요소(인터프리터, 컴파일러, 전체 런타임 시스템)는 단항 연산 명령에 대해 알 필요가 없었습니다. 왜냐하면 그것들이 항상 곱셈을 처리하기만 하면 되기 때문입니다.

빅인트(BigInt)를 사용하면, 이 구현은 갑자기 무효가 됩니다. 왜냐하면 빅인트를 숫자(Number, 예: -1)와 곱하면 TypeError4를 발생시켜야 하기 때문입니다. 파서는 -x를 빅인트인 x에 대해 x * (-1n)으로 디슈가링해야 하지만, 파서는 x가 무엇으로 평가될지 알 방법이 없습니다. 그래서 우리는 초기 디슈가링에 의존하지 않고, 대신 숫자와 빅인트 모두에서 단항 연산을 올바르게 지원해야 했습니다.

비트 연산의 즐거움을 조금​

오늘날 사용되는 대부분의 컴퓨터 시스템은 부호 있는 정수를 저장할 때 “2의 보수”라는 깔끔한 트릭을 사용합니다. 이는 첫 번째 비트가 부호를 나타내고, 비트 패턴에 1을 더하면 항상 1씩 증가하여 자동으로 부호 비트를 처리하는 멋진 속성을 가지고 있습니다. 예를 들어, 8비트 정수의 경우:

  • 10000000은 -128로, 표현 가능한 가장 낮은 숫자입니다,
  • 10000001은 -127입니다,
  • 11111111은 -1입니다,
  • 00000000은 0입니다,
  • 00000001은 1입니다,
  • 01111111은 127로, 표현 가능한 가장 높은 숫자입니다.

이 인코딩은 매우 일반적이어서 많은 프로그래머들이 기대하고 의존합니다. 빅인트 사양도 빅인트가 2의 보수 표현을 사용하는 것처럼 동작해야 한다는 점을 반영합니다. 하지만 위에서 기술된 것처럼, V8의 빅인트는 그러지 않습니다!

사양에 따라 비트 연산을 수행하려면, 우리의 빅인트는 내부적으로 2의 보수를 사용하는 척해야 합니다. 양수의 경우 별반 다를 것이 없지만, 음수는 이를 달성하기 위해 추가 작업을 해야 합니다. 이렇게 하면 약간 놀라운 효과가 발생할 수 있습니다. 예를 들어, a & b에서 a와 b가 둘 다 음수 빅인트라면 실제로 네 단계를 수행하게 됩니다 (두 값이 양수일 때는 한 단계에 불과한데도): 두 입력은 가짜 2의 보수 형식으로 변환되고, 실제 연산이 완료된 후 결과가 다시 실제 표현으로 변환됩니다. 왜 이렇게 왔다 갔다 하는 걸까요? 비트 연산 이외의 모든 연산이 이렇게 함으로써 훨씬 더 쉬워지기 때문입니다.

새로운 두 가지 타입의 TypedArrays​

빅인트 제안에는 새로운 TypedArray 두 가지 종류: BigInt64Array와 BigUint64Array가 포함됩니다. 이제 빅인트가 이러한 요소의 모든 비트를 읽고 쓸 수 있는 자연스러운 방식을 제공하기 때문에 64비트 정수 요소를 가진 TypedArray를 가질 수 있습니다. 빅인트를 사용하지 않고 숫자를 시도했다면 몇몇 비트가 손실될 수 있습니다. 따라서 이러한 새로운 배열은 기존의 8/16/32 비트 정수 TypedArray와는 다릅니다: 요소 접근은 항상 빅인트를 통해 이루어지며, 숫자를 사용하려고 하면 예외가 발생합니다.

> 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 구현을 일반화하여 다르게 동작하도록 해야 했습니다.

최적화 고려 사항​

현재, 우리는 빅인트의 기본 구현을 출시하고 있습니다. 이 구현은 완전하며 견고한 성능을 제공해야 하지만 (기존 사용자 라이브러리보다 약간 더 빠름), 특별히 최적화된 상태는 아닙니다. 이는 인위적인 벤치마크보다는 실질적인 응용 프로그램을 우선시하고자 하는 우리의 목표에 따라, 먼저 여러분이 빅인트를 어떻게 사용하는지 확인하고, 이후 여러분이 신경 쓰는 사례를 정확히 최적화하려는 것입니다!

예를 들어, 비교적 작은 빅인트 (최대 64비트)가 중요한 사용 사례라는 것을 확인하면, 이를 위해 특별한 표현 방식을 사용하여 메모리를 더 효율적으로 사용할 수 있습니다:

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

이를 “int64” 값 범위, “uint64” 범위, 또는 둘 다에 대해 수행해야 하는지 여부는 앞으로 더 지켜봐야 할 세부 사항입니다. 지원해야 할 빠른 경로가 적으면 더 빨리 구현할 수 있지만, 역설적이게도 추가적인 빠른 경로가 모든 것에 대해 다소 느려질 수 있습니다. 이는 사용 가능한지 확인하기 위한 추가 검사를 항상 수행해야 하기 때문입니다.

또 다른 이야기는 최적화 컴파일러에서의 빅인트 지원입니다. 64비트 값을 다루고 64비트 하드웨어에서 실행되는 계산 집약적인 애플리케이션의 경우, 현재처럼 힙에 객체로 할당하는 대신 이 값을 레지스터에 유지하면 훨씬 더 효율적일 것입니다. 우리는 이러한 지원을 구현하는 방법에 대한 계획이 있지만, 이것이 정말로 사용자들이 가장 신경 쓰는 것인지, 아니면 다른 무언가에 시간을 들이는 것이 더 나을지를 먼저 파악하고자 합니다.

빅인트를 무엇에 사용하고 있으며 발생한 문제에 대해 피드백을 보내주세요! 우리의 버그 트래커 crbug.com/v8/new, [email protected]로 메일, 또는 트위터 @v8js로 연락할 수 있습니다.

Footnotes​

  1. 구현 정의된 한계까지 임의로 가능합니다. 죄송합니다, 컴퓨터의 유한한 메모리에 무한 데이터를 넣는 방법은 아직도 개발되지 않았습니다. ↩

  2. Chrome Beta, Dev 또는 Canary 버전 혹은 Node.js 미리보기 버전을 사용한다면 지금. 그렇지 않으면 곧 (아마도 Chrome 67 또는 Node.js 최신 트리와 비슷한 시기). ↩

  3. 64비트 머신에서는 64비트 숫자(0에서 18446744073709551615까지, 2n**64n-1n)를 사용합니다. ↩

  4. BigInt와 Number 타입의 연산자 혼합은 일반적으로 허용되지 않습니다. 이는 자바스크립트에서 다소 드문 일이지만, 이 결정에 대한 설명이 있습니다. ↩