4 ms·

Try to do a bitmap allocator. Each word of memory has a free/used bit attached in a separate map. It allows quick resizing before or after the block without mov

Try to do a bitmap allocator. Each word of memory has a free/used bit attached in a separate map. It allows quick resizing before or after the block without moving. It can also be optimal by reducing the fragmentation (find the best block for a given size in the map). It can be optimized with bit counting intrinsics (like popcntl()).

JoshTriplett 8y ago
That works well if you allocate many blocks of the same size, or you have some other data structure that tracks which blocks belong to a specific object (such as in a filesystem). For a malloc/free implementation, however, you'd need some way to track the size of the allocation to free it later.
- 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 ago
    1 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 ago
      No 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 ago
        Well, you're welcome to try, but it's not like free space bitmaps are unknown to allocator writers.
  - JoshTriplett 8y ago
    How would you implement the free function? You need some way to track how much memory to free.
    - CodesInChaos 8y ago
      By 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 ago
        That makes sense, yes. If you're allocating blocks of uniform size, a bitmap works just fine.

JoshTriplett 8y ago

That works well if you allocate many blocks of the same size, or you have some other data structure that tracks which blocks belong to a specific object (such as in a filesystem). For a malloc/free implementation, however, you'd need some way to track the size of the allocation to free it later.

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 ago
  1 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 ago
    No 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 ago
      Well, you're welcome to try, but it's not like free space bitmaps are unknown to allocator writers.
- JoshTriplett 8y ago
  How would you implement the free function? You need some way to track how much memory to free.
  - CodesInChaos 8y ago
    By 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 ago
      That makes sense, yes. If you're allocating blocks of uniform size, a bitmap works just fine.