DiffArray Performance

Simon Marlow simonmar at microsoft.com
Mon Nov 3 13:40:51 EST 2003

> Hello again,
> Another thought..
> Could it be that sTree0 is cyclic that accounts for this
> dramatic slow down? I'm not to sure how DiffArray are
> implemented, but if it's how I would do it it seems you
> would end up with a massive chain of indirections.

Possible.  It is possible to get an O(n) slowdown by using DiffArrays,
but only if you index the original array after making updates to it.  If
you use the array in a single-threaded way, then indexing should be O(1)
and additionally update should be O(1) compared to O(n) for ordinary

It's possible that your use of array here is being implemented as a
sequence of updates, which will lead to highly suboptimal behaviour:

> > > sTree0 :: STree
> > > sTree0 = STree (array (0,9) [(n,(sTree0,[]))| n <- [0..9]])

I haven't checked the DiffArray implementation, though (it would be nice
if someone could investigate DiffArray and fix any perf problems they


More information about the Glasgow-haskell-users mailing list