Subject: Re: [boost] [Heaps] benchmarks
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-06-09 17:30:28
Tim Blechmann wrote:
>> Tim, you're proposing this b-heap purely as a performance optimisation
>> compared to the "traditional" heap, but we've not yet seen any cases
>> where it is actually faster. If it can be faster we need to see some
>> examples, and the documentation should qualify when it can be expected
>> to be better. If it's not faster, it should be dropped.
>
> just for the record:
> core i7 920, x86_64, linux-3.0-rc2, hyperthreading/frequency scaling disabled,
> 12gb triple-channel ddr3 ram
>
> stressed with:
> stress -m 1 --vm-bytes 4G --io 16 -c 3
> and two boinc processes running at nice 10
>
> configured the problem size to 15000000
> changed work_t from boost::function to int (24byte to 4byte)
>
>
> comparison of b-heap and dary_heap (with arity 2) ... running all at nice 1 to
> increase the number of context switches.
>
> Performance counter stats for './bench_boostbheap':
[snip]
> 615.223322417 seconds time elapsed
>
> Performance counter stats for './bench_boostdary':
[snip]
> 659.415916004 seconds time elapsed
That's great. But I was comparing with your priority_queue<> and the
std::push|pop_heap, not your d_ary_heap<>. Could you do the same test
with one of those?
> Performance counter stats for './bench_boostbheap':
> 1,421,230,219,856 cycles
> 928,444,569,746 stalled-cycles-frontend
> 643,217,557,503 stalled-cycles-backend
> 1,517,920,671,665 instructions
> Performance counter stats for './bench_boostdary':
> 1,536,548,826,172 cycles
> 1,304,937,894,945 stalled-cycles-frontend
> 999,244,398,224 stalled-cycles-backend
> 747,525,733,877 instructions
That's the interesting part: the b-heap takes twice as many
instructions as the d-array heap, so the improvement in cache locality
needs to be substantial enough to double the instruction throughput
before the b-heap does better. You've had to pull all the stops out to
make that happen.
Regards, Phil.