3 ms·
No. The purpose is the opposite. A map to describe the memory instead of a list of blocks. The granularity can be 1 bit to describe 1 byte (or 2/4/8...). Recen
by mabynogy 8y ago
No. The purpose is the opposite. A map to describe the memory instead of a list of blocks. The granularity can be 1 bit to describe 1 byte (or 2/4/8...).
Recent x64 instructions to count bits from left or right can help a lot to make that fast.
- gliptic 8y ago1 bit per byte would require an awful lot of memory access to find a free block. You would need something like a hierarchy of bitmaps to cut down on scanning.
- mabynogy 8y agoNo because you'll end up with the same problem elsewhere (handling blocks). If I'm correct tcmalloc memory overhead is around 4%. More overhead can be acceptable if the memory is less fragmented (less fragmentation, less cache misses, better compactness and better perfs).
- gliptic 8y agoWell, you're welcome to try, but it's not like free space bitmaps are unknown to allocator writers.
- JoshTriplett 8y agoHow would you implement the free function? You need some way to track how much memory to free.
- CodesInChaos 8y agoBy allocating from a different block for different sizes. This means the bitmap only needs one bit per element, not per byte and reduces fragmentation. You can keep the number of blocks small by limiting the allocation sizes to a number of pre-defined buckets. From what I remember jemalloc uses bitmaps for small allocations (below the 4 KiB page size) but switches to different data structures for medium and large allocations.
- JoshTriplett 8y agoThat makes sense, yes. If you're allocating blocks of uniform size, a bitmap works just fine.