figure 1. comparison of runtime speeds of binary heap and B-heap.
binary heap (left scale)
b-heap (left scale)
1e +00
12
speedup (right scale)
100000
10
Runtime in seconds
10000
1000
100
8
6
4
10
1
– 8
1M records
512 per page
1ms disk
– 7
2
– 6
– 5
Vm pressure in megabytes
– 4 – 3 – 2
– 1
0
0
figure 2. close-up comparison of binary-heap and B-heap runtime speeds.
binary heap (left scale)
b-heap (left scale)
1e +00
12
speedup (right scale)
100000
10
Runtime in seconds
10000
1000
100
8
6
4
10
1
0 4 8 12 16 20 24
1M records
512 per page
1ms disk
2
28 32 36
Kb resident
40 44 48 52 56
0
60 64
of their CPU available for twiddling
their digital thumbs.a
The short version of the story is that
Varnish knows it is not running on the
bare metal but under an operating sys-
tem that provides a virtual-memory-
based abstract machine. For example,
Varnish does not ignore the fact that
memory is virtual; it actively exploits
it. A 300GB backing store, memory
mapped on a machine with no more
than 16GB of RAM, is quite typical.
a This pun is included specifically to inspire
Stan Kelly-Bootle.
The user paid for 64 bits of address
space, and I am not afraid to use it.
One particular task inside Varnish
is expiring objects from the cache
when their virtual life-timers run out
of sand. This calls for a data structure
that can efficiently deliver the smallest keyed object from the total set.
A quick browse of the mental catalog flipped up the binary-heap card,
which not only sports a O(log2(n))
transaction performance, but also has
a meta-data overhead of only a pointer
to each object—which is important if
you have over 10 million objects.
Careful rereading of Knuth confirmed that this was the sensible
choice, and the implementation was
trivial: “Ponto facto, Caesar transit,”
and so on.
On a recent trip by night train to
Amsterdam, my mind wandered, and
it struck me that Knuth might be terribly misleading on the performance
of the binary heap, possibly even by an
order of magnitude. On the way home,
also on the train, I wrote a simulation
that proved my hunch right.
Before any fundamentalist CS theoreticians choke on their coffees: don’t
panic! The P vs. NP situation is unchanged, and I have not found a systematic flaw in the quality of Knuth et
al.’s reasoning. The findings of CS, as
we know it, are still correct. They are
just a lot less relevant and useful than
you think—at least with respect to performance.
The oldest reference to the binary
heap I have located, in a computer
context, is J. W.J. Williams’ article published in the June 1964 issue of
Communications of the ACM, entitled “
Algorithm Number 232—Heapsort.” 2,b The
trouble is, Williams was already out
of touch, and his algorithmic analysis
was outdated even before it was published.
In an article in the April 1961 issue
of Communications, J. Fotheringham
documented how the Atlas Computer
at Manchester University separated
the concept of an address from a
memory location, which for all practical purposes marks the invention
of virtual memory (VM). 1 It took quite
some time before VM took hold, but
today all general-purpose, most embedded, and many specialist operating systems use VM to present a standardized virtual machine model (such
as POSIX) to the processes they herd.
Of course, it would be unjust and
unreasonable to blame Williams for
not realizing that Atlas had invalidated one of the tacit assumptions of
his algorithm: only hindsight makes
that observation possible. The fact is,
however, 46 years later most CS-educated professionals still ignore VM as
a matter of routine. This is an embar-
b How wonderful must it have been to live and
program back then, when all algorithms in the
world could be enumerated in an 8-bit byte.
