Re: [jamboost] bjam performance [was: how to skip regenerating the dependency tree]

From: Rene Rivera (grafik.list_at_[hidden])
Date: 2004-05-17 08:23:45

Toon Knapen wrote:
> 
> So I was interested in this info and tried to get a profile of a typical 
> bjam run. So I ran 'bjam lib' on my project with all targets up to date 
> to avoid influencing the timing with calls to the compiler or linker.
> 
> First conclusions :
> 25% of time is spend in hashitem, 19% in string_append and 15% in 
> var_expand (the total run took 264 seconds) (profile in attach)

I did some investigations over the weekend on why things are so slow... 
As you point out there are a small number of places that eat up most of 
the time. For hashitem, it's calculating the hash value for strings that 
takes all the time. I did some minor changes and got a 2x speed increase 
in that but that's not a significant impact overall. The next item to 
take up time is string_append. -- not much I could do to that one. And 
lastly we come to var_expand. This is the one that we should focus on. 
The biggest time sink on this one is the number of calls it makes to 
string_append and newstr, which multiply as it's a recursive function.

There are a few things one might try to improve:

1. The performance of hash tables. Some possibilities are: to use a tri 
instead of hashing; to augment strings to have a hashvalue with them (to 
reduce re-calculation of the hash value).

2. The performance of newstr. For this we'd need to find an alternative 
storage for string reuse which is currently the heaviest use of the hash 
tables (that is, don't use hashitem in newstr). Another possibility here 
is to remove the requirement of having immutable strings. If strings 
could get deleted there might not be a need to attempt to reuse strings.

3. Performance of variable expansion. This boils down to both improving 
the performance of newstr (which calls hashitem), and reducing the 
number of calls to string_append. So if one is brave enough doing a 
rework of that code might improve things.

And lastly we could see where in Boost.Build is taking up most of the 
time and improving at that end so that it doesn't do as much var 
expansions. Using the -d+10 option it looks like get-properties, and 
simplify-path-tokens are the big time culprits.

-- 
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org - grafik/redshift-software.com - 102708583/icq