BNet2.0 Will Harm Custom Content - Page 12

Concerns about the Galaxy language

Hello, I have some concerns about the Galaxy language after examining data from the StarCraft II beta. First off, this list only contains issues which are not easily fixable with a preprocessor or a higher level language, some of it are just guesses which may or may not be wrong.

Dynamically allocated records
There is an error which implies that this isn't supported. This is quite an important issue since if this isn't supported it renders garbage collection, records and pointers pretty much useless.

You can't reference a record before it's defined
You fixed the chicken and egg problem with functions, please do the same for records.

Garbage collection
I don't know if and how garbage collection will work in Galaxy, but I'm confident you will screw it up anyway.

Function pointers
There doesn't seem to be any sign of function pointers. However TriggerCreate references to functions be strings, which is bad news, if Galaxy supports function pointers or not. If Galaxy doesn't support them (I'd slap the idiot who suggested that), I'll pray that there will be a way to execute triggers directly in the same and a new thread.

Fixed point arithmetics
Fixed point arithmetics, while good in certain scenarios can cause problems with doing more complex calculations. There doesn't seem to be alternative float type you can use to avoid the problems.

If you want to read more about my findings with Galaxy, I suggest you visit this thread: http://www.wc3c.net/​showthread.php?t=1090​11 (Viewing requires registration for some reason)

I have some additional concerns after studying the language and API further.

Associative arrays
This is a very important structure, which allows you to attach, e.g., a structure to a unit. In JASS2, the "return bug" was utilized to get an integer from a native type which was used as an index into an array, or previously as an string to a gamecache entry. This allowed you to construct an associative array. When the return bug was fixed, new natives was introduced (thank god Vexorian managed to convince you!) to replace that specific use of the return bug.

Galaxy has a more advanced type system with structures and pointers, which basically means it has a infinite number of types. Creating natives to return a index for a subset of these types would be a bad solution. You could however:
- allow every scalar value to be typecasted to an integer. We could use the integer as an index to a fixed size hashtable. This may however perform bad in a poor VM (which is probably the kind Galaxy will get).
- add a new type to the language which syntax similar to an array, e.g. int[string] map, which would be a mapping from integers to strings. You could use it in code like map["hello"​] = 3.

These two solutions are rather unclean and mess up the language. A much better solution would be to implement boxing (see http://en.wikipedia.​org/wiki/Boxing_(comp​uter_science)). This would add a new native type which you could call 'object' or 'box'.
A box would contain a value of the type of this value. The type should be reduced to a simple integer ID at compile time to allow quick comparison of types. You could then for example box an object by doing this:
object b = 5;
This could be represented by by an opcode 'box', e.g., box(5, int) -> b, where int would be an integer representation of the type. Unboxing could be done like this:
int i = b;
This could be represented by by an opcode 'unbox', e.g. unbox(b, int) -> i. If you tried the following:
unit u = b;
This would result in unbox(b, unit) -> u. The unbox opcode would compare the type stored in the box b (int) to the argument in the unbox (unit), if they don't match (like now) it should raise a runtime error.

Now you could simply add a type and some natives to implement a map, here is an example for such natives:
native map MapCreate();
native void MapClear(map m); // Removes all the key/value pairs in the map.
native bool MapCompare(map a, map b); // Returns true if all the key/value pairs of map 'a' is equal to all the key/value pairs of map 'b'.
native void MapMerge(map m, map other); // Overwrites the key/value pairs in 'm' with those in 'other'.
native void MapSet(map m, object key, object value);
native object MapGet(map m, object key); // This should raise a runtime error if the key doesn't exist.
native bool MapHasKey(map m, object key);
native void MapFindValue(map m, object value, object *result); // Sets variable 'result' to the key if a key with the value 'value' was found. Sets the variable 'result' to null if no keys with the value 'value' was found.
native bool MapDeleteKey(map m, object key); // Returns true if the key was found and thus deleted.
native void MapDestroy(map m);


API Design
Native functions should not use function pointers unless absolutely required. In the case that it's required (events/timers), you should be able to pass along a boxed type to reduce the need for associative arrays.

The native functions that work on groups should not use function pointers. Here is some examples of possible ways to loop over a group:
unit *u = UnitGroupFirst(group​);
while(u) {
RemoveUnit(*u);
u = UnitGroupNext(group, u);
}

object u = UnitGroupFirst(group​);
while(u) {
RemoveUnit((unit)u);
u = UnitGroupNext(u);
}

int i;
int count = UnitGroupCount(group​);
while(i < count) {
RemoveUnit(UnitGroup​Unit(group, i);
i += 1;
}

You seem to have gone with the last approach, which is basically a dynamic array of units. So why not implement a dynamic array instead, and get rid of those group types?
Here is an example of natives to represent a dynamic array:
native array ArrayCreate();
native bool ArrayCompare(array a, array b); // Returns true if all the elements of array 'a' is equal to all the elements of array 'b'.
native array ArrayConcat(array a, array b); // Adds the elements of array 'b' to the end of array 'a'.
native array ArrayRange(array a, int start, int stop); // Returns the elements from start to stop as a new array.
native int ArraySize(array a);
native void ArrayResize(array a, int size);
native object ArrayGet(array a, int index);
native void ArraySet(array a, int index, object value);
native void ArrayInsert(array a, int index, object value);
native int ArrayPush(array a, object value); // Adds the object to the end of the array. Returns the number of elements in the array after the addition.
native object ArrayPop(array a); // Removes and returns the object at the end of the array.
native bool ArrayFind(array a, object value); // Returns true if the object was found.
native void ArrayDelete(array a, int index);
native bool ArrayRemove(array a, object value); // Returns true if the object was found and removed.
native void ArrayDestroy(array a);

Now if dynamic arrays are added, you could extend the map natives with a few convenient functions:
native array MapKeys(map m); // Returns an array of all the keys.
native array MapValues(map m); // Returns an array of all the values.

Not all the natives I've listed here for arrays or maps would be required, but having the most common usage patterns as natives will help speed up and clean up the code.


The difference between string and text types
Strings in JASS2 was fairly limited. They were string table based (a leaking one at that!). There wasn't many operations to perform on them and they were slow. This begs the question, why are there two string types in Galaxy? It seems like the text type is used when text is needed to be displayed on screen, this suggests that text types are internally optimized to be displayed on screen somehow and are possibly still string table based. Let's hope that neither the string or text leaks memory or are too slow.


Pointers
Currently null pointers does not raise a runtime error when dereferenced. This is obviously quite bad and should be fixed. It's also weird that you can't take a pointer of a constant, maybe you should use a read-only data section if you want these to stay constant?


Function pointers
Apparently (*(&function))()​; is a valid syntax, but it generates a runtime error and I can't find out the syntax for that type. Either you aren't done taking out the functionality of a C parser/compiler, or it's still work in progress. I'm hoping it's the latter one.


Dynamically allocated records
Records (or structs if you like) could be allocated with the new operator. So you could do:
structure *a = new structure;

Deletion of dynamic records could be done with:
delete a;

This would require a runtime check to make sure you aren't trying to delete anything on the heap or stack. Extra points are given if you can allocate arrays and native types the same way.


Opcode limit/execution limit
Ever heard of threading?
This limit should be put as high as possible or simply removed.


Performance
Galaxy has the potential to be just as fast as C. However that is not a realistic goal since C programs tend to be very well optimized using relativity slow state of the art compilers. You can't compile Galaxy code and store it in a map (not the whole process anyway). It would not be safe nor portable to store x86 code there. You either need to store the bytecode there (which reduces loading times, but it's more work) or compile the code when the map is loaded. Either way the best way to give Galaxy decent performance would be to write (or reuse) a JIT compiler. Even a trivial JIT for x86 lacking stuff like register allocation would provide a substantial performance increase over a bytecode based VM and is relativity simple to write. However if you want to port StarCraft II to other architectures (PPC, x86-64 springs to mind), or you want to combine it with a decent garbage collector you will be better off using a library. I do hope that it at least performs better than the JASS2 VM did.

I've been testing and benchmarking the runtime further and I have some more input.

Performance
Galaxy seems to have fairly poor performance. Here is some benchmarks comparing it to Ruby which is regarded as a rather slow language:
- Linear graph: http://img697.images​hack.us/img697/175/ga​laxybench1.png
- Logarithmic graph: http://img444.images​hack.us/img444/450/ga​laxybenchlog1.png

Strings are still interned, but they don't seem to leak and they don't have the terrible performance of JASS2 (although I wouldn't call them fast).

Opcode limit/execution limit
The opcode limit seems to be around 20 times of JASS2's one, but that still only allows computation for around 200 ms. The opcode limit mostly limits what can be done while loading the map or in other appropriate situations, you don't want to play a map that constantly freezes for 200 ms, but then again I'd much rather have the map freeze for a while rather than ruining the game. If a map wanted to intentionally freeze StarCraft II, some computations and a Wait call effectively achieves that.


Type-safety
Pointers to stack variables of executed functions is persists after the function returns (more return bugs, yay!). This means you can change the value of new stack variable should they reside the in same location. You can even replace the return address to implement some goto like behavior. However, Blizzard seems to have added a lot of runtime checks to reduce the possibilities for arbitrary code execution, but they don't actually fix the issue.

The simplest and fastest solution to this problem is to implement a tracing garbage collector and allocate local variables which gets referenced on the heap, but I doubt that will happen.

Another solution would be to tag every value on the heap and the stack. This is similar to the boxing type except all values are tagged and all pointer dereferences are checked to make sure they get or set a value of the right type. You could either use two separate heaps and stacks or store pairs of a type and a value in a single heap and stack. Using separate heaps and stacks may be more secure, but it's likely slower due to cache effects and you need to calculate the offsets of the pointers into each area. With a single heap and stack, pointers can be absolute and a simple addition is enough to find the position of the other type or value. This might seem like a lot of overhead, but it will likely perform better than Blizzard's naive checks and actually solve the issue.


Function pointers/closures
Closures are extremely handy when doing event-driven programming, which is what Galaxy will be used for, so this is a must-have feature. Closures should have the same syntax as function pointers and be interchangeable with them. Closures should be able to nested and they should be garbage collected. With a tracing garbage collector implementing closures is trivial, without one, you'll need to implement reference counting to keep track off the local variables which are stored on the heap. Hopefully, Blizzard has already written this to track handles, so they could probably reuse that. If closures were implemented, natives taking function pointer arguments wouldn't need an extra parameter for passing values.

Here is some suggested syntax for closures:
int calc(int value) {

return 4 / value;

}

void run() {

int i = 2;

int(int) func;

func = int(int value) { return value + i; }; // Assign a closure to the function pointer.

func = calc; // You should be able to assign regular functions too.

print(IntToString(cl​osure(2))); // Should print 2.

}

1Very severe problems


1.1The 2^21 byte limit


As you might know, galaxy code and data is restricted to 2^21 byte (2 megabytes). We found out that this limit includes globals, locals (aka. the stack), and compiled galaxy bytecode all together. This is very serious! It means that if you have 1.5 megabyte code in your map (which may happen for bigger projects), you can only have 500 kB globals and stack.

To get you a clue about how much this is: In Warcraft 3, each array was 8192 entries, 4 byte each, so 32 kilobytes per array. This means, 60 arrays would already hit the 2mb limit (and you had no more space for stack and code!). If you have used vJASS and structs and consider that EVERY struct member variable was compiled to an array, you would notice that 60 struct members (accumulated from all structs) can happen fast.

Okay, galaxy offers us arrays where we can determine the size, so at least we don't need a 8192'er array for stuff where we actually only need 10 entries. However, since blizzard does not allow dynamic struct allocation at the moment, we need again arrays of structs to mimic dynamic allocation. Since we don't know how much instances of an array will be in our map, we have to choose higher values for our arrays again.

There were many WC3 maps that needed a lot more than 2 mb script memory (not concerning leaks). There will also be SC2 maps that will surely hit that limit.

The 2^21 byte limit is an inherent problem of the galaxy virtual machine (the subprogram that runs your galaxycode while sc2 is running), since it seems that its "load from address" operation is capped to a 21 byte pointer. So Blizzard will have to change the architecture of this program drastically to bypass this limit. So this is no easy fix and thus Blizzard will think twice before doing it. But it is a necessary fix!

So I think I speak for the whole modding community when I say: "Please Blizzard fix this, even if it might be some work!"