gyro@cymbal.reasoning.COM (Scott Layson Burson) (05/04/91)
I've received several private replies to my message of the other day on stack/heap continuation allocation. A couple of comments: In my haste to send that message I neglected to be perfectly clear about what I take to be the primary value of my approach, which is that it eliminates *all* copying of continuations, both at capture time and at invocation time (though the GC can, and typically will, move them around). Several people have said "this sounds like ...". You're all correct, it does *sound like* various ideas that were already in the literature. I haven't yet dug up the paper on Chez Scheme (can somebody give me a precise reference?), but I have looked at both the original Bobrow & Wegbreit paper (CACM '73) on "spaghetti stacks" and the Clinger et al. paper from Snowbird (L&FP '88) and the results so far are very interesting indeed. In a nutshell: all the key components of my approach have been thought of before. But nobody seems to have put them all together at once to eliminate continuation copying entirely. I refer you particularly to Will Clinger's description of the "stack/heap" strategy in that paper. The assembly code for frame allocation and deallocation, shown in Figure 2, is identical to that used in my approach. But the paper also contains this sentence: "When a continuation is captured, however, the contents of the stack cache are moved into the heap and the stack cache is cleared." Nobody seems to have thought of the simple hack of bumping a pointer to effectively transfer frames from the stack to the heap without actually copying them. Granted, this is probably not all that big a deal performance-wise even for a continuation-intensive program. Furthermore, Marc Feeley points out quite correctly that certain operating system issues impinge at this point: if the stack is to be kept in the system stack area, my approach requires that the stack area be able to grow more-or-less indefinitely. Whether that's possible varies. However, my initial thinking (within the context of a Un*x- based implementation) was actually to allocate large chunks of stack space in the data segment, and leave the system stack alone (especially with 32 registers to work with, I think it's defensible to allocate three of them for stack control); it was only secondarily that I realized that one could, at least under some operating systems, use the system stack. So anyhow, while my idea is admittedly only an incremental improvement over previous approaches, it does appear that it is not quite identical to any that have preceded it. -- Scott