EDIT 2009-08-11: The patch has been updated to fix a memory leak. Please un-apply your old patches and apply the new 1.2 version.

EDIT 2009-10-15: TGE users will need to make an additional change. Scroll down for details.

(Too long; didn't read; just give me the code!)

Introduction

Try this script. Just open up a Torque console and type it in:

for ($i = 0; $i < 1000000; $i++) { $j++; }

Now try this one:

for ($i = 0; $i < 1000000; $i++) { getWord("abcd efgh", 1); }

Finally, try this one:

function addJ() { $j++; }
for ($i = 0; $i < 1000000; $i++) { addJ(); }

Go on; try it. I'll wait. And if you're running a stock build of TGB and your machine is anything like mine, so will you. A lot. You don't need a stopwatch to tell you there's something seriously wrong here. But for the sake of the scientific method, I'll show some numbers. First, I've put together a small suite of tests for this resource:

function addJ() { $j++; }
function addThree(%a, %b, %c) { return %a + %b + %c; }

function swapWords( %words, %first, %second )
{
	%numWords = getWordCount(%words);

	if( ! ( ( 0 == %numWords) ||
		(%first < 0) ||
		(%first >= %numWords)  ||
		(%second < 0)  ||
		(%second >= %numWords) ||
		( %first == %second) ) )
	{
		%tmp = getWord( %words , %first );
		%words = setWord( %words , %first , getWord( %words , %second ) );
		%words = setWord( %words , %second , %tmp );

	}

	return %words;
}

function tsSpeedTest()
{
	%before = getRealTime();
	for (%i = 0; %i < 1000000; %i++) { $j++; }
	%after = getRealTime();
	echo("Test #1: " @ (%after - %before) @ " ms");

	%before = getRealTime();
	for (%i = 0; %i < 1000000; %i++) { getWord("abcd efgh", 1); }
	%after = getRealTime();
	echo("Test #2: " @ (%after - %before) @ " ms");

	%before = getRealTime();
	for (%i = 0; %i < 1000000; %i++) { addJ(); }
	%after = getRealTime();
	echo("Test #3: " @ (%after - %before) @ " ms");

	%before = getRealTime();
	for (%i = 0; %i < 1000000; %i++) {
		%a = 1; %b = 2; %c = 3;
		%d = %a + %b + %c;
	}
	%after = getRealTime();
	echo("Test #4: " @ (%after - %before) @ " ms");
	
	%before = getRealTime();
	for (%i = 0; %i < 1000000; %i++) { addThree(1, 2, 3); }
	%after = getRealTime();
	echo("Test #5: " @ (%after - %before) @ " ms");
	
	%before = getRealTime();
	for (%i = 0; %i < 1000000; %i++) { swapWords("this is a test", 0, 3); }
	%after = getRealTime();
	echo("Test #6: " @ (%after - %before) @ " ms");
	
	%before = getRealTime();
	for (%i = 0; %i < 1000000; %i++) { swapWords("this is a test that is longer", 0, 3); }
	%after = getRealTime();
	echo("Test #7: " @ (%after - %before) @ " ms");
}

Test #1, #2, and #3 are the first three tests from above.

swapWords() is taken from Edward F. Maurina III's TSTK page, and is mainly used as an example of a function that does a little actual work instead of the other tests, which are more trivial.

I should point out that getRealTime() on Windows uses the Windows API function GetTickCount() under the hood, which has a granularity of about 17 milliseconds, so it's not the most accurate thing in the world, but these numbers are so drastically different that it's accurate enough:

[TGB-stock]
==>tsSpeedTest();
Test #1: 640 ms
Test #2: 1152 ms
Test #3: 19456 ms
Test #4: 1280 ms
...

OK, so a tight loop with a million iterations takes just over half a second (#1), and one with a single built-in function call takes just over 1 second (#2). That's decent enough. But then we get to #3. 20 seconds? Roughly a 2900% slowdown for the crime of using a scripted function? It gets even worse if your function has a few arguments, as evidenced by tests #5-#7:

...
Test #5: 63872 ms
Test #6: 93824 ms
Test #7: 94976 ms

Wow. That's harsh.

Just to be sure, I tried this on a different Torque project on a different computer and the results were not nearly as bad. I also tried it in the console of all the Torque demos available for download and got better results as well. What the heck is going on?

The Torque Memory Manager

Into the debugger we go. Most of the lines I'm stepping over look harmless enough: an addition here, a hash lookup there. But then I run into this:

consoleInternal.cc, line 483:
   Dictionary *newFrame = new Dictionary(this);

Uh-oh. I've seen this problem before: a new hash table each time. And it brought its friends:

consoleInternal.cc, lines 297,301:
      hashTable = new HashTableData;
      ...
      hashTable->data = new Entry *[hashTable->size];

And what are those hash tables for? The variables in a particular stack frame. And each variable comes with yet another allocation:

consoleInternal.cc, line 249:
   ret = new Entry(name);

Then it hit me: In the other Torque project, I had defined TORQUE_DISABLE_MEMORY_MANAGER a long time ago. Apparently the default with TGB is to have the Torque memory manager enabled, and it seems this wreaks havoc on TorqueScript speed. Recompiling and trying the scripts again gave me the following results:

[TGB-stock-TDMM]
==>tsSpeedTest();
Test #1: 512 ms
Test #2: 1152 ms
Test #3: 2816 ms
Test #4: 1152 ms
Test #5: 12416 ms
Test #6: 18560 ms
Test #7: 19328 ms

(Note: To calculate speed up percentage, I have used the formula speedUp = ((oldTime / newTime) - 1) * 100. So, for example, if the old time is 100 and the new time is 75, that's ((100 / 75) - 1) * 100 = 33% speed up)

No real difference in #1, #2, or #4 (although none was expected), but a 600% speed up over the previous results in #3, 410% in #5 and #6, and 390% in #7. It seems the Torque memory manager is not so efficient with lots of tiny little allocations and deallocations, which Torque does A) every time a script enters a new stack frame (a.k.a. calls a user function), and B) every time a new variable is declared (including parameters to a function). (A) is bad enough, and (B) just makes it worse, since local variables are "new" every time a function is run. We're getting nickel-and-dimed to death.

I encountered this problem in writing the first (scripted) version of my SCXML state machine, and it was a killer. Lots of little support functions meant damage to the frame rate even with only a few instances running, and every transition and state used a scripted callback as well.

Now, I hear that the memory manager brings good things to the table, and that it's suitable for production code. I've also heard it's been disabled in TGEA because it was too problematic. So I'm not entirely sure what to believe. But I'd rather err on the side of caution and try to get something that works both ways.

The easiest thing to do is just to add a bunch of preprocessor directives that disable the Torque memory manager only for the code in consoleInternal.cc. But the whole problem got me thinking about various other advanced memory management techniques -- would it be possible to speed things up further?

Free Lists

My first attempt at this was to create a simple free list implementation and then use it for the script stack frame allocations. With a few exceptions, most of the allocations are fixed-size, so this makes them suitable for free lists. The allocation of hashTable->data presents a little problem, because it's not a fixed-size array. Or is it? It's designed to grow if too many variables get defined, but the initial allocation is always the same:

consoleInternal.cc, lines 300-301:
      hashTable->size = ST_INIT_SIZE;
      hashTable->data = new Entry *[hashTable->size];

ST_INIT_SIZE is 15 by default, and the hash table doesn't grow until the number of variables reaches more than twice that. In practice, most scripted functions won't ever need 30 different variables, so as long as we have a way of keeping track of where we allocated our memory from, we can effectively consider this array to be fixed-size as well and yet still throw it back to the right memory pool when we're done with it.

My free list implementation for this was quick and dirty, but the main goal was first to make sure that it could work. The plus side is that allocations and deallocations become a constant-time operation and only involve changing a few pointers, whereas the minus side is that these structures are never released back to the heap unless you explicitly purge them (again, there are other implementations which may not have this problem; this is just how mine works).

After putting in the code changes, I re-ran the benchmarks from the beginning:

[TGB-freelist-TDMM]
==>tsSpeedTest();
Test #1: 640 ms
Test #2: 1280 ms
Test #3: 1664 ms
Test #4: 1152 ms
Test #5: 11136 ms
Test #6: 16000 ms
Test #7: 16640 ms

That's a 70% speed up for #3 over the previous run. But #5 has barely changed, and it's only a 16% speed up for #6 and #7. And #5-7 are probably more likely in real-world situations. There's room for improvement there.

The Frame Allocator

Another thing that we can take advantage of with the script execution code is the fact that the access pattern is essentially stack based, which would make sense, considering they're implementing script stack frames. One of the things found in compiledEval.cc are these lines:

compiledEval.cc, lines 473-474:
   static S32 VAL_BUFFER_SIZE = 1024;
   FrameTemp<char> valBuffer( VAL_BUFFER_SIZE );

OK, so this means it's safe to use the frame allocator. If you're not familiar with Torque's frame allocator, you can read this, but basically it's an allocation strategy for temporary memory that only needs to add to a single value, and mass deallocation can occur simply by decreasing this value. The catch is that memory basically has to be deallocated in the reverse order in which it was allocated. But again, with a few exceptions, that's almost a perfect fit for script execution.

Now there are some different problems to deal with. As with the free list solution, the size of hashTable->data is variable. And as with that one, I chose to speed up the initial allocation and then fall back on the regular allocation for any subsequent enlargements. The next problem is that not all Dictionary objects are suitable for the frame allocator. All global variables are kept in a Dictionary created at the beginning of the program, and new global variables can be created at any time. In order to keep everything working, Dictionary and supporting code had to be aware of whether or not it was allocated using the frame allocator and use the proper deallocation mechanisms when necessary. Therefore, for global variables, I chose not to use the frame allocator at all -- it acts just as before. Yet another problem is that of stack frame references. In the script code, it is possible to push a reference to a previous stack frame. This is mainly done during the exec() and eval() functions to allow the evaluated script to have access to the local variables of the calling code, but what it means is that if new local variables are created in a stack frame that is not the topmost stack frame, they would be trashed by the frame allocator when the stack frame reference was popped, and we can't have that. So, again, we fall back to the regular allocator for any exceptions to our rules. It'll be a little slower, but at least the majority of the code will be faster.

With the frame allocator version, here are the results:

[TGB-frame-TDMM]
==>tsSpeedTest();
Test #1: 768 ms
Test #2: 1024 ms
Test #3: 1536 ms
Test #4: 1280 ms
Test #5: 9344 ms
Test #6: 14592 ms
Test #7: 15744 ms

Comparing against [TGB-stock-TDMM], we've got 83% speed up in #3, 33% in #5, 27% in #6, and 23% in #7.

Preallocation

I realized, however, that there's another thing I was missing here -- the allocation of storage for variable values. When Torque calls a scripted function, it also creates a copy of all the string arguments passed in. Since we have the frame allocator handy, I figured it was possible to alleviate that as well by allocating small strings with the frame allocator. By default these strings are 16 bytes, but this can be changed with a #define. 16 bytes is large enough to store the string representation of a 32-bit integer or float, and if the value size goes over, then we can fall back on the existing allocator. As before, the results:

[TGB-frame-prealloc-TDMM]
==>tsSpeedTest();
Test #1: 640 ms
Test #2: 1152 ms
Test #3: 1280 ms
Test #4: 1280 ms
Test #5: 7808 ms
Test #6: 12160 ms
Test #7: 13952 ms

Not too shabby. Comparing against [TGB-frame-TDMM], that's another 20% speed up for #5 and #6, and 13% for #7. Against [TGB-stock-TDMM], that's a grand total of 120% speed up for #3, 60% for #5, 53% for #6, and 39% for #7.

I see this last addition as benefitting any functions that make use of local variables (either as parameters or just internally). The more variables with small values that your function uses, the more you'll get out of it.

Lastly, I mentioned above that there may be reasons you want to use the Torque memory manager. So I tried turning it back on while keeping my code changes:

[TGB-frame-prealloc]
==>tsSpeedTest();
Test #1: 640 ms
Test #2: 1280 ms
Test #3: 1280 ms
Test #4: 1408 ms
Test #5: 7936 ms
Test #6: 11904 ms
Test #7: 16768 ms

There's some speed loss in #7, but overall the results are nearly the same as before, and a far sight better than running stock TGB with the memory manager enabled.

Conclusion

For faster script execution right off the bat, TORQUE_DISABLE_MEMORY_MANAGER will net you a big gain. I mention this mainly for TGB, because this is the default, and for non-pro TGB, it can't be changed. (Maybe TGB 1.7.5 could fix this?) Beyond that, replacing the memory allocator used by TorqueScript with the frame allocator where possible and preallocating space for small variable values gave anywhere from 40-120% speed up in the above tests. Depending on how much script you're executing, this could mean the difference between skipping a frame or not.

While this resource does not address the fundamental speed issue with TorqueScript (namely, over-reliance on strings), it can help cut out some of the fat in the current system. I haven't seen any of the new T3D stuff, so I don't know if this has already been addressed or what, but until all the new stuff is released, I'm hoping this will help.

After putting up with reading this, you'd probably like to have the code. I've created a diff patch for TGB Pro 1.7.4. It may or may not work for the other Torque variants.

Download the patch

EDIT 2009-08-11: The patch has been updated to fix a memory leak. Please un-apply your old patches and apply the new 1.2 version.

Drop it into the main Torque directory and then run the following from the command line:

patch -p0 < tsFrameAllocator-1.2.patch

(If you're running Windows and don't have the patch program, you can get it here.)

If you want to change the preallocation size, it is defined as SMALL_STRING_SIZE in consoleInternal.cc. Make sure to use increments of 16 bytes, since TorqueScript's string code rounds up to boundaries of 16 bytes anyway.

Please let me know how it works for you. (Do you get a noticeable improvement? Is it still stable? Any memory leaks? How does it work with the engines other than TGB? etc.)

EDIT 2009-10-15: TGE users will need to make an additional change.

If you are applying this patch to TGE (and maybe other engines as well), you will also need to make the following change in game/game.cc, function GameRenderWorld():

void GameRenderWorld()
{
   PROFILE_START(GameRenderWorld);
   FrameAllocator::setWaterMark(0);
...
   AssertFatal(FrameAllocator::getWaterMark() == 0, "Error, someone didn't reset the water mark on the frame allocator!");
   FrameAllocator::setWaterMark(0);
   PROFILE_END();
}

becomes

void GameRenderWorld()
{
   PROFILE_START(GameRenderWorld);
   U32 waterMark = FrameAllocator::getWaterMark();
   FrameAllocator::setWaterMark(waterMark);
...
   AssertFatal(FrameAllocator::getWaterMark() == waterMark, "Error, someone didn't reset the water mark on the frame allocator!");
   FrameAllocator::setWaterMark(waterMark);
   PROFILE_END();
}

The cause of the TGE problem is that the original code, FrameAllocator::setWaterMark(0), assumes that it has access to the full memory space of the frame allocator. If you are running TGEA or Torque 3D, you may need to search the code and make sure there are no other similar calls like this. If so, they should be replaced by calls that save and restore the frame allocator watermark as above.