The C free() API means memory allocation must save some metadata

utcc.utoronto.ca

4 points·signa11··2 comments

I don't think this is necessarily true. You could just have malloc() bump an allocation pointer by the size, return the pointer pre-bump, or return NULL if we run out of space. Then free() can do nothing.

If you decide you want to have a malloc/free implementation that isn't as garbage as that, then you need some way to ensure malloc() does not ever return a pointer to memory that was already handed out - and I would argue that the book-keeping for this is this metadata being talked about. Even if free() took a "size" parameter, this would still be needed.

FTA: “Of course you can build C memory allocators that avoid or amortize this overhead, mostly obviously by having free() never do anything (some programs will be perfectly fine with this and it's very fast)”

I also don’t see how that bookkeeping would be necessary for allocated memory. For example, make you minimal allocation large enough to keep a (pointer, size) pair, keep a linked list of free blocks, each with their size, implement first fit malloc, splitting of any remaining parts, and have free chain up freed blocks to the end of that list. Not a good allocator (it could fragment memory badly, for example), but it would work.

It also would break horribly if the program passed incorrect pointers or sizes to free, but that would be the program’s problem. malloc isn’t required to protect against buggy programs.

Reply on news.ycombinator.com