[m-rev.] the grade library is ready for review

[Zoltan Somogyi]

On Mon, 4 Apr 2016 14:42:10 +1000, Paul Bone <paul at bone.id.au> wrote:
> So far this all looks good.

Thanks.

> I've been checking some compilation model combinations.  I found that it was
> okay with:
> 
>     $ ./choose_grade thread_safe=thread_safe debug=debug
>     $ ./choose_grade thread_safe=thread_safe deep_prof=deep_prof
> 
> AFAIK these don't work with multiple threads.  Is there a missing
> constraint?

I was copying the constraints I found in runtime/mercury_grade.h
and compiler/handle_options.m. Neither of those prevents either
of the above combinations. I just tried the commands

    mmc --grade none.par.profdeep.gc -vc queens.m
    mmc --grade none.par.debug.gc -vc queens.m

and they both generate .o files: both the Mercury compiler and the
C compiler (meaning runtime/mercury_grade.h) accept both grades.

I think you are right: neither the debugger nor the deep profiler
will work correctly in the presence of multiple threads, so neither
the current compiler nor the grade library should accept either grade.
I will add the missing constraints, though I will wait until we think
we have identified all the other missing constraints as well, since
that reduces redundant work. Thanks.

> How about:
> 
>     $ ./choose_grade debug=debug deep_prof=deep_prof
> 
> This also succeeds.  But does this grade work?  Even if it does work it
> probably doesn't make sense.

Actually, that combination does not only work, I specifically
designed it to work. Both debugger and deep profiling need the
identities of procedures, and I made sure that the executable
has only one copy of the procedure id of every procedure
even if both are enabled.

Without that grade combination, it would been significantly
harder to debug the implementation of deep profiling itself.
Non-developer users may not find the combination useful,
but I did.
 
> I also made it crash:
> 
>     $ ./choose_grade pregen=pregen
>     ...
>     Uncaught Mercury exception:
>     Software Error: function
>     `grade_lib.grade_structure.encode_low_tags_floats'/3: Unexpected: pregen
>     but MercFloat != boxed double
>     Stack dump not available in this grade.

That is strange. I just tried that command, and for me,
it worked just fine. Did you test the current version
of the library?

> Twice:
> 
>     $ ./choose_grade ssdebug=ssdebug tscope_prof=tscope_prof 
>     Uncaught Mercury exception:
>     Software Error: predicate
>     `grade_lib.grade_solver.accumulate_why_var_is_not_values'/5: Unexpected:
>     is_possible
>     Stack dump not available in this grade.

That is an expected failure: tscope requires LLDS, but ssdebug
does not make sense in LLDS grades, since the C debugger is
significantly better.

The problem you found is in how the failure is presented: it should
generate an error message, not a stack dump. I will fix it.

> > I tried to make the code of the grade library itself easy to read.
> > Please tell me whether I succeeded.
> 
> I've looked over parts of it.  It seems fine.  I like the combinators in
> grade_solve.m.

Thanks, but I don't know what combinators you refer to.

> There's a typo in grade_state.m line 63: "auconfiguration"

Fixed.

> Some additional questions:
> 
>  + Does labeling in the solver choose the "best" grade?

The labeling step makes its choice using the algorithm described
in the comment on init_solver_var_specs in grade_specs.m:
it always sets the first variable in the variable priority list
whose value hasn't been fixed yet by propagation, and it always
sets that variable to the first of its values that has not yet been
ruled out by propagation. That is what its notion of "best" is.

As for whether this notion of "best" agrees with our subjective
perception of what is best, that is one of the questions before the court.

People can try to answer that question by themselves both
by just trying to stump choose_grade, and by looking at the priorities
implicit in the list returned by init_solver_var_specs.

>  + Does it attempt to evaluate all possibilities or will it commit to the
>    first valid solution?

When computing an absolute grade, the solver always commits
to the choices it makes during labeling; it never revisits such choices.
This is for two reasons: one, I think backtracking, if implemented,
would take too long, and two, I was pretty sure that backtracking
would not be needed to avoid failures.

When computing a grade relative to an installed grade set (i.e. choosing
the installed grade that best fits the user's requirements), neither of
those reasons held, so I did implement backtracking. It is optional:
it is controlled by the should_commit argument to solve_best_installed_grade.
However, for none of the 160 tests done by test_grades.m does it get
a different results when backtracking is enabled than when it is not enabled.
The code of  run_installed_grade_set_test runs each of those tests
both with and without backtracking, and prints INCONSISTENT if they get
different results. I never saw that in any output.

On that basis, I tentatively conclude that backtracking should never be needed
to find the best solution. I would have to revisit that conclusion if anyone adds
some tests to test_grades.m that cause it to generate INCONSISTENT.

As for attempting to evaluate all possibilities: the solver never does that.
The try_all_grade_structs tool does, and it shows that there are over a million
valid grade combinations (modulo the conversation above wrt thread safety).
While you would only get a fraction of that for any real invocation of the solver,
you can still easily get thousands, differing from each other in the presence
or absence of some feature that the user hasn't mentioned at all. I don't see
any situation whatever in which printing them all would help the user, and
without that, I don't see why the grade library should ever compute them all.

>  + Can we add / do you plan to add support for other requirements that
>    aren't compilation model things.  For example, it'd be nice if the user
>    could say "I want parallel conjunctions", even though this is not a
>    compilation model setting it implies other settings, in this case:
>
>      backend=llds
>      thread_safe=thread_safe
> 
>    Likewise "threading model" might be another thing.  The LLDS has an N:M
>    threading model while the MLDS grades have 1:1 threading (unless their
>    targets override this, some old JVMs used to implement N:M).

I think those would only need three additional solver vars (want par conj,
want 1:1 thread model, want N:M thread modules) and two requirements
for each of those vars (e.g. want par conj requires backend=llds, want par
conj requires thread safe). The cost should be minimal: the solver throws
away every requirement that it knows won't be needed again. So if want par
conj is set to "no", both those requirements will be thrown away after being
tested just once.

Thanks for the review.

For something this important, I would prefer to have two or three reviews,
though it may be a good idea for other reviews to look at the grade library
after I fixed the issues raised by Paul.

Zoltan.