Redjen TIL
Redjen TIL

Contents

Javascript Array에 대해

   2778 words   6 minutes 

배열은 모든 프로그래밍 언어에서 사용하는 가장 기본적인 자료구조이다. 그런데 자바스크립트에서의 배열은 다른 언어들과는 약간 다른 면모를 보이는데…

https://blog.devgenius.io/arrays-and-array-in-javascript-345b4f87a232

배열이란

배열은 성질이 동일한 구성 요소들을 고정 크기만큼 모아놓은 집합이다.

배열은 다음과 같은 특징들을 가지고 있다.

  • 배열은 미리 정의된 고정 크기를 가질 수 있다.
  • 배열 안의 모든 원소들은 동일한 데이터 타입을 가진다.
  • 모든 원소들은 0부터 시작해서 N-1으로 끝나는 인덱스를 할당 받는다. (N은 배열의 크기)
  • 배열은 연속된 메모리 공간을 사용할 수 있다. (아닌 경우도 있다)
  • 삽입과 랜덤 액세스에 O(1) 시간 복잡도를 가진다.
  • 삭제와 검색에 O(N) 시간 복잡도를 가진다.

자바스크립트에서의 배열 객체

자바스크립트에서의 배열은 좀 다르다. 리스트처럼 생긴 전역 객체이다.

자바스크립트에서의 배열은 C나 자바에서처럼 연속된 메모리 공간을 가지는, primitive한 배열 자료구조를 가지는 것처럼 생겼지만, 실제로는 해시 테이블을 구현한 API이다. (!)

자바스크립트의 배열은 일반적으로 생각하는 ‘배열’이라고 보기엔 다음과 같은 특성을 가지기 때문에 좀 다르다.

  • 가변 길이를 가진다. 초기 크기 설정을 할 수도 있지만, 필수는 아니다.
  • 동일한 배열 안에 서로 다른 데이터 타입을 가지는 원소들이 들어갈 수 있다.
  • 자바스크립트는 dense array와, sparse array 모두 지원한다.

Dense Array

Dense Array는 연속된 메모리 블럭을 할당 받는 배열이다.

Sparse Array

Sparse Array는 연속된 메모리 블럭을 할당받지 않을 수 있는 배열이다.

자바스크립트의 Array가 특별하게 만들어진 이유

Sparse array를 지원하면

  1. 고정된 배열 크기를 가지지 않고
  2. 다양한 데이터 타입을 한 배열 내에 담읋 수 있고
  3. 무엇보다 메모리 활용을 효율적으로 할 수 있기 때문이다.

아래의 코드는 어떻게 동작할까?

let arr = [1, 2, 3];
arr[50] = 50;

console.log(arr[41]);
console.log(arr.length);

arr[41]은 undefined, arr.length는 51을 출력한다. 또 3부터 49까지의 원소들에 대해서는 모두 undefined를 출력한다.

위 예제에서, 자바스크립트는 절대로 선언되지 않은 3부터 49까지의 인덱스에 대해 메모리를 할당하지 않는다. let arr = new Array(100000) 으로 10만의 크기를 가진 배열을 선언해도, 실제로는 아무런 메모리를 할당하지 않는 것이다.

자바스크립트의 배열은 객체이다. (사실 primitive한 값을 제외한 자바스크립트의 모든 것은 객체이다. 심지어는 함수도!) let arr = new Array(100000)은 Array 객체 내부의 length 속성을 10만으로만 설정한다. 사용하지 않는 원소들에 대한 메모리를 할당하지 않음으로써 메모리 사용량을 현저히 아낄 수 있다는 장점이 있다. 또 자바스크립트의 배열은 가변 길이를 가지기 때문에 실제로는 let arr = new Array(100000) 처럼 사용할 필요가 하나도 없다.

그럼 arr.length는 왜 51일까? 자바스크립트는 선언되지 않은 인덱스에 대해서는 ‘구멍을 뚫음으로써’ 인덱스를 consistent하게 유지한다. 이 편이 개발하는 입장에서는 더 편하기도 하다.

메모리 구조에 따른 상이한 동작?

자바스크립트의 배열은 저장하는 것이 어떤 것인지에 따라 내부 동작이 조금 상이하다.

https://stackoverflow.com/questions/20321047/how-are-javascript-arrays-represented-in-physical-memory

  • 배열에 할당된 primitive한 값을 변경해도 값 별로 저장되기 때문에 배열에 저장된 값은 변하지 않는다.
  • 하지만 배열에 할당된 객체를 변경하면 해당 배열이 저장하고 있는 객체에 변경 내용이 반영된다.
let arr = [];
let obj = { name: "John" };
let isBool = true;

arr.push(obj);
arr[1] = isBool;

console.log(arr[0]); // {name: "John"}
console.log(arr[1]); // true

obj.age = 40;
isBool = false;

console.log(arr[0]); // {name: "John", age: 40}
console.log(arr[1]); // true

최적화에 대한 단상

