[Haskell-cafe] idea for avoiding temporaries

David Roundy droundy at darcs.net
Thu Mar 8 16:27:16 EST 2007

On Thu, Mar 08, 2007 at 08:45:06PM -0000, Claus Reinke wrote:
> >Except that DiffArrays are slow and expensive in both space and time
> >(compared with strict unboxed arrays).  They necesarily hold boxed values
> >so you pay a factor of at least two in space cost (for arrays of Doubles)
> >right off the top, and there's no way you could recover that.  I'll admit
> >that they could be useful for something, but I couldn't guess what.  In my
> >experience, arrays are always used with strict values, and updates change
> >all the values in an array.
> i never quite understood why DiffArrays are so slow at the moment, so 
> perhaps this is a good opportunity to ask for enlightenment on this issue?-)
> and i don't understand why they should necessarily hold boxed values only:
> the idea was to hold an efficient full version at the front, and slower
> differences at the back. what would stop the main version from being
> unboxed?

I guess if you do it in this way you'd still have worse memory use than
with ordinary arrays, since you'd hang onto the old unboxed version
indefinitely, and also store a bunch of boxed new versions.

The real issue for me is that DiffArrays only make any sense at all if you
often update a subset of your array, which I never expect to do... so even
if they were efficiently implemented to the point of zero overhead, they
would gain me nothing, and that's almost certainly overly optimistic.

And to be honest, I'm doubtful that there are many applications in which
you want to update only a very small subset of an array, so I'm not really
sure what DiffArrays are intended to be used for.  Once you've updated all
(or most of) the elements, DiffArrays are as slow as their back end, and
you may as well just use their back end without the DiffArray business.
David Roundy
Department of Physics
Oregon State University

More information about the Haskell-Cafe mailing list