이 라이브러리는 Rust에서 유용하게 쓰이는 여러 불변(immutable) 자료구조를 구현합니다.
URL: https://docs.rs/im/latest/im/
Title: im - Rust
설명 확장
이 라이브러리는 Rust에서 더 흔히 유용하게 쓰이는 여러 불변 자료구조를 구현합니다.
불변 자료구조는 원본을 변경하지 않고도 효율적으로 복사하고 수정할 수 있는 자료구조입니다. 가장 단순한 예는 오래된 전통의 cons 리스트입니다. 이 크레이트는 비슷한 성질을 가지면서도 더 현대적이고 유연한 자료구조들을 Rust 개발자의 필요에 맞게 조정하여 제공합니다.
간단히 말해, 다음 자료구조들을 제공합니다:
불변 자료구조는 다른 프로그래밍 언어에서는 판도를 바꿀 만큼 강력할 수 있지만, 가장 눈에 띄는 장점인 “실수로 데이터를 변경(mutation)하는 것을 방지”하는 문제는 Rust의 타입 시스템이 워낙 잘 처리하기 때문에, 표준적으로는 Rust 프로그래머가 (성실한 Clojure 프로그래머라면 공황에 빠질 만한) 변경 가능한 자료구조를 사용하더라도 크게 걱정할 필요가 없습니다.
그럼에도 불변 자료구조는 다른 장점들을 제공하며, 그중 일부는 Rust 같은 언어에서도 유용합니다. 가장 두드러진 것은 _구조적 공유(structural sharing)_로, 두 자료구조가 대부분 서로의 복사본이라면 그들이 차지하는 메모리 대부분을 서로 공유한다는 뜻입니다. 이는 불변 자료구조의 복사가 저렴함을 의미합니다. 실제로는 포인터를 하나 복사하고 참조 카운터를 증가시키는 정도에 불과합니다. 반면 Vec의 경우 같은 크기의 메모리를 다시 할당하고 내부의 모든 원소를 복사해야 합니다. 불변 자료구조에서는 복사본이나 원본을 수정하기 전까지 추가 메모리를 할당하지 않으며, 수정이 일어나더라도 차이를 기록하는 데 필요한 만큼의 메모리만 추가로 사용합니다.
이 라이브러리의 또 다른 목표는, 최적화를 걱정해야 하는 시점이 오기 전까지(실제로는 그런 시점이 오지 않는 경우가 많습니다) “어떤 상황에 어떤 자료구조를 써야 하는지”를 굳이 깊게 생각하지 않아도 되게 하는 것입니다. 데이터의 형태(예: 리스트를 쓸지 맵을 쓸지)만 결정하면, 그 뒤로는 자료구조를 과하게 고민하지 않아도 괜찮아야 합니다. 알맞은 형태의 것을 고르면, 필요한 연산에 대해 수용 가능한 성능 특성을 제공해야 합니다. 특화된 자료구조는 자신이 특화된 작업에서 항상 더 빠르겠지만, im은 실수로 “잘못된 용도”로 사용했을 때의 위험이 가장 적은 자료구조들을 제공하는 것을 목표로 합니다.
예를 들어 Vec는 메모리 사용량, 인덱싱, 리스트의 뒤쪽에서 일어나는 연산에서 다른 무엇보다 뛰어나지만, 삽입과 삭제에는 매우 취약하며 리스트의 앞쪽에 가까울수록 더 나빠집니다. VecDeque는 약간의 복잡성을 추가하여 앞쪽 연산도 뒤쪽 연산만큼 효율적으로 만들지만, 여전히 삽입이 좋지 않고 특히 연결(concatenation)에 약합니다. Vector는 또 다른 복잡성을 더하며 Vec가 가장 잘하는 부분에서는 결코 따라잡을 수 없지만, 그 대가로 어떤 연산을 던져도 합리적인 시간 안에 완료할 수 있습니다. 보통 비싼 연산인 복사와 특히 연결도 Vector를 사용하면 비교적 저렴합니다.
다만 단순성 덕분에, Vec는 작은 크기에서는 Vector가 가장 강한 연산에서조차 이기는 경우가 많습니다. 현대 CPU는 연속된 메모리의 작은 덩어리를 복사하는 같은 작업에 극도로 최적화되어 있기 때문입니다. 실제로는 어느 정도 크기(보통 수백 개 원소 근처)를 넘어야 Vec가 항상 가장 빠른 선택이 아닌 지점에 도달합니다. Vector는 아주 작은 크기에서는 실제로 단순 배열로 동작하고, 충분히 커지면 전체 자료구조로 효율적으로 전환할 수 있게 해서 이를 보완합니다. 따라서 Vector는 단일 청크의 크기를 넘기 전까지는 Vec와 사실상 동등하게 동작합니다.
맵들—HashMap과 OrdMap—은 대체로 표준 라이브러리의 대응 자료구조와 비슷한 성능을 보이지만, 기본 연산에서는 다소 느리게 동작하는 경향이 있습니다(HashMap은 표준 대응물과 거의 비슷한 수준인 반면, OrdMap은 현재 보통 2~3배 느린 편입니다). 반면 불변 자료구조에서 기대할 수 있는 저렴한 복사와 복사본 간의 구조적 공유를 제공합니다.
결론적으로, 이 라이브러리의 목표는 가장 흔한 종류의 자료구조에 대해 안전한 기본 선택지를 제공하여, 최적화가 필요해질 때까지 “적합한 자료구조가 무엇인지”에 대한 깊은 고민을 미뤄둘 수 있게 하는 것입니다. 특히 더 큰 데이터 세트에서는, 불변 자료구조가 여전히 올바른 선택일 수 있음을 알게 될지도 모릅니다.
이 자료구조들에서는 공유된 노드를 업데이트하기 전에 복사해야 하므로, 그 안에 저장하는 값은 Clone을 구현해야 합니다. 숫자처럼 Copy를 구현하는 기본 타입 값의 경우에는 문제가 없습니다. 자료구조들은 이런 경우에 최적화되어 있으며 성능도 매우 좋습니다.
반면, 클로닝이 비싼 값이나 Clone을 구현하지 않는 값을 저장하고 싶다면, Rc나 Arc로 감싸야 합니다. 따라서 복잡한 구조체 BigBlobOfData가 있고 이를 Vector<BigBlobOfData>로 저장하고 싶다면, 대신 Vector<Rc<BigBlobOfData>>를 사용해야 합니다. 이렇게 하면 큰 데이터 덩어리를 클론하는 데 드는 시간뿐 아니라, 여러 복사본을 유지하는 데 드는 메모리도 절약할 수 있습니다. Rc는 참조 카운트 기반으로 단일 복사본을 공유하기 때문입니다.
Copy할 수 없는 더 작은 값을 저장하는 경우에는 판단이 필요합니다. 값의 클론 비용이 아주 작다면(짧은 String이나 작은 Vec처럼), Rc로 감싸지 않고 직접 저장하는 편이 더 나을 가능성이 큽니다. 이 값들은 Rc처럼 힙의 데이터에 대한 포인터에 불과하고, 그 데이터 자체도 클론 비용이 크지 않기 때문입니다. 오히려 Rc로 감싸는 추가 간접 참조 비용이 가끔 클론하는 비용보다 더 큰 성능 손실을 만들 수도 있습니다.
그렇다면 값은 실제로 언제 클론될까요? 쉬운 대답은 자료구조 자체를 clone할 때뿐이며, 그마저도 변경이 일어날 때까지 지연(lazy)된다는 것입니다. 값들은 자료구조 내부의 트리 노드에 저장되며, 각 노드는 최대 64개의 값을 담습니다. 자료구조를 clone해도 실제로는 아무것도 복사되지 않습니다. 루트 노드의 참조 카운트만 증가하여 두 자료구조가 이를 공유함을 나타낼 뿐입니다. 공유된 자료구조 중 하나를 실제로 수정할 때에만 노드들이 클론됩니다. 트리 어딘가에 변경을 가하면, 변경이 포함된 노드를 클론해야 하고, 그 부모 노드들도 이전 자식 대신 새 자식 노드를 가리키도록 업데이트되어야 하므로 함께 클론됩니다.
이를 “지연(lazy) 클로닝”이라고 부를 수 있습니다. 자료구조를 두 번 복사해 놓고 둘 다 변경하지 않는다면, 내부 데이터는 클론될 필요가 전혀 없습니다. 변경을 시작할 때만 클로닝이 발생하며, 그마저도 변경에 포함된 특정 트리 노드에서만 일어납니다. 지연 클로닝의 함의는 CPU에서 데이터 복사 작업량뿐 아니라 메모리 사용량에도 확장됩니다. 불변 자료구조를 클론하면 두 복사본은 변경을 시작할 때까지 동일하게 할당된 메모리를 공유합니다.
가장 중요한 점은, 자료구조를 전혀 클론하지 않는다면 그 안의 데이터도 전혀 클론되지 않는다는 것입니다. 이 경우 (공유 노드 여부를 검사해야 하므로 차이는 여전히 있지만) 최소한의 성능 차이만 있을 뿐 사실상 변경 가능한 자료구조처럼 동작합니다.
아래에서 사용 가능한 자료구조들에 대한 포괄적인 안내를 제공하려고 합니다.
“Big O 표기법”은 자료구조 연산의 시간 복잡도를 말하는 표준적인 방법입니다. Big O 표기법이 익숙하지 않다면, 빠른 치트시트는 다음과 같습니다:
_O(1)_은 연산이 상수 시간에 실행된다는 뜻입니다. 자료구조의 크기와 무관하게 같은 시간에 완료됩니다.
_O(n)_은 연산이 선형 시간에 실행된다는 뜻입니다. 자료구조 크기를 두 배로 늘리면 연산 시간도 두 배가 되고, 네 배로 늘리면 네 배가 되는 식입니다.
_O(log n)_은 연산이 로그 시간에 실행된다는 뜻입니다. log 2 기준으로는 자료구조 크기를 두 배로 늘릴 때마다 연산에 필요한 단계가 1단계씩 늘고, 네 배면 2단계 늘어나는 식입니다. 하지만 이 라이브러리의 자료구조들은 보통 log 64 시간에 가깝게 동작합니다. 즉, 자료구조를 64배 키워야 1단계가 늘고, 4096배 키워야 2단계가 늘어납니다. 따라서 여전히 O(log n)으로 분류되지만, 정말 큰 데이터 세트가 아니면 사실상 O(1)에 가까워서 보통은 체감하지 못합니다.
_O(n log n)_은 이 라이브러리에서 보게 될 가장 비싼 연산입니다. 자료구조의 _n_개 원소 각각에 대해 _log n_번의 연산이 필요하다는 의미입니다. 위에서 말했듯이 우리의 경우 종종 O(n)에 가깝지만, O(n)도 결코 싸지 않으며 데이터가 커질수록(느리지만) 로그적으로 비용이 증가합니다. O(n log n)은 기본적으로 “정말 이걸 해야 하나요?”라는 뜻입니다.
O(1)*는 ‘상각(amortised) O(1)’을 의미합니다. 즉 연산은 보통 상수 시간에 실행되지만 가끔 더 비싸질 수 있습니다. 예를 들어 Vector::push_back을 연속으로 호출하면 대부분 O(1)이지만, 64번째마다 꼬리(tail) 청크를 채우고 트리에 삽입해야 하므로 O(log n)이 됩니다. 참고로 별표가 붙은 O(1)은 일반적인 표기법은 아니며, 여기 문서에서 ‘상각’이라는 단어를 계속 타이핑하지 않기 위해 사용한 관례입니다.
리스트는 삽입한 순서를 유지하는 단일 원소들의 시퀀스입니다. 이 라이브러리에서 제공하는 유일한 리스트는 Vector이며, 전반적으로 가장 균형 잡힌 성능 특성을 제공합니다. 모든 면에서 꽤 좋지만, 특정 작업에서는 더 나은 다른 종류의 리스트가 항상 있을 수는 있습니다.
맵은 키에서 값으로의 매핑이며, 가장 흔한 읽기 연산은 주어진 키에 연관된 값을 찾는 것입니다. 맵은 정해진 순서를 가질 수도 있고 아닐 수도 있습니다. 어떤 키든 맵 내부에는 한 번만 존재할 수 있으며, 어떤 키에 다른 값을 설정하면 이전 값은 덮어써집니다.
| 타입 | 알고리즘 | 키 제약 | 순서 | Insert | Remove | Lookup |
|---|---|---|---|---|---|---|
HashMap<K, V> | HAMT | Clone + Hash + Eq | 정의되지 않음 | O(log n) | O(log n) | O(log n) |
OrdMap<K, V> | B-트리 | Clone + Ord | 정렬됨 | O(log n) | O(log n) | O(log n) |
세트는 중복 없는(unique) 값들의 컬렉션이며, 정해진 순서를 가질 수도 있고 아닐 수도 있습니다. 핵심 성질은 어떤 값이든 한 세트 안에는 한 번만 존재할 수 있다는 점입니다.
| 타입 | 알고리즘 | 제약 | 순서 | Insert | Remove | Lookup |
|---|---|---|---|---|---|---|
HashSet<A> | HAMT | Clone + Hash + Eq | 정의되지 않음 | O(log n) | O(log n) | O(log n) |
OrdSet<A> | B-트리 | Clone + Ord | 정렬됨 | O(log n) | O(log n) | O(log n) |
이 모든 자료구조는 제자리(copy-on-write) 변경을 지원합니다. 즉, 어떤 자료구조의 유일한 사용자라면, 수정 전에 자료구조를 복사하느라 성능 손실을 겪지 않고 제자리에서 업데이트할 수 있습니다(이는 불변 연산보다 대략 한 자릿수(10배 내외) 더 빠르며, std::collections의 변경 가능한 자료구조만큼 거의 빠릅니다).
Rc의 참조 카운팅 덕분에, 우리는 자료구조의 어떤 노드가 다른 자료구조와 공유되고 있는지, 아니면 제자리에서 안전하게 변경할 수 있는지를 판별할 수 있습니다. 공유되고 있다면, 수정하기 전에 자동으로 노드를 복사합니다. 그 결과, 자료구조의 클로닝은 지연(lazy) 연산이 됩니다. 초기 클론은 즉시 끝나고, 클론된 자료구조를 수정하는 과정에서 변경된 부분에서만 청크를 클론하게 됩니다. 따라서 전체를 모두 바꾸면 결국 전체 클론과 같은 작업을 수행하게 됩니다.
이는 추가 최적화도 몇 가지 ‘공짜로’ 제공합니다. 다른 언어에서의 불변 자료구조 구현은 종종 Clojure의 transient나 Haskell의 ST 모나드처럼 로컬 변경(local mutation) 개념을 갖습니다. 즉, 관리되는 스코프 안에서 불변 자료구조를 변경 가능한 것처럼 다루어, 매 연산마다 변경된 노드를 복사하지 않고 “공유 구조를 가진 노드에 처음 도달했을 때만” 복사함으로써 상당한 성능 향상을 얻습니다. Rust에서는 이런 관리 스코프를 굳이 고민할 필요가 없습니다. 우리에게는 가비지 컬렉터에 대한 저수준 접근(여기서는 단순한 Rc)이 있기 때문에, 모든 것이 뒤에서 자동으로 처리됩니다.
im 크레이트의 자료구조들은 Arc를 통해 스레드 안전합니다. 이는 약간의 성능 영향을 동반하므로, 스레드 안전성보다 속도를 우선한다면 대신 im-rc 크레이트를 사용할 수 있습니다. 이는 im과 동일하지만 Arc 대신 Rc를 사용합니다. 따라서 im-rc의 자료구조들은 Send 및 Sync를 구현하지 않습니다. 그 결과 전반 성능이 대략 20~25% 향상됩니다.
im은 Cargo 기능 플래그를 통해 다음 크레이트들에 대한 선택적 지원을 제공합니다. Cargo.toml에서 다음처럼 활성화할 수 있습니다:
[dependencies]
im = { version = "*", features = ["proptest", "serde"] }
| 기능 | 설명 |
|---|---|
pool | refpool 메모리 풀을 위한 생성자와 풀 타입(im-rc에서만 사용 가능) |
proptest | proptest 네임스페이스 아래 모든 im 데이터 타입에 대한 전략 제공(예: im::vector::proptest::vector()) |
quickcheck | 모든 im 데이터 타입에 대한 quickcheck::Arbitrary 구현(im-rc에서는 사용 불가) |
rayon | Vector를 위한 병렬 이터레이터 구현(im-rc에서는 사용 불가) |
serde | 모든 im 데이터 타입에 대한 Serialize 및 Deserialize 구현 |
arbitrary | 모든 im 데이터 타입에 대한 arbitrary::Arbitrary 구현 |
hashmap정의되지 않은(unordered) 맵. hashset정의되지 않은(unordered) 세트. iter불변 데이터에 대한 이터레이터. ordmap정렬된(ordered) 맵. ordset정렬된(ordered) 세트. proptestProptest 전략. vector퍼시스턴트 벡터. get_in여러 단계의 자료구조 안에서 값을 가져옵니다. hashmap키/값 쌍 시퀀스로부터 해시 맵을 생성합니다. hashset값 시퀀스로부터 세트를 생성합니다. ordmap키/값 쌍 시퀀스로부터 맵을 생성합니다. ordset값 시퀀스로부터 세트를 생성합니다. update_ in여러 단계의 자료구조 안에 있는 값을 업데이트합니다. vector원소 시퀀스로부터 벡터를 생성합니다. HashMap정의되지 않은(unordered) 맵. HashSet정의되지 않은(unordered) 세트. OrdMap정렬된(ordered) 맵. OrdSet정렬된(ordered) 세트. Vector퍼시스턴트 벡터.