🔒 Locked

Compile performance notes.

Started by m4ttbush Nov 16, 2011 at 3:08 AM 11 replies 3.3k views

Original Post

Nov 16, 2011 at 3:08 AM

First of all, thanks Andreas for your work on AngelScript! It's been great to work with.
Our game project ( Dustforce ) is getting larger (~35,000 lines of AngelScript ) and as a result has started to take a long time to compile ( ~19 seconds )
19 seconds isn't too bad, but being able to quickly make changes and test the results is important for gameplay programming.

So I had a quick look at where that time was getting spent.

More than half the time was spent in [font="Lucida Console"]asCScriptEngine::ParseToken[/font] which didn't really surprise me.
But the line that was spending all the time did...


 if( stringLength == 0 )
 stringLength = strlen(string);

I traced the source back to the script builder add-on, and there's a few places where [font="Courier New"]ParseToken[/font] is called with 0 as the length which causes the length to be calculated again for every single token...

Fixing that got my compile time down to ~9 seconds which was exciting.

Another big one was [font="Courier New"]asCTokenizer::IsKeyWord[/font][font="Arial"] which I optimised away by making a [/font][font="Courier New"]std::map[/font][font="Arial"] from the [/font][font="Courier New"]tokenWords[/font][font="Arial"] array and searching the map for the token starting at length of the longest element and working down ( to avoid !is missing !isTrue etc ) and also replaced all the linear searches on that array where I could.[/font]
[font="Arial"]Here's my code:[/font][font="Arial"]

bool asCTokenizer::IsKeyWord()
 {
 int maxLength = sourceLength > 9? 9:sourceLength;
 
 while( maxLength > 0 )
 {
 char test[10];
 memcpy( test, source, maxLength );
 test[ maxLength ] = '\0';
 
 map<string, eTokenType>::iterator tokenI = tokenWordsMap.find( test );
 if ( tokenI != tokenWordsMap.end() )
 {
 tokenType = tokenI->second;
 tokenLength = maxLength;
 return true;
 }
 maxLength--;
 }
 
 return false;
 }

[/font]
[font="Arial"]This cut the compile time down to ~6 seconds which is pretty good.[/font]

The remaining 6 seconds doesn't look quite as easy to cut down, but a good amout of it appears to be spent in linear searches.

I understand that compile performance isn't really a priority for AngelScript at the moment, but these small changes might be useful for people with larger projects.
The ParseToken thing in CScriptBuilder should probably be fixed, I can try to work out how to submit a patch if you'd like. Otherwise I think you can just find-replace
[font="Courier New"]engine->ParseToken(&modifiedScript[pos], 0, &len);[/font]
with
[font="Courier New"]engine->ParseToken(&modifiedScript[pos], (int)modifiedScript.length() - pos, &len);[/font]
[font="Arial"]in scriptbuilder.cpp[/font]

And if anyone has any ideas on how to improve performance further, let me know!

Thanks.
-Matt

WitchLord

Nov 16, 2011 at 5:11 PM

Thanks a lot for these suggestions. I'll try to incorporate the changes as soon as possible.

vroad also contributed a patch for improving the compilation times. I've yet to apply it, but perhaps you wish to take a look at it for your own project in the meantime.

Patch from vroad

Regards,
Andreas

PS. DustForce looks like a cool game. I especially like how the player movement stirs the leafs. It's great to learn that you're using AngelScript to make the game.

FDsagizi

Nov 17, 2011 at 12:02 PM

this is a very important change, I fully support m4ttbush
I myself have to constantly reload scripts, now number of lines around 5k and it is already noticeable.

This is very noticeable when you compile your code while typing
Waiting for the new version!

droz

Nov 17, 2011 at 5:45 PM

My only concern is using libstdc++, as I use angelscript at work on a very ancient SH-4 security controller server. So if you add this could you please allow it to be disabled and revert back to the old method, something in as_config would work great.

TheAtom

Nov 17, 2011 at 6:06 PM

A long awaited change. Saving the bytecode helps a lot but it's of no use if I change something in one of the common headers causing almost everything to recompile. The project (a MMO server) has 125k lines of AS and still counting, compilation time exceeds one minute even on pretty adequate machines.

m4ttbush

Nov 17, 2011 at 7:04 PM

