[Haskell-cafe] idea for avoiding temporaries

[Claus Reinke]

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

it seems i should qualify that. some simple-minded testing shows that DiffArrays do
become faster than Arrays if the arrays get big enough. for small arrays, though, just 
copying the Array seems faster than maintaining the DiffArray. copying then discarding 
old arrays can be cheaper than the overhead associated with avoiding copies.

so in the simple test attached, loop 10000 a has Array winning for n=10, and 
DiffArray winning for n=30, with DiffUArray always lagging behind DiffArray.

and that is for the most expensive kind of update - updating every element, one 
element at a time (meaning one array copy for each element). for bulk-updates 
(whole-array operations), the picture is likely to be even worse for DiffArrays, 
as the Array version needs only one copy, then a loop to fill it. 

in the test code, loop2 10000 (n=30) has Array winning, Diff(U)Array far behind.

that is, provided i got the strictness right - otherwise, lazyness could lead the code
to access old versions of arrays, defeating the object of single-threaded access to
only the newest version of the DiffArray..

so, your intuition seems to have been more or less correct: if one can do whole-array 
updates, DiffArrays don't seem to buy anything (the copying cost for Array disappears 
in the update loop, the cost of managing DiffArray is not offset by any gains), if one 
has to do partial updates, DiffArrays can be a win, provided the Array copying gets 
more expensive than the DiffArray management overhead. and unboxed DiffArrays,
while they exist, don't seem to buy much (apart from making it easier to avoid the
non-strictness pitfall).

but if one does whole-array updates, there isn't much to be gained by avoiding 
intermediate copies, is there? whether you fill a new memory area, or overwrite
an old one, you still have to loop through the whole thing, writing and reading.

claus
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Arrays.hs
Type: application/octet-stream
Size: 1181 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070309/c3fb9f35/Arrays.obj