Boost logo

Boost :

Subject: Re: [boost] [Heaps] benchmarks
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-08 09:26:32


> > well, benchmarking this can be tricky ... first, your work is
> > boost::funtion<> (iirc 3 pointers) and a float ... so 16 bytes on 32bit
> > or 28 bytes on 64bit ... on 32bit systems you will have a better
> > matching with actual physical cache lines ...
> > second ... synthetical benchmarks are not necessarily the best way to
> > test cache-aware data structures: when stressing the heap, all its
> > content will be located in the cpu caches ... so you won't necessarily
> > see the benefit of the cache-awareness, since the data of the
> > non-cache-aware data structure are still in the CPU cache. unless you
> > manually add some work to thrash the caches ... in your case, you will
> > have a maximum of 90000 items in the queue, on 32bit platforms this is
> > rougly 1.4mb ... you won't see a big effect, if this fits all into the
> > caches ...
>
> The data cache sizes on the test systems are I think:
>
> 1. AMD Athlon II X2: 64 kB L1 + 1 MB L2.
> 2. VIA C7-M: 32 kB L1 + 128 kB L2.
> 3. ARM v5 (Marvell Kirkwood): 16 kB L1 + 256 kB L2.

on machine 2 and 3, i assume the size of a cacheline is 32/16 kb

> So this data set really shouldn't fit in the cache. Even if it did, it
> would be great if the b_heap implementation performed no worse than the
> "naive" version.

it cannot: it uses a different tree structure than binary heaps, causing a
higher tree. with d-ary heaps, the arity is a tradeoff between tree height and
number of comparisons (higher arity, lower tree height but more comparisons). in
a similar manner, the b-heap adds a tradeoff between memory locality and tree
height ...

> Also I've looked at your own benchmark graphs and it seems that there
> is a fairly constant performance difference between the different heaps
> - I don't see b_heaps getting faster than the alternatives as the queue
> size increases.

maybe because my workstation has 8mb of cache ... the

> (BTW, I find it almost impossible to distinguish the
> colours in those graphs...)

gnuplot defaults ... i generally find it hard to visualize multidimensional data
... if the plots will be included in the final documentation, i will try to find
a better visualization ...

tim




Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk