From: Jurko Gospodnetiæ (jurko.gospodnetic_at_[hidden])
Date: 2008-04-09 09:48:21
I have taken a look at the proposed patch and it seems to work
properly. It changes only the list_sort() function and does it by
replacing a merge sort with a quick-sort algorithm. It introduces an
extra memory allocation and deallocation for each list_sort() call
(temporary storage used for calling the C qsort() function) but this
does not seem to slow down the build system.
As for the build timings - we have not seen any improvement when
comparing the current trunk version with and without the patch applied.
In fact the milestone 12 bjam seemes a tiny bit faster then the trunk
I do not think the patch should be applied to the trunk until someone
can present a better use case/usage description where benefits can be
seen & reproduced.
I have not analyzed the original implementation or how and why it
could be slower than quick-sort. I have also not counted the number of
copies done while executing the original merge sort algorithm.
The only problem I see with this function, and it is the same problem
that exists in the original implementation and is spread out through
most of bjam's list management routines, is that it depends heavily on
bjam *never* releasing any memory allocated to store its string data. If
that were ever to change then freeing the original list passed as a
parameter would mess up the newly sorted list (they contain pointers to
shared and not reference counted string data) and not freeing the
original list would cause memory leaks (list node structures would be
I'm attaching some profiling results from my project. All profiling
has been done under cygwin using the following commands:
time ( bjam_old -a -n Development toolset=msvc variant=debug -d0 -d+10 )
> log_old.log 2>&1
time ( bjam_new -a -n Development toolset=msvc variant=debug -d0 -d+10 )
> log_new.log 2>&1
time ( bjam_m12 -a -n Development toolset=msvc variant=debug -d0 -d+10 )
> log_m12.log 2>&1
where 'Development' is name of the main test project target, bjam_m12
is the name of the boost build milestone 12 executable, bjam_old is the
trunk bjam version and bjam_new is the patched trunk bjam version.
Trunk version used is revision 44110.
Note that the cygwin time command does not seem to display the
correct user & system time and that the internal Boost profiling result
table sometimes displays negative times which seems strange. :-)
Hope this helps.
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