4 ms·

The complexity of malloc comes from the fact that the objects can be of variable size and have unknown lifespans. Faster allocators usually work on "pools" of

The complexity of malloc comes from the fact that the objects can be of variable size and have unknown lifespans. Faster allocators usually work on "pools" of objects that have the SAME size and/or lifespan. Using "pools" lets you avoid the extra overhead. If you can be sure that your allocator is only called in one thread, you can also avoid expensive memory fences.

marshray 13y ago
I don't know this for a fact, but some implementations of malloc() seem to allow realloc() the possibility of later growing the memory in-place. A custom allocator may gain efficiency by optimizing explicitly for or against the realloc() scenario.
- spc476 13y ago
  If you are following the C standard for malloc(), then realloc() comes along. In fact, according to the C standard, malloc(size) is the same as realloc(NULL,size) and free(ptr) is the same as realloc(ptr,0). realloc() can also shrink a previous allocation, in addition to growing it (but you must be aware that you might get back an entirely new pointer).
  - marshray 13y ago
    Yes, but the C standard also allows a realloc() that can never actually succeed in growing the allocation. The probability by which a given allocation pattern is likely to result in a successful growing realloc() seems like a pretty big design choice. Do you leave space after allocations for them to grow? Do you have power-of-2 size-based tables with an allocation bitmap? If so, what sizes? Etc.
    - spc476 13y ago
      Which is why you might get back a new pointer---because the original block couldn't be grown, so a new block has to be allocated and the contents copied.
  - mistercow 13y ago
    >but you must be aware that you might get back an entirely new pointer Which is super fun if someone else adds code that keeps a copy of the pointer, not knowing that it might change. Incidentally, is that possibility realistic in a 64-bit system? It seems like the addresses could easily be spaced out enough that you would never actually expect to see a realloc return a different pointer.
    - marshray 13y ago
      They could, but it would be extremely inefficient for small allocations. Pages are 8 KiB minimum, so it would waste memory, bloat up the page tables, and ruin cache efficiency.
      - deleted 13y ago
        [deleted]
      - mistercow 13y ago
        Hmm, I see what you mean. But it seems like that could be solved by more sophisticated virtual memory management, although it seems like it would essentially take an entire other layer of virtualization to make it work, which might have other performance consequences.
        Sharlin 13y ago
        Basically you would just reimplement malloc on the MMU level.
    - bzbarsky 13y ago
      It depends on your allocator. For example, jemalloc stores medium-sized allocations in big contiguous buffers, binned by size rounded up to 16 bytes. So if you realloc to a different size class, your pointer will change, because you need to move to a different big buffer.

marshray 13y ago

I don't know this for a fact, but some implementations of malloc() seem to allow realloc() the possibility of later growing the memory in-place. A custom allocator may gain efficiency by optimizing explicitly for or against the realloc() scenario.

spc476 13y ago
If you are following the C standard for malloc(), then realloc() comes along. In fact, according to the C standard, malloc(size) is the same as realloc(NULL,size) and free(ptr) is the same as realloc(ptr,0). realloc() can also shrink a previous allocation, in addition to growing it (but you must be aware that you might get back an entirely new pointer).
- marshray 13y ago
  Yes, but the C standard also allows a realloc() that can never actually succeed in growing the allocation. The probability by which a given allocation pattern is likely to result in a successful growing realloc() seems like a pretty big design choice. Do you leave space after allocations for them to grow? Do you have power-of-2 size-based tables with an allocation bitmap? If so, what sizes? Etc.
  - spc476 13y ago
    Which is why you might get back a new pointer---because the original block couldn't be grown, so a new block has to be allocated and the contents copied.
- mistercow 13y ago
  >but you must be aware that you might get back an entirely new pointer Which is super fun if someone else adds code that keeps a copy of the pointer, not knowing that it might change. Incidentally, is that possibility realistic in a 64-bit system? It seems like the addresses could easily be spaced out enough that you would never actually expect to see a realloc return a different pointer.
  - marshray 13y ago
    They could, but it would be extremely inefficient for small allocations. Pages are 8 KiB minimum, so it would waste memory, bloat up the page tables, and ruin cache efficiency.
    - deleted 13y ago
      [deleted]
    - mistercow 13y ago
      Hmm, I see what you mean. But it seems like that could be solved by more sophisticated virtual memory management, although it seems like it would essentially take an entire other layer of virtualization to make it work, which might have other performance consequences.
      - Sharlin 13y ago
        Basically you would just reimplement malloc on the MMU level.
  - bzbarsky 13y ago
    It depends on your allocator. For example, jemalloc stores medium-sized allocations in big contiguous buffers, binned by size rounded up to 16 bytes. So if you realloc to a different size class, your pointer will change, because you need to move to a different big buffer.