Re: Containers and strictness

On Thu, Jul 1, 2010 at 11:54 AM, Johan Tibell wrote:

On Thu, Jul 1, 2010 at 3:38 AM, Felipe Lessa wrote:

...

On Wed, Jun 30, 2010 at 8:02 PM, Johan Tibell wrote:

...

On Thu, Jul 1, 2010 at 12:03 AM, Milan Straka 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