Repository navigation
Use a principled, and consistent, implementation of freelists. #100240
Description
Activity
Size classes
Most modern allocators use segregated freelists; one freelist per size-class.
I believe jemalloc uses 4 size classes per power-of-2:
1,2,3,4,
5,6,7,8,
10,12,14,16,
20, 24...Other allocators use a similar scheme, although dlmalloc used by glibc uses power of 2 sizes (I believe).
We allocate in mutliples of
sizeof(void*) *2(for C alignment reasons) and the stats show that 99.5% of allocations are size <= 512 bytes (this might be an artifact of the benchmark suite, so we might want to have freelists to 1k or 2k).
512 bytes is (on a 64bit machine) 32 units of allocation, giving us the following size classes (in units ofsizeof(void*) *2)1,2,3,4,
5,6,7,8,
10,12,14,16,
20,24,28,32for 16 size classes in total (adding another 4 for each additional power of 2 that we want to handle).
Implementation
The simplest implementation of the function mapping size to size-class is probably a lookup table:
/* Declaring this const is vital, as it allows compilers to treat `size_to_size_class` as a pure function */ const uint8_t LOOKUP_TABLE[32] = { ... }; #define QUANTUM (2*SIZE_OF_VOID_P) inline int size_to_size_class(intptr_t size) { assert(size <= QUANTUM*32); intptr_t size_in_quantum = (size + QUANTUM - 1)>>LOG_2_QUANTUM; return LOOKUP_TABLE[size_in_quantum]; }
We currently implement freelists for the following object and internal structs
All of these are implemented independently and rather inefficiently.
They take up 3672 bytes of space, instead of the ~200 bytes they should take.
This is not a lot in terms of memory, but it is a lot in terms of L1 cache.
A freelist should look like this:
Only one test is needed for allocation and deallocation (on the fast path).
Allocation needs to test
freelist.head != NULL. Deallocation needs to testfreelist.space != 0.The actual list is threaded through the objects on the list, terminated by
NULL.Cache locality is good. The
headandspaceare adjacent, and 4 freelists fit in a single cache line.When freeing, the object is hot (and thus in cache).
When allocating, the object is about to be used, so needs to be moved to cache anyway.
The
capacityfields are there to allow the capacity of a freelist to be temporarily set to 0, ensuring that all allocations go through the main allocator, for use cases liketracemalloc. Currentlytracemallocdoesn't see a lot of allocations, due to freelists.Unifying the code for freelists reduces code duplication, and simplifies things for further improvements.
Original discussion
faster-cpython/ideas#132
Linked PRs