들어가며

이제 러스트를 사용한지 8개월 정도가 되가는 러스트 뉴비입니다. 러스트를 사용하면서 조금 더 효율적으로 러스트를 사용하고 싶어서 data structure에 대해 이것저것 찾아본 점이 많았는데 정리를 해두지 않으면 잊어버리기 쉬어서 이렇게 글로 남기려고 합니다. 물론 수요가 없는 공급이겠지만 배운 점은 항상 다른 사람과 나누라는 좋은 말이 있듯이 미래에 누군가를 위하여 간단히 정리해두려고 합니다. Rust official book에 개념들을 설명이 매우 잘되어있어서 이 시리즈에서는 개념적인 설명보다는 잡기술? 혹은 연관된 개념들? 쪽으로 글을 작성하려고 합니다~

이번 편은 Vec에 대하여 입니다.

Vec이란?

Rust 에서 Vec이란 "re-sizable arrays" 라고 정의되어 있습니다. 즉, slice처럼 compile 타임에 사이즈는 모르는 상태지만 slice와는 다르게 사이즈가 유동적으로 변할수 있다는 특징을 가지고 있습니다. 그렇기 때문에 당연하게도 vec은 heap 에 저장됩니다. Vec은 다음과 같은 세 가지 parameter로 표현이 가능합니다

1. capacity: vec의 사이즈는 유동적으로 변할수 있기에 현재 heap memory 에 할당해놓은 사이즈입니다.
2. len: 실제로 vec에 들어가있는 object의 len 입니다.
3. ptr: Vec이 차지하고 있는 heap memory 의 시작점을 나타내는 포인터입니다.

https://doc.rust-lang.org/src/alloc/vec/mod.rs.html#293-304

자 그렇다면 Vec이 원래 capacity 10을 가지고 있고 len 5인 상황에서 6개 item을 추가하게 될 경우 어떻게 될까요? 네... 안타깝게도 capacity 가 20(원래 capacity 의 두배를 default로 가집니다) 인 새로운 메모리 영역에다가 원래 item 5개를 copy 해서 넣고 새로운 6개의 item도 추가합니다. 여기까지만 읽었을때에는 원래 item 5개의 item만 copy한거라서 큰 비효율성이 없어 보일수도 있습니다. 그러나 다음과 같은 코드가 있다고 가정해보죠.

let mut my_list = vec![];
for a in 0..10000 {
  my_list.push(a);
}

이 코드에서는 무슨 일이 발생할까요? 먼저 my_list가 기본으로 T1 의 capacity 를 가지고 있다고 가정한다면 a > T1이 되는 시점에 my_list는 capacity를 T2 = 2 * T1 로 증가시키고 원래 있던 item 들을 memory copy 하게 됩니다. 즉, 매번 my_list의 capacity 가 차는 순간 불필요한 memory copy 가 발생하게 됩니다. 이는 매우 비효율적이죠. 원래 vec 자체가 길이가 정해지지 않은 item들을 저장하기 위해서 있는 data structure 이기 때문에 어쩔수 없는 문제이기는 합니다. 다만 만약 위의 예시처럼 길이를 미리 알수 있다면 이야기가 달라집니다.

let mut my_list = Vec::with_capacity(10000); 
for a in 0..10000 {
  my_list.push(a);
}

이 방식으로 처음에 my_list 를 initialize할때 with_capacity()로 필요한 메모리 공간을 미리 만들어놓게 되면 더 이상 dynamic 하게 추가 메모리 공간을 찾을 필요가 없습니다. 즉, 불필요한 mem copy 가 없다는 뜻이죠!

Vec의 효율성

• 제가 아래에 array와 vec을 혼용해서 사용했는데 양해 부탁드립니다.

Data structure 를 공부하면서 binary tree, linkedlist등 다양한 자료 구조를 을 접하게 되면 모르게 array는 다른 자료 구조들에 비해 비효율적이라는 생각을 하기 쉽습니다. 실제로 어떤 경우에서는 array가 다른 자료 구조들에 비해 비효율적이기도 하고요. 그러나 array 의 특징을 잘 이용하면 몇몇 자료구조들은 array로 구현을 하는게 tree나 linkedlist 보다 더 효율적일수도 있습니다.

이해를 돕기 위해 현업에서 자주 사용되는 priority queue를 한번 살펴보죠. 여러분들도 알다시피 priority queue는 일반 queue와는 다르게 element 사이에 우선순위가 있는 data structure 입니다. 즉, 우선순위가 높은 element 가 우선순위가 낮은 element 전에 serve 되기 마련이죠.

Priority queue를 만드는 방법은 여러가지가 있지만 그 중 가장 많이 사용되는게 max heap 인데 이 max heap 은 대부분의 언어에서 array로 구현이 됩니다. 이상하다구요? 네. 위 그림처럼 max heap은 complete binary tree의 성질을 가지고 있습니다. 그런데 왜 tree가 아니라 array 로 구현이 될까요? 이는 다음과 같은 이유 때문입니다.

1. complete binary tree 는 간단하게 array 로 표현이 가능합니다.

   // assume i_th node in the heap has value A[i], then following stands 
   // parent of i_th node = A[i/2]
   // left child of i_th node = A[2i]
   // right chile of i_th node = A[2i + 1]

2. tree는 포인터를 들고 있습니다. 즉, 각 node에 data값과는 별개로 pointer가 존재하는데 이 pointer또한 메모리를 차지합니다. 즉, array는 필요없는 pointer가 있으므로 총 N(# of elements) * S(size of a pointer)의 추가 메모리가 필요합니다.

3. array에서 cpu cache 에서의 효율성이 더 뛰어나기 때문입니다. cpu cache에 대해서 공부를 해보신 분들은 L1, L2, L3 캐싱에 대해 들어보셨을겁니다. array의 경우 메모리가 연속적으로 할당되어있는 구조인 반면 tree는 포인터를 들고 있기 때문에 메모리의 연속성을 보장하지 않습니다. 즉 array 의 경우 첫번째 item 을 가져온다는것은 매우 높은 확률로 캐시에 array전체가 있을 확률이 높습니다. 즉, 첫번쨰 item을 가져온순간 두번째 item 혹은 N 번째 item을 가져올때에는 캐시에서 바로 가져올수 있다는 뜻이죠. 이에 비해 tree는 포인터로 다음 item의 위치를 들고 있기 때문에 첫번째 item 을 가져와도 다음 item 들을 가져고기 위해서는 해당 포인터를 통해 메모리에서 다음 item을 찾아서 가져와야 합니다.. 즉, array는 memory가 연속적이라는 특징을 가지고 있기 때문에 이런 cpu cache를 효율적으로 사용할수 있습니다.

마치면서

이번글을 통해 vec의 특성에 대해 알아보았습니다. 혹시나 글에 틀린 부분이 있다면 pandawithcat@gmail.com으로 연락주시면 감사하겠습니다~

References

https://stackoverflow.com/questions/40792801/best-way-to-concatenate-vectors-in-rust

https://stackoverflow.com/questions/12065774/why-does-cache-locality-matter-for-array-performance

https://www.geeksforgeeks.org/priority-queue-set-1-introduction/