• Guido van Rossum's avatar
    Rewrite the simple free list allocator using Tim's suggestion of · 60185c00
    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
simul.py 21.1 KB