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

요즘 생각하는 문제 중 하나는 작은 메모리 영역, 대략 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 연산도 필요 없다. 용량을 초과하면 덮어 쓰게 되고, 디버깅하는게 어려울 것.

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