FW: [abc] Possible reduction in filtering costs

To me that sounds very much like an observation we had documented in our AOSD 06 paper, which got rejected (http://www.sable.mcgill.ca/~ebodde/data/aosd06.ps). Section 7, "discussion" says something about this.

I thought, you might probably find my slides for the DAW useful (see http://www.sable.mcgill.ca/~ebodde/data/daw.pdf), where I discuss the dynamic enablement of matching advice. This is probably also something we should consifer for a future release. Please let me know if I make any false statements in there about TMs.

Oh yeah and I think the algebra looks correct.

Eric

> -----Original Message-----
> From: Majordomo list server
> [mailto:majordomo@comlab.ox.ac.uk] On Behalf Of Julian Tibble
> Sent: Friday, March 10, 2006 8:37 AM
> To: abc@comlab.ox.ac.uk
> Subject: [abc] Possible reduction in filtering costs
>
> [Please check my algebra, if the optimisation is correct I'll
> check in]
>
>
> "In general the result of turning off negative bindings
> in tracematches in nonsensical, but for this particular
> example it yields correct results..."
>
> I've been thinking about this - surely if we can sometimes
> safely ignore skip loops, then there should be an
> optimisation that determines some of the cases where its
> possible and does it automatically.
>
> How about the following:
>
> First a reminder definition:
>
> skip = AND_{s} ¬match(s,e)
>
>
> Consider a state i, with a self-loop for symbol "foo".
> Assuming the predicate "in" represents constraints for
> transitions from other states the update equation for label_i is:
>
> label_i
>
> = {update equation}
>
> in OR (label_i_old AND match("foo", e))
> OR (label_i_old AND skip_i)
>
> = {boolean algebra}
> in OR (label_i_old AND
> (match("foo", e) OR skip_i))
>
> = {skip definition}
>
> in OR (label_i_old AND
> (match("foo", e) OR AND_{s} ¬match(s,e)))
>
> = {boolean algebra}
>
> in OR (label_i_old AND
> AND{s} (match("foo", e) OR ¬match(s,e))
>
> = {X OR ¬X === true}
>
> in OR (label_i_old AND
> AND{s =/= "foo"} (match("foo", e) OR ¬match(s,e))
>
> = {boolean algebra}
>
> in OR (label_i_old AND
> (match("foo", e) OR AND{s =/= "foo"} ¬match(s,e)))
>
> =
>
> in OR (label_i_old AND (match("foo", e))
> OR (label_i_old AND AND{s =/= "foo"} ¬match(s,e))
>
>
> So we can ignore the symbol "foo" when calculating skip
> for state i.
> Since we calculate skip incrementally for each state anyway,
> this idea translates into a 3-line patch.
>
>
> I ran jhotdraw on musketeer without and with the patch:
>
>
> without
> -------
> animation took: 557134
> memory used: 1049392
>
> with
> ----animation took:
> animation took: 314668
> memory used: 1036064
>
>
Received on Fri Mar 10 14:01:25 2006