DiffArray Performance

Adrian Hey ahey at iee.org
Tue Oct 28 14:46:10 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.

Actually, it's probably not a good idea to have a
DiffArray as a top level CAF, cyclic or otherwise?

Hmm.. I think that must be it.

On Monday 27 Oct 2003 6:21 pm, Adrian Hey wrote:
> > -- Search Tree data type
> > newtype STree = STree (Array Int (STree,[Match]))
> > -- Initial value for Search Tree
> > sTree0 :: STree
> > sTree0 = STree (array (0,9) [(n,(sTree0,[]))| n <- [0..9]])


> The code is otherwise identical, so any difference in execution time
> must be caused the difference between reading/writing the respective
> arrays. I wouldn't expect them to be identical but for DiffArrays
> to be over 100 times slower seems a bit strange (especially for
> a relatively small array of 10 elements). That's an O(n^2) difference
> somewhere (neglecting any constant factors).

More information about the Glasgow-haskell-users mailing list