DiffArray Performance

[Adrian Hey]

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]])

<snip>

> 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).