[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: RFA: invert-speedup-1.diff
From: |
Alexandre Duret-Lutz |
Subject: |
Re: RFA: invert-speedup-1.diff |
Date: |
Sat, 29 Mar 2003 23:43:31 +0100 |
User-agent: |
Gnus/5.090016 (Oort Gnus v0.16) Emacs/21.2 (gnu/linux) |
>>> "Raja" == Raja R Harinath <address@hidden> writes:
Raja> Hi,
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?)
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.
--
Alexandre Duret-Lutz