-
Guido van Rossum authored
keeping track of the beginning and end address of all free blocks, to make merging of adjacent blocks a breeze. The free list is no longer kept sorted order. Unfortunately, this still performs poorly. It has a higher hit rate (with the 38 minute trace I'm using; the longer traces take too long) than the buddy system allocator with the same arena size, it is *much* slower, the memory usage is under 20% (!!!), and despite a roving pointer, the allocation loop is taken an average of 692 times per allocation. At the end of the simulation the free list contains 1039 blocks; I presume this is a steady state approximating the average behavior. (There are 2280 allocated blocks at that point, roughly confirming Knuth's "50% rule" and suggesting that the block merge code works properly.) I guess the next idea is separate free lists per size.
60185c00