Cost of Overloading vs. HOFs

Adrian Hey ahey at iee.org
Fri May 4 16:53:43 EDT 2007


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



More information about the Glasgow-haskell-users mailing list