Thanks Andreas! (:
I'll take a look at vroad's patch.

Jeremy: I agree, I was only suggesting the script builder bug be fixed, the other stuff should be given more thought, and by someone better suited to the task than me!

WitchLord

Nov 17, 2011 at 11:57 PM

I've applied the fix to CScriptBuilder in revision 1044.

I'll take a closer look at the optimization you did for the IsKeyWord(). While I won't use std::map (for the same reasons that Jeremy stated) I should be able to do a similar optimization using my own asCMap implementation that is already in use in the library.

I would very much like to hear about other bottlenecks that you or other developers are seeing in the compilation performance. It's true that I don't prioritize compilation time, but that doesn't mean I can't make an effort once in a while when there is a specific point in the code with an issue.

Regards,
Andreas

WitchLord

Nov 20, 2011 at 5:22 PM

I've applied vroad's patch in revision 1050. It should improve compilation times quite a bit if the script contains a lot of literal string constants.

WitchLord

Nov 20, 2011 at 8:40 PM

I've implemented the improvement that you suggested in the asCTokenizer in revision 1054+1055.

I took it a step further, and split the keyword map in 2, one with the alpha keywords and the other with the non-alpha keywords. In most cases the algorithm can now make a shorter search in the map.

The final code looks like this (I reused the asCStringPointer that vroad implemented too):

[source]
bool asCTokenizer::IsKeyWord(const char *source, size_t sourceLength, size_t &tokenLength, eTokenType &tokenType) const
{
// TODO: optimize: This can probably be optimized further with a specialized algorithm
// As most keywords are shorter, then we should start from the shortest
// to the longest. Only for some of the keywords is it necessary to look
// for a longer part, e.g. ! and !is.

// Choose the best map
const asCMap *map;
int maxLength;

if( (source[0] >= 'a' && source[0] <= 'z') ||
(source[0] >= 'A' && source[0] <= 'Z') )
{
map = &alphaKeywordMap
// 'interface' is the longest alpha keyword
maxLength = sourceLength > 9 ? 9 : sourceLength;
}
else
{
map = &nonAlphaKeywordMap
// '>>>=' is the longest non-alpha keyword
maxLength = sourceLength > 4 ? 4 : sourceLength;
}

// Find the longest keyword that matches the start of the source string
while( maxLength > 0 )
{
asSMapNode *cursor;
if( map->MoveTo(&cursor, asCStringPointer(source, maxLength)) )
{
// Tokens that end with a character that can be part of an
// identifier require an extra verification to guarantee that
// we don't split an identifier token, e.g. the "!is" token
// and the tokens "!" and "isTrue" in the "!isTrue" expression.
if( maxLength < int(sourceLength) &&
((source[maxLength-1] >= 'a' && source[maxLength-1] <= 'z') ||
(source[maxLength-1] >= 'A' && source[maxLength-1] <= 'Z')) &&
((source[maxLength] >= 'a' && source[maxLength] <= 'z') ||
(source[maxLength] >= 'A' && source[maxLength] <= 'Z') ||
(source[maxLength] >= '0' && source[maxLength] <= '9') ||
(source[maxLength] == '_')) )
{
// The token doesn't really match, even though
// the start of the source matches the token
maxLength--;
continue;
}

tokenType = cursor->value;
tokenLength = maxLength;
return true;
}
maxLength--;
}

return false;
}
[/source]

I would very much like to know if the tokenizer is still one of the major bottlenecks in the compilation times. I have some ideas on how it can be improved even further, but I'm not sure how much worth there is in adding the extra complexity in the code.

m4ttbush

Nov 21, 2011 at 7:34 AM

Thanks Andreas!
Your [font="Courier New"]IsKeyWord[/font] optimization is faster than mine, it's down to ~5 seconds with revision 1055 (:

According to CodeAnalyst, about 30% of the remaining time is spent in [font="Courier New"]asCBuilder::GetFunctionDescriptions()[/font]
And another 20% is spent in [font="Courier New"]asCompareStrings()[/font]
[font="'Courier New"]
[/font]
Looks like speeding up those linear searches might help a bit, but don't worry about it too much if you have other things to do.

Thanks for taking the time to help with this, I really appreciate it!
-Matt

WitchLord

Nov 21, 2011 at 11:02 PM

Thanks. It's good to know the solution worked well. I have a little performance test that auto generates a script with ~40 thousand lines, and then compiles it. With the optimizations the compilation time improved almost 4 times, but the autogenerated script doesn't really reflect a real world script, so I wasn't too sure the improvements would be that good.

I'll see if I get the time to look into improving the GetFunctionDescriptions. 30% of the time is quite a bit, and it shouldn't be too difficult to replace the current linear searches by storing the functions in a map, similar to the enhancement done for the string constants by vroad.

The asCompareStrings() function is more difficult to improve. It would be easier to eliminate the string comparisons from the calling functions. Can you see where it is called the most? GetFunctionDescriptions() would be one one of them, but where else?

InvalidPointer

Nov 28, 2011 at 4:32 PM

As an additional, slightly dumb trick, have you investigated using something like Boost's flat_map structure? Since the number of tokens can be easily predicted and isn't likely to change at all once the lookup table is constructed, this could be an interesting (and fairly easy) way to avoid cache misses. For the uninitiated, it's basically a vector-based map structure that sorts the contents in a method similar to how std::map works instead of using a linked list structure to hold entries.

WitchLord

Nov 28, 2011 at 8:19 PM

Thanks for the tip. I'll have a look at boost's flat_map structure to see if it something I can easily use.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.