[Haskell-cafe] Wrong Answer Computing Graph Dominators

[Denis Bueno]

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