Sun, 22 Jul 2007 08:53:58 -0000

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: | Nick <Ibeam2000@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Sun, 22 Jul 2007 08:53:58 -0000 |

Organization: | Compilers Central |

References: | 07-07-066 |

Keywords: | optimize, analysis |

*> 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 .....*

This sounds to me like a typical array programming problem. If the

code fragment you've supplied is the inner part of a larger loop which

iterates across eight potentially large bitmaps (arrays), and the

interpretive overhead of an expression far exceeds the time to

actually do the arithmetic, then one of your choices is to attempt the

operations as arrays.

As a programmer, I would definitely write the expression having

eliminated the common subexpression myself. (This was mentioned

earlier) At the very least, your code is much, much clearer.

Or use a max function. r := max(0, (-4113.26 + 0.07*i7 -

5.08*i8/100 .....

But if you can change your computational procedure to deal with i1,

i2, i3 as entire matrices, then at least you have a force multiplier

where you have do the parsing and tree traversal once, but get the

answers for a million or more pixels.

The operations +, -, /, *, abs, max, etc. should have the correct

missing value handing for nulls. 1 2 3 + 4 MV 6 should be 5 MV 9 and

so on.

If a substantial fraction of the pixels are nulls, then you can build

a mask, weed out only the relevant values, perform the computations,

then build a result using a null or the computed value for the

corresponding element, depending on the mask.

If i1 through i8 are small integer values always in the range of

0..255, then you can do the computations with pre-calculated tables.

(You can return scaled large integer values with just enough digits

behind the decimal places). If you truncate to get back a pixel

value, all that excess precision will be cut off.

Use 4 byte floats, rather than 8 byte doubles. (This is not a big

help)

I would suggest reading Jim Blinn's books, and Jon Bentley's book

"Writing Efficient Programs".

Also, have a look at "J", www.jsoftware.com, for ideas.

Regards, Nick

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.