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

Written December 20, 2007 in Computer

Jump to comments

요즘 생각하는 문제 중 하나는 작은 메모리 영역, 대략 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 연산도 필요 없다. 다만 "운"을 믿어야한다는 것.  링버퍼가 작다면 이미 할당된 곳을 또 할당하는 악수를 둘 수 있다.

 

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

  Related Posts  

Trackback URI: http://rein.upnl.org/wordpress/archives/483/trackback

12 comments on ' 작은 메모리 할당을 빨리하려면? '

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

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

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

      Written by 수원 on December 21, 2007 at 5:18am

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

      Written by ipkn on December 21, 2007 at 7:07am

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

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

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

      Written by rein on December 21, 2007 at 10:43am

  4. 내가 말했던거 구현해줘 ㅡㅡ (떼쓴다)

      Written by ehooi on December 23, 2007 at 2:02am

  5. 내가 말했던것도 구현해줘!

      Written by Rica on December 23, 2007 at 10:06am

  6. ehooi, Rica / 님들 맨허염(…)

      Written by rein on December 23, 2007 at 10:54am

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

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

      Written by object on May 11, 2008 at 2:23pm

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

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

      Written by rein on May 11, 2008 at 2:26pm

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

      Written by object on May 11, 2008 at 2:54pm

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

      Written by rein on May 11, 2008 at 3:31pm

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

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

      Written by kalstein on May 13, 2008 at 2:58pm

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

      Written by rein on May 13, 2008 at 4:19pm

Leave a comment