[Haskell-cafe] Wrong Answer Computing Graph Dominators
dbueno at gmail.com
Mon Apr 21 17:42:55 EDT 2008
On Mon, Apr 21, 2008 at 5:21 PM, Bertram Felgenhauer
<bertram.felgenhauer at googlemail.com> wrote:
> Denis Bueno wrote:
> > On Wed, Apr 16, 2008 at 2:33 PM, Bertram Felgenhauer
> > <bertram.felgenhauer at googlemail.com> wrote:
> > > No. Data.Graph.Inductive.Query.Dominators is just buggy.
> > [...]
> > > Here's a quick fix:
> > Thanks! This fixes my problem.
> > Have you submitted a bug and your patch to the appropriate tracker?
> > If not, would someone point me to the appropriate one? Would in be
> > the GHC trac, or is there a libraries-specific one?
> The library is shipped with ghc, and the darcs repository lists
> libraries at haskell.org as the maintainer, so GHC's trac seems to be the
> right place.
> I've created a ticket for this now, See
> Note that I opted for reimplementing the whole module instead of
> just fixing the bug.
/me grovels before int-e.
My code went from 310s to 28s (as measured by the profiler, which
represents a much longer wall time) after merely switching to your
dominators implementation. Thank you for taking the time to
reimplement the module.
In particular, in the original dominators code the `intersection'
function was the time-hog, followed by `builddoms':
COST CENTRE MODULE %time %alloc
intersection DPLLSat 73.6 18.5
builddoms DPLLSat 11.1 46.4
With your new module I now have the bottleneck I expected from my
code, and the dominators code nowhere approaches that bottleneck.
More information about the Haskell-Cafe