So, I decided I'd do some memory allocation benchmarks before I worked on the lock-free, zero-fragmentation allocator I mentioned. I'll probably post more detailed information later, but for now here are a few key findings (either important or just interesting):
- When there is nothing but allocations, HeapAlloc/malloc/new appear to be O(log N) with respect to block size
- When there is a significant amount of deletions intermixed with allocations, HeapAlloc/malloc/new are O(1), and actually as fast or faster than HeapAlloc/malloc/new with allocations only (big surprise)
- HeapAlloc from a private heap is O(log N), faster than HeapAlloc from the global heap for allocations <> 100 bytes (also a big surprise).
- SMemAlloc is just about the biggest POS ever coded. By about 50 byte allocations it passes HeapAlloc/malloc/new, and continues in what appears to be O(N) (it's really hard to tell, because the data is all over the freakin' place; it could also be O(log N)). At 320 bytes, it becomes O(x^N), getting up to around 100 K cycles for 500 byte allocations. I know that's my shock and awe for the day.