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 00:51
Subject:
Re: Continuations, basic blocks, loops and register allocation
Message ID:
73566872-36E3-11D9-AFE8-000393A6B9DA@mac.com
On Nov 14, 2004, at 3:03 AM, Leopold Toetsch wrote:

> Matt Fowles <ubermatt@gmail.com> wrote:
>
>> Yes, but in the case of the continuation resuming after foo, the
>> continuation should restore the frame to the point where it was taken.
>>  Thus all of the registers will be exactly as they were when the
>> continuation was taken (i.e. in the correct place).
>
> Yes, but Jeff's example wasn't really reflecting the problem.

How come? (Not quibbling--just afraid I'm missing something.) It seems 
that even this function body shows the problem:

	a = 1
	foo()
	print a
	b = 10
	return b

It would seem (w/o continuations) that b should be able to re-use a's 
register, but if it does then we'll print 10 instead of 1 "the second 
time".

> So what to do:
>
> 1) Extending register frame size ad infinitum and never reuse a Parrot
> register will definitely blow caches.
>
> 2) Generating an edge for every call to every previous calls will blow
> the CFG and cause huge pressure on the register allocator. A lot of
> spilling will be the result.
>
> 3) Using lexicals all over is slower (but HLL compilers will very 
> likely
> emit code that does exactly that anyway). So the problem may not be a
> real problem anyway. We just know that an optimizer can't remove the
> refetch of lexicals in most of the subroutines.

It seems that, in term of cache locality, the same problem is there 
with more registers v. spilling v. lexicals. That is, if you have 100 
local variables whose lifetimes overlap (due to continuations), then 
you need 100 distinct memory locations to (repeatedly) access.

> 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.


On the other hand, this Ruby code really bugs me (note: "$" variables 
in Ruby are globals):

% cat continuation5.ruby
def strange
     callcc {|continuation| $saved = continuation}
end

def outer
     a = 0
     strange()
     a = a + 1
     print "a = ", a, "\n"
     a = "hello"
     print "a = ", a, "\n"
end

outer()

$saved.call

% ruby continuation5.ruby
a = 1
a = hello
continuation5.ruby:8:in `+': failed to convert Fixnum into String 
(TypeError)
         from continuation5.ruby:8:in `outer'
         from continuation5.ruby:14

What bugs me is that "outer" gets an error when the continuation is 
invoked, because "the second time" strange() returns, "a" is a string 
and so you can't add 1 to it. But looking at the definition of "outer", 
you'd expect that you could never get such an error. (Without the line 
setting "a" to "hello", you get an infinite loop, printing increasing 
integers.)

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