Jan Skibinski wrote:
>
> On Fri, 4 Dec 1998, Fergus Henderson wrote:
>
> ...
> > I think your understanding is gravely mistaken.
> >
> > The intent, I believe, is that Haskell Arrays should be
> > implemented as contiguous memory, at least for optimizing compilers.
> > Implementations using association lists would IMHO only be
> > suitable only for non-optimizing compilers.
> >
>
> Well, this was only my understanding and was qualified as
> one of the things that were not clear to me. I still
> have my doubts and I would really like to find some
> authoritative answer instead of heresays about slugishness
> of Haskell arrays that I see here and there on the net.
>
> See for example, "Implementing the conjugate gradient
> algorithm" by P.R. Serrarens, http://www.cs.kun.nl/~pascalrs/
> He very definitely dismisses Haskell arrays as unsuitable for
> scientific computations. He used GHC - optimized compiler
> after all. On the other hand, he speaks highly of Haskell lists.
You are right that Haskell lists compared favourably against Haskell
Arrays and GHC's ByteArray's. The Haskell Array used a non-optimised
implementation using lists and could not be fast. The ByteArrays use
contiguous memory but were surprisingly slow. The reason for that was
that the state monad introduced quite a lot overhead.
On the other hand I showed some good results using the arrays provided by
Clean: (The efficiency of lists in Clean is comparable to Haskell lists)
|| Lists || Arrays
Size || Lazy | Strict || Lazy | Strict | Unboxed
----------------------------------------------------
625^2 || 1.09 | 0.70 || 1.38 | 0.28 | 0.18
2500^2 || 9.06 | 7.51 || 15.10 | 3.23 | 1.45
10000^2 || | 73.01 || | 31.21 | 14.57
40000^2 || | || | 318.45 | 159.13
The most important here is the unboxed array, where the arrays is
stored in contiguous memory. Apart from being more efficient in
memory usage (the reason why some numbers are left out is that
those problems used too much memory, see paper), is is also
considerably faster.
So we may conclude that the specific implementation of GHC ByteArrays is
not efficient. Arrays in general will give better performance in cases
were indexing is important.
> Which prompted me to do my little tests in Hugs. Also favouring
> the lists..
Which does not provide a good implementation for arrays either.
Pascal Serrarens.
