malloc/realloc only powers of two?

antirez / sds

Simple Dynamic Strings library for C

BSD 2-Clause "Simplified" License

4.89k stars 473 forks source link

malloc/realloc only powers of two? #117

Open ericcurtin opened 4 years ago

ericcurtin commented 4 years ago

It might be worth considering only allocating strings of a capacity that is a power of two (including header) to reduce memory fragmentations:

A simple code snippet to round up to the next power of two:

unsigned int v; // compute the next highest power of 2 of 32-bit v

--v;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
++v;

I can make the code contribution if you'd like.

geniiii commented 4 years ago

How much does this really help with fragmentation? It would also be more efficient to go for an approach using CLZ to calculate the next power of two, if supported.