rassment for CS as a discipline and
profession, not to mention wasting
enormous amounts of hardware and
electricity.
figure 3. close-up of the effect of Vm pressure on binary-heap and B-heap runtime speeds.
binary heap (left scale)
b-heap (left scale)
speedup (right scale)
25
2
Performance simulation
Enough talk. Let me put some simulated facts on the table. The plot in
Figure 1 shows the runtime of the binary heap and of my new B-heap version for one million items on a 64-bit
machine.c (My esteemed FreeBSD colleague Colin Percival helpfully pointed out the change I have made to the
binary heap is very much parallel to
the change from binary tree to B-tree,
so I have adopted his suggestion and
named my new variant a B-heap.d)
The x-axis is VM pressure, measured in the amount of address space
not resident in primary memory, because the kernel paged it out to secondary storage. The left y-axis is runtime in seconds (log-scale), and the
right Y-axis shows the ratio of the two
runtimes: (binary heap/B-heap).
Let’s get my “order of magnitude”
claim out of the way. When we zoom
in on the left side in Figure 2, we see
there is indeed a factor 10 difference
in the time the two algorithms take
when running under almost total VM
pressure: only 8 to 10 pages of the
1,954 pages allocated are in primary
memory at the same time.
Did you just decide that my order of
magnitude claim was bogus because
it is based on only an extreme corner
case? If so, you are doing it wrong,
because this is pretty much the real-world behavior seen.
Creating and expiring objects in
Varnish are relatively infrequent actions. Once created, objects are often
cached for weeks if not months, and
therefore the binary heap may not be
updated even once per minute; on
some sites not even once per hour.
In the meantime, we deliver giga-
20
1. 5
Runtime in seconds
15
1
10
0.5
5
0
– 64 – 48
1M records
512 per page
1ms disk
– 32
0
0
16
figure 4. comparisons of runtime speeds of binary heap and B-heap on a mechanical disk.
binary heap (left scale)
b-heap (left scale)
speedup (right scale)
180
2
160
140
1. 5
Runtime in seconds
120
100
80
60
1
0.5
40
20
0
1M records
512 per page
10ms disk
– 64 – 48
– 32
Vm pressure in kilobytes
– 16
0
0
16
c Page size is 4KB, each holding 512 pointers
of 64 bits. The VM system is simulated with
dirty tracking and perfect LRU page replacement. Paging operations set to 1 millisecond.
Object key values are produced by random( 3).
The test inserts one million objects, then alternately removes and inserts objects one million
times, and finally removes the remaining one
million objects from the heap. Source code is
at http://phk.freebsd.dk/B-Heap.
d Does Communications still enumerate algorithms, and is eight bits still enough?
bytes of objects to clients’ browsers,
and since all these objects compete
for space in the primary memory, the
VM pages containing the binheap that
are not accessed get paged out. In the
worst case of only nine pages resident,
the binary heap averages 11. 5 page
transfers per operation, while the B-heap needs only 1. 14 page transfers.
If your server has solid state drives
(SSD), that is the difference between
each operation taking 11 or 1. 1 milliseconds. If you still have rotating platters, it is the difference between 110
and 11 milliseconds.
At this point, is it wrong to think,
“If it runs only once per minute, who
cares, even if it takes a full second?”
We care because the 10 extra pages
needed once per minute loiter in RAM
for a while, doing nothing—until the
kernel pages them back out again,
at which point they get to pile on top
of the already frantic disk activity,
typically seen on a system under this
heavy VM pressure.e
e Please don’t take my word for it: applying
queuing theory to this situation is a very edu-
cational experience.
