[Varnish] #210: The binary heap implementation does not scale

[Varnish]

#210: The binary heap implementation does not scale
-------------------------+--------------------------------------------------
 Reporter:  phk          |        Owner:  phk   
     Type:  enhancement  |       Status:  closed
 Priority:  lowest       |    Milestone:  Later 
Component:  varnishd     |      Version:  trunk 
 Severity:  normal       |   Resolution:  fixed 
 Keywords:               |  
-------------------------+--------------------------------------------------
Changes (by phk):

  * status:  new => closed
  * resolution:  => fixed

Comment:

 (In [3390]) 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

-- 
Ticket URL: <http://varnish.projects.linpro.no/ticket/210#comment:5>
Varnish <http://varnish.projects.linpro.no/>
The Varnish HTTP Accelerator