• Poul-Henning Kamp's avatar
    Rework the binary heap, we use for expiry processing, to deal more · dd288af6
    Poul-Henning Kamp authored
    gracefully with large number of objects.
    
    Previously we kept all objects in a single array which resultined
    in increasingly infrequent but increasingly demanding calls to
    calloc(3) with the consequent massive memory copies.  We also did
    not release memory again if unused.
    
    Now we stripe the array into rows of 64k objects each.
    
    This number is a compromise between space wastage, max 1MB on a
    64bit machine, and the desire to not add and delete rows all the
    time.  With 64k objects in a row, even on a very busy server would
    only add a new row every 5...10 seconds during ramp up.
    
    Delete unused rows, but keep a hysteresis of an entire empty row
    to avoid silly add-delete-add-delete-add-delete behaviour at row
    boundaries.
    
    Streamline some of the functions a bit.
    
    Fixes #210
    
    
    
    
    git-svn-id: http://www.varnish-cache.org/svn/trunk/varnish-cache@3390 d4fa192b-c00b-0410-8231-f00ffab90ce4
    dd288af6
binary_heap.c 10 KB