Rust Vec의 growth strategy (feat. Java)

오늘은 Rust의 Vec가 가지는 growth strategy에 대하여 알아보겠습니다.

growth strategy 이란?

초기 용량인 capactiy을 오버한 경우, 증가시키는 방법입니다.

capacity이란?

현재 컬렉션이 가지고 있는 size가 아닌, 미리 확보한 용량을 의미합니다.

 

언어별 및 자료구조별로 growth strategy를 하는 방식이 다양합니다.

 

Java의 ArrayList는 1.5배입니다.

 

예를 들어

import java.lang.reflect.Field;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws Exception {
        ArrayList<Integer> list = new ArrayList<>();

        // capacity 출력
        // 10
        System.out.println("capacity: " + getCapacity(list));

        // 값 추가	
	    for(int i = 0; i < 11; i++) {
    		list.add(i);
    	}

        //15
        System.out.println("capacity: " + getCapacity(list));
    }

    private static int getCapacity(ArrayList<?> list) throws Exception {
        Field field = ArrayList.class.getDeclaredField("elementData");
        field.setAccessible(true);
        Object[] elementData = (Object[]) field.get(list);
        return elementData.length;
    }
}

Java의 ArrayList는 초기 capacity를 0으로 지정했고, 값을 1개라도 넣은 경우 10이 되고, 11개의 값을 넣으니 15의 capacity 값을 출력합니다.

그러면 Rust는?

이 블로그의 주제인 Rust의 Vec방식에 대하여 이야기해보고자 합니다.

 

처음에는 '초기 용량은 정해져 있고, 당연히 1.5배나 2배겠지?'라고 생각했으나... 보고 놀랐습니다.

Vec 초기 용량은?

Rust의 내부 코드를 보면 다음과 같은 함수가 존재합니다.

// Tiny Vecs are dumb. Skip to:
// - 8 if the element size is 1, because any heap allocator is likely
//   to round up a request of less than 8 bytes to at least 8 bytes.
// - 4 if elements are moderate-sized (<= 1 KiB).
// - 1 otherwise, to avoid wasting too much space for very short Vecs.
const fn min_non_zero_cap(size: usize) -> usize {
    if size == 1 {
        8
    } else if size <= 1024 {
        4
    } else {
        1
    }
}

해당 코드는 무려 타입에 따른 초기 용량 설정입니다.

#[cfg(not(no_global_oom_handling))]
pub(crate) const MIN_NON_ZERO_CAP: usize = min_non_zero_cap(size_of::<T>());

다음과 같이 초기 용량을 설정할때 size_of::<T>()를 인자값으로 줘서, capacity 용량을 설정합니다.

 

예를 들어, 다음과 같이 타입별로 설정됩니다.

// u8은 8
Vec<u8>

//i32는 4
Vec<i32>

// [u8; 2048]은 1
Vec<[u8; 2048]>

그러면 Rust Vec의 growth strategy는?

Rust에는 다음과 같은 함수가 존재합니다.

/// # Safety
/// - `elem_layout` must be valid for `self`, i.e. it must be the same `elem_layout` used to
///   initially construct `self`
/// - `elem_layout`'s size must be a multiple of its alignment
/// - The sum of `len` and `additional` must be greater than the current capacity
unsafe fn grow_amortized(
    &mut self,
    len: usize,
    additional: usize,
    elem_layout: Layout,
) -> Result<(), TryReserveError> {
    // This is ensured by the calling contexts.
    debug_assert!(additional > 0);

    if elem_layout.size() == 0 {
        // Since we return a capacity of `usize::MAX` when `elem_size` is
        // 0, getting to here necessarily means the `RawVec` is overfull.
        return Err(CapacityOverflow.into());
    }

    // Nothing we can really do about these checks, sadly.
    let required_cap = len.checked_add(additional).ok_or(CapacityOverflow)?;

    // This guarantees exponential growth. The doubling cannot overflow
    // because `cap <= isize::MAX` and the type of `cap` is `usize`.
    let cap = cmp::max(self.cap.as_inner() * 2, required_cap);
    let cap = cmp::max(min_non_zero_cap(elem_layout.size()), cap);

    // SAFETY:
    // - cap >= len + additional
    // - other preconditions passed to caller
    let ptr = unsafe { self.finish_grow(cap, elem_layout)? };

    // SAFETY: `finish_grow` would have failed if `cap > isize::MAX`
    unsafe { self.set_ptr_and_cap(ptr, cap) };
    Ok(())
}

하나하나 코드별로 설명을 하면 다음과 같다

// len + additional > capacity일 경우에만 호출
unsafe fn grow_amortized(
    &mut self,
    len: usize,
    additional: usize,
    elem_layout: Layout,
) -> Result<(), TryReserveError> {
    // 반드시 1개 이상의 값을 추가할려는 상황인지 체크
    debug_assert!(additional > 0);

    if elem_layout.size() == 0 {
        // 타입의 크기가 0이라면, 더 늘릴 수 없으므로 error
        return Err(CapacityOverflow.into());
    }

    // 현재 필요한 capacity 구하기
    // overflow 나면 에러 반환
    let required_cap = len.checked_add(additional).ok_or(CapacityOverflow)?;

    // max(기존 capacity의 2배, 필요한 capacity)
    let cap = cmp::max(self.cap.as_inner() * 2, required_cap);

    // max(기본 capacity사이즈, cap)
    let cap = cmp::max(min_non_zero_cap(elem_layout.size()), cap);

    // capacity 증가 로직 수행
    let ptr = unsafe { self.finish_grow(cap, elem_layout)? };

    // 내부 상태 업데이트
    unsafe { self.set_ptr_and_cap(ptr, cap) };
    Ok(())
}

코드 없이 설명을 한다면,

1. 1개의 값 추가
2. 현재 capacity의 값이 size보다 작은 경우 grow capacity 로직 수행
3. 새로운 capacity를 max(자료구조 최소 capacity, max(현재 capacity + 추가할 데이터 개수, 현재 capacity * 2));
4. 새로운 capacity로 증가 로직 수행

그렇다면 여기서 의문점이 하나 발생합니다.

 

cmp::max(self.cap.as_inner() * 2, required_cap);에서 required_cap이 선택되는 상황이 나올까?

 

Vec의 함수중에 reserve라는 함수가 존재합니다.

 

reserve는 현재 자료구조에 인자로 받은 값만큼 현재 size + capacity의 값을 증가시킵니다.

fn main() {
    let mut vec : Vec<u8> = Vec::new();

    vec.push(1);
    vec.push(1);

    //8
    println!("{}", vec.capacity());

    vec.reserve(1000);

    //1002
    println!("{}", vec.capacity());
}

reserve를 사용하면, cmp::max(self.cap.as_inner() * 2, required_cap);의 값이 max(2 * 2, 2 + 1000)과 같이 수행하게 되어, capacity의 값은 1002가 됩니다.

 

Rust를 공부하면서, capacity에 대해 알아보다가 해당 내용을 알게 되어 작성하게 되었습니다.

 

어떤 언어인지, 어떤 자료구조인지에 따라서 capacity 초기 용량 및 증가시키는 방법이 다른데, 해당 부분에 대하여 알고 사용하면 더욱 좋을거 같습니다.

 

개발을 진행하던 도중, capacity로 인하여 heap memory error가 발생한 적이 있고, 자료구조를 변경하여 해당 문제를 해결한 경험이 있습니다.