[Haskell-cafe] idea for avoiding temporaries
claus.reinke at talk21.com
Fri Mar 9 11:02:04 EST 2007
> 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
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.
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 1181 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070309/c3fb9f35/Arrays.obj
More information about the Haskell-Cafe