hi all, during this `summer of code', i will do the review of two proposed libraries, boost.lockfree and boost.heap. the boost.heap review will be the first one, taking place from may 30th to june 8th. boost.heap is an implementation of different priority queue data structures. they can be found at: tarball: http://tim.klingt.org/git?p=boost_heap.git;a=snapshot;h=HEAD;sf=tgz git repository: git://tim.klingt.org/boost_heap.git documentation: http://tim.klingt.org/boost_heap/ there will be a `formal' review announcement, i want to invite people to check out code, examples and documentation ... cheers, tim -- tim@klingt.org http://tim.klingt.org Question: Then what is the purpose of this "experimental" music? Answer: No purposes. Sounds. John Cage
Hi Tim, Tim Blechmann <tim@klingt.org>
boost.heap is an implementation of different priority queue data structures. they can be found at:
tarball: http://tim.klingt.org/git?p=boost_heap.git;a=snapshot;h=HEAD;sf=tgz git repository: git://tim.klingt.org/boost_heap.git documentation: http://tim.klingt.org/boost_heap/
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 and execute in microseconds. I encourage you to consider cases that are orders of magnitude larger. Regards, Phil.
Den 11-05-2011 18:25, Phil Endecott skrev:
Hi Tim,
Tim Blechmann <tim@klingt.org>
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 and execute in microseconds. I encourage you to consider cases that are orders of magnitude larger.
+1. Please test for n = 10, 100, 1000, 10k, 100k, 1M -Thorsten
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).
and execute in microseconds.
fortunately, single heap operations are on the order of microseconds :)
I encourage you to consider cases that are orders of magnitude larger.
+1. Please test for n = 10, 100, 1000, 10k, 100k, 1M
the plots are loglog plots: the x axis shows the size of the heap, the y axis the time to perform 16 operations for this size. maybe this needs to be made more explicit? tim -- tim@klingt.org http://tim.klingt.org Every word is like an unnecessary stain on silence and nothingness Samuel Beckett
Tim Blechmann wrote:
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. Otherwise, repeat a few thousand times. 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. Otherwise, this looks like useful work! Regards, Phil.
Phil Endecott wrote:
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. Otherwise, repeat a few thousand times.
http://www.fftw.org/cycle.h But I agree, measuring something on the order of 1 microsecond won't be reliable, even with this non-portable code. Not sure whether fftw uses this itself when measuring which algorithm to use for a specific setup at runtime. Regards, Thomas
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@klingt.org http://tim.klingt.org The aim of education is the knowledge, not of facts, but of values William S. Burroughs
Hi Tim, Thank you for your work on this useful library! I'm definitely interested in it. I have a question about the library. Are there linear-time functions to construct a heap from unordered data? AFAIK, at least for d-ary heaps, there exists a linear time construction algorithm (often called `build_heap`). In STL, there is `make_heap` function which has linear-time complexity. I think such construction functions are useful in some applications. And here are some comments on source codes and documentation: * Use of double underscores In heap/detail/tree_iterator.hpp, there are a few names that contain double underscores. But such names are reserved by compilers and should not be used. * Naming of functions of `increase` and `decrease` For min heap, the meaning of `increase` and `decrease` becomes ambiguous. Would it be nice to use ordinary `up_heap` and `down_heap` or something like that? * Coding style of nullary function signature In header files and documentation, nullary functions are written as return_type some_function(void) It is more C++'ish to write them as return_type some_function() * Readability of ampersands In the documentation (heap/xxxx_mutable.html), ampersands ('&') are used in the description of `update`, `increase` and `decrease`. I think it would be better to write 'and' instead of '&', since they are a bit ambiguous with reference symbols. Regards, Michel
From the docs on stable priority queue:
"If a priority queue is configured to be stable, an integer timestamp is associated with each node, specifying the time ..." I was one of the people discussing priority queue use cases, probably a year ago, and specifically was wanting a stable priority queue. I also said that adding a time stamp or counter to each entry was a naïve approach (and one that I had done myself in about an hour, adapting a std::priority_queue). I asked for a true, "native" implementation of a stable priority queue, because adding a time stamp to each entry has a couple of drawbacks: 1) It adds storage to each element - while for many (most?) applications this extra storage is negligible, in some cases it is not negligible (embedded systems with large queues) 2) It can fail - if a true time stamp is used, what happens when times are adjusted? If a counter is used, what happens when the counter overflows? While the failures are edge cases, there's no need to have any failures. I can dig out the e-mail, if more details of the discussion are needed. I'm a bit perplexed that either this discussion was completely missed, or somehow "read but misremembered, with the opposite of the desired result". There must be heap data structures for priority queues that preserve order (with no extra memory) at the cost of being slightly slower (but still with the same big-O complexity). This is what I expect of a Boost library - finding and implementing the best, not something naïve and easily thrown together. So this gives me very little confidence for a robust, world-class implementation of heap structures. Please read this as encouragement to do the hard work, not just the minimum necessary for a review, at least for the case mentioned in this e-mail. Cliff
hi,
From the docs on stable priority queue:
"If a priority queue is configured to be stable, an integer timestamp is associated with each node, specifying the time ..."
I was one of the people discussing priority queue use cases, probably a year ago, and specifically was wanting a stable priority queue. I also said that adding a time stamp or counter to each entry was a naïve approach (and one that I had done myself in about an hour, adapting a std::priority_queue). I asked for a true, "native" implementation of a stable priority queue, because adding a time stamp to each entry has a couple of drawbacks:
1) It adds storage to each element - while for many (most?) applications this extra storage is negligible, in some cases it is not negligible (embedded systems with large queues) 2) It can fail - if a true time stamp is used, what happens when times are adjusted? If a counter is used, what happens when the counter overflows? While the failures are edge cases, there's no need to have any failures.
i remember this issue ... i need to have a closer look at the algorithms again. using a counter works for every algorithm, even if the algorithm cannot support a stable ordering `natively' ... tim -- tim@klingt.org http://tim.klingt.org Most of the trouble in this world has been caused by folks who can't mind their own business, because they have no business of their own to mind, any more than a smallpox virus has. William S. Burroughs
participants (6)
-
Cliff Green -
Michel MORIN -
Phil Endecott -
Thomas Klimpel -
Thorsten Ottosen -
Tim Blechmann