cgvis the IT thing

GGP Reasoner online

The General Game Playing Reasoner (C++, LGPL3) is now online. It consists of a logic unit (unify and such things, you remember from your AI course ) and a Game Description Language (GDL) abstraction layer.

You'll find it on the General Game Playing Website of TUD.

Fast std::string on the stack & fast string concatenator

So, as I promised, here are some techniques I used to speed up the logic system in the General Game Player module. The logic subsystem is using the standard unify-approach from the book Artificial Intelligence - A modern approach. By doing this there are a lot of string operations which were slow when using std::string for the strings and std::ostringstream for concatenation. On the other side, I did not wanted to loose the object oriented approach, so I did not used C-Strings.

But StackStrings These are small objects covering a C-String (char [] field) and providing operations like substr(), length() and conversion operators. The recursive unify algorithm garantuees that the length of the strings (at least most) will not get bigger, so it is possible to allocate the string on the stack and let all subfunctions use them. The string is not 0-terminated, it has it's length as a second member variable. This makes it possible to generate a substring just by providing a pointer and the length of the original string, without copying and inserting a 0.

How to use?

// Allocating by Hand
char field [length];
SString s (field, length);
// Doing this with a Macro
STACKSTRING (field, s, length);
s.setTo ("what ever you want it to have");
// now all functions can use s as long as the memory on the stack exists (no allocation & deallocation)

The profiler showed me no significant string operation consts anymore; before it was >50% just by allocation & deallocation.

The other slow part I found was std::ostringstream for string concatenation. When you gurarantee, that all strings live until the final concatenation, then you can use it. Original std::ostringstream copies all and does some thread locking which was not necessary for me.

FastStringCollector collector;
std::string a; SString b; // for SString see above
collector << a << b;
std::string c = collector.str(); // collection will be done all here.

So both classes are not as powerful as the C++ STL variants but much faster in the special cases for me.

The stackstring can be fond here: stackstring.h
The fast collector here: faststringcollector