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<string, eTokenType>[/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

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.

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!

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.

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.

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!

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

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.

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<asCStringPointer,eTokenType> *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<asCStringPointer, eTokenType> *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.

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