[JavaScript] 자바스크립트의 배열

최근 감사한 기회로 짝꿍이 활동하고 있는 스터디 그룹에 참여하게 되었다. 이번 주는 배열에 관한 주제로 이야기를 나누는 시간이다.

나는 자바스크립트 배열은 배열이 아니라는 것과 자바스크립트 배열은 희소 배열이라는 것에 대해서 이야기를 해보고 싶다.

자바스크립트의 배열은 배열이 아니다.

먼저, 자바스크립트 배열이 아닌 배열은 무엇일까? 이 배열은 밀집 배열이라고 부르는데, 주로 다음과 같은 특징을 가진다.

1. Fixed Capacity: 요소가 들어갈 수 있는 개수가 정해져 있다. 이 개수는 바뀌지 않는다.

2. Contiguous Memory: 배열은 연속된 메모리 공간을 차지하며 인덱스(offset)를통해 특정 메모리 공간에 접근할 수 있다.

 

많은 언어가 밀집 배열을 자료형으로서 지원하기 때문에 자연스럽게 밀집 배열이 배열이라는 인식이 생긴 듯하다. 밀집 배열을 말미암아 생각해보면 자바스크립트 배열은 밀집 배열이 아니다. 왜냐하면 배열의 크기는 변할 수 있기 때문이다(Dynamic Capacity). 그리고 엄밀히 말해 자바스크립트는 배열 자료형이 없다. 언어를 둘러싼 환경에서 배열의을 객체로서 정의하기 때문이다. 자바스크립트의 배열은 자료구조고, 스펙에서는 Array-Like Object 이라는 단어로 표현한다.

 

자바스크립트의 배열은 희소 배열이다.

이 말은 배열이라는 단어의 적용 범위를 언어가 돌아가는 '환경'에 국한할 것인지 '언어 자체'에 국한할 것인지에 따라 맞는 말이기도 하고 틀린 말이기도 하다. 전자의 관점에서 생각해보면 환경이 희소 배열의 성질로 배열을 구현을 하여야지만 언어가 희소 배열이 된다. 후자 ECMA-262에 의거해야 한다.

아무리 봐도 후자의 관점에서는 명백히 규정할 수 없다. 왜냐하면 스펙에서는 배열을 Array-Like Object 으로 정의를 하였기 때문이다. 자바스크립트의 배열이 배열을 흉내낸 객체라고 한다면 배열의 무엇을 흉내냈는지는 결국 환경에 의존할 수밖에 없다. 그래서 나는 V8에 한정하여 환경이 어떻게 배열을 흉내냈는지 알아보고자 한다.

 

자바스크립트의 배열이 희소 배열이 아닐 수 있는 이유

node --allow-natives-syntax -e "const a = [1,2,3]; a[10] = 5; %DebugPrint(a);"

 

 

 

이 커맨드를 입력하면 D8을 사용하여 V8이 어떻게 a가 가리키는 배열을 관리하는지 볼 수 있다. 이 출력의 내용은 다음과 같다.

DebugPrint: 0x12cb03f29ca9: [JSArray]
 - map: 0x1512d980a621 <Map[32](HOLEY_SMI_ELEMENTS)> [FastProperties]
 - prototype: 0x1512d9803b09 <JSArray[0]>
 - elements: 0x12cb03f29cc9 <FixedArray[32]> [HOLEY_SMI_ELEMENTS]
 - length: 11
 - properties: 0x38c6c7140c31 <FixedArray[0]>
 - All own properties (excluding elements): {
    0x38c6c71417c9: [String] in ReadOnlySpace: #length: 0x38c6c7171c19 <AccessorInfo name= 0x38c6c71417c9 <String[6]: #length>, data= 0x38c6c7140069 <undefined>> (const accessor descriptor), location: descriptor
 }
 - elements: 0x12cb03f29cc9 <FixedArray[32]> {
           0: 1
           1: 2
           2: 3
         3-9: 0x38c6c7140c69 <the_hole_value>
          10: 5
       11-31: 0x38c6c7140c69 <the_hole_value>
 }
0x1512d980a621: [Map] in OldSpace
 - map: 0x1512d98011a1 <MetaMap (0x1512d9801231 <NativeContext[287]>)>
 - type: JS_ARRAY_TYPE
 - instance size: 32
 - inobject properties: 0
 - unused property fields: 0
 - elements kind: HOLEY_SMI_ELEMENTS
 - enum length: invalid
 - back pointer: 0x1512d9827061 <Map[32](PACKED_SMI_ELEMENTS)>
 - prototype_validity cell: 0x38c6c7141249 <Cell value= 1>
 - instance descriptors #1: 0x1031eacb78f1 <DescriptorArray[1]>
 - transitions #1: 0x1512d980a669 <TransitionArray[4]>Transition array #1:
     0x38c6c71418d1 <Symbol: (elements_transition_symbol)>: (transition to PACKED_DOUBLE_ELEMENTS) -> 0x1031eacb7921 <Map[32](PACKED_DOUBLE_ELEMENTS)>

 - prototype: 0x1512d9803b09 <JSArray[0]>
 - constructor: 0x1512d9806b51 <JSFunction Array (sfi = 0x38c6c717bc09)>
 - dependent code: 0x38c6c7140c51 <Other heap object (WEAK_ARRAY_LIST_TYPE)>
 - construction counter: 0

 

 

우리가 관심있게 봐야할 부분은 elements 필드다. V8에서 구현한 배열은 요소를 따로 관리하는 Backing Store를 elements 필드에 할당한다. Backing Store가 무엇이냐에 따라 배열을 관리하는 메커니즘이 달라진다. 출력물에서는 FixedArray를 사용하는 것을 볼 수 있고. 요소에 <the_hole_value>가 있는 것도 볼 수 있다.

 

FixedArray는 TaggedArrayBase의 서브 타입으로, 힙에서 고정된 메모리 영역을 차지한다. (FixedArray의 생성자 링크)(메모리 할당 관련 링크1, 메모리 할당 관련 링크 2). TaggedArrayBase 에 있는 메소드를 보면 인덱스를 기준으로 오프셋을 정하고, 인스턴스의 주소(곧 0번 째 오프셋의 주소)와 오프셋을 더한 주소로 메모리 영역을 계산한다. 밀집 배열이 동작하는 방식과 똑같은 것이다.

 

그런데 elements 필드를 잘 보면 리터럴로 할당한 값이 아닌 <the_hole_value> 도 할당되어있다. 이 값은 sentinel value로, 논리적으로 없는 값, 또는 <empty item>을 뜻한다. FixedArray는 특정 인덱스를 sentinel value로 할당함으로써 논리적으로 없는 값, 즉 희소성을 표현하고 있다. 

 

한편, 요소의 개수가 비약적으로 늘어나면 Backing Store는 Hash Table(NumberDictionary)으로 변경되고 이 전 자료구조의 요소가 전부 해쉬테이블에 할당된다. 물리적인 자료구조가 고정된 메모리 영역을 차지하는 개념이 아니니, 이 때 배열은 희소 배열처럼 동작한다.

 

모든 것을 정리해보면 다음과 같다.

 

1. 논리적으로 자바스크립트 배열은 희소 배열이 될 수 있다.

2. 물리적으로 자바스크립트 배열은 일정 척도까지는 밀집 배열이며, 그 척도를 넘어서면 희소 배열이다.