Fearless leadership...

0 views
Skip to first unread message

Chip Salzenberg

unread,
Mar 22, 2005, 3:21:21 PM3/22/05
to Perl 6 Internals
It seems to me that the most productive things to worry about, from a
design point of view, are the things that interest the hubristic
and/or impatient people.

Therefore, in the spirit of the Hindmost: If you're out ahead of me,
who are you and what are you doing?
--
Chip Salzenberg - a.k.a. - <ch...@pobox.com>
Open Source is not an excuse to write fun code
then leave the actual work to others.

Chip Salzenberg

unread,
Mar 22, 2005, 3:29:16 PM3/22/05
to Perl 6 Internals
According to Chip Salzenberg:

> Therefore, in the spirit of the Hindmost: If you're out ahead of me,
> who are you and what are you doing?

It's been suggested to me on IRC that my previous message was a bit
opaque. Let me try again:

What design issues are crying for attention right now?

I know different people will have different lists. That's good.
I'll make a list of lists. It'd be nice if I had a good language
for manipulating complex data structures. Oh, wait...

Leopold Toetsch

unread,
Mar 23, 2005, 6:01:41 AM3/23/05
to Chip Salzenberg, perl6-i...@perl.org
Chip Salzenberg <ch...@pobox.com> wrote:

> What design issues are crying for attention right now?

The CPS (continuation passing style) call scheme has some still
unsolved implications. There are mainly two issues:

1) correctness
2) speed

I'd like to summarize mainly the correctness item.

"Branching" around via a continuation is invisible to the register
allocator. The register allocator just sees a linear control flow from
a subroutine call to the next statements after the call. But if the
subroutine captured the return continuation, it can return repeatedly
through the same location, which effectively creates a loop in the CFG
(control flow graph).

A detailed analysis is in:

Subject: "Continuations, basic blocks, loops and register allocation"
Date: Sat, 13 Nov 2004

The mentioned point 1) Exceptions is solved, the "push_eh label"
opcode is implemented.

Still unsolved is the issue with continuations. There was a lot of
discussion but it boils basically down to two things we can do:

,--[ Dan ]------------------------------------------------------------
| The loop variable must have a backing store outside of the register
| set. The contents of registers must be assumed to be unreliable when
| a continuation is continued. If we declare that they are put back
| into the state they were when the continuation was taken, which is
| reasonable though not required, the values of non-reference type
| registers (ints and floats) will be reset. The rference type
| registers (strings and PMCs) will also be reset so the pointers to
| the string/pmc structs will be what they were when the continuation
| was taken, but as they are references the referred-to thing may have
| changed and the changed value will be seen.
`---------------------------------------------------------------------

NB: the STRING variables also behave like value types: e.g.

concat S0, S1

creates a new string in S0, if the storage isn't sufficient to
concatenate S1 in place.

This seems to imply that e.g. integer count variables are unusable
around function calls. The need for a backing store invalidates all
efficiency gained by the usage of native types. PMCs and other
register types would suddenly have different semantics with the
presence of a continuation. Additionally the term "put back" smells
like copying register frames, which is known to be highly inefficient.

More on this issue is in the thread:

Subject: "continuation enhanced arcs"
Date: Mon, 22 Nov 2004

with another summary in my discussion with Piers:

,--[ Leo ]---------------------------------------------------------------
| Piers Cawley <pdca...@bofh.org.uk> wrote:
| > Okay, I'm confused, I thought that the whole point of a caller saves,
| > continuation passing regime was that the caller only saves what it's
| > interested in using after the function returns.
|
| We don't have a problem WRT register preservation, the problem arises
| due to register re-using.
|
| > ... Exactly *where* that
| > return happens, and whether it happens more than once, is completely
| > irrelevant from the point of view of the caller.
|
| The return can only happen, where the normal function call would have
| returned, but anyway.
|
| > ... ISTM that the register
| > allocator should work on the principle that anything it didn't save
| > before it made the call will be toast afterwards.
|
| Yes. But - please remember your example "Fun with nondeterministic searches".
| Here's the relevant piece of code from main:
|
| arr1=[1,3,5]
| arr2=[1,5,9]
| x = choose(arr1)
| y = choose(arr2)
| $P0 = find_lex "fail"
| $P0()
|
| You know, both "choose" calls capture the continuation and backtrack via
| "fail" (basically). But the register allocator isn't aware of that. The
| control flow graph (CFG) is linear top down, with new basic blocks
| starting after each function call. "arr2" is obviously used around a
| call and allocated in the preserved (non-volatile) register area. This
| works fine.
|
| Now the register allocator assigns a register to "$P0". It finds the
| register that "arr2" had usable, because in a linear CFG, there's no way
| that "arr2" might be used again. So that register is considered being
| available. Now if $P0 happens to get the register that "arr2" had,
| backtracking through the call to "fail()" obviously fails, as "arr2" is
| now the Closure PMC. And that was exactly the case.
`--------------------------------------------------------------------------

