On Mar 29, 2006, at 11:50 AM, Robert Dockins wrote:
On Mar 29, 2006, at 2:23 PM, Andy Gill wrote:
John, et. al.,
I'd rather just use a polymorphic function, but would having some sort of ... notation in class contexts help?
sort (Eq a,_) => [a] -> [a]
Which means that we need at least the Eq a, but perhaps more. See #86 http://hackage.haskell.org/trac/haskell-prime/wiki/ PartialTypeAnnotations
In terms of seq, and deepSeq, here is a space leak problem I often need to solve.
Imagine a function
cpuStep :: CPUState -> CPUState
where the CPUState is a large structure, for (say) the 68000 register file, a and also contains information about a level-1 cache.
I want to run for 100,000 instructions.
runCPU :: Int -> CPUState -> CPUState runCPU 0 state = state runCPU n state = runCPU (n-1) (cpuStep state)
My job is to make this run in approximately constant space; a reasonable request.
Well, we can add a seq to the modified state:
runCPU n state = state'` `seq` runCPU (n-1) state' where state' = cpuStep state
But the thing still leaks like crazy. *I've seen this again and again.* Some internal piece of data inside CPUState depends on the value of another piece of CPUState from the previous iteration.
[snip]
Questions - Does anyone have any better suggestions of how to fix this real issue?
My initial thought is to add strictness flags to the datatype declaration for the bits of state that cause trouble (report, section 4.2.1). For something like this, I'd expect you could safely mark _every_ field strict; in that case you might be able to coerce the compiler to unbox the entire state record and save a few allocations.
But it strikes me that you must have thought of this already; is there some reason it won't work?
[snip]
The principal concern is the space leak, not the performance. But you ask a good question. Well, first the number of datatypes involved was large, over 100 data's. Put in the 100s of bangs, and the problem was still there. Secondly, we might not have access the the code for cpuStep, it might be in a library. The problem(s) were things like regs :: !Array Int RegVal status :: ![Status] The ! gives you a single level of strictness, so the list above is only strict in its first cons, not its spine or its elements. The Array is not strict in its values. If a RegVal depends on a previous register value, it might keep the *whole* array inside the thunk. Consider this example: copyRegister :: Int -> Int -> Array Int RegVal -> Array Int RegVal copyRegister r1 r2 arr = arr // [(r1,arr ! r2)] a simple fix is: copyRegister :: Int -> Int -> Array Int RegVal -> Array Int RegVal copyRegister r1 r2 arr = deepSeq $ arr // [(r1,arr ! r2)] But what happens if 'copyRegister a b' is itself a thunk? Perhaps something like: regs :: !!Array Int RegVal status :: !![Status] should be considered. (Aside: What would be nice to have is "there should only be one instance of this type, tell me if that is not the case" evaluation mode. I'm not quite sure how to express this, though). Andy Gill