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

From: Jurko Gospodnetiæ (jurko.gospodnetic_at_[hidden])
Date: 2008-04-09 09:48:21

   Hi.

   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 
version.

   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 
leaked).

   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.

   Best regards,
     Jurko Gospodnetiæ