Neil Mitchell wrote:

Hi Adrian

...

The GHC users guide says overloading "is death to performance if left to linger in an inner loop" and one thing I noticed while playing about with the AVL lib was that using a HOF and passing the (overloaded) compare function as an explicit argument at the start seemed to give noticable a performance boost (compared with dictionary passing presumably).

I'm not sure why that should be, but has anyone else noticed this?

A HOF is one box, the Ord dictionary is an 8-box tuple containing HOF boxes. When you invoke compare out of Ord, you are taking something out of the tuple, whereas when you use the HOF its directly there.

Well I can understand why overloading might be slow compared to a direct call (presumably this is what you get from specialisation). But I wouldn't have thought this additional indirection cost of method lookup was very significant compared with the HOF approach (at least not after everything was in cache). IOW I would have expected HOFs to just about as deathly to performance as (unspecialised) overloading, but it seems this isn't the case.

This is also the reason you get a performance decrease moving from a 1-element class to a 2-element class.

Why is that? Does ghc pass just the single method rather than a one entry dictionary in such cases? Regards -- Adrian Hey

Adrian Hey wrote:

Duncan Coutts wrote:

...

One might hope that in this case we could hoist the extraction of the dictionary members outside the inner loop.

This possibility had crossed my mind too. If HOFs really are faster (for whatever reason) then it should be possible for a compiler to do this automatically.

Once everything is in terms of dictionaries, this should even be part of ``full laziness''. Wolfram

Cool. You know which types to consider because jhc is a whole-program compiler? Given the whole program, why not monomorphize, and inline away all of the dictionaries? - Conal On 5/4/07, John Meacham wrote:

On Fri, May 04, 2007 at 03:07:41PM -0700, Conal Elliott wrote:

...

Does anyone know what became of Dictionary-free Overloading by Partial Evaluation http://web.cecs.pdx.edu/%7Empj/pubs/pepm94.html? Is it impractical for some reason?

jhc also uses a dictionary free approach, doing a case directly on the type parameter.

The nice thing about this is that _all_ methods can be determined by a single case evaluation, because finding out the right instance for any method will determine the right instance for all other methods too for a given type. The standard case-of-known-value optimization takes care of later scrutinizations (method lookups) on the same type.

John

-- John Meacham - ⑆repetae.net⑆john⑈ _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

Stefan O'Rear:

Data.Sequence doesn't use overloading

Data.Sequence uses overloading for subtree size annotations. The structural recursion seems to make it quite awkward to express size annotations without overloading.

On Fri, May 04, 2007 at 05:06:10PM -0700, Conal Elliott wrote:

Cool. You know which types to consider because jhc is a whole-program compiler?

Yes. though, i have since redone the back end so there is no technical reason for it to be whole program any more, you can just benefit from more optimizations that way. The old backend required global knowledge to compile at all.

Given the whole program, why not monomorphize, and inline away all of the dictionaries?

Well that is the thing, there are no dictionaries at all, the only extra arguments passed in are the types so, f :: forall a . (Foo a, Baz a, Bar a Int, Bred a) => a -> a still is only passed the single hidden argument of 'a' since a case on it will determine what method to use. (+) a x y = case a of Int -> plusInt x y Float -> plusFloat x y and so forth. a here is a type, of kind '*'. since the method lookup is done explicitly via the case statement, it can be optimized via standard transformations in nice ways. John

- Conal

On 5/4/07, John Meacham wrote:

...

On Fri, May 04, 2007 at 03:07:41PM -0700, Conal Elliott wrote:

...

Does anyone know what became of Dictionary-free Overloading by Partial Evaluation http://web.cecs.pdx.edu/%7Empj/pubs/pepm94.html? Is it impractical for some reason?

jhc also uses a dictionary free approach, doing a case directly on the type parameter.

The nice thing about this is that _all_ methods can be determined by a single case evaluation, because finding out the right instance for any method will determine the right instance for all other methods too for a given type. The standard case-of-known-value optimization takes care of later scrutinizations (method lookups) on the same type.

John

-- John Meacham - ⑆repetae.net⑆john⑈ _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

-- Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

-- John Meacham - ⑆repetae.net⑆john⑈