지금까지 알아봤듯이 자바스크립트의 배열은 sparse 할 수 있다. 그렇다면 delete 를 통해서 배열의 원소를 삭제하면 어떻게 될까?

let arr = [1, 2, 3, 4, 5];
console.log(arr); // [1, 2, 3, 4, 5]

delete arr[2]
console.log(arr); // [1, 2, 4, 5]

예상했듯이, 1 다음에는 2가 오지만 (숫자 2가 아닌 2번째 원소를 삭제했기 때문에) 그 사이의 메모리는 비어있게 된다.

자바스크립트의 배열은 그 특성 때문에 엔진이 최적화를 시도하는 대상이지만 이렇게 삭제나 중간 삽입 등의 연산으로 인해 메모리가 여기저기 흩어지게 되면 –

Branch Prediction

https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array

여담이지만 10년 가까이 되는 기간 동안 스택 오버 플로우를 봤지만 이렇게 많은 수의 vote는 보지 못했다.

결론만 놓고 말하면 흩어진 메모리를 찾기 위해서 메모리의 이 곳 저 곳을 쑤시며 돌아다니는 행위는 확률적으로 일어날 확률이 적기 때문에, 패턴 예측 기반으로 이루어지는 컴파일러 단에서의 최적화가 되기 어렵다.

자바스크립트의 배열은 sparse array를 지원하지만 성능 상 이점이 있는 것은 분명 dense array이다. 그럼에도 불구하고 왜 자바스크립트가 sparse array를 지원하느냐? 성능 상 이점을 가지는 대신 유연함과 확장성을 가지는 것이 우선시되었기 때문이다. 나는 이것이 자바스크립트 기저에 깔린 철학이라고 생각한다..

Typed Array에 대해

자바스크립트를 다른 언어의 배열처럼 연속된 메모리를 할당하기 위해서는 TypedArray를 사용해야 한다.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Typed_arrays

Typed Array란

메모리 버퍼에 들어 있는 raw 이진 데이터를 읽고 쓰는 메커니즘을 제공하는, ‘배열처럼 보이는’ 객체이다.

배열 객체는 위에서 설명했듯이 모든 자바스크립트의 값을 담고, 담을 수 있는 개수에도 제한이 없다.

자바스크립트 엔진은 이런 배열이 빠르게 동작할 수 있도록 최적화를 수행하지만, 웹 어플리케이션이 수행하는 역할이 점점 커지고 교환해야 할 데이터 자체도 다양하고 커지게 되었다. (오디오나 비디오, 웹 소켓을 사용한 raw data에의 접근 등)

때문에 자바스크립트 코드에서 빠르고 쉽게 이진 데이터를 접근할 수요가 생기게 되었고, typed array를 탄생시켰다.

Typed array는 많은 면에서 배열과 비슷하지만, 일반 배열과 혼동되지 않기 위해 Array.isArray() 값을 false로 가진다. 또한, push와 pop처럼 일반 배열에서 지원하는 모든 함수들이 사용가능한 것은 아니다.

Typed Array의 아키텍쳐

자바스크립트의 Typed Array는 효율성과 유연성을 극대화 시키기 위해 버퍼와 뷰로 쪼개어 구현되었다.

  • 버퍼는 (ArrayBuffer 객체로 구현되는) 데이터 덩어리를 표현하는 객체이다.
    • 내부에 접근하는 메커니즘을 제공하지 않는다.
    • 버퍼 안에 있는 메모리를 접근하기 위해서는 뷰의 도움이 필요하다.
  • 뷰는 데이터를 접근하기 위한 컨텍스트를 제공한다.
    • 데이터 타입, 데이터 시작 오프셋, 원소의 개수 등이 뷰에 해당된다.
    • 뷰는 버퍼에 저장된 데이터를 실제로 typed array로 만드는 역할을 수행한다.

ArrayBuffer

ArrayBuffer는 범용적이고 고정된 크기의 이진 데이터 버퍼를 표현하기 위한 데이터 타입이다. ArrayBuffer 안에 있는 내용을 직접 조정하는 것은 불가능하며, DataView를 생성해서 내용물을 읽고 쓸 수 있다.

Typed Array Views

Typed array의 뷰들은 자명한 (self-descriptive) 이름을 가지고, 범용적으로 많이 사용하는 숫자 타입인 Int8, Uint32, Float64와 같은 타입을 지원한다.

DataView

DataView는 버퍼에 임의의 데이터를 쓰기 위한 getter / setter API를 제공하는 로우 레벨 인터페이스이다. DataView는 서로 다른 데이터를 다룰 때 유용하며, 이외에도 아래와 같은 특징을 가진다.

  • Typed Array의 뷰는 플랫폼의 엔디안을 따른다. (인텔은 리틀 엔디안, 구형 Mac은 빅 엔디안 등)
  • DataView를 통해 사용하는 엔디안을 조정할 수 있다.
    • 기본적으로는 빅 엔디안을 사용하고, getter / setter 함수를 통해 리틀 엔디안으로 설정될 수 있다.
Updated on 2023-02-08
Back | Home