[augeas-devel] Minimization effect on typecheking

[David Lutterkort]

On Mon, 2010-05-03 at 16:14 -0400, Francis Giraldeau wrote:
> Selon Francis Giraldeau <Francis.Giraldeau at USherbrooke.ca>:
> > I did a few experiments to try to see if we minimize automatons before
> > computing the costly fa_ambig_example, if we could get better
> > performance.
> >
> > It seems yes. Here are the results for a sample httpd lens :
> >
> > test      | time(s) | peak mem(bytes)
> > normal    | 8.12    | 142640
> > minimized | 6.59    | 30128
> >
> > Even while reducing the automaton takes a while, it seems that overall
> > performance is better. On this lens, it gives 18% better time and 78%
> > reduction in peak memory.
> >
> > I will run it on all lenses to verify that performance improvement is
> > not a special case because of the lens I'm using.
> 
> results for all modules :
> 
>                           normal    minimized
> Average	time (s)          0.73      6.13
> Average peak mem (bytes)  38541     14103
> 
> Memory usage is reduced by half, but few lenses are taking much more time to
> compute, like the squid module that takes over 120s with minimization, against
> only 3s when not. So, we should let this as is...

Thanks for doing all this work - this meshes with my casual tests from a
while back: minimzation helps with some FA's, but isn't worth the effort
for most other ones, especially the simpler ones.

It might be interesting to see in more detail why minimization is slow -
one immediate suspect is the determinization that has to happen first;
if that should not be the case, it would be worth looking if there are
some wins in the data structure that the minimization routine uses.

Ultimately, I think that a good way to improve typechecker performance
would be to use the DFA-based construction from Turon et.al.

David