Date: Sat, 21 Apr 2018 22:22:39 -0400 From: Rich Felker <dalias@...c.org> To: musl@...ts.openwall.com Subject: Improving malloc header/footer structures? Right now, we're using size_t slots for the header and footer on malloc chunks. This results in 16 bytes of overhead per allocation on 64-bit archs. We could do a lot better, because, except for large free zones, chunks can never be larger than a little under 256k. Obviously, and this is the simplest improvement, we could just go with uint32_t headers/footers instead of size_t, at the cost of some special-casing to prevent a large free chunk from exceeding 4GB. The easiest way to do that is leaking a tiny "divider" chunk whenever the free zone would grow over 4GB. There are also solutions involving the "freezing" approach described in this thread from 2014: Message-ID: <20140402210805.GA852@...ghtrain.aerifal.cx> Subject: [musl] malloc & uncommitting memory Note that switching to uint32_t would make it so we don't need SIZE_ALIGN to be 32 on 64-bit archs anymore. It could be 16 just like on 32-bit. Bin 0 (size 16-8==8) would be unusable on 64-bit though since it's too small to hold linked list pointers; the smallest available allocation size would be 32-8==24. The next size up would be 48-8==40 rather than 64-16==48, so situations where you save ~25% overhead/waste (structures/strings over 24 bytes but under 41 bytes) sound like they'd be rather common. On the other hand, since leftover space of just 16 bytes can't be split off and freed, there's a bit more complexity, and it might turn out that lots of the time you end up allocating sizes that are still multiples of 32 just because you can't free the extra 16 bytes. It turns out we can do better, though, if we want to. Since sizes are always a multiple of SIZE_ALIGN (16 or 32, 16 if we make this improvement), sizes up to 512k fit in 16 bits, leaving space for a one-bit in-use flag. This would make the bin sizes 16-4==12, 32-4==28, ... (with the first one unusable on 64-bit), potentially saving a good deal of space for short strings (likely not so much for structs whose sizes are likely to be multiples of 8). For what it's worth, I don't actually like that approach so much. Some other ideas I'm working on suggest we might want to do atomics on the chunk headers/footers, and packing them together as 16-bit halves of a 32-bit atomic would make accesses a lot more expensive. A different approach which might be more worthwhile is using 32-bit fields, but rather than storing a raw size in them, storing the bin index and a size displacement relative to it. This avoids most calls to bin_index (a moderately costly clz-type operation) by essentially caching the result of it; the inverse transformation is just a table lookup that's near-free. All of the above are just notes/ideas, posted publicly for record. Rich
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.