Re: Efficient Evaluation of Image Expressions

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

Return to the comp.compilers page.
Search the comp.compilers archives again.