• Tollef Fog Heen's avatar
    Merge r3390: Rework the binary heap we use for expiry processing · 834b8409
    Tollef Fog Heen authored
    Rework the binary heap, we use for expiry processing, to deal more
    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/branches/2.0@3606 d4fa192b-c00b-0410-8231-f00ffab90ce4
    834b8409
binary_heap.c 10 KB