[m-rev.] for review: set_of_progvar

[Julien Fischer]

On Tue, 19 Jul 2011, Zoltan Somogyi wrote:

> Julien: the bug fix described in the last paragraph of the log message
> (a one-line diff) should be applied to the release branch as well.

Ok.

> Predicates with many variables, such as some of those in zm_enums.m,
> tickle pretty bad behavior in the liveness and stack_alloc passes.
> This is because those passes manipulate sets of variables, which in
> such cases are large sets of variables, and the quadratic behavior
> of repeated operations on sets represents as sorted lists hurts us.
>
> This diff changes the representation of the sets of variables involved
> in those two passes, which are the prebirth, postbirth, predeath and postdeath
> sets in goal_infos, to be values of an abstract type (set_of_progvar).
> By default, these are implemented using tree_bitsets, which have much better
> worst case behaviour that set_ordlists.
>
> When compiling zm_enums with debugging enabled, this diff speeds up
> the liveness pass by about half and the stack alloc pass by about a third,
> with the overall speedup being about 6% (due to some other expensive passes).
>
> On tools/speedtest -l, the result is a 3.4% slowdown. Since the slowdown
> worsens slightly if I make the abstract representation of sets of prog_vars
> be the existing representation (an ordinary set), I think this slowdown is
> due to the conversions that are now required in some places between the
> abstract representation and an explicit set(prog_var) representation.
> As such, as other uses of set(progvar) get converted to set_of_progvar,

I've skimmed through the diff and have no objections to you committing
this.  (I don't have the time available to do a full review of this at
the moment.)

Julien.
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------