develooper Front page | perl.perl6.internals | Postings from November 2004

Re: Continuations, basic blocks, loops and register allocation

Thread Previous | Thread Next
From:
Jeff Clites
Date:
November 15, 2004 09:12
Subject:
Re: Continuations, basic blocks, loops and register allocation
Message ID:
787FEB7D-3729-11D9-AFE8-000393A6B9DA@mac.com
On Nov 15, 2004, at 3:27 AM, Leopold Toetsch wrote:

> Jeff Clites <jclites@mac.com> wrote:
>> On Nov 14, 2004, at 3:03 AM, Leopold Toetsch wrote:
>
>>> Yes, but Jeff's example wasn't really reflecting the problem.
>
>> How come?
>
> Your code didn't reuse C<a> after the call.

Oops.

>> It seems that, in term of cache locality, the same problem is there
>> with more registers v. spilling v. lexicals.
>
> Not quite. We can't extend just one register set, we'd do that for all 
> 4
> kinds. You can not easily have 64 PMC registers and just 10 INTVALs.
> A lexical access is just an array lookup (at least if the compiler uses
> the indexed addressing of lexicals).

Ah. What I don't like, though, is that in the in the lexical case you 
have things sitting in an  array, from which you need to move things 
back-and-forth to registers to work on them. In the "more registers" 
case, they're sitting in a quite similar array, but you can work on 
them directly there. Adding 2 such INTVALs is one op, instead of 4 (2 
loads, 1 add, 1 store). Since the problem exists for all register types 
(unless HLLs only use PMCs, which is possible), then we either need 4 
lexical arrays for maximum locality (so that they can be sized 
independently), or we need to be able to size the register frames 
independently for the 4 types. (I realize that currently lexicals must 
be PMCs, but it seems we have the same issue with other reg. types.)

>> ... That is, if you have 100
>> local variables whose lifetimes overlap (due to continuations), then
>> you need 100 distinct memory locations to (repeatedly) access.
>
> Sure. If the program is complex you need the storage anyway.

But I think the real problem is that it's only due to CPS that the 
lifetimes are overlapping so much--that's what's biting us. (By 
expanding my example code, you could come up with simple code which 
uses 100 locals be would only need 1 register w/o continuations, and 
needs 100 "spots" with them.) It's just a pretty unfortunate price 
we're paying, if the feature is not extensively used. Now we're just 
figuring out how to survive it.

>>> 4) Having an explicit syntax construct 
>>> "(call-with-current-continuation
>>> " that expresses verbatim, what's going on, like e.g. with a reserved
>>> word placed as a label:
>>>
>>>   RESUMEABLE: x = choose(arr1)
>
>> I don't think that really helps either: If you have such a call, then
>> all the frames higher up the stack also can "return multiple times", 
>> so
>> they have the behavior, even w/o the label.
>
> The RESUMABLE label is of course at the invocation that might
> resume, somehwere up the call chain. Again: the HLL compiler (or the
> programmer) knows the effect of the continuation. Just the PIR code is
> too dumb, i.e. is lacking this information.

Picture this call stack:

	main --> A --> B --> C --> D --> E

The call from D to E uses the "RESUMEABLE" label, and E stores the 
resulting continuation in a global, and everything up to main returns. 
Then, main invokes the continuation, and we find ourselves back in D. 
Now, C, B, and A will return "again", without any compile-time hint.

>> On the other hand, this Ruby code really bugs me (note: "$" variables
>> in Ruby are globals):
>
>> ... , you get an infinite loop, printing increasing
>> integers.)
>
> Sure. With callcc you are calling the function again and again.

I know--the infinite loop was the "desired" behavior (just mentioned it 
so that people wouldn't have to run it). What bugs me is that you can 
get that error, though looking at the code it should be impossible. The 
author of outer() might have no clue that could happen, so it's not 
really his bug, and the person using a continuation needs really 
detailed knowledge of everything in the call stack, to know if it will 
work. I guess that's "just how it is", but it seems to mean that 
continuations have limited usefulness in languages with side-effects, 
except for very local usage (breaking out of a loop and such).

JEff


Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About