On Mon, 2007-03-05 at 15:06 +1100, skaller wrote:
> I have added a monomorphisation pass to the optimisation process.
> The main reason for doing all this is so that polymorphic calls
> to virtual functions of typeclasses become monomorphic which
> allows them to be instantiated, and subsequently inlined,
> so that there is zero performance penalty for using
> virtual functions.
> Strangely this didn't fix the dispatch to 'ge' in Takfp ..
> well not so strangely, since this was monomorphic anyhow.
> The reason is probably that the dispatch is an "apply_prim"
> which isn't considered for inlining.
It aint so :) The reason is simpler: virtual functions are
marked 'noinline'. Here's the reason:
// total order
typeclass Tord[t]{
inherit Eq[t];
virtual fun lt: t * t -> bool;
virtual fun gt(x:t,y:t):bool =>lt(y,x);
virtual fun le(x:t,y:t):bool => not (gt(x,y));
virtual fun ge(x:t,y:t):bool => not (lt(x,y));
virtual fun max(x:t,y:t):t=> if lt(x,y) then y else x endif;
virtual fun min(x:t,y:t):t => if lt(x,y) then x else y endif;
}
Consider the ge function. If we inlined the default definition, we'd
be left with a dispatch to lt. However we could have had:
virtual fun lt(x:t,y:t):bool => not (ge(x,y));
which would lead to an infinite recursion. And, we could have
had
instance Tord[int]{
fun ge: int * int -> bool = "$1>=$2";
...
}
which 'overrides' the definition of ge.
The 'default definition' of a virtual function has two roles:
to provide a way to reduce the complexity of instances by
reducing the number of definitions you have to have, and,
to provide an AXIOM which acts as a semantic obligation
for specification for instances. You could write:
axiom ax(x:t, y:t): ge(x,y) == not (lt(x,y));
or indeed:
reduce ax(x:t, y:t): ge(x,y) => not (lt(x,y));
which 'theoretically' would have the same impact: the
default method syntax is easier and more natural,
but it allows a choice between the axiom and reduce
forms to be made on an instance by instance basis.
The PROBLEM I am having is simple: I can't tell so easily
whether a call to a virtual function is going to be
dispatched to an overriding instantiation or a specialisation
of the default body. Indeed part of the problem is that I
can't tell so easily if a call is to a virtual function or not.
This is similar to the problem of deciding whether a call
might be reduced by a reduction.
The following algorithm is safe: check if a call is
to a virtual function. If it is, try to find an instance.
If you find an instance, replace the call with one to
the instance.
Felix applies that algorithm left right and centre,
it is in fact named:
Flx_typeclass.maybe_fixup_typeclass_instance
The sooner this is done, the more likely we'll be able
to optimise the code.
Now, IF this fixup fails to change anything there are
actually five possibilities:
(a) The call isn't to a virtual function in the first place
(b) The call is to a virtual function but isn't monomorphic
and so can't be instantiated **** (it is a white lie)
(c) The call is monomorphic, there is no instance,
so the default method should be used
(d) The call is monomorphic, there is no instance,
and there's no default method -- ERROR
(e) The call is monomorphic and there is an instance
In order to inline a default method we have to know
that it is case (c). It is easy to detect case (e)
by simply comparing
i,ts = maybe_fixup_typeclass_instance i,ts
If the comparison fails, we have found an instance.
However this is pointless because the code already
replaces the call to the virtual with a call to the
instance.
The trick here is to know when there is a typeclass
instance selected but no function instance.
**** the white lie is that instances can be polymorphic
So whilst a monomorphisation check will work it is too
conservative.
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Felix-language mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/felix-language
