Re: RFA: invert-speedup-1.diff

[Raja R Harinath]

Hi,

Alexandre Duret-Lutz <address@hidden> writes:

>>>> "Raja" == Raja R Harinath <address@hidden> writes:
>
>  Raja> This is the first of a couple of patches to speed up 
>  Raja> Automake::DisjConditions::invert.
>
>  Raja> With this patch and the original tests/DisjConditions.pl, a 'make
>  Raja> check' in lib/Automake/tests went from ~1.25s to ~0.33s.
>
>  Raja> After removing the FIXME in the test script, the time taken by
>  Raja> 'make check' was ~4.00s, even with the large inputs.
>
> Excellent !  Please install this with a proper ChangeLog entry.
> (Could you post ChangeLog entries in the future?)

Yes.  I'm trying to get my workflow right.

> Recently I've learned about a nifty structure called "(reduced
> ordered) binary decision diagram", and since then I'm dreaming
> about using BDDs to represent Automake conditionals (Conditions
> and DisjConditions, all together).  I haven't yet had the time
> to think about it seriously (i.e., more seriously than in
> dreams), but it seems BDDs would simplify and speed up many
> things, for instance inversion would be performed in constant
> time.

I thought of them too.  However, when you convert them back to SOP
form to describe to the user, they sometimes may seem more verbose
than necessary.  Also, the size of a ROBDD is related to the ordering
of variables, though for normal usage, there shouldn't be a major
problem.

- Hari
-- 
Raja R Harinath ------------------------------ address@hidden