[javascript] 불변성(Immutability)을 위한 자료구조적 최적화

 

 

Intro.

함수형 프로그래밍을 접하면 아마 '불변성'이란 키워드에 대해서 듣게된다.

말 그대로, 원본 데이터에 대한 변이(Mutation) 과정을 진행하지 않겠다는 의미이다.

대신 변이 과정이 필요하다면, 원본 데이터를 복제 / 수정하여 사용한다.

 

function square(data){
   return data.map((d) => d ** 2); // data = [1,2,3] , return -> [1,4,9]
}

square([1,2,3])

 

Side Effect 방지 , 참조 투명성을 보장한다 etc.. 다 좋은데 매번 변이 과정이 필요할 때 마다 원본 데이터의 복제가 필요하다니, 메모리 관리 측면에선 정말 최악이란 생각이 든다.

 

원본 데이터의 크기가 크면 클 수록, 복제를 위한 메모리 & 시간 자원 전부 비례해서 증가할 것이기 때문이다.

 

이 부분에 대한 솔루션을 정말 우연히도 JsConf 영상을 보다 발견했는데, 개인적으로는 흥미롭게 보아서 그 방법을 공유하고자 한다.

 

 

 

Persistant Data structure

 

기존 데이터에 대해 새로운 복제본을 만들 때 마다, 일반적으로 대부분의 요소들은 기존 데이터와 유사하다.

 

예를 들어 특정 배열의 값 하나만 변경하고 싶은 경우, 하나의 요소를 제외한 나머지 요소는 전부 원본 데이터와 동일하기에,

이 경우, 중복 값은 원본 배열의 길이를 n이라 할 때 n-1이나 된다.

 

const origin = [1,2,3,4,5,6,7];

const copied = origin.map((d,idx)=> {
    if(idx ===0){
    	return 8
    }
    return d
})

 

이 경우, 원본 데이터와 복제된 데이터끼리 특정 값 들을 공유하면 되지 않을까?

 

마치 git version control 처럼 이전 버전을 보존 & 접속할 수 있다면, 불필요한 연산들을 줄일 수 있을것 같다.

 

 

Structual Sharing

 

이를 위해, 배열을 다음의 트리로 생각한다.

 

배열 X의 포인터는 트리의 루트 노드를 가르키고, 배열의 모든 요소들은 트리의 leaf에 저장된다.

 

여기서 변이가 일어날 시엔, 변이 부분에 대해서만 새로운 leaf노드들을 생성하고 중복되는 노드들에 대해선 공유한다.

 

 

복제된 배열 X'은 X와 보라색 동그라미 쳐진 노드들을 공유한다.

 

이 기법을 경로 복제 (path copying)이라고 부른다. 

 

 

Bitmap Vector Trie

 

자 그러면, 이제 위 트리에서 어떻게 인덱스로써 요소에 접근할 수 있을까?

 

위 트리 꼴이 트라이(Trie)와 유사한데, 트라이의 경우, 단어를 키로 가지는데, 현재 우리는 인덱스로 접근해야하는 상황이다.

 

이를 위해, 인덱스를 이진데이터로 생각하여, 트라이의 각 레벨을 비트 수 단위로써 접근한다.

 

 

예를 들어, X의 6번째 값을 접근한다 하면, 6은 이진 표현시 (110)이므로,

 

1 (우측)

1 (우측)

0 (좌측)

==> X -> 1 -> 1 -> 0 = 8 로 접근 가능하다.

 

 

 

실제로는 위 예시 처럼, 2-way가 아니라 32-way 방식의 branching을 하는것이 가장 적합하다고 한다.

 

예를 들어, X[18977] 의 경우, 이진 표현 시,  (100101000100001)

즉, 데이터에 접근하기 위해서 15 레벨깊이를 움직여야하기 때문이다.

 

따라서, 1 비트 단위로 하나의 레벨을 나누는 것이 아닌, 5비트 단위 (32가지)로 레벨을 나눈다.

이 경우, 단 3번의 순회만에 목표 데이터에 접근할 수 있다.

 

 

Hash Array Mapped Trie(HAMT)

 

그럼 배열이 아닌 객체는 어떻게 다뤄야할까?

 

객체는 배열과 달리, 정수값을 key로 삼지 않는다.

 

생각보다 간단한 방법이 있는데, 키값을 해시하여, 해시된 문자열을 숫자로 치환시키면 된다.

 

이 후 과정은, 배열과 같다.