Thu, 19 Jul 2007 09:49:19 +0200

Related articles |
---|

Efficient Evaluation of Image Expressions hermann.rodrigues@gmail.com (Hermann) (2007-07-18) |

Re: Efficient Evaluation of Image Expressions torbenm@app-2.diku.dk (2007-07-19) |

Re: Efficient Evaluation of Image Expressions tmk@netvision.net.il (Michael Tiomkin) (2007-07-19) |

Re: Efficient Evaluation of Image Expressions Ibeam2000@gmail.com (Nick) (2007-07-22) |

Re: Efficient Evaluation of Image Expressions hermann.rodrigues@gmail.com (Hermann) (2007-07-23) |

Re: Efficient Evaluation of Image Expressions Ibeam2000@gmail.com (Nick) (2007-07-30) |

Re: Efficient Evaluation of Image Expressions Ibeam2000@gmail.com (Nick) (2007-08-01) |

From: | torbenm@app-2.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen) |

Newsgroups: | comp.compilers |

Date: | Thu, 19 Jul 2007 09:49:19 +0200 |

Organization: | Department of Computer Science, University of Copenhagen |

References: | 07-07-066 |

Keywords: | optimize |

Hermann <hermann.rodrigues@gmail.com> writes:

*> Hi all,*

*>*

*> I have a language used perform map/image algebra calculations using*

*> expressions like the following:*

*>*

*> ------------------------------------------------------*

*> if isNull(i1) or isNull(i2) or isNull(i3) or isNull(i4) or isNull(i5)*

*> or isNull(i6) or*

*> isNull(i7) or isNull(i8)*

*> then null*

*> else*

*> (if (-4113.26 + 0.07*i7 - 5.08*i8/100 + 47.89*abs(i1) +*

*> 99.72*abs(i2) + 214.96**

*> (*

*> -2.332 + 2.561*i4 + 0.55*i6*

*> ) +*

*> 1.57*i3) > 0 then*

*> -4113.26 + 0.07*i7 - 5.08*i8/100 + 47.89*abs(i1) +*

*> 99.72*abs(i2) + 214.96**

*> (*

*> -2.332 + 2.561*i4 + 0.55*i6*

*> ) +*

*> 1.57*i3*

*> else 0*

*> )/1000*

*> -------------------------------------------------------*

*>*

*> Basically, the expression is parsed and an intermediate structure is*

*> constructed. Then, for each image coordinate, the corresponding cells*

*> of the eight images are scanned, presented to expression, and the*

*> expression evaluated, much like a pixel shader does.*

*>*

*> The problem is how to represent the expression so that the execution*

*> becomes more efficient.*

*>*

*> Currently I have a base Expression class and subclasses representing*

*> the possible operators (+, -, abs, if-then-else, isNull etc). This*

*> expressions are linked forming a tree. The evaluation process walk on*

*> this tree evaluating sub-expression by expression and passing the*

*> resulting values to the dependent ones, until I get a final result*

*> representing the overall expression value.*

*>*

*> Simple expressions, like the one above, have good performance, but if*

*> the expression gets more complicated, the evaluation process becomes*

*> painfully slow. Any advice?*

First of all, I suggest you do common subexpression elimination. The

expression in the then-branch is an exact copy of a subexpression in

the condition. You can do that by adding a let-expression at the

source level, so the innermost if-then-else above is rewritten to

something like

let t = -4113.26 + 0.07*i7 - 5.08*i8/100 + 47.89*abs(i1) +

99.72*abs(i2) + 214.96*(-2.332 + 2.561*i4 + 0.55*i6) +

1.57*i3

in if t>0 then t else 0

This saves about half the computation. You can add a rewrite step

that looks for common subexpressions, or you can let this be up to the

user.

Secondly, I suggest making the logical or operator shortcut, i.e.,

don't evaluate the second argument if the first is true (and

vice-versa for logical and).

Since you perform the same computation for all pixels in an image, it

might be worthwhile to compile the expression. How you do this

depends on which platform you are on. In Java or .NET, there are

functions in the reflection libraries that allows you to generate

bytecode and link it to the running program, so you can call it. You

can see some details on http://www.itu.dk/people/sestoft/rtcg/rtcg.pdf

This paper is a bit old, so there might be easier ways of doing it

now. Other systems have other ways of allowing runtime code

generation.

You could also code everything in a language that allows explicit

meta-computation, such as MetaOCaml (http://www.metaocaml.org/) or `C

(http://pdos.csail.mit.edu/tickc/).

If you can't do dynamic code generation or if you think it is

overkill, you can still benefit from generating bytecode and then

write a simple bytecode interpreter. That way, you avoid the overhead

of method calls for every operator.

Torben

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.