Pages: 1
  Print  
Author Topic: Optimizations  (Read 1671 times)
Offline (Male) Josh @ Dreamland
Posted on: April 02, 2013, 10:33:21 PM

Prince of all Goldfish
Developer
Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2958

View Profile Email
There is a lot of room in a typical piece of GML for optimizations; the kind GCC is not capable of making in arbitrary code. I want ENIGMA's optimizer to be extensible so that we aren't hard-coding a lot of passes into the mechanism. That said, some passes will need hard-coded, and do not seem like a hack to hard-code.

To best avoid hacks, we need to lay out how we want the optimizer to promote extensible lists of things to optimize. To best lay out that framework, we need to know the kinds of optimizations that need made. I will name as many optimizations and classes of optimizations as I can. I've added emphasis to phrases I'm trying to pay attention to, such as what needs to have hard code, what optimizations we can automatically enumerate, and what optimizations we can kickstart through pattern matching.

ENIGMA, as you all know, is typed; I wouldn't call it strongly typed, due to var, but it you can specify strong types explicitly. When you do not specify a type, presently, var is used as the default. This is *terrible*, as var is like half the speed of a regular primitive in terms of raw calculations per second. Even when optimized. Variant, on the other hand, is equally fast as a double.

ENIGMA should, at very least, determine whether the variable is used as an array, and if it is not, use variant. Then GCC will do some inlining magic and, in general, no speed will be lost.

ENIGMA should, preferably, go one step further than that, and determine whether strings are ever assigned to it, and if not, use a double instead. Or, if no reals are assigned, only strings, it should use a string.

ENIGMA should, ideally, then go one step further and determine the slowest data type assigned (in terms of double, fastint_t, and long) and narrow the variable type down to it.

This process will simply be hard coded, but will possibly employ other aspects.
Let's go one step further. The above seem easy to implement, yes? But consider this case:

Code: (EDL) [Select]
var a;
a = choose(1, 2, 3, 4, 5);

We're going to look at two optimizations that can be made to that snippet. An intelligent human would reduce that code to the single line int a = random_integer(1, 5);, but an EDL optimizer could only reasonably be expected to produce one of these outputs:

Code: (C++) [Select]
int a;
a = choose(1, 2, 3, 4, 5);

Code: (C++) [Select]
int a;
a = random_integer(1, 5);

In the first sample output, a is reduced to int, even though choose returns variant. I believe this can be done in an enumerable fashion by having either a macro or an entry in an optimization file to denote which parameter(s) share a potential return type. For choose(), any parameter can define the return type. I can't think of a function that has a specific parameter which can be either real or string, and defines a return type, but I'm sure there is one.

In the second sample output, choose(sequence) is replaced with random_integer(min(sequence), max(sequence)). This is a non-trivial replacement which would need hard coded, though it is possible we could enumerate functions which might need replaced with other functions based on their parameters. This way, implementers would need only supply the name of the funtion and a method/virtual class which does the checking and replacement.

Moving the assignment into the initializer is a potential optimization, though in most languages, it would not make a difference, and the attempt could therefore only serve to cause harm if initialization was not valid for whatever reason.

More simple optimizations exist in other codes. Consider this code:

Code: (EDL) [Select]
draw_set_color(c_red);
b = 10;
draw_set_color(c_blue);

It's clear to a human that the first call to draw_set_color does nothing. However, if the assignment b = 10 were replaced with draw_circle(mouse_x,mouse_y,10,0), removing line 1 would cause misbehavior. It would therefore be necessary to have the implementer either specify a list of functions to reference in determining whether two successive function calls of the same type undo each other, or else specify a class/method for examining an AST between two given nodes to make that call for the optimizer.

We then run into a separate, but related, case:
Code: (EDL) [Select]
draw_set_color_rgba(0, 0, 0, 0.5);
draw_set_color(c_blue);
draw_circle(0,0,10,0);
draw_set_color(c_red);
draw_set_alpha(1);

The most efficient code output for that is as follows:
Code: (EDL) [Select]
draw_set_color_rgba(0, 0, 255, 0.5);
draw_circle(0,0,10,0);
draw_set_color_rgba(c_red, 1);

But how does the optimizer know to do that? My only thought is that a good pattern to look for would be consecutive calls to related functions in a given set. A class would be provided to give that set of functions, along with hard code to do the merging—how else do we get 0,0,255 out of c_blue? The best we seem to be able to automate here is auto-matching consecutive calls to functions in set A which are not separated by calls to any functions in set B, and then invoking the merge method on the functions from the first set.

I will post more optimizations when I have some more time and am not so tired. I'll also do some proofreading, because I'm sure this reads like ass.

From what I have written here, it looks like the best approach is to have a base class defining a kind of optimization to perform, and then have child classes to carry out a specific operation, which can then have child classes for very similar optimizations. So call-consolidating (as in draw_set_color optimizations above) would be one child of the optimization class, which would employ its own virtual class for specifying sets of functions to consolidate, as described above.

Please do submit feedback; this process is going to need a lot more thought.
Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Offline (Unknown gender) TheExDeus
Reply #1 Posted on: April 03, 2013, 02:01:06 PM

Developer
Joined: Apr 2008
Posts: 1872

View Profile
But who will code that?
Logged
Offline (Male) DaSpirit
Reply #2 Posted on: April 03, 2013, 03:55:16 PM

Member
Location: New York City
Joined: Mar 2013
Posts: 124

View Profile
These seem like very specific optimizations which would make them difficult to add.

One question would be if it's worth it. As you said, these are obvious optimizations and I think you should leave them for the user.
Logged
Offline (Male) polygone
Reply #3 Posted on: April 03, 2013, 04:04:00 PM

Contributor
Location: England
Joined: Mar 2009
Posts: 803

View Profile
Those function optimizations look crazy. The only thing I'm in favour of is the type cast optimization, if you can detect that a variable is only ever used as a specific type then switch the cast to it. But could issues arise with this due to with() statements?
Logged
I honestly don't know wtf I'm talking about but hopefully I can muddle my way through.
Offline (Male) Josh @ Dreamland
Reply #4 Posted on: April 03, 2013, 04:36:00 PM

Prince of all Goldfish
Developer
Location: Pittsburgh, PA, USA
Joined: Feb 2008
Posts: 2958

View Profile Email
The hardest part about type optimization is doing the optimization for literally every variable. Basically, I'll be generating dependency graphs between variables, and then using the smallest value in the largest cycle. It still won't be as efficient as if the user optimized the code himself, but it's a start.

The optimizations I gave are specific cases; the point was that there are lots of functions other than draw_set_color which might need reduced by the optimizer.

Something we might want to consider is having some optimization passes warn the user instead of enacting the optimization itself, that way the user can choose to ignore the optimization and no code is accidentally broken.
Logged
"That is the single most cryptic piece of code I have ever seen." -Master PobbleWobble
"I disapprove of what you say, but I will defend to the death your right to say it." -Evelyn Beatrice Hall, Friends of Voltaire
Offline (Male) DarkAceZ
Reply #5 Posted on: April 03, 2013, 05:45:21 PM

Member
Location: United States
Joined: Dec 2011
Posts: 75

View Profile
But who will code that?
We need more info on this.
Logged
My Goodness! Is it 4:30? I'm supposed to be having a back, sack and crack!

[edit]
Offline (Male) polygone
Reply #6 Posted on: April 03, 2013, 05:57:05 PM

Contributor
Location: England
Joined: Mar 2009
Posts: 803

View Profile
Something we might want to consider is having some optimization passes warn the user instead of enacting the optimization itself, that way the user can choose to ignore the optimization and no code is accidentally broken.
Sound fine for an optional pass somebody could run, but not automated.
Logged
I honestly don't know wtf I'm talking about but hopefully I can muddle my way through.
Pages: 1
  Print