SimonM:
I can get it to fail another way too:
main = do p <- mallocBytes 64 newForeignPtr p (print x) print x where x = sum [1..10000]
Alastair:
The problem is probably this shared mutable variable used behind the scenes in the implementation of the numeric show code (hugs98/src/printer.c)
static Cell out; /* GC'd var used by printer code */
[It's also used if you use the -u flag to use Hugs' builtin printer instead of the Show function - but I don't think anyone does that anymore and we could probably kill that code without anyone noticing (???). (Unless, does Hood or some such use it?)]
I think all the functions affected return void so it'd be easy to replace the global variable with a local which is threaded through that set of functions.
My impression is that the problem is more fundamental: the thunk for x is under evaluation when the finalizer begins to run, so it already has a bunch of stuff on the stack. The finalizer starts to run, and demands the value of x - probably we shouldn't get a crash, but a blackhole instead. Fixing it so that the evaluation of x is actually continued is what we want, but I can't see an easy way to do that. I suppose you could suspend either the finalizer or the main thread using the trick of saving its stack on the heap - is this implemented in Hugs? The only other solution I can think of is to delay finalizers until we get back up to the IO monad. Usual disclaimers apply: I have very little idea how the Hugs backend works, so there might be another way around this. Cheers, Simon
On Fri, Oct 18, 2002 at 04:38:24PM +0100, Simon Marlow wrote:
SimonM:
I can get it to fail another way too:
main = do p <- mallocBytes 64 newForeignPtr p (print x) print x where x = sum [1..10000]
Alastair:
The problem is probably this shared mutable variable used behind the scenes in the implementation of the numeric show code (hugs98/src/printer.c) [...]
My impression is that the problem is more fundamental: the thunk for x is under evaluation when the finalizer begins to run, so it already has a bunch of stuff on the stack. The finalizer starts to run, and demands the value of x - probably we shouldn't get a crash, but a blackhole instead. Fixing it so that the evaluation of x is actually continued is what we want, but I can't see an easy way to do that.
It's both, I think -- I missed the evalWithNoError() in printer(). But if you bypass the builtin printer by replacing print x with putStrLn (showInt x ""), you get an incorrect answer instead of the expected black hole.
SimonM:
I can get it to fail another way too:
main = do p <- mallocBytes 64 newForeignPtr p (print x) print x where x = sum [1..10000]
FWIW, both GHC and nhc98 seem to have similar problems with this code. In nhc98, depending on heapsize, you either get the normal output (and the finaliser does not run), or the finaliser runs giving its output, and the main thread crashes immediately afterwards. In GHC, no matter the heapsize, you only ever get one output. Either the finaliser is not run, or it runs after stdout has already been closed, or it does run and the main thread does not complete. (I can't immediately tell which case pertains.) In nhc98 at least, I am certain that the problem is as you say:
My impression is that the problem is more fundamental: the thunk for x is under evaluation when the finalizer begins to run, so it already has a bunch of stuff on the stack. The finalizer starts to run, and demands the value of x - probably we shouldn't get a crash, but a blackhole instead.
Since for us the finaliser does actually evaluate correctly, I suspect that after the closure for x is updated with its value, control returns to the main thread, which still has a bunch of intermediate values on the stack that are now invalid. Do we /want/ a blackhole? If so, then I can fix nhc98. If not, then I can't immediately see a good solution. Regards, Malcolm
Do we /want/ a blackhole? If so, then I can fix nhc98. If not, then I can't immediately see a good solution.
A blackhole would be wrong semantically because: - blackholes mean that a value depends on itself - that isn't true here - changing evaluation order shouldn't change whether the program produces an answer or what answer it produces (as would happen in this case if you deferred the finalizer or ran the finalizer immediately the object was garbage (i.e., before the main thread continued). - decreasing sharing shouldn't change whether the program produces an answer or what answer it produces but it would change the result in this program. btw What abstract machine is NHC based on? Given its Swedish origins, I expect it's a slightly modified G machine? In my paper about the stack->heap trick http://www.reid-consulting-uk.ltd.uk/alastair/publications/ifl98.ps.gz I claimed that it was a fix for a problem in the STG machine which was not present in pure graph-reduction implementations. That is, I claimed that pure graph-reduction implementations don't need blackholing and can be interrupted/context-switched at the end of any reduction step. Not only is this not true of teh STG-machine, but it isn't true of G-machine implementations either -I think blackholing was first described for LML-. The problem is that the G-machine optimizes away some of the updates which make sure that the heap is always in a consistent state in a pure graph-reduction system. This leaves me wondering whether there is some way to fix G-machine implementations so that it is always possible to abort a thread (i.e., a finalizer) and restart it later in just the same way that reverting black holes lets us do that with the STG machine? (There's then a separate question as to whether it is feasible to apply this to Hugs and NHC without rewriting their evaluators from scratch. I'm not overly optimistic about this but who knows?) -- Alastair
Alastair Reid <alastair@reid-consulting-uk.ltd.uk> writes:
Do we /want/ a blackhole?
A blackhole would be wrong semantically because: - blackholes mean that a value depends on itself - that isn't true here
Agreed. The usual operational discovery of a blackhole in a non-threaded system is exactly when the mutator is attempting to evaluate a node that is already under evaluation. Since the finaliser is essentially a separate thread, that simple operational understanding no longer points definitively to a blackhole.
- changing evaluation order shouldn't change whether the program produces an answer or what answer it produces
Apart from possibly changing the order of any side-effects, yes.
btw What abstract machine is NHC based on? Given its Swedish origins, I expect it's a slightly modified G machine?
Exactly so. The paper "nhc - a space-efficient Haskell compiler" in Niklas's thesis (also presented at IFL94, ICFP95) mentions that it is a very basic G machine, based on the SimonPJ implementation book (1987). Since then, we've made a few tweaks for performance, but no major changes to the model.
The problem is that the G-machine optimizes away some of the updates which make sure that the heap is always in a consistent state in a pure graph-reduction system.
A pure G-machine updates all redexes, but the STG-machine only updates /shared/ redexes, yes? Regards, Malcolm
The problem is that the G-machine optimizes away some of the updates which make sure that the heap is always in a consistent state in a pure graph-reduction system.
A pure G-machine updates all redexes, but the STG-machine only updates /shared/ redexes, yes?
It's a while since I looked at it but, IIRC, a naive graph reducer can update the same redex multiple times while the G-machine tries to update it just once. -- Alastair
SimonM:
My impression is that the problem is more fundamental: the thunk for x is under evaluation when the finalizer begins to run,
Urgle.
probably we shouldn't get a crash, but a blackhole instead.
Even a blackhole is wrong. There's no cycle so it ought to evaluate successfully.
Fixing it so that the evaluation of x is actually continued is what we want, but I can't see an easy way to do that.
I think GHC does the right thing (semantically) here. From memory, GHC works like this: on entering thunk: turn it from a thunk into a blocking queue (optimization: delay the transformation until context switch time) on entering a blocking queue: if cyclic structure (i.e., already under evaluation by same thread), report blackhole. otherwise, put this thread to sleep on the blocking queue. Based on this, what does GHC do here when a finalizer tries to evaluate a thunk already being evaluated? The finalizer is put to sleep until the main thread finishes evaluation of the thunk. And what does GHC do if a call to unsafePerformIO hits a thunk already under evaluation by the same thread? This is a blackhole (i.e., deadlock). The thread throws the blackhole exception. I think Hugs should report a blackhole in the unsafePerformIO case (I believe it does already). Hugs (and NHC, I believe) have no way to block finalizers once they start executing. I think our only choice is to turn off blackholing, allow the shared term to be evaluated twice over and hope that the two updates to the thunk (one by finalizer and then one by the main thread) don't do any harm. I don't know if this would work. Even if it does, it's not too palatable because of the loss of sharing and the space leaks (that blackholing normally fixes).
I suppose you could suspend either the finalizer or the main thread using the trick of saving its stack on the heap - is this implemented in Hugs?
No - it is an STG-specific trick. Hugs is based on the G-machine. In Hugs, the state of a pure evaluation is stored on the C stack and in the heap. We could try longjmp-ing out of the finalizer and hope that the heap has a full and consistent record of the state but I'm not overly confident that this would work. (Hmmm, longjmp-ing out is what exception handlers do and we believe that those work....)
The only other solution I can think of is to delay finalizers until we get back up to the IO monad.
and not inside an unsafePerformIO call. -- Alastair
participants (4)
-
Alastair Reid -
Malcolm Wallace -
Ross Paterson -
Simon Marlow