As the problem isn't register preserving per se, but register
re-using, it seems to me that any "solution" that involves register
copying isn't correct. Value registers would be restored to a previous
state, pointer registers keep on pointing to the same item.

,--[ Luke ]---------------------------------------------------------------
| ... The problem is the
| semantics. If you copy the registers, then when you invoke the
| continuation, their *values* restore to what they were when you made the
| continuation. These are not proper semantics, and would result in
| subtle, incorrect infinite loops.
`-------------------------------------------------------------------------

My proposal to attack this problem is here:

Subject: Lexicals, continuations, and register allocation
Date: Tue, 23 Nov 2004

which basically states: we use a variable sized register frame, where
lexicals and preserved temporaries have a distinct storage.

,--[ Ken Fox ]---------------------------------------------------------
| A very strong architecture for sure.
|
| > + no lexical fetch overhead
|
| That alone is worth the price of admission. No register allocator
| needed because the HLL only needs volatiles for anonymous temporaries
| which are easily allocated during expression parsing.
`----------------------------------------------------------------------

Dan was mandating the register preserving idea:

,--[ Dan ]----------------------------------------------------------
| ... We mandated that call/return preserved the top 16
| registers of all the types automatically. That's *all* we did. The
| rest is implementation detail.
`-------------------------------------------------------------------

which IMHO does not solve the issue at all.

Related but also abandoned is my proposal:

Subject: [PROPOSAL] for a new calling scheme
Date: Tue, 16 Nov 2004

which has some ideas about variable sized register frames.

leo

Leopold Toetsch

unread,
Mar 23, 2005, 7:29:40 AM3/23/05
to Chip Salzenberg, perl6-i...@perl.org
Chip Salzenberg <ch...@pobox.com> wrote:

> What design issues are crying for attention right now?

I forgot another related issue in my previous mail. In
Subject "Scope exit and timely destruction" I've written:

> Given is a Perl snippet like:

> {
> my $fh = IO::File->new;
> $fh->open(">test.tmp");
> print $fh "a";
> }

> The filehandle is closed automatically at scope exit and the file
> contains the expected contents.

> That's quite easy in the current Perl implementation as it does
> reference counting. At the closing bracket the last reference to
> C<$fh> has gone and the file gets closed during object destruction.

> As parrot isn't using reference counting for GC, we have to run a GC
> cycle to detect that the IO object is actually dead. This is
> accomplished by the "sweep 0" opcode, which does nothing if no object
> needs timely destruction.

> Above example could roughly translate to Parrot code like:

> new_pad -1 # new lexical scope
> $P0 = new ParrotIO
> store_lex -1, "$fh", $P0
> open $P0, "test.tmp", ">"
> print $P0, "a"
> pop_pad # get rid of $fh lexical
> sweep 0 # scope exit sequence

> Alternatively a scope exithandler could be pushed onto the control
> stack.

> With such a sequence we got basically two problems:

> 1) Correctness of "sweep 0"

> At scope exit we've somewhere in the PMC registers the ParrotIO
> object still existing. This means that during marking the root set,
> the ParrotIO object is found being alive, where it actually isn't.
> The usage of registers keeps the object alive until this register
> frame isn't referenced anymore, that is after that function was left.

[ snipped performance considerations ]

There was some discussion about GC and performance, but the main problem
wasn't addressed at all.

The implication for me is that we can't keep the current register frame
layout anyway. As long as the register frame of the scope is around, the
ParrotIO object is kept alive. That is: we have to use one register
frame per variable scope like we have one frame per subroutine now.

leo

Reply all
Reply to author
Forward
0 new messages