]> err.no Git - varnish/commit
Rework the binary heap, we use for expiry processing, to deal more
authorphk <phk@d4fa192b-c00b-0410-8231-f00ffab90ce4>
Fri, 14 Nov 2008 00:19:33 +0000 (00:19 +0000)
committerphk <phk@d4fa192b-c00b-0410-8231-f00ffab90ce4>
Fri, 14 Nov 2008 00:19:33 +0000 (00:19 +0000)
commit3bfb5dc4e698e83963d7e83df3f384008862ea58
tree9c6ed490e13b0a442b200df41c4a7a42060bfc79
parent51b23438333383d89565e1fbb22b58983e82bb65
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: svn+ssh://projects.linpro.no/svn/varnish/trunk@3390 d4fa192b-c00b-0410-8231-f00ffab90ce4
varnish-cache/lib/libvarnish/binary_heap.c