From: Vladimir Prus (ghost_at_[hidden])
Date: 2008-04-09 04:24:59
On Friday 04 April 2008 21:52:18 Igor Nazarenko wrote:
> > It's somewhat hard to say, since apparently the counters overflow.
> Oh. How does one tell that they overflowed? In fact, is there some
> documentation on the profiling output somewhere?
> >> Looking at the source code of SORT in lists.c, it seems to me that the
> >> function (list_sort) is more complicated than it needs to be, and may
> >> be degrading to quadratic behavior on somewhat-pre-sorted lists.
> > Why? It's standard merge sort, which is O(N*logN).
> I'm not sure why: the code is a bit too much for me to follow in my
> head. However, I hacked that function to print the number of elements
> in the list and the number of split/merge iterations it does. I only
> print it if the number of elements is above 1000. Here's the output:
> $ bjam variant=debug,release
> Fri Apr 4 10:26:42 2008
> : entering list_sort for 46198 elements
> Fri Apr 4 10:27:03 2008
> : exiting list_sort after 5223 iters
Is this the number of top-level interations? It indeed does not look
like logN :-(
Boost-Build list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk