[OOD] Patterns & Optimization

Policy based design may be what you're looking for. It is a good way to take a lot of different type of behavior and piece it together. Also, component based design could work as well. I believe there is an article in game programming gems 4 or 5 on component base design. I haven't tried the policy base design myself on a large scale so I don't know how well it handles with the more code you add. Though, we're about to ship a game using a component based design. This design worked great for installing behaviors in a data driven way. We can lego piece together different behaviors without the object having to know about those behaviors. This may work well for code generation.

Hope that helps.



[Edited by - David Neubelt on August 9, 2007 2:03:42 AM]

You're writing a code generator to generate code that will be later compiled by a standard compiler, right?

Wouldn't most modern compilers perform all the optimizations you have specified? If you write "for(x = 5; x < 5; x++) foo()", the output of g++ (using -O3) is basically "x = 5".

Flagging functions as "const" indicates 'no side-effects' etc, most of what you are trying for seems to be part of g++. Although you say you're not able to transmit these properties, couldn't your generator supply them by writing "const" etc?

Are you wanting to do more complex things that probably won't be optimized by the compiler? or are you writing code for a compiler or system that doesn't optimize (well).



In essence: If you're looking for a way to pre-optimize your code via the generator and your target is g++ or VC++ or similar, you may want to attempt to ensure your output code is optimizable rather than optimized.

If you're target is not an optimizing compiler, I think the first place to look would simply be the optimizing routines in g++, since they're open-source.


This is all speculation tho. HTH but I'm not too confident.

David Neubelt: I'll look into policy-based design. I have trouble imagining how component-based design would make this manageable, though.

Quote:

Original post by shukapi You're writing a code generator to generate code that will be later compiled by a standard compiler, right? Are you wanting to do more complex things that probably won't be optimized by the compiler? or are you writing code for a compiler or system that doesn't optimize (well).

That was an example, which I thought would be more accessible to programmers because it involves a simple concept (a for loop). My actual code generator targets my own compiler and virtual machine, and it's highly unlikely that you would understand the exact details of it without a quite lengthy explanation . So, I'd say it's "like a for loop", but without an optimizing compiler.

Quote:

If you're target is not an optimizing compiler, I think the first place to look would simply be the optimizing routines in g++, since they're open-source.

