[m-dev.] for review: type specialization [2]

[Fergus Henderson]

Here's a review of just the documentation.

On 17-Feb-1999, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> 
> Index: doc/reference_manual.texi
> +* Type specialization::		Produce specialized versions of polymorphic
> +				predicates.
>  * Obsolescence::                Library developers can declare old versions
>                                  of predicates or functions to be obsolete.
>  * Source file name::            The @samp{source_file} pragma and
> @@ -4422,6 +4424,61 @@
>  simply for performance concerns (inlining can cause unwanted code bloat
>  in some cases) or to prevent possibly dangerous inlining when using
>  low-level C code.
> +
> + at node Type specialization
> + at section Type specialization
> +
> +The overhead of polymorphism can in some cases be significant, especially
> +where polymorphic predicates make heavy use of the built-in unification
> +and comparison routines. The Mercury compiler includes a pass which perform
> +type specialization of polymorphic procedures. Unfortunately, the current
> +implementation of inter-module optimization is not suited to performing type
> +specialization because it would create copies of a type-specialized version
> +of a predicate in each module it is needed, rather than just creating
> +one shared copy. To avoid this, the programmer can specify which specialized
> +versions should be created, ensuring that they are only created once.

s/which perform/which performs/

Type specialization should be just as important for polymorphic predicates
that make heave use of type class method calls as it is for predicates
that make heave use of the built-in unification and comparison.


This whole discussion is too focused on implementation-specifics.
We shouldn't add a language feature simply because "the current
implementation ... is not suited ...".  If that were the only rationale,
then this pragma should go in the "implementation-dependent pragmas"
section of the reference manual, rather than being something that
*all* implementations are expected to recognize.

I don't think that is the case -- I think the feature is worth
adding to the language rather than just being something
implementation-specific.  Ghc has a similar pragma,
and that some Haskell programmers wish that this was a standard
feature of Haskell rather than a ghc-specific thing,
so I think we may as well make it a standard feature of Mercury
rather than something implementation-specific.
(Of course, in the absense of a second implementation, such
distinctions are subtle, but I think they are still worth making,
if only to encourage the possibility of other implementations.)

Implementations should of course be free to ignore such pragmas --
just like `pragma inline', they're only a hint.  So adding the
pragmas to the language does not impose any significant implementation
burden.

> +A declaration of the form
> +
> + at example
> +:- pragma type_spec(@var{Name}/@var{Arity}, @var{Subst}).
> +:- pragma type_spec(@var{Name}(@var{Modes}), @var{Subst}).
> + at end example
> +
> + at noindent
> +suggests to the compiler that a specialized version of the named predicate
> +should be created with the type substitution given by @var{Subst} applied
> +to the argument types. The second form of the declaration only suggests
> +specialization of the specified mode of the predicate.

s/predicate/predicate or function/g

> +The substitution is written as a list of @samp{type variable - type} pairs.

You should state it more precisely as "... @samp{@var{TypeVar} -
@var{Type}} pairs, where @var{TypeVar} is a type variable and
@var{Type} is a type".

But I think a slightly different syntax might be better:
I would suggest using "=" instead of "-", and using a conjunction
"(..., ..., ...)" rather than a list "[..., ..., ...]".

> +The replacement types must be ground -- this restriction may be lifted later.
> + at c The main reason for this restriction is that it is tricky to ensure that
> + at c any extra typeclass_infos that may be needed are ordered the same way in
> + at c different modules. The efficiency gain from replacing a type variable with 
> + at c a non-ground type will usually be pretty small anyway.

This restriction is clearly too implementation-specific to make part of
the language.   It should be documented as a limitation of the
of current University of Melbourne Mercury implementation.
The Mercury compiler should issue a warning and then ignore
the declaration rather than issuing an error in such cases.

> +For example, the declarations
> +
> + at example
> +:- pred map__lookup(map(K, V), K, V).
> +:- pragma type_spec(map__lookup/3, [K - int]).
> + at end example
> +
> + at noindent
> +give a hint to the compiler that a version of @samp{map__lookup}/3 should
> +be created for integer keys.

I think elsewhere we have been using `@samp{foo/N}' rather than
`@samp{foo}/N'.  Please check that what you use here is consistent
with what is used elsewhere.

> +The set of types for which a predicate should be specialized is best
> +determined by profiling your application. Overuse of type specialization
> +will result in code bloat. Type specialization is most effective when
> +the specialized types are built-in types such as @samp{int}, @samp{float}
> +and @samp{string}, or enumeration types, since their unification and comparison
> +procedures are small and can be inlined.

This ignores procedures that call typeclass methods.

It would be good if this kind of advice on how to use the feature
was more clearly separated from the documentation on the semantics
of the feature.

> +An implementation is free to ignore @samp{:- pragma type_spec(...)}
> +declarations. The Melbourne Mercury compiler does not when invoked with
> + at samp{--user-guided-type-specialization}, which is enabled at @samp{-O2}.

s/@samp{-O2}/optimization level @samp{-O2} or higher/

It's better to state things positively rather than negatively where
possible; "does not (ignore)" is almost a double negative.
Also it might be better if the implementation-specific stuff was
better separated from the language definition stuff.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "Binaries may die
WWW: <http://www.cs.mu.oz.au/~fjh>  |   but source code lives forever"
PGP: finger fjh at 128.250.37.3        |     -- leaked Microsoft memo.