트랜지언트 데이터 구조
트랜지언트 데이터 구조 (Transient Data Structures)
근거 (Rationale)
나무가 숲에서 쓰러지면 소리가 날까? +
순수 함수가 불변 반환 값을 만들기 위해 어떤 지역 데이터를 변경(mutate)한다면, 괜찮은 걸까?
재미있는 질문이에요. Clojure 데이터 구조는 예를 들어 assoc를 호출할 때마다 변경을 사용해요 — 하나 이상의 배열을 만들고 그것들을 변경한 다음, 이후 불변으로 사용할 수 있게 반환해요. 그 이유는 성능이에요 — 순수 함수와 불변 데이터만으로는 그만큼 빠를 수가 없거든요. 하지만 일단 만들어지고 공유되면, 불변이자 영속적인 것(persistent)은 견고한 프로그램에 필수예요. Clojure가 내부적으로 변경하는 것들은 작고 새로 할당된 배열들인데, 그것들이 데이터 구조의 내부 노드를 구성해요. 아무도 그 배열들을 보지 못해요.
비슷한 시나리오가 더 높은 수준에서도 생겨요 — 큰 영속 데이터 구조를 여러 단계로 초기화하거나 변환하고 싶은데, 그중 어떤 것도 변환/구성하는 코드 외에는 어떤 코드에도 보이지 않아야 해요. 여기서의 난제는 변환의 소스가 기존 영속 데이터 구조이고, 함수의 결과 는 공유된다는 점이에요. 전통적인 변경 가능한(mutable) 데이터 구조로 복사하고 다시 복사하는 것은 O(n) 복사가 포함되고, 내부 코드는 나머지 Clojure 코드와 달리 명령형 난장판이 돼요. 게다가 특히 작업을 수행하기 위해 헬퍼 함수를 호출해야 한다면, 변경 가능한 데이터 구조를 실수로 공유하거나 별칭(alias)을 만드는 것을 막는 보호 장치도 없어요. 한마디로, 이런 코드 조각을 빠르게 하려고 Clojure의 모델을 떠나야만 한다면 유감스러운 일이에요. 트랜지언트(transient) 데이터 구조는 이 최적화 문제에 대한 해결책으로, Clojure 모델과 통합되고 Clojure에서 기대하는 것과 같은 스레드 안전성 보장을 제공해요.
본문
그것들은 어떻게 동작하나 (How they work)
트랜지언트 데이터 구조는 항상 기존 영속 Clojure 데이터 구조에서 만들어져요. Clojure 1.1.0부터 벡터, 해시맵, 해시집합이 지원돼요. 모든 Clojure 데이터 구조가 이 기능을 지원하는 것은 아니지만 대부분은 지원할 거라는 점에 주의하세요. 리스트는 이점이 없어서 지원하지 않아요.
데이터 구조의 트랜지언트 '복사본'은 transient를 호출해 얻어요. 이것은 소스의 복사본이고 같은 성능 특성을 가진 새 트랜지언트 데이터 구조를 만들어요. 사실 대부분 이 소스 데이터 구조이고, 트랜지언트의 첫 번째 특징을 보여줘요 — 만드는 것이 O(1)이라는 점이에요. 영속 복사본이 구조를 공유하듯이, 소스와 구조를 공유해요.
트랜지언트의 두 번째 특징은, 만들 때 소스를 수정하지 않고 소스가 트랜지언트 사용을 통해 수정될 수 없다는 점이에요. 소스 데이터는 언제나처럼 불변이고 영속적이에요.
트랜지언트는 소스의 읽기 전용 인터페이스를 지원해요. 즉 영속 벡터처럼 트랜지언트 벡터에서 nth, get, count를 호출하고 함수 호출(fn-call)할 수 있어요.
트랜지언트는 소스 데이터 구조의 영속 인터페이스를 지원하지 않아요. assoc, conj 등은 모두 예외를 던지는데, 트랜지언트는 영속적이지 않기 때문이에요. 따라서 영속을 요구하는 맥락에 트랜지언트를 실수로 흘려보낼 수 없어요.
트랜지언트는 이름이 같고 *!*가 붙는 병렬적인 '변경' 연산 집합(assoc!, conj! 등)을 지원해요. 이것들은 영속 대응물과 같은 일을 하지만, 반환 값이 그 자체로 트랜지언트라는 점이 달라요. 특히 트랜지언트는 제자리(in-place)에서 때려 넣는(bash) 용도로 설계되지 않았어요. 반환 값을 잡아서 다음 호출에서 사용해야 해요. 이렇게 해서, 대체하는 함수형 영속 코드와 같은 코드 구조를 지원해요. 예시에서 보듯이, 이렇게 하면 구조 변경 없이 코드 조각의 성능을 쉽게 향상시킬 수 있어요.
결과를 구축하는 일을 마쳤으면 트랜지언트에 *persistent!*를 호출해 영속 데이터 구조를 만들 수 있어요. 이 연산도 O(1)이에요. persistent! 호출 이후에는 트랜지언트를 사용해서는 안 되며, 모든 연산이 예외를 던져요. 만들었을지도 모를 어떤 별칭에도 마찬가지예요.
예시 (Example)
매우 전형적인 예시로, 반환용 벡터를 구축하는 코드로 모든 '변경'이 함수에 지역적인 경우예요. 트랜지언트를 쓰는 버전이 정확히 같은 구조를 가진다는 점에 주목하세요. 그냥:
- 소스 벡터에 transient를 호출하고
- conj 대신 *conj!*를 사용하며
- 반환 시 *persistent!*를 호출해요
(defn vrange [n]
(loop [i 0 v []]
(if (< i n)
(recur (inc i) (conj v i))
v)))
(defn vrange2 [n]
(loop [i 0 v (transient [])]
(if (< i n)
(recur (inc i) (conj! v i))
(persistent! v))))
;; benchmarked (Java 25, Clojure 1.12)
(def v (vrange 1000000)) ;; 8.4 ms
(def v2 (vrange2 1000000)) ;; 5.5 ms
아, 그래요, 트랜지언트는 빠릅니다!
동시 사용 (Concurrent use)
트랜지언트 사용은 여기까지인데, 중요한 제약이 하나 더 있어요: 트랜지언트는 스레드 격리(thread isolation)를 요구해요. 트랜지언트 연산의 각 결과가 이전 결과와 (변경 가능한) 구조를 공유하므로, 한 번에 두 개 이상의 스레드가 트랜지언트를 조작하는 것은 오류예요. 특정 트랜지언트 인스턴스의 사용은 단일 스레드 범위에서 사용하거나, 이를 강제하는 프레임워크에서 사용함으로써 통제해야 해요.
Clojure 1.6 이하에서는 트랜지언트가 그것을 만든 스레드가 아닌 다른 스레드로부터의 (읽기든 쓰기든) 사용을 감지하면 예외를 던졌어요. 그 검사는 단일 스레드 제약을 다른 수단으로 강제하는 core.async go 블록 같은 프레임워크에서 더 유연하게 사용할 수 있도록 1.7에서 제거됐어요.
요약 (Summary)
트랜지언트는 Clojure의 데이터 구조와 함께 동작하고 중요한 안전성 보장을 제공하는, 함수형 데이터-구조-구축 코드의 고성능 최적화를 제공해요.
- 단일 경로 사용
- 영속 데이터 구조에서 O(1) 생성
- 영속 소스와 구조 공유
- 편집 세션이 끝났을 때 영속 데이터 구조를 O(1)로 생성
- 함수형 버전과 같은 코드 구조 ** 반환 값을 잡아서 다음 호출에 사용 ** 제자리에서 때려 넣지 않기 ** 영속적이지 않으므로 중간 값을 붙잡거나 별칭을 만들 수 없음
- 영속 버전을 반환한 후에는 사용할 수 없음
- 빠름
트랜지언트 영속 벡터, 해시맵, 해시집합은 Clojure 1.1에서 추가됐어요.