I did (that, and also several optimizing compilers courses and papers from my school). However, the structure of my problem is quite different (the target language doesn't really have conditional statements, for example, only conditional expressions). Besides, i'm looking more for general guidelines about design, than for precise optimization opportunities.

This kind of problem sounds a lot like what type traits are meant to solve in a "generic" way.

A quick overview of type traits is here: type traits

The basic premise is specializing what actions are taken based on attributes of the types they are being done on. If objects have a similar interface for traits you can defer/decide what to do based on the trait's value. A lot of the boost libraries use this technique to get more efficient/generic code.

For example the UBLAS matrix/vector library in Boost uses type traits to help decide which functions to call based on things like the matrix storage type (dense, sparse, compressed, etc) and value type (int, double, complex<double>, etc)

Perhaps something like the Visitor pattern?

class Optimizer {    virtual Statement* optimizeIF(IFNode&) = 0;    virtual Statement* optimizeCASE(CASENode&) = 0;    /* etc */};Statement* IFNode::optimize(Optimizer& opt) {    // imagine more memory management going on here    condition = condition->optimize(opt);    thenClause = thenClause->optimize(opt);            elseClause = elseClause->optimize(opt);    return opt.optimizeIF(*this);}Statement* ConstantConditionOptimizer::optimizeIF(IFNode& node) {    if (node.condition->isConstantTrue()) {        return node.thenClause;    } else if (node.condition->isConstantFalse()) {        return node.elseClause;    } else return &node}

EDIT: I thought you could just apply a list of optimizers until "nothing changes anymore", but that might be too inefficient, since each optimizer will only work on a small part of the tree. Perhaps a more clever combination scheme for optimizers is necessary.

[Edited by - Barius on August 9, 2007 11:37:52 PM]

Quote:

Original post by ToohrVyk I'll look into policy-based design.

If you're interested, here's some samples from Modern C++ Design, including a full chapter introducing policy-based design and a full chapter showing how to use it to implement a smart pointer class. It also contains many other articles that use policy-based design to achieve various other things.

Quote:

Original post by Barius EDIT: I thought you could just apply a list of optimizers until "nothing changes anymore", but that might be too inefficient, since each optimizer will only work on a small part of the tree. Perhaps a more clever combination scheme for optimizers is necessary.

I guess it depends on just "how optimal" the code should be.

Scanning wikipedia, it sounds as though the requirements of whatever pattern you use will be determined a little by the kind of language you're implementing. How is memory modelled, for example? Will exploiting locality be a worthwhile task with your VM? Depending on what you want to do, the problem will very possibly be NP-complete. I guess heuristics are the way forward.


Starting with your problem #2:

Quote:

These optimizations rely on properties of the manipulated objects (side-effects, inequality and equaliy relationships, etc) that are not part of the user-side interface of my objects (they don't need it), but I need a way to transmit these properties simply from object to object, and also to add them when I start needing them.

I do wonder whether a fancy new design pattern is really needed here. For one thing, some optimization techniques will require relatively global information (where references are allocated, how they're used, what happens to values later on in the code, and so on). It may be easier, rather than trying to pass this information around from one Optimizer class to another, simply to annotate the syntax tree in one or more passes with the information needed, and then to optimize that.

(EDIT: Although you say you don't want to add this information until it's needed, as far as I can see you probably wouldn't need to include more than information about the location of each term in the tree (i.e. the scope at which it exists, and the scope at which it is used), and perhaps how it's allocated. Each Optimizer can then deduce further information from the syntactical structure of the surrounding code if needed.

If you find you need to add optimization-specific information to the tree, then see my edit below.)


This makes #1 easier:

Quote:

I have a large number of optimization opportunities, both present and future, and I need to be able to add them in an elegant and efficient way when the time comes—I don't want to add them from the start just in case they aren't necessary.

Jut use a standard visitor/possibly policy/pattern matching approach and traverse the tree.


But #3 is still interesting:

Quote:

# These optimizations should naturally cascade: in the above example, the loop could be collapsed to { x = max; }. Then, if x is not used anywhere outside the loop, there's no need for that, so the statement is collapsed to {}. But then, if max was a variable set as the sole side-effect of a loop right before that, then the entire loop loses its side-effect and becomes { x = max; } as well, and so on.

There are a few subtleties here. One is that the order in which you apply optimizations may be important (though presumably this will depend on what optimizations you can apply to your language; you may have to prove certain properties about each). This would be where the heuristics come in.

The algorithm is then a case of asking each optimization in the list to compute just how significant its affect may be, applying the most useful optimization, and then repeating (also recursively) until no more can be applied. Don't forget to reannotate the affected parts of the tree; you can get each optimizer to do this as it applies itself. Also make sure that each optimizer checks that any semantic affects resulting from changes made to the subtree it's given will be local to that subtree (e.g. don't make variables more local if they're used in an enclosing scope).


Please bear in mind, though, that I don't know anything about optimization and I just made this up in a few minutes. There are probably a whole host of flaws and gaps in the idea.

Finally, I would personally not want to implement this in an imperative language: it's just crying out for pattern matching of some kind. Are you sure you can't use ocaml? ;-)


(EDIT 2: In case you need to add information to the annotated nodes which is specific to each Optimizer...

1. Have each annotated node include a map from Optimizers to a new kind of tag information class. Derive subclasses of this tag information class for each type of Optimzer. (The information can be safely retrieved using double dispatch or pattern matching.)

2. When each Optimizer is asked to examine a term (or subterm) in the tree, have it add the information, in the form of the appropriate tag information class, to the annotated term's map using the Optimizer as the key.

3. When applied to a subterm, the Optimizer can then lookup the node in the tree at which this information would be stored by referring to the location information in the subterm's tag.

4. The information can then be retrieved safely from the map.)

[Edited by - MumbleFuzz on August 10, 2007 5:11:18 AM]