개발 노트 custum array (2) 2018/02/24 11:19 by cagetu

allocator 및 array 구현 중에 고민이 되는 점들..

1. Array 늘어나는 크기를 얼마로 할 것인가???

적절한 Array 사이즈를 잡을 때, 생각해야 할 점은 대략 2가지로 예상해볼 수 있다.
  • 너무 잦은 메모리 재할당을 피해야 한다.
  • 불필요하게 많은 메모리를 할당하지 않는다.
stl::vector는 2의 승수로 증가한다고 알려져 있다. 하지만, 2배씩 증가하면 초반에는 재할당 빈도수가 높을 수 있고, Array가 커질수록 불필요하게 할당하는 메모리가 많아질 수가 있다. 그렇다면 어떻게 해야 할까?

대략 다음과 같은 전략이 있다고 보여진다.
  • N배씩 선형적으로 증가.
  • N개씩 선형적으로 증가.
  • 비선형적으로 증가 시킨다. (보정값 적용) 
UE4를 보면 다음과 같이 구현되어 있다. (Reserve에 대해서는 약간 다른 전략인 듯)
FORCEINLINE int32 DefaultCalculateSlackGrow(int32 NumElements, int32 NumAllocatedElements, SIZE_T BytesPerElement, bool bAllowQuantize, uint32 Alignment = DEFAULT_ALIGNMENT)
{
       int32 Retval;
       checkSlow(NumElements > NumAllocatedElements && NumElements > 0);
       SIZE_T Grow = 4; // this is the amount for the first alloc
       if (NumAllocatedElements || SIZE_T(NumElements) > Grow)
       {
              // Allocate slack for the array proportional to its size.
              Grow = SIZE_T(NumElements) + 3 * SIZE_T(NumElements) / 8 + 16;
       }
       if (bAllowQuantize)
       {
              Retval = FMemory::QuantizeSize(Grow * BytesPerElement, Alignment) / BytesPerElement;
       }
       else
       {
              Retval = Grow;
       }
       // NumElements and MaxElements are stored in 32 bit signed integers so we must be careful not to overflow here.
       if (NumElements > Retval)
       {
              Retval = MAX_int32;
       }
       return Retval;
}

처음에는 4개가 증가하고, 다음부터는 16개 + @ 형태로 증가 하는 것을 볼 수 있다. 커질수록 조금 더 가중치로 더 할당해주는 형태로 보인다.

다음은 FBVector의 내용이다. 

1) 초기값은 최소 64byte가 넘도록 설정한다.
2) 너무 크거나 작은 백터에 대해서는 2x씩 증가시킨다. (경험상 그렇다고 한다.)
3) 중간 크기의 버퍼는 1.5x 씩 증가시킨다.

size_type computePushBackCapacity() const {
if (capacity() == 0) {
return std::max(64 / sizeof(T), size_type(1));
}
if (capacity() < folly::jemallocMinInPlaceExpandable / sizeof(T)) {
return capacity() * 2;
}
if (capacity() > 4096 * 32 / sizeof(T)) {
return capacity() * 2;
}
return (capacity() * 3 + 1) / 2;
}

찾아보니 다양한 의견이 많은데, 2^K 선형적으로 증가할 때 K=1.5 vs K=2에 대한 이야기도 찾아볼 수 있었다.
개인적으로는 그냥 N개씩 증가하는 방법도 나쁘지 않다고 생각이 들고, 1.5 승수로 증가하는 방법도 괜찮아보인다. 아니면, 일정 크기까지는 N개씩 증가하다가 1.5승으로 가는 식이어도 좋을까? 라는 생각도 들고... 아직 조금 더 읽어보고 판단해야 할 것 같다. 

게임으로 생각했을 때, 처음 할당할 때에는 굳이 fbvector처럼 64byte로 맞추는 것보다그냥 ue4나 다른 custom vector 처럼 초기 개수를 정해주는 것이 나을 것 같다 (4개 혹은 8개). 다음 증가치에 대해서는 둘다 비슷할 것 같은데, 일단 개수 기반으로 하는 UE4 형태가 더 직관적이어서 사용해보기로 한다.
(증가 폭을 그래프로 만들어보니, 이런 느낌이다. 초반에는 아무래도 초기값을 넣어주는 것이 빈번한 재할당을 줄이는데 도움이 되는 것 같고, 어느 정도 커지는 시점에서는 2배수로 커지게 불필요하게 증가폭이 너무 클 수 있음을 볼 수 있다. ue4 형태가 꽤 적절해 보인다. 혹은 1.5x 정도...)

재밌는 주제다... 10년 넘게 그냥 쓰기만 했는데, 이제서 이런 생각을 해보게 되다니.. 부끄럽다... 


핑백

덧글

댓글 입력 영역



메모장

내가 먼 훗날에 이 글들을 보았을 때, 좋은 추억이 될 수 있기를...

나를 위해... 나에게 쓰는...

msn: cagetu@hotmail.com
mail: cagetu79@gmail.com
twitter: twitter.com/cagetu
facebook: facebook.com/cagetu