Bin 구조 도입을 통한 메모리 할당 탐색 시간 O(n)에서 O(1)로 단축

Context

단일 Linked List 기반의 Free List 관리로 인한 free 및 malloc 시 전체 리스트 순회 발생. 이로 인해 할당 횟수 증가 시 시간 복잡도가 O(n^2)로 급증하며 CPU 점유율이 90%를 상회하는 성능 병목 현상 노출.

Technical Solution

• 크기별 독립적 Singly-linked List인 Bin 구조를 도입한 메모리 관리 체계 설계
• 64-bit 환경의 Alignment 요구사항인 16-byte 배수를 고려한 (sz >> 4) - 2 인덱싱 로직 적용
• LIFO(Last-In-First-Out) 원칙 기반의 Fastbins 설계를 통한 Head 포인터 즉시 접근 및 Pop/Push 최적화
• 80-byte 이하 Fastbins, 16-512-byte Smallbins, 512-byte 초과 Largebins로 구분한 계층적 메모리 버킷팅
• Largebins의 경우 Unsorted Bin 영역을 통한 Lazy Evaluation 방식을 채택하여 정렬 비용을 다음 malloc 시점으로 지연
• A ∪ F = Total Memory 및 A ∩ F = ∅ 조건을 Invariant로 설정하여 메모리 누수와 중복 할당을 방지하는 수학적 검증 체계 구축