[Haskell-cafe] idea for avoiding temporaries

[Claus Reinke]

> * The algorithm as written already tries to express minimal storage.   
> The only question is, do +=, -=, and := update their left-hand side  
> in place, or do we think of them (in the Haskell model of the  
> universe) as fresh arrays, and the previous values as newly-created  
> garbage?  My challenge to fellow Haskell hackers: find a way to  
> express this such that it doesn't look so imperative.
> 
> * Even if we do a good job with += and -=, which is what David seems  
> to be looking for, we still have those irritating := assignments--- 
> we'd like to throw out the old p and reuse the space in the last  
> line.  And we'd like to have one piece of storage to hold the q on  
> each successive iteration.  So even if we solve David's problem, we  
> still haven't matched the space requirements of the imperative code.

i find it difficult to discuss performance issues without concrete code examples, 
so i decided to convert Jan-Willem's loop code into Haskell. at first, i just naively 
translated the loop to recursion over lists, then i tried to produce an update-inplace 
variant based on some form of arrays, and finally i added a variant based on strict 
lists (would be nice to have standard libraries for (head-/spine-)strict lists, btw).

both the array and strict list versions avoid some intermediate structures; for the 
arbitrarily invented, relatively small inputs i've tried, strict lists are the clear winner, 
thanks to lower memory traffic, but i'd like some feedback from the experts:

-are there any obvious inefficiencies in the array code?
-what does your real code look like, in view of scaling to much larger inputs?

-i tried to keep the computations equal, but seem to have introduced a
    small variance in the strict list version, which i can't seem to spot by
    staring at it. any ideas?

-i assume the memory overhead of binary strict lists is unacceptable for
    large inputs, but i'm still waiting for those polymorphic bytestrings..;-)

while playing with this code, it occurred to me that situations as that described by 
David (small numbers of huge structures of constant size, with no nested pointers) 
are less suited for compacting garbage collection than for slot-reusing reference 
counting. GC wins in the common situation of many variable-sized, frequently 
created/destroyed structures, by touching only those objects that are live when 
space runs out, while RC has a higher continuous overhead.

as i mentioned earlier, i'm not sure whether update-in-place vs recreate is so 
bad for whole-array updates, but the real win could be not having to copy the 
huge live arrays arround at GC time (either from old to new space, or within 
one space, to create contiguous free slots while compacting the occupied slots). 

so instead of update-in-place in virtual memory space, which will still be copied 
at GC time, one would want to pin the virtual region in which the arrays are 
allocated to a real memory region, and tell the GC to keep its hands off it (none 
of that space will be released until the loop ends, all of it will be released after 
the loop ends and a copy of z has been made). does this make sense to the 
number crunchers and memory managers out there? and is there a way to 
allocate Haskell arrays to such pinned memory regions?

claus
-------------- next part --------------
A non-text attachment was scrubbed...
Name: CG.hs
Type: application/octet-stream
Size: 5796 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070311/74e5b3b8/CG.obj