Containers and strictness

[Edward Kmett]

On Thu, Jul 1, 2010 at 11:54 AM, Johan Tibell <johan.tibell at gmail.com>wrote:

> On Thu, Jul 1, 2010 at 3:38 AM, Felipe Lessa <felipe.lessa at gmail.com>wrote:
>
>> On Wed, Jun 30, 2010 at 8:02 PM, Johan Tibell <johan.tibell at gmail.com>
>> wrote:
>> > On Thu, Jul 1, 2010 at 12:03 AM, Milan Straka <fox at ucw.cz> wrote:
>> >> After suggestions by others I am thinking about
>> >>  data Some elem = Single {-# UNPACK #-} !elem | More (Set elem)
>> >> or
>> >>  data Some elem = Single {-# UNPACK #-} !elem | More {-# UNPACK #-}
>> !elem
>> >> (Some elem)
>> >
>> > Unfortunately unpacking doesn't work for polymorphic fields (the new
>> warning
>> > for ineffective unpack pragmas in GHC head should warn about this).
>> Given
>> > this you might as well use a standard list.
>>
>> However strictness information does work.  But I don't know the answer
>> for the following questions:
>>
>>  - Should the elements be strict even while they are not unpacked?
>> Performance gains?
>>
>
For keys that are used by the structure, this can mean that during lookups,
etc. the compiler can know that it can skip evaluation. But since you hand
off to a user provided comparison function (even for the Eq/Ord
typeclasses), the information that it can skip evaluation is often lost.

  - Should the spine of the list be strict? Performance gains? Space leak
>> gains?
>>
>
> In my experience/benchmarks strict spines are faster, probably due to
> better cache usage as the whole structure is updated at once.
>

That and the compiler can emit code that just checks tags and doesn't have
to deal with forcing evaluation at all on recursion.

All the container data structures use strict spines.
>

Almost all. =)

Strict spines are a must, except in those few cases where you need to not be
strict to retain appropriate asymptotics in a persistent environment (the
deep node pointers in Data.Sequence.Seq for instance must be lazy or
operations can be logarithmically more expensive when used persistently).

In practice this applies to none of the other types in containers though.

-Edward Kmett
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100701/eb30c6e8/attachment.html