3 ms·
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, th
by 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 agoSo 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 agowell, 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[].