Re: [Haskell-cafe] Wrong Answer Computing Graph Dominators

On Mon, Apr 21, 2008 at 5:21 PM, Bertram Felgenhauer wrote:

Denis Bueno wrote:

...

On Wed, Apr 16, 2008 at 2:33 PM, Bertram Felgenhauer 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@haskell.org as the maintainer, so GHC's trac seems to be the right place.

I've created a ticket for this now, See http://hackage.haskell.org/trac/ghc/ticket/2227

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. -- Denis