Calculating size class

user_45843 0
Viewed 44

High-performance malloc implementations often implement segregated free lists, that is, each of the more common (smaller) sizes gets its own separate free list.

A first attempt at this could say, below a certain threshold, the size class is just the size divided by 8, rounded up. But actual implementations have more nuance, arranging the recognized size classes on something like an exponential curve (but gentler than simply doubling at each step), e.g. http://jemalloc.net/jemalloc.3.html

I'm trying to figure out how to convert a size to a size class on some such curve. Now, in principle this is not difficult; there are several ways to do it. But to achieve the desired goal of speeding up the common case, it really needs to be fast, preferably only a few instructions.

What's the fastest way to do this conversion?

implementation malloc language-agnostic algorithm performance
2 Answers

In the dark ages, when I used to worry about those sorts of things, I just iterated through all the possible sizes starting at the smallest one.

This actually makes a lot of sense, since allocating memory strongly implies work outside of the actual allocation -- like initializing and using that memory -- that is proportional to the allocation size. In all but the smallest allocations, that overhead will swamp whatever you spend to pick a size class.

Only the small ones really need to be fast.

user_54835260

Lets assume you want to use all the power of two sizes and a plus half the size, ie 8, 12, 16, 24, 32, 48, 64 etc. ... 4096.

Check the value is less than or equal 4096, I have arbitrarily chosen that to be the highest allocable for this example.

Take the size of your struct, then use the highest set bit times two, and add 1 if the next bit is also set and you get an index into the size list add one more if the value is higher than the value the two bits would give. Should be 5-6 ASM instructions

So 26 is 16+8+2 bits are 4,3,1 4*2 + 1 + 1 so the 10th index is chosen for a 32 byte list.

Your system might require some minimum allocation size.

Also if your doing a lot of allocations, consider using some pool allocator that is private to your program with backup from the system allocator.

user_40132580
Related