JS array의 자료구조는 무엇일까? - V8 엔진에서 JS array 구현

1. 크롬에서 쓰이는 JS 엔진인 V8 엔진은 C++로 구현되어 있고, 깃허브에 소스가 공개되어 있습니다
2. JS integer array는 V8 내부에서는 C++ array인데, 중간에 빈 value가 많은 경우(sparse한 경우) hash table로 구현됩니다
   • 그래서 sparse한 array는 성능이 더 나쁘다고 합니다
3. JS array를 선언할 때 V8 내부에서는 length를 element 개수보다 더 크게 잡은 배열을 선언합니다 (dynamic array)
   1. 그래서 일반적인 상황에서 push() 를 O(1) 시간에 수행할 수 있습니다
   2. 공간이 부족할 경우 크기를 늘리는 공식(growth factor) - 약 1.5배로 늘림
      1. new_capacity = (old_capacity + 50%) + 16
      2. 실제 코드
         
         

파이썬 알고리즘 인터뷰 책 보다가 python array의 내부 구현에 관한 내용이 나오길래 JS는 어떤지 궁금해서 찾아봤다. 의외로 정리된 내용이 없어서 깊게 들어갔다. JS 엔진이 여러개고, 엔진 따라 내부 구현이 다르기도 하고.

 

[참고자료]
How do JavaScript arrays work under the hood?
[V8 Deep Dives] Understanding Array Internals
V8 블로그 - Elements kinds in V8
v8docs - Array Class Referecne