Re: [Boost-build] Help optimizing a slow BJAM build

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 :-(

- Volodya