Re: [boost] [gsoc] heap review

Subject: Re: [boost] [gsoc] heap review
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-05-12 17:53:50

>>>>> there will be a `formal' review announcement, i want to invite people
>>>>> to check out code, examples and documentation ...
>>>>
>>>> One quick note: your benchmarks operate on just 16 items
>>
>> not quite: they operate on differently sized heaps (roughly 1 to 100000
>> elements), but each operation is performed 16 times (to get some kind of
>> averaging).
> 
> OK, but the issue is that I don't trust that you can accurately measure
> execution times of the order of microseconds.  The overhead of, for
> example, the system call to read the clock will be significant.  If you
> believe that you can accurately measure such short periods, you should
> justify your methodology. 

iirc, i was running the benchmarks with rt scheduling to avoid that the 
scheduler preempts the benchmark program. smt/frequency scaling are disabled and 
high-resolution timers are used to get precise timing. for another project, i 
have done reliable histograms with microsecond resolution.

i also have a class somewhere, which can be used to directly query hardware 
performance counters via the `perf' subsystem, which should give cycle-accurate 
results (whatever that means on superscalar out-of-order machines)

> Otherwise, repeat a few thousand times.

well ... if you run a `push' operation for a few thousand times, the performance 
will change, because each `push' changes the size. also it may be difficult to 
run `pop' a few thousand times on an almost empty heap.

> Also, it might be interesting to look at non-random data.  Howard
> Hinnant (IIRC) did some great work on the libc++ sort implementation to
> benchmark things like sorting already-sorted, reverse-sorted, and other
> non-random inputs.  (Sorry, I can't find a link right now.)  I could
> imagine that non-random inputs might be quite important for heaps too.

yes, this may be interesting. however i wonder, maybe it will be better to 
completely replace the benchmarks of single operation types by a reasonable set 
of operations. there are too many interesting aspects, which will probably lead 
to a combinatoric explosion of test cases:

- sorted/reverse-sorted/random input
- fill the heap simply via push or via insert some other heap operations: in the 
first case, some heaps are degenerated to a linked list.
- element size - the bigger the size, the higher the overhead of container 
adaptors compared to node-based heaps
- at a certain heap size, the size of the CPU cache may have a significant 
influence
- cache hits/misses
- in-order vs out-of-order CPUs
- amortized vs worst-case costs

so imo, the benchmarks should mainly be a hint for people to be able to get a 
rough understanding of the constants ... since all heap data structures use the 
same interface, people should probably be encouraged write their own benchmarks 
for their specific use cases.

cheers, tim

-- 
tim_at_[hidden]
http://tim.klingt.org
The aim of education is the knowledge, not of facts, but of values
  William S. Burroughs