Actionscript3, Flash, Scala, Java, C#, C++, Algorithms & Imageprocessing
I am definitly not good at choosing names for software projects. However TurboDieselSportInjection is a release of my experiments from yesterday. It is a spinoff from the whole framework and allows you to inline __bytecode and of course to use the new Memory API.
Hopefully you are kind enough to provide me with some feedback. I am especially interested in Exceptions that occur when reading or writing ABC files. Have fun!
Update: TDSI is now open source!
Today I had to do something else than backend development and since FOTB is getting closer and I could not really continue working on TAAS I decided to add something which is easy to implement and has a huge benifit: Alchemy support in ActionScript.
So what is the idea? TAAS is part of a framework I developed to manipulate SWF, SWC and ABC files. The main focus are of course ABC files since they contain the bytecode which gets executed.
Part of the framework are tools for control flow analysis, various bytecode analyzers and also a search-and-replace system which work on a bytecode level. There are for instance pattern matchers that search for bad code produced by the ASC and replace the match with a more performant set of instructions.
With all those weapons in my arsenal I thought it should be a walk in the park to implement the Alchemy features in a way that makes sense. So the first idea is to have the old functionality AS3C had but more robust. AS3C had a feature that was the __asm function which allowed you to inline instructions. The new framework comes with the old __asm and also another cool method: __bytecode! This will inline raw bytes. This means also you would have to know all the indices for variables you want to use from the constant pool in advance so __asm will still be your friend.
With the __bytecode method it is already possible to use all Alchemy features again. It would also be possible with the __asm method but writing plain bytes is simply more elitist. In order to make it easy for the developer I want a high-level API. Having a class with some static methods is nice of course but also slow. Alchemy is fast because those opcodes that write and read from a ByteArray are no method calls. They are low-level FlashPlayer features.
The first attempt was to write a Memory class that allows you to use the Alchemy features. This class contains raw bytecode implementations and ActionScript code. This means if you do not use the optimizer everything will still work — only 1000 times slower. When looking at the memory class there is another tool of the framework that becomes very helpful. Both the __bytecode and ActionScript stuff should not co-exist with each other. So when we inline the bytecode a dead-code-elimination will simply cleanup afterwards. Since the 0x47 byte for instance is “ReturnVoid” the ActionScript code which would follow afterwards can be dropped. That code is now unreachable.
Step two is to replace all calls to the Memory class with the correct Alchemy opcode. This was really simple and the result is a really really fast way to access a ByteArray while still maintaining a high comfort. Of course one might think now that the __bytecode method becomes useless since no methods of the Memory class are called at all. But if anyone is crazy enough to access the Memory class untyped with a runtime namespace for instance you are still happy to have the code optimized inside. In some circumstances it is simply impossible to figure out that someone called Memory.writeByte(). End of the story: your calls to a ByteArray are always optimized in the best way possible.
This is an example of the Memory.readByte() method before applying optimizations:
0x000000 GetLocal0
0x000001 PushScope
0x000002 FindPropStrict QName(PackageNamespace("com.joa_ebert.abc.bytecode.asbridge"), "__bytecode")
0x000004 PushShort 0xd1
0x000007 PushByte 0x35
0x000009 PushByte 0x48
0x00000b CallPropVoid QName(PackageNamespace("com.joa_ebert.abc.bytecode.asbridge"), "__bytecode"), 3
0x00000e GetLex QName(PackageNamespace("flash.system"), "ApplicationDomain")
0x000010 GetProperty QName(PackageNamespace(""), "currentDomain")
0x000012 GetProperty QName(PackageNamespace(""), "domainMemory")
0x000014 GetLocal1
0x000015 SetProperty QName(PackageNamespace(""), "position")
0x000017 GetLex QName(PackageNamespace("flash.system"), "ApplicationDomain")
0x000019 GetProperty QName(PackageNamespace(""), "currentDomain")
0x00001b GetProperty QName(PackageNamespace(""), "domainMemory")
0x00001d CallProperty QName(PackageNamespace(""), "readUnsignedByte"), 0
0x000020 ReturnValue
The same method after inlining the bytes and applying various other analysis like dead-code-elimination:
0x000000 GetLocal0
0x000001 PushScope
0x000000 GetLocal1
0x000001 GetByte
0x000002 ReturnValue
This is an example of the famous inverse square root using the Memory API:
private function invSqrt( value: Number ): Number
{
var half: Number = 0.5 * value;
Memory.writeFloat( value, 0 );
Memory.writeInt( 0x5f3759df - ( Memory.readInt( 0 ) >> 1 ), 0 );
value = Memory.readFloat( 0 );
value = value * ( 1.5 - half * value * value );
return value;
}
The same method before optimization in bytecode representation:
0x000000 GetLocal0
0x000001 PushScope
0x000002 PushDouble 0.5
0x000004 GetLocal1
0x000005 Multiply
0x000006 ConvertDouble
0x000007 SetLocal2
0x000008 GetLex QName(PackageNamespace("com.joa_ebert.abc.bytecode.asbridge"), "Memory")
0x00000a GetLocal1
0x00000b PushByte 0x0
0x00000d CallPropVoid QName(PackageNamespace(""), "writeFloat"), 2
0x000010 GetLex QName(PackageNamespace("com.joa_ebert.abc.bytecode.asbridge"), "Memory")
0x000012 PushInt 0x5f3759df
0x000014 GetLex QName(PackageNamespace("com.joa_ebert.abc.bytecode.asbridge"), "Memory")
0x000016 PushByte 0x0
0x000018 CallProperty QName(PackageNamespace(""), "readInt"), 1
0x00001b PushByte 0x1
0x00001d ShiftRight
0x00001e Subtract
0x00001f PushByte 0x0
0x000021 CallPropVoid QName(PackageNamespace(""), "writeInt"), 2
0x000024 GetLex QName(PackageNamespace("com.joa_ebert.abc.bytecode.asbridge"), "Memory")
0x000026 PushByte 0x0
0x000028 CallProperty QName(PackageNamespace(""), "readFloat"), 1
0x00002b ConvertDouble
0x00002c SetLocal1
0x00002d GetLocal1
0x00002e PushDouble 1.5
0x000030 GetLocal2
0x000031 GetLocal1
0x000032 Multiply
0x000033 GetLocal1
0x000034 Multiply
0x000035 Subtract
0x000036 Multiply
0x000037 ConvertDouble
0x000038 SetLocal1
0x000039 GetLocal1
0x00003a ReturnValue
The same method after inlining the Memory API:
0x000000 GetLocal0
0x000001 PushScope
0x000002 PushDouble 0.5
0x000004 GetLocal1
0x000005 Multiply
0x000006 ConvertDouble
0x000007 SetLocal2
0x00000a GetLocal1
0x00000b PushByte 0x0
0x000000 SetFloat
0x000012 PushInt 0x5f3759df
0x000016 PushByte 0x0
0x000000 GetInt
0x00001b PushByte 0x1
0x00001d ShiftRight
0x00001e Subtract
0x00001f PushByte 0x0
0x000000 SetInt
0x000026 PushByte 0x0
0x000000 GetFloat
0x00002b ConvertDouble
0x00002c SetLocal1
0x00002d GetLocal1
0x00002e PushDouble 1.5
0x000030 GetLocal2
0x000031 GetLocal1
0x000032 Multiply
0x000033 GetLocal1
0x000034 Multiply
0x000035 Subtract
0x000036 Multiply
0x000037 ConvertDouble
0x000038 SetLocal1
0x000039 GetLocal1
0x00003a ReturnValue
As you can see this is blazing fast. Now the next job is to finish TAAS. Once TAAS is complete even a method like the inverse square root might be inlined and optimized much better. I did a simple test using the Lorenz attractor from before and replacing the Vector.<uint> buffer with a ByteArray gave a performance boost of about 5fps. Afterwards I tried getting rid of the Particle class completly and the framerate dropped a little bit. But imagine having 300.000 particle’s x, y and z coodrinates stored in an Array. It was still faster than the old version but not as fast as combining the power of Alchemy with simple ActionScript optimizations like linked lists.
I just want to share with you how Taas can actually optimize code and what happens behind the scenes. So in my last post I talked about stackless code and optimizations that are possible but how does it work at all?
Imagine you have got this ActionScript code:
var x: Number = 1.0;
var y: Number;
if(true)
{
y = 3.0;
}
else
{
y = 2.0;
}
x += y;
return x;For the sake of simplicity I will not use local variables in the bytecode. But it will be easier to figure out what happens in the bytecode.
PushDouble 1.0
PushTrue
IfTrue L0
PushDouble 2.0
Jump L1
L0: PushDouble 3.0
L1: Add
ReturnValueThis bytecode is nearly the same as the method but without local variables. This should be fairly simple to understand.
When converting bytecode to Taas, its corresponding control flow graph is converted into a control flow graph of Taas expressions. I do not want to go into much detail how the stack based code is converted but here is the graph before and after the transformation from bytecode to Taas. It looks quite similar but there is a major difference. All those constant values in the Taas graph are not values pushed on a stack but assignments to virtual variables which exist only in theory. You can see also that the Add in the bytecode has known operands and type in the Taas version. Since it is currently not know if 2.0 or 3.0 has been used there is a Φ function that says “This value is either 2.0 or 3.0 depending on the path taken at runtime”.
So as I said this code can be optimized much better than stack based code. This graph is very redundant. There are three utilities to compact and simplify the current graph of Taas expressions. The algorithm has been developed for Java bytecode but works with ActionScript very well tool. The concept is quite simple. Perform copy propagation, constant folding and dead code elimination until the graph stops changing. Applying these techniques to the Taas graph yields the following results.
Most of the theoretical variables have been eliminated using copy propagation.
Known constants have been replaced. Even the if condition is no longer needed and the false branch has been removed. The dead code elimination will clean up this code afterwards.
Dead code elimination has removed the dead Jump statement and also the value 2.0 from the Φ expression. Afterwards constant folding replaced the Φ expression with its one constant value. Then another iteration of constant folding replaced the Add expression with the constant value 4.0. Afterwards copy propagation has put the result into the Return statement and voilá.
This result may have seemed quite obvious from the beginning and you may ask who writes such code. Probably nobody. But once you start inlining methods this makes a lot of sense. A lot of preconditions are known in that case and unnecessary branches can be removed. Since inlining methods bloats up the code it is very important to compact it afterwards as much as possible. I hope you see now how interesting all of this might be in the future.
