[책] 데이터 지향 프로그래밍 - 9장 영속 자료구조

 DOP에서 데이터는 불변이다. 데이터를 직접 변경할 수 없고 필요하다면 새로운 버전의 데이터를 만들어야 한다. 이런 방식에서 우려되는 점은 크게 2가지, 안정성과 효율성이다. 어디서도 데이터를 변경할 수 없음을 보장할 수 있을까? 매번 새로운 버전의 데이터를 만들어야 한다면 성능적인 문제는 없는 걸까? 이번 장에서는 이 2가지에 대한 해답을 제시한다.

 

 

 

영속 자료구조로 안정성을 보장하는 방식

---

 안정성을 보장하는 방식은 사실 간단하다. 수정 메서드를 사용할 경우 예외를 발생시키면 된다. 예를 들어 Java에서 불변 Collection에 데이터를 수정하려 하면 UnsupportedOperationException을 발생시킨다. Javascript의 경우 Object.freeze를 사용하면 동일한 효과를 얻을 수 있다. 다만, 변경을 시도할 때 오류가 발생하냐 마냐는 strict/sloppy mode에 따라 다르다. 하지만 어떤 경우이든 데이터가 변경되지는 않으니 큰 문제는 아니다.

 

 

 

영속 자료구조로 효율성을 보장하는 방식

---

 영속 자료구조를 사용할 경우 효율성은 정말 큰 문제이다. 예를 들어 10만개 요소를 포함한 리스트에 요소 1개를 추가한다고 해보자. 영산의 경우 리스트를 생성하고 요소 10만개 하고도 1개를 추가해야 한다. 또한 업데이트마다 사용 메모리가 크게 증가할 것이다.

 

 

 

 

 효율성을 보장하기 위한 핵심 아이디어는 위 사진과 같다. 예를 들어 10만개의 리스트를 단일 리스트로 보관하는 게 아니라 4개의 리스트 조합으로 구성한다면 어떨까? 만약 단일 리스트로 보관할 경우 75,100번째 요소를 변경하여 새로운 버전의 리스트를 생성해야 한다면 10만번의 연산이 필요할 것이다. 하지만 리스트가 4개로 쪼개져 있다면? 리스트 1 공유 연산 1회 / 리스트2.1 공유 연산 1회 / 75,000 ~ 99,999 요소 복제 및 생성 연산 25,000회로 총 25,002회 연산으로 줄어든다. 이 효율성은 데이터 수정 뿐만 아니라 조회에서도 동일하게 적용된다.

 

 리스트의 크기가 2가 될 때까지 쪼개면 데이터 조회/수정에 필요한 연산은 log₂N이 된다. 10만 개를 가정하면 16.6이다. 여기서 더 나아가 2개씩 쪼개지 말고 32개씩 쪼갠다면 log₃₂N가 되고 필요한 연산은 3.3이 된다. 오 그러면 가지 수를 늘리면 되겠다!라  생각할 수 있겠지만 32개의 분기로 갈라진다면 복제해야 하는 요소의 수가 크게 늘어난다. 하지만 현대의 CPU 아키텍처에서 캐시 라인은 대개 32바이트나 64바이트 길이이다. 현대 CPU 아키텍처의 데이터 접근 패턴을 고려하면 크기가 2인 배열 16개를 복제하는 것보다 크기가 32인 배열을 복제하는 것이 빠르다는 결론에 이른다. 이를 실제 메모리 접근 패턴으로 살펴보면 아래와 같다.

 

 

1. 크기가 2인 배열 16개를 복제하는 경우

// 메모리 상의 위치가 흩어져 있는 작은 배열들
위치1: [10, 20]         // 캐시 미스 #1
위치2: [30, 40]         // 캐시 미스 #2
위치3: [50, 60]         // 캐시 미스 #3
...
위치16: [310, 320]      // 캐시 미스 #16

 각 배열은 다른 메모리 위치에 저장되고 각 배열에 접근할 때마다 새로운 캐시 라인을 로드해야 한다. 결과적으로 16번의 캐시 미스 발생이 가능하다.

 

2. 크기가 32인 배열 하나를 복제하는 경우

// 연속된 메모리 공간에 있는 하나의 큰 배열
[10, 20, 30, 40, 50, ..., 320]  // 캐시 미스 #1

 모든 데이터가 연속된 메모리 공간에 저장되며 한 번의 캐시 라인 로드로 모든 데이터에 접근이 가능하다. 결과적으로 1번의 캐시 미스만 발생한다.

 

 이처럼 CPU 캐시의 특성상, 메모리에서 데이터를 가져올 때 연속된 메모리 공간에서 한 번에 가져오는 것이 여러 번 나누어 가져오는 것보다 훨씬 효율적이다. 때문에 이론과 다르게 현실에서 크기가 2인 배열을 사용하는 것보다 32인 배열을 사용하는 것이 성능상 유리한 이유이다.

 

 

결론적으로 DOP는 영속 자료구조를 사용한다. 영속 자료구조는 불변 컬렉션과 다르게 어디서도 값이 변경되지 않도록 안정성을 보장하며, 차기 버전을 효율적으로 만들 수 있는 로직을 포함한다. 때문에 안전하게 데이터를 불변으로 다루면서도 효율적으로 차기 버전을 계산할 수 있게 된다.