4 ms·

Any idea how much space overhead malloc has with entries as small as this? (<1 to 4> * 8 bytes) Seems to me it could easily be a significant amount of overhead

Any idea how much space overhead malloc has with entries as small as this? (<1 to 4> * 8 bytes) Seems to me it could easily be a significant amount of overhead.

ekimekim 11y ago
Common practice if you're doing a large number of very small allocations is to pre-allocate a larger area of memory for them, then use a more naive allocation algorithm to parcel it out.
- TheLoneWolfling 11y ago
  Define "more naive allocation algorithm".
  - eutectic 11y ago
    What about bump-pointer + maintaining a count of live allocations?
    - TheLoneWolfling 11y ago
      That won't work if you ever want to deallocate things - which, given that due to the compressed arrays you have to deallocate to add elements (deallocate the old array with <0,1,2,3> elements, allocate a new with <1,2,3,4> elements), won't work for this.
      - eutectic 11y ago
        You can deallocate if you use small enough chunks, although you might need to use some other strategies to minimize fragmentation.
        TheLoneWolfling 11y ago
        If you're using "small enough chunks" your space overhead balloons to the point where you may as well not use it.
kuschku 11y ago
Most malloc implementations use a set of segregated explicit linked lists, which can be implemented with as low as 2 bit overhead, although, due to aligning, this ends up being 2 times the wordsize: in the end of the chunk you have a bit that tells if it’s free, and in the beginning of the chunk. If the bit is set to "free", then you use the free space inside the chunk for an offset pointer to the next and the last free element of the same size.
- TheLoneWolfling 11y ago
  So in other words, up to twice the overhead as amount of storage allocated for the actual elements? Yow! This makes this sort of scheme decidedly less attractive.
  - kuschku 11y ago
    well, sometimes you can actually put those bits into the padding, but often you can not. This is how many of the simpler malloc implementations, which do not directly mmap, work. So, remember, if you want to malloc 20 ints, don’t do 20 times malloc(sizeof(int)), do malloc(20*sizeof(int)) and treat them as int[].

Any idea how much space overhead malloc has with entries as small as this? (<1 to 4> * 8 bytes) Seems to me it could easily be a significant amount of overhead.

ekimekim 11y ago

Common practice if you're doing a large number of very small allocations is to pre-allocate a larger area of memory for them, then use a more naive allocation algorithm to parcel it out.

TheLoneWolfling 11y ago
Define "more naive allocation algorithm".
- eutectic 11y ago
  What about bump-pointer + maintaining a count of live allocations?
  - TheLoneWolfling 11y ago
    That won't work if you ever want to deallocate things - which, given that due to the compressed arrays you have to deallocate to add elements (deallocate the old array with <0,1,2,3> elements, allocate a new with <1,2,3,4> elements), won't work for this.
    - eutectic 11y ago
      You can deallocate if you use small enough chunks, although you might need to use some other strategies to minimize fragmentation.
      - TheLoneWolfling 11y ago
        If you're using "small enough chunks" your space overhead balloons to the point where you may as well not use it.

kuschku 11y ago

Most malloc implementations use a set of segregated explicit linked lists, which can be implemented with as low as 2 bit overhead, although, due to aligning, this ends up being 2 times the wordsize: in the end of the chunk you have a bit that tells if it’s free, and in the beginning of the chunk. If the bit is set to "free", then you use the free space inside the chunk for an offset pointer to the next and the last free element of the same size.

TheLoneWolfling 11y ago
So in other words, up to twice the overhead as amount of storage allocated for the actual elements? Yow! This makes this sort of scheme decidedly less attractive.
- kuschku 11y ago
  well, sometimes you can actually put those bits into the padding, but often you can not. This is how many of the simpler malloc implementations, which do not directly mmap, work. So, remember, if you want to malloc 20 ints, don’t do 20 times malloc(sizeof(int)), do malloc(20*sizeof(int)) and treat them as int[].