작은 메모리 할당을 빨리하려면?

요즘 생각하는 문제 중 하나는 작은 메모리 영역, 대략 16 bytes ~ 64bytes 정도의 영역을 엄청나게 자주, 그리고 길지 않은 시간동안 할당하고 해제하는 작업이다. 물론 멀티스레딩 환경에서 해야하는 작업이라, 여러 개의 작업 스레드 – 아마도 4개 이상 12개 미만 – 에서 원활히 메모리 할당해제가 이루어져야 한다.

즉, 요약하면 이런 문제다.

  • Win32환경의 복수의 스레드에서 메모리 할당 해제가 이뤄진다
  • 할당 단위는 미리 알려진 고정길이이고 그 크기는 16 bytes에서 64 bytes 수준
  • 메모리를 할당한 스레드에서 해제까지 한다는 보장은 없다
  • 할당/해제 속도가 충분히 빨라야하며, 상위 레이어에서 락 문제를 신경쓰게 만들어서는 안된다
  • 메모리 할당~해제까지 걸리는 시간은 한정된 시간으로 제한 된다.

이런 것을 해결해야하는데, 생각한 답들/주변에서 얻은 답들은 이런 것.

(thread) local heap을 프로그램 시작 시에 스레드 별로 할당받고, 여기에서 할당, 해제는 일종의 마커를 사용해서 각 스레드들이 일정 주기마다 GC처럼 동작.

이 방법의 문제는 일종의 가비지 콜렉션;GC 처럼 동작하는 부분의 성능. 로컬 힙에서 할당하는 것은 매우 빨라서(락이 없으니) 맘에 들지만 해제역시 빈번하다는 점에서 감점.

 

Win32 API의 slist_entry를 사용해서 미리 할당한 버퍼를 계속 재사용하는 것. slist_entry는 interlocked operation만으로 동작하는 링크드 리스트로 동작할 수 있기 때문에 락 없이 상대적으로 빠른 속도로 FIFO 큐로 동작할 수 있다.

Locking이 없다는게 매우 좋고, 잘 정의된 동작을 보이긴하지만, 일종의 이중 포인터를 유지하는 셈이고해서 약간의 오버헤드가 추가된다 = 캐쉬 힛이 좀 더 떨어진다. 즉 slist_entry 자체의 메모리도 할당해 줘야해서 하나의 메모리 영역에 대해서 이런 공간이 생긴다.

(이전 원소) | slist_entry(포인터 타입 1개 크기)) | 실제 데이터(16bytes~64bytes) | (이후 원소)

이런 점에서는 조금 괴롭다. 오버헤드가 대략 20%~6%수준이구만; 할당하는 메모리 단위가 클수록 쓸만할 것 같음

 

마지막으로 할당~해제 사이의 시간이 유한하게 한정(bound)된다는 것과 약간의 운(…)을 믿는 할당 방법.

프로그램 시작 시에 큰 버퍼를 잡거나 할당받고, 이를 고정 길이로 쪼개고 링버퍼로 생각한다.

즉 이런 링버퍼가 생긴다: static ALLOC_UNIT ring_buffer[ TOTAL_ELEMENTS ];

현재 할당 위치를 가리키는 volatile 카운터를 둔다.

volatile 카운터를 증가시키면서 해당 값에 해당하는 버퍼 부분을 쓴다.

아무런 Lock도 없고, 관리하기 위한 공유 변수도 한 개고, 한 번의 증가 연산 + mod 연산으로 메몰 힐당이 끝난다. 심지어 메모리 할당 동작도 없고(…), 링버퍼 길이를 2의 제곱수로 하면 mod 연산도 필요 없다. 다만 "운"을 믿어야한다는 것.  링버퍼가 작다면 이미 할당된 곳을 또 할당하는 악수를 둘 수 있다.

 

…뭐가 실제로 빠를지도 모르고 심지어 문제를 갖는 알고리즘도 있지만, 아마도 다 짜보고 다 돌려봐야겠지 =_=
(그리고 상황에 따라서 성능도 다 다르게 나올걸…)

Author: rein

나는 ...

12 thoughts on “작은 메모리 할당을 빨리하려면?”

  1. 운에 맡긴다는 얘길 들으니…

    예전에 OS 시간에 캐시 매니져든가 버퍼 관련 정책 설명할 때 이것 저것 설명하면서

    “랜덤”하게 만드는 것도 왠만한 거 보다 성능이 좋다는 말을 들었던게 생각나네 ㅡㅡ;;

  2. 상황에 정말 디펜던트 할 꺼 같아요.
    차라리 할당을 하지 않는건 안되나요;
    premature optimization 일것도 같음

  3. 수원 / 내 그렇죠. 비슷하게(?) quicksort도 운에 맡기는(물론 intro-sort같은 변종은 아니지만) 알고리즘…

    ipkn / 상황에 굉장히 디펜던트한데, 할당을 하지 않는다는 건 무슨 의미인지 모르겠음. 그냥 built-in new/delete를 쓰란거면 그거보다는 성능이 잘 나오는 해답이 하나 존재한다고 알려주지;
    존재하는 *범용 MT용 메모리 할당기* 라이브러리를 써보면 성능이 올라감. 물론 저기서만 올라가는 것은 아니지만…

    근데 실제로 2번째 케이스를 적용해서 기본 할당기(MT용 아님)보다 성능이 안나온 경우는 있다고(……………….)

  4. 오래된 글에 댓글 남겨 썰렁하네요.

    멀티스레딩 환경에서의 malloc (HeapAlloc도 마찬가지)의 가장 큰 적은 false sharing으로 알고 있습니다. Hoard라는 메모리 할당자를 한 번 검색해보세요.

  5. object / Hoard 류의 라이브러리는 이미 적용하고 있습니다. 일부는 TBB malloc에서 할당되기도 하고요.

    이 경우엔 아예 per-thread 할당을 받고, 그 영역을 다시 쪼개주는 식으로 스레드간에 안겹치게 만드는 중입니다 ~_~

  6. 옷.. 네 5월 1일 잡담에 보니 이미 적용 중에 있으셨군요. 뒷북쳐서 죄송해요 ㅎㅎ 그럴 땐 그냥 말씀대로 하시는 방법이 가장 좋아 보이네요. 저는 bulk alloc/dealloc을 하기도..

  7. bulk alloc/dealloc을 하는 코드들도 있던데 — 다른 서버의 코드에 — 그 쪽도 좀 보고 따라해보긴 해야할 것 같아요. 이미 서비스 중인 녀석의 성능을 믿어볼 순 있으니. 흐흐;

  8. 작은 객체들을 위한 메모리할당은…’Modern C++ Design’에 나왔던것을 좀 참고해보시면 어떨까 싶네요… 상대적으로 큰 객체들(수KB급 이상)은 그냥 C++기본할당기가 쓸만하다고 알고있습니다.

    책에서 언급되는 SmallObjAllocator 에다가…상당히 많은 스레드에서 접근을 한다면 (8개 그 이상?) 할당기 자체를 여러개로 만들어서 race condition을 좀 줄이는것도 괜찮은 방향같구요…

  9. 상대적으로 큰 객체는 할당 빈도가 작아서 큰 차이가 안 날것 같고; 작은 객체를 자주 할당할 일이 있는데 (초당 수백+) 이 부분은 윗쪽에 나온것들을 대충 조합해서 해결한 것 같습니다.

Leave a Reply