About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Sun, 06 Aug 2006

Network tree allocator.


Let's see how fragmentation problem is being solved in NTA.
For initial test I've run NTA with set of pseudo-random sized allocations until first allocation fails, when it hapens I decrease maximum allocation size in two times. Each graph below shows free and used chunks inside each page (there are 4094 pages), green points correspond to free and red ones - to used chunks (each one of 32 bytes).
Maximum allocation size is equal to PAGE_SIZE, failed allocation was for 1912 bytes (60 chunks of 32 bytes):


Maximum allocation size is equal to PAGE_SIZE/2 (decreased after allocation failure), failed allocation was for 968 bytes (31 chunks of 32 bytes):


Maximum allocation size is equal to PAGE_SIZE/4 (decreased in two times after first and second allocation failures), last failed allocation was for 504 bytes (16 chunks of 32 bytes):


Maximum allocation size is equal to PAGE_SIZE/8 (decreased in two times after each of three allocation failures), last failed allocation was for 252 bytes (8 chunks of 32 bytes):


This tests do not show how fragmentation is changed with the time, when there are a lot of allocations and freeings are completed, but even existing results show that network tree allocator performs very well. Next time I will run the same tests after some pseudo-random allocation and freeing periods.

For comparison I've run the same test with power-of-2 slab-like allocator (actually it is much more simple, but it has the same ideas as SLAB allocator and probably can behave even better if we get into account big-sized chunks). Picture does not change when maximum allocation size is being decreased after allocation failures, since most of the overhead and fragmentation is obtained from power of 2 rounds.


This SLAB-like power-of-two allocator overhead and fragmentation actually looks different than on the picture, since almost all allocations have fragmentation overhead, so each vertical line actually must contain several red(used)-green(free or fragmentation overhead) pieces, where sum of all pieces of the same colour will be equal to what is shown on the picture. But picture presents that absolute amount of fragmentation overhead is extremely high for power-of-2 allocators. For the real SLAB allocator picture will be better for small-sized chunks (since chunks never share pools with different sized ones, except when they can steal pages when cache is refilled), but much worse for big-sized ones.

Difference in used and free chunks position on the pictures is due to the fact, that in network tree allocator chunks in page are shown in reverse order (i.e. higher addresses are first).

/devel/networking/nta :: Link / Comments ()