[Fwd: Register stacks again]
Leopold Toetsch
have to improve calling speed, here is again the original text. Below
are some additional remarks.
-------- Original Message --------
Subject: Register stacks again
Date: Sat, 08 May 2004 13:29:20 +0200
From: Leopold Toetsch <l...@toetsch.at>
To: Perl 6 Internals <perl6-i...@perl.org>
For reference Dan's blog entry at:
http://www.sidhe.org/~dan/blog/archives/000321.html
I think that the situation has changed again and that we should consider
the original register in the stack scheme.
1) In the presence of MMD and delegate functions, object acessor methods
and OO in general, we'll probably do a lot more function calls, then the
assumptions stated in the article.
2) Hardware CPU speeds increase much faster then RAM access timings. The
relative cost of one extra pointer indirection is decreasing steadily.
3) JIT can execute as fast as now, when we reserve one register as the
stack frame pointer. JITs speed isn't so much gained by the absolute
address access, but by avoiding any memory access. That is: on the begin
of a basic block fill CPU registers (mov mem, %reg), then execute as
much as possible just in registers and at the end of a basic block store
hardware regs back to Parrot's. The "mov mem, %reg" or "mov %reg, mem"
operations are the expensive part of it (2 cycles instead of 1 mostly).
So a register fetch could look like "mov x(%ebp), %reg", where x is the
offset in the register array and %ebp the register frame pointer. [1]
This instruction has the same execution speed as the absolute memorx access.
4) The absolute addressing scheme in prederefed and JIT run cores
implies a separate "compilation" (predereferencing or JITting) of the
code per thread. This has additionally some memory costs and possible
negative cache effects when different threads execute different code.
[1] yes I'm thinking of just one frame pointer :) Well, the whole scheme
makes a stack machine out of Parrot:
I0,...In, In+1....Ik, Ik+1...Il
^
|
frame
pointer
I0..In are the incoming function arguments
In+1..Ik are the working registers of the function
Ik+1...Il are outgoing args for a function call
Calling a function is just a move of the frame pointer to "Ik".
The working register file size is adjusted to the actual needs of the
function.
Actually registers would be arranged (I0,S0,P0,N0,I1,S1...)
Is this scheme just crazy?
leo
------------------
ad 3), 4) all prederefed cores and the JIT run core now use absolute
register addresses. This currently needs reJITing and repredereferencing
for each new thread. With an addressing scheme relative to *one* base or
frame pointer, this isn't necessary anymore - again at the expense of
one CPU hardware register.
When the emitted code for a CPU register access is like:
Rx := base_pointer[const_offset]
there is very likely no measurable slowdown in these run loops. The
base_pointer needs only reloading after an C<invoke> statement. Please
note that the normal function core does the same addressing with the
interpreter pointer.
Eventually, given a fairly big linear stack, we could actually address
as many registers as a function is using. Incoming registers could be
addressed with a negative offset. Outgoing (or spilled) registers could
be used with bigger positive offsets (beyond the actual working range of
registers).
Comments still welcome ;)
leo
Leopold Toetsch
> Didn't get much response
... so I'm responding to myself ;)
I've checked in docs/nanoparrot.c. While it should be a document
showing, how the interpreter actually performs its work, it also allows
comparison of the additional performance penalty of the indirect
register access.
Its around 1% (OS X) up to 3% (athlon/linux).
This impact would be on function-based cores only and is worst case.
Other opcode functions burn much more cycles, so that the one additional
assembler instruction does harm less.
leo
Matt Fowles
This feels similar in spirit to the old framestacks that we used to
have. I throught that we moved away from those to single frame things
so that we did not have to perform special logic around continuations.
I would feel more comfortable if someone explained both the initial
motivation of leaving the chunked system and why this does not violate
that motivation or that motivation was wrong.
Thanks,
Matt
On Mon, 18 Oct 2004 15:09:53 +0200, Miroslav Silovic <mi...@puremagic.com> wrote:
> This is a summary of a private mail conversation between Leo and myself.
> <lie>No, it didn't start by me forgetting to fix Reply-To when trying to
> post follow-up on the list.</lie> ;)
>
> Essentially we whipped up a GC scheme for collecting the register stacks
> that doesn't make call/cc-using code, well, unusably slow.
>
> In addition to LT's original post on the register stack, here's how to
> allocate them and clean up after their use. LT, feel free to hit me with
> wet noodles if I forgot anything.
>
> Terminology:
> ---
>
> Register frame is an actual frame of 4x16 registers.
>
> Register chunk is a flat chunk of memory containing multiple register
> frames. It has a water mark that points where a new frame should be
> pushed into the chunk. I'm using stack and chunk interchangably.
>
> Frames are subject to DoD, and chunks are subject to GC. There are
> plenty of tricks that can prevent GC from happening in many cases (read
> on for details). DoD is necessary anyway (to retrieve the live PMCs
> pointed from the register frames).
>
> A chunk is pinned if GC currently can't copy it over and kill it (read
> on for details).
>
> Allocation:
> ---
>
> Register stacks should be allocated in fairly big chunks. However, since
> there must be at least one active chunk per thread (and per coroutine),
> choosing anything actually huge will pose a scaling problem.
>
> Frames are allocated from the current stack, simply by advancing the
> water mark of the currently active chunk. If this causes the water mark
> to overflow, a new chunk needs to be allocated.
>
> Note that if a continuation has been captured and then invoked, the
> water mark will not necessarily point at the end of the current frame
> (since the invoked continuation may keep its registers deeper in the chunk)
>
> Deallocation:
> ---
>
> The stack frame can only be popped if the current continuation hasn't
> been captured (from the frame being popped). Here, pop means changing
> both frame pointer and the watermark. This ammounts to adding a flag to
> the current frame and bumping the flag if the return continuation gets
> moved into any directly accessible location. If the frame can't be
> popped, only the frame pointer should be changed to the caller's.
>
> GC:
> ---
>
> During DoD, the register frames should be marked (as parts of their
> chunks). Then the dead frames get dealt with in the following manner:
>
> Remove the trailing dead frames from each chunk (by just lowering the
> water mark).
>
> If after this the water mark remains high (e.g. past 50% of the chunk)
> but more than certain ammount of the chunk is salvagable as dead frames
> (50% seems like a good number again), the chunk should be copied, all
> the frame pointers fixed up, then the chunk gets killed. Essentially the
> chunks are treated as buffers. The watermark lowering won't help in
> cases when continuations get invoked in a round-robin manner (wish I
> could think of some simple Scheme example here that behaves this way),
> and start littering the chunk with interlaced dead frames.
>
> Two caveats:
>
> The frame pointer of the currently active frames (can be more than 1 due
> to threads) may be kept in a CPU register and can't be fixed-up. So the
> chunk containing currently active frame is pinned until it either
> overflows into another chunk or gets freed by popping.
>
> Chunks can contain reverse pointers to the continuations that use its
> frames. When copying the frame, just go through these reverse pointers
> and fix the continuations they point to.
>
> Performance:
> ---
>
> This scheme requires some GC flags to each frame (as well as reverse
> pointers). Possibly also next pointers to the frames, if they are not
> cut to equal size.
>
> Without continuations, this behaves like C function calling. Nothing
> will read return continuation and so the frames will simply get popped
> from the stack on return.
>
> When continuations begin to prevent popping, the stack will start
> growing from the last captured continuation (even if its dead).
> Watermark will drop in GC if the GC happens to hit while the active
> frame is way down the stack (i.e. just between two function calls).
> Otherwise, GC will wait till the chunk overflows (so that the active
> frame is in a higher chunk) and then will copy the live frames to a
> newly allocated chunk, compacting several chunks together if possible.
> Copying can be skipped if the chunk is near-full of the live frames.
>
> I think this about sums it up. Comments, corrections, wet noodles?
>
> Miro
>
>
--
"Computer Science is merely the post-Turing Decline of Formal Systems Theory."
-???
Leopold Toetsch
> All~
> This feels similar in spirit to the old framestacks that we used to
> have. I throught that we moved away from those to single frame things
> so that we did not have to perform special logic around continuations.
> I would feel more comfortable if someone explained both the initial
> motivation of leaving the chunked system and why this does not violate
> that motivation or that motivation was wrong.
The problem currently is that we do too much copying. The caller has to
preserve it's registers. That is currently done by copying onto the
frame stacks. After function return there's another copy going on to
restore registers.
Until around Parrot 0.0.3 there were chunked stacks *with* an
indirection for the register frame pointers. During development of the
JIT system these indirections got dropped to be able to use absolute
addresses for registers in JIT code and for about 3% of more
performance.
To support continuations the chunks were first copied then COWed, and
later replaced by the single frame stack, we now have.
What I want to achieve is to find the best combination of all these
variations. That is:
- again one indirection for register access. The cost is near zero
because almost all JIT subsystems are already using register indirect
addressing.
- but only one frame stack, not 4 to be able to have the frame pointer
in a CPU register
- no COW copying of frames because that is expensive too. Instead the
register chunks are compacted occassionally during GC.
> Thanks,
> Matt
leo
Matt Fowles
Thanks for the detailed explanation.
On Tue, 19 Oct 2004 10:50:22 +0200, Leopold Toetsch <l...@toetsch.at> wrote:
> Until around Parrot 0.0.3 there were chunked stacks *with* an
> indirection for the register frame pointers. During development of the
> JIT system these indirections got dropped to be able to use absolute
> addresses for registers in JIT code and for about 3% of more
> performance.
>
> To support continuations the chunks were first copied then COWed, and
> later replaced by the single frame stack, we now have.
>
> What I want to achieve is to find the best combination of all these
> variations. That is:
>
> - again one indirection for register access. The cost is near zero
> because almost all JIT subsystems are already using register indirect
> addressing.
> - but only one frame stack, not 4 to be able to have the frame pointer
> in a CPU register
> - no COW copying of frames because that is expensive too. Instead the
> register chunks are compacted occassionally during GC.
Could we have the chunks only hold one frame and avoid much of the
compaction work? If we return to the inderict access mechanism, we
can switch register frames by changing one pointer. But if we keep
the one frame per chunk, we do not need to compact frames, standard
DOD/GC will be able to reclaim frames. I recall there being
efficiency issues with frames being frequently allocated/deallocated
too frequently, so we could have a special free list for frames.
This proposal feels to me like a slightly simpler version of yours.
Thus I would argue for it on the grounds of do the simple thing first
and compare its efficiency.
Matt
Miroslav Silovic
>Could we have the chunks only hold one frame and avoid much of the
>compaction work? If we return to the inderict access mechanism, we
>can switch register frames by changing one pointer. But if we keep
>the one frame per chunk, we do not need to compact frames, standard
>DOD/GC will be able to reclaim frames. I recall there being
>efficiency issues with frames being frequently allocated/deallocated
>too frequently, so we could have a special free list for frames.
>
>This proposal feels to me like a slightly simpler version of yours.
>Thus I would argue for it on the grounds of do the simple thing first
>and compare its efficiency.
>
>
Well, for the code that doesn't do call/cc, bigger chunks mean that that
you can use them as a classical stack. So you won't ever have to
allocate them, and never have to run the compaction. For call/cc, you
still don't have to compact them as often, since the non-captured
continuations will get popped normally, and the watermark lowering will
take care of temporarily captured continuations (between two GC's).
Basically bigger chunks mean that frames are allocated using the special
scheme just for them. Considering that you're going to allocate one on
each function call, I would agree with LT that the complexity is
justified (and is not too bad - the way I understand the Parrot
internals, which is to say, not too well ;), arrays of PMC pointers
already get copy-collected; stack frame chunks are not too different
from these).
Miro