Re: An overview of the Parrot interpreter

[Paolo Molaro]

On 09/07/01 Dan Sugalski wrote:
> >The only optimizations that interpreter had, were computed goto and
> >allocating the eval stack with alloca() instead of malloc().
> 
> Doesn't this really get in the way of threading? You'll chew up great gobs 
> of system stack, and that's a scarce resource when running with threads.

The number of entries in the eval stack is bounded, I've never seen it
grow past 13.

> >I think they worked also on outputting IL bytecode...
> 
> Yep, but that version was slower. Dick Hardt snagged me at TPC this year (I 
> think I spent most of my non-speaking time being pinned to a table or bench 
> by folks with Things To Say... :) and made a .NET pitch. They were going 
> with the translation to .net but switched to embedding perl. It was a lot 
> faster. (Brad Kuhn had a paper on translating perl to java bytecode and he 
> had lots of trouble, but for different reasons)

My point is that using their experience, a few changes should be designed to
better support dynamic languages in the CLR in the same way that currently
the research is focused on extending it for functional languages, generics
etc.

lupus

-- 
-
[EMAIL PROTECTED] debian/rules
[EMAIL PROTECTED] Monkeys do it better

Re: An overview of the Parrot interpreter [speed]

[Bryan C . Warnock]

On Friday 07 September 2001 11:08 pm, Sterin, Ilya wrote:
> Actually there were some tests done, can't recall where now, though by a
> trusted source. I will be digging it up in my email and emailing it to the
> list.  There were a few languages tested including Perl, C, C++, Java
> (can't remember if Python was there).  Perl came in in second place after
> C.  Yes, that's faster than C++.  Again, I totally understand that a lot
> of it is dependent on what's being tested, which I couldn't recall at this
> time either, though I believe to recall that it was some general stuff.

IIRC, Dr. Dobb's reported a similar (if not the same) test a couple years 
ago.  However, they speculated a known bug in the MFC for the C++ test is 
what caused it to be slower.  They were doing textual processing, and C, 
Perl, and awk, I believe, were pretty quick, with the problematic C++ in the 
middle, and Java significantly slower.

But that was then...

-- 
Bryan C. Warnock
[EMAIL PROTECTED]

RE: An overview of the Parrot interpreter [speed]

[Sterin, Ilya]

Actually there were some tests done, can't recall where now, though by a
trusted source. I will be digging it up in my email and emailing it to the
list.  There were a few languages tested including Perl, C, C++, Java (can't
remember if Python was there).  Perl came in in second place after C.  Yes,
that's faster than C++.  Again, I totally understand that a lot of it is
dependent on what's being tested, which I couldn't recall at this time
either, though I believe to recall that it was some general stuff.

Ilya

> -Original Message-
> From: raptor [mailto:[EMAIL PROTECTED]]
> Sent: Friday, September 07, 2001 3:30 PM
> To: [EMAIL PROTECTED]
> Subject: Re: An overview of the Parrot interpreter [speed]
>
>
> hi,
>
> I see that it was mentioned that Perl5 is fast than Java, Python
> etc...  and
> was wondering is there any comparison how-much, if ? and if why ?
> and if we
> know the reason can we exploit it further ... and similar...
> And does really Perl6 will be faster. how much u expect ?
> Thanx
> =
> iVAN
> [EMAIL PROTECTED]
> =

Re: An overview of the Parrot interpreter [speed]

[Dan Sugalski]

At 05:54 PM 9/7/2001 -0400, Bryan C. Warnock wrote:
>On Friday 07 September 2001 05:51 pm, Dan Sugalski wrote:
> > >(Like
> > >Unicode Everywhere).
> >
> > Who's doing that? We're keeping things in native format as much as we can.
>
>If one of our stated goals is Unicode support (even for the source itself -
>that's what I meant by "everywhere": source, input, output), we're going to
>be a little more hindered than if we didn't have to worry about it at all,
>no?

No. We don't want Unicode everywhere because:

*) Conversion to Unicode is sometimes lossy
*) Conversion back out of Unicode is sometimes lossy
*) Converting when we know how to work on the underlying string data is 
wasted cycles
*) Lots of folks using non-7-bit ASCII have perfectly adequate character 
sets with defined operations, so why should they have to use Unicode if 
they don't need it?

Unicode's sort of a greatest-common-multiple character set. We'll use it if 
we need to, but it's no panacea. (Unfortunately)

>Or will you only compare Granny Smiths with Granny Smiths?

If you compare, say, a Shift-JIS string to a Big5/traditional string, 
they'll probably both end up both converting to Unicode and the result 
compared. (Assuming that neither the Big5/traditional nor the Shift-JIS 
string library knows how to convert to the other losslessly) And a plain 
string comparison for gt/lt is less straightforward than you might think...

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter [speed]

[Bryan C . Warnock]

On Friday 07 September 2001 05:51 pm, Dan Sugalski wrote:
> >(Like
> >Unicode Everywhere).
>
> Who's doing that? We're keeping things in native format as much as we can.

If one of our stated goals is Unicode support (even for the source itself - 
that's what I meant by "everywhere": source, input, output), we're going to 
be a little more hindered than if we didn't have to worry about it at all, 
no?

Or will you only compare Granny Smiths with Granny Smiths? 

-- 
Bryan C. Warnock
[EMAIL PROTECTED]

Re: An overview of the Parrot interpreter [speed]

[Dan Sugalski]

At 05:41 PM 9/7/2001 -0400, Bryan C. Warnock wrote:
>On Friday 07 September 2001 05:38 pm, Dan Sugalski wrote:
> >
> > As for perl 6 vs perl 5, that's reasonably easy. We benchmark things on
> > perl 5.004_04 and 6.x, and see who wins. If 6 doesn't, we find out why and
> > speed it up. :)
>
>5.004?  (Is that where the big drop-off begins?)

Dunno. I came into perl with 5.004 (Well, 5.003_92, but close enough) and 
that's the earliest perl it's feasible to benchmark, as it's the earliest 
perl that's really safe. The numbers go downhill from 5.004_04 to 5.005 to 
5.6. (Try a 5.004_04 build against a 5.6.1 build with any of the thread 
options. Yowtch!)

>You are going to take into consideration where Perl 6 might take a little
>longer just because it has to do something 5.004 doesn't, right?

No. If the task is the same, then I don't care what perl 6 needs to do. If 
we decide all integers need to be 128 bits that's fine, but we still had 
damn well be faster than perl 5. If perl 6 needs to do more under the hood, 
it better do it fast enough to not matter.

>(Like
>Unicode Everywhere).

Who's doing that? We're keeping things in native format as much as we can.

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter [speed]

[Bryan C . Warnock]

On Friday 07 September 2001 05:38 pm, Dan Sugalski wrote:
>
> As for perl 6 vs perl 5, that's reasonably easy. We benchmark things on
> perl 5.004_04 and 6.x, and see who wins. If 6 doesn't, we find out why and
> speed it up. :)

5.004?  (Is that where the big drop-off begins?)

You are going to take into consideration where Perl 6 might take a little 
longer just because it has to do something 5.004 doesn't, right?  (Like 
Unicode Everywhere).

-- 
Bryan C. Warnock
[EMAIL PROTECTED]

Re: An overview of the Parrot interpreter [speed]

[Dan Sugalski]

At 10:30 PM 9/7/2001 +0300, raptor wrote:
>I see that it was mentioned that Perl5 is fast than Java, Python etc...  and
>was wondering is there any comparison how-much, if ? and if why ? and if we
>know the reason can we exploit it further ... and similar...
>And does really Perl6 will be faster. how much u expect ?

This stuff is all very benchmark-specific. Doing low-level things, like 
integer math operations, Java's faster. Doing higher-level stuff, like 
regexes or things with hash variables, perl's faster. The more time a perl 
program spends inside its "fat" opcodes, the more likely perl is to win 
over java/python/tcl/ruby/etc. Competent C programmers can beat perl every 
time. (Actually *finding* a competent C programmer is left as an exercise 
for the reader... :)

There are a variety of benchmarks scattered around the 'net. Google or 
Northern Light should find them for you. How valid they are is something 
else entirely. There are benchmarks in a variety of books, but I don't have 
cites handy. Tom Christiansen did for a while, but I think they've fallen 
off his website, and they were getting kind of stale anyway.

As for perl 6 vs perl 5, that's reasonably easy. We benchmark things on 
perl 5.004_04 and 6.x, and see who wins. If 6 doesn't, we find out why and 
speed it up. :)

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter [speed]

[raptor]

hi,

I see that it was mentioned that Perl5 is fast than Java, Python etc...  and
was wondering is there any comparison how-much, if ? and if why ? and if we
know the reason can we exploit it further ... and similar...
And does really Perl6 will be faster. how much u expect ?
Thanx
=
iVAN
[EMAIL PROTECTED]
=

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 10:47 PM 9/6/2001 +0200, Paolo Molaro wrote:
>On 09/06/01 Dan Sugalski wrote:
> > Then I'm impressed. I expect you've done some things that I haven't yet.
>
>The only optimizations that interpreter had, were computed goto and
>allocating the eval stack with alloca() instead of malloc().

Doesn't this really get in the way of threading? You'll chew up great gobs 
of system stack, and that's a scarce resource when running with threads.

>Of course, now it's slower, because I implemented the full semantics required
>by IL code (the biggest slowdown came from having to consider
>argments and local vars of any arbitrary size; making the alu opcodes
>work for any data type slowed it down by 10 % only): but the parrot
>interpreter doesn't need to deal with that kind of stuff that slows
>down interpretation big time. Still, it's about 2x faster than perl5
>on the same benchmarks, though I haven't tried to optimize the new code, yet.

Well, we should have code ready for checkout on Monday--I'm really 
interested to see what our respective speeds are with low-level operations.

> > Also, while I have numbers for Parrot, I do *not* have comparable numbers
> > for Perl 5, since there isn't any equivalence there. By next week we'll
> > have a basic interpreter you can build so we can see how it stacks up
> > against Mono.
>
>See above, I expect it to be faster, at least handling the low-level stuff
>since I hope you're not going to add int8, uint8 etc, type handling.

Gack, no. Ints are native sized. If people want shorter ints, they can use 
full-blown variables.

> > >Yep, but for many things there is an overlap. As for the dynamic language
> > >issue, I'd like the ActiveState people that worked on perl <-> .net
> > >integration to share their knowledge on the issues involved.
> >
> > That one was easy. They embedded a perl interpreter into the .NET 
> execution
> > engine as foreign code and passed any perl to be executed straight to the
> > perl interpreter.
>
>I think they worked also on outputting IL bytecode...

Yep, but that version was slower. Dick Hardt snagged me at TPC this year (I 
think I spent most of my non-speaking time being pinned to a table or bench 
by folks with Things To Say... :) and made a .NET pitch. They were going 
with the translation to .net but switched to embedding perl. It was a lot 
faster. (Brad Kuhn had a paper on translating perl to java bytecode and he 
had lots of trouble, but for different reasons)

> > completely counter to what .NET (and java, for that matter) wants to do.
> > Including runtime compilation from source and runtime redefinition of
> > functions. (Not to mention things like per-object runtime changeable
> > multimethod dispatch, which just makes my head hurt)
>
>Naah, with the reflection support you can create types and methods on the 
>fly, the rest can probably be done with a couple of ad-hoc opcodes.

Maybe. It'd be nice if that's true, though spitting out to .Net's a 
secondary issue for me--a working interpreter's first. Once we get the 
interpreter fast is when we (well, someone at least--probably not me) work 
on emitting .net or jvm code instead of perl bytecode.

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter

[Paolo Molaro]

On 09/06/01 Dan Sugalski wrote:
> Then I'm impressed. I expect you've done some things that I haven't yet. 

The only optimizations that interpreter had, were computed goto and
allocating the eval stack with alloca() instead of malloc().
Of course, now it's slower, because I implemented the full semantics required
by IL code (the biggest slowdown came from having to consider
argments and local vars of any arbitrary size; making the alu opcodes
work for any data type slowed it down by 10 % only): but the parrot
interpreter doesn't need to deal with that kind of stuff that slows
down interpretation big time. Still, it's about 2x faster than perl5
on the same benchmarks, though I haven't tried to optimize the new code, yet.

> Also, while I have numbers for Parrot, I do *not* have comparable numbers 
> for Perl 5, since there isn't any equivalence there. By next week we'll 
> have a basic interpreter you can build so we can see how it stacks up 
> against Mono.

See above, I expect it to be faster, at least handling the low-level stuff
since I hope you're not going to add int8, uint8 etc, type handling.

> >Yep, but for many things there is an overlap. As for the dynamic language
> >issue, I'd like the ActiveState people that worked on perl <-> .net
> >integration to share their knowledge on the issues involved.
> 
> That one was easy. They embedded a perl interpreter into the .NET execution 
> engine as foreign code and passed any perl to be executed straight to the 
> perl interpreter.

I think they worked also on outputting IL bytecode...

> >I know the ActivState people did work on this area. Too bad their stuff
> >is not accessible on Linux (some msi file format stuff).
> >I don't know if .net is the best back-end arch, it's certanly going
> >to be a common runtime to target since it's going to be fast and
> >support GC, reflection etc. With time and the input from the dynamic 
> >language
> >people may become a compelling platform to run perl/python on.
> 
> Doubt it. That'd require Microsoft's involvement, and I don't see that 
> happening. Heck, most of what makes dynamic languages really useful is 

The ECMA people are not (only) m$, there is people in the committee
interested in both other implementations and input on the specs.

> completely counter to what .NET (and java, for that matter) wants to do. 
> Including runtime compilation from source and runtime redefinition of 
> functions. (Not to mention things like per-object runtime changeable 
> multimethod dispatch, which just makes my head hurt)

Naah, with the reflection support you can create types and methods on the fly,
the rest can probably be done with a couple of ad-hoc opcodes.

lupus

-- 
-
[EMAIL PROTECTED] debian/rules
[EMAIL PROTECTED] Monkeys do it better

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 09:22 PM 9/6/2001 +0200, Paolo Molaro wrote:
>A 10x slowdown on that kind of code is normal for an interpreter
>(where 10x can range from 5x to 20x, depending on the semantics).

If we're in the normal range, then, I'm happy.

Well, until we get equivalent benchmarks for Mono, in which case I shall 
be  unhappy if we're slower. :)

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 09:11 PM 9/6/2001 +0200, Paolo Molaro wrote:
>On 09/06/01 Dan Sugalski wrote:
> > >The original mono interpreter (that didn't implement all the semantics
> > >required by IL code that slow down interpretation) ran about 4 times
> > >faster than perl/python on benchmarks dominated by branches, function
> > >calls,
> > >integer ops or fp ops.
> >
> > Right, but mono's not an interpreter, unless I'm misunderstanding. It's a
> > version of .NET, so it compiles its code before executing. And the IL it
> > compiles is darned close to x86 assembly, so the conversion's close to
> > trivial.
>
>Nope, if we had written a runtime, library, compiler and JIT engine in two
>months we'd be all on vacation now ;-)

Then I'm impressed. I expect you've done some things that I haven't yet. 
The implementation of the current interpreter is somewhat naive.

>no assembly whatsoever. And, no, IL is not close to x86 assembly:-)

I dunno about that. From reading the Microsoft docs on it, it doesn't look 
that far off. (OK, the x86 doesn't do objects, but the rest maps in pretty 
darned well)

Also, while I have numbers for Parrot, I do *not* have comparable numbers 
for Perl 5, since there isn't any equivalence there. By next week we'll 
have a basic interpreter you can build so we can see how it stacks up 
against Mono.

> > >Java is way faster than perl currently in many tasks:
> >
> > Only when JITed. In which case you're comparing apples to oranges. A 
> better
> > comparison is against Java without JIT. (Yes, I know, Java *has* a JIT, 
> but
> > for reasonable numbers at a technical level (and yes, I also realize that
> > generally speaking most folks don't care about that--they just want to 
> know
> > which runs faster) you need to compare like things)
>
>It's not so much that java *has* a JIT, but that it *can* have it. My 
>point is,
>take it into consideration when designing parrot. There's no need to
>code it right from the start, that would be wrong, but allow for it in the 
>design.

Ah. That's a long-done deal. (You missed it by about a year... ;) TIL 
capabilities are on the list of things to remember, as is a straight-to-C 
translator for bytecode. Compilation to java bytecode, .NET, and tie-ins to 
native compilers (GCC, GEM, whatever) are as well.

That's in for the design. We're not doing them to start, but they're there 
for the design.

> > >it will be difficult
> > >to beat it starting from a dynamic langauge like perl, we'll all pay
> > >the price to have a useful language like perl.
> >
> > Unfortunately (and you made reference to this in an older mail I haven't
> > answered yet) dynamic languages don't lend themselves to on-the-fly
> > compilation quite the way that static languages do. Heck, they don't tend
> > to lend themselves to compilation (certainly not optimization, and don't
> > get me started) period as much as static languages. That's OK, it just
> > means our technical challenges are similar to but not the same as for
> > Java/C/C++/C#/Whatever.
>
>Yep, but for many things there is an overlap. As for the dynamic language
>issue, I'd like the ActiveState people that worked on perl <-> .net
>integration to share their knowledge on the issues involved.

That one was easy. They embedded a perl interpreter into the .NET execution 
engine as foreign code and passed any perl to be executed straight to the 
perl interpreter.

> > >The speed of the above loop depends a lot on the actual implementation
> > >(the need to do a function call in the current parrot code whould blow
> > >away any advantage gained skipping stack updates, for example).
> >
> > A stack interpreter would still have the function calls. If we were
> > compiling to machine code, we'd skip the function calls for both.
>
>Nope, take the hint: inline the code in a big switch and voila', no
>function call ;-)

Not everywhere. We've run tests, and we'll run more later, but... given the 
various ways of dispatch--big switch, computed goto, and function 
calls--the right way is platform dependent. Different architectures like 
different methods of calling, depending on the chip design and compiler. 
We're actually going to test for the right way at configure time and build 
the core interpreter loop accordingly.

Also, we can't do away with some of the function calls, since we've 
designed in the capability to have lexically scoped opcode functions, which 
means we have to dispatch to a function for all but the base opcodes.

> > numbers. (This is sounding familiar--at TPC Miguel tried to convince me
> > that .Net was the best back-end architecture to generate bytecode for)
>
>I know the ActivState people did work on this area. Too bad their stuff
>is not accessible on Linux (some msi file format stuff).
>I don't know if .net is the best back-end arch, it's certanly going
>to be a common runtime to target since it's going to be fast and
>support GC, reflection etc. With time and the input from the dynamic language
>people may become a c

Re: An overview of the Parrot interpreter

[Paolo Molaro]

On 09/06/01 Dan Sugalski wrote:
> Okay, I just did a test run, converting my sample program from interpreted 
> to compiled. (Hand-conversion, unfortunately, to C that went through GCC)
> 
> Went from 2.72M ops/sec to the equivalent of 22.5M ops/sec. And with -O3 on 
> it went to 120M ops/sec. The smaller number is more appropriate, since a 
> JIT/TIL version of the code won't do the sort of aggressive optimization 
> that GCC can do.
> 
> I'm not sure if I like those numbers (because they show we can speed things 
> up with a translation to native code) or dislike them (because they show 
> how much time the interpreter's burning). Still, they are numbers.

A 10x slowdown on that kind of code is normal for an interpreter
(where 10x can range from 5x to 20x, depending on the semantics).
But I think this is not a big issue: speed optimizations need
to be possible, there's no need to implement them right now.

lupus

-- 
-
[EMAIL PROTECTED] debian/rules
[EMAIL PROTECTED] Monkeys do it better

Re: An overview of the Parrot interpreter

[Paolo Molaro]

On 09/06/01 Dan Sugalski wrote:
> >The original mono interpreter (that didn't implement all the semantics
> >required by IL code that slow down interpretation) ran about 4 times
> >faster than perl/python on benchmarks dominated by branches, function 
> >calls,
> >integer ops or fp ops.
> 
> Right, but mono's not an interpreter, unless I'm misunderstanding. It's a 
> version of .NET, so it compiles its code before executing. And the IL it 
> compiles is darned close to x86 assembly, so the conversion's close to 
> trivial.

Nope, if we had written a runtime, library, compiler and JIT engine in two 
months we'd be all on vacation now ;-)
The figures are actually for a stack-based interpreter that executes IL opcodes,
no assembly whatsoever. And, no, IL is not close to x86 assembly:-)
I don't expect a new perl to run that fast, but there is a lot of room for
improvement.

> >Java is way faster than perl currently in many tasks:
> 
> Only when JITed. In which case you're comparing apples to oranges. A better 
> comparison is against Java without JIT. (Yes, I know, Java *has* a JIT, but 
> for reasonable numbers at a technical level (and yes, I also realize that 
> generally speaking most folks don't care about that--they just want to know 
> which runs faster) you need to compare like things)

It's not so much that java *has* a JIT, but that it *can* have it. My point is,
take it into consideration when designing parrot. There's no need to
code it right from the start, that would be wrong, but allow for it in the design.

> >it will be difficult
> >to beat it starting from a dynamic langauge like perl, we'll all pay
> >the price to have a useful language like perl.
> 
> Unfortunately (and you made reference to this in an older mail I haven't 
> answered yet) dynamic languages don't lend themselves to on-the-fly 
> compilation quite the way that static languages do. Heck, they don't tend 
> to lend themselves to compilation (certainly not optimization, and don't 
> get me started) period as much as static languages. That's OK, it just 
> means our technical challenges are similar to but not the same as for 
> Java/C/C++/C#/Whatever.

Yep, but for many things there is an overlap. As for the dynamic language
issue, I'd like the ActiveState people that worked on perl <-> .net
integration to share their knowledge on the issues involved.

> >The speed of the above loop depends a lot on the actual implementation
> >(the need to do a function call in the current parrot code whould blow
> >away any advantage gained skipping stack updates, for example).
> 
> A stack interpreter would still have the function calls. If we were 
> compiling to machine code, we'd skip the function calls for both.

Nope, take the hint: inline the code in a big switch and voila', no
function call ;-)

> numbers. (This is sounding familiar--at TPC Miguel tried to convince me 
> that .Net was the best back-end architecture to generate bytecode for) 

I know the ActivState people did work on this area. Too bad their stuff
is not accessible on Linux (some msi file format stuff).
I don't know if .net is the best back-end arch, it's certanly going
to be a common runtime to target since it's going to be fast and
support GC, reflection etc. With time and the input from the dynamic language
people may become a compelling platform to run perl/python on.

lupus

-- 
-
[EMAIL PROTECTED] debian/rules
[EMAIL PROTECTED] Monkeys do it better

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 06:12 PM 9/6/2001 +0200, Paolo Molaro wrote:
>As I said in another mail, I think the stack-based approach will not
>be necessarily faster, but it will allow more optimizations down the path.
>It may well be 20 % slower in some cases when interpreted, but if it allows
>me to easily JIT it and get 400 % faster, it's a non issue.

Okay, I just did a test run, converting my sample program from interpreted 
to compiled. (Hand-conversion, unfortunately, to C that went through GCC)

Went from 2.72M ops/sec to the equivalent of 22.5M ops/sec. And with -O3 on 
it went to 120M ops/sec. The smaller number is more appropriate, since a 
JIT/TIL version of the code won't do the sort of aggressive optimization 
that GCC can do.

I'm not sure if I like those numbers (because they show we can speed things 
up with a translation to native code) or dislike them (because they show 
how much time the interpreter's burning). Still, they are numbers.

When I get the assembler to spit out C instead of bytecode I'll add it into 
the repository.

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter

[Dan Sugalski]

(Firstly, I'd say trust Nick's expertise--he has spent a good-sized chunk 
of his career doing software simulations of CPUs, and knows whereof he 
speaks, both in terms of software running on hardware and software running 
on software)

At 05:33 PM 9/6/2001 +0200, Paolo Molaro wrote:
>I believe that a stack-based machine will have roughly the same
>performance when interpreted as a register-based machine, but
>it easily allows to take a step further and JIT compile the bytecode
>to machine code. If we are going to execute low-level opcodes,
>no matter what architecture you choose for the interpreter,
>JIT code runs faster:-)

On x86 machines. Maybe. I think you both underestimate

> > is a pain.) Explicit stack ops are going to give them indigestion.
> > The P-III+ model is that most things are "on the C stack" i.e. offsets
> > from the few "base" registers. The hardware then "aliases" those offsets
> > into its real registers. I don't think Parrot's register files will give
> > it much trouble, but throwing away the right inc/dec-of-pointer ops that
> > a stack machine implies will (there are obviously HW special cases for 
> x86's
>
>With the difference that the registers are malloc()ed while the eval
>stack in a stack machine is in the actual cpu stack.

Absolutely *not*. No way is the eval stack going to be the real CPU stack. 
That puts nasty artificial limits, or massive memory requirements, on the 
interpreter. It also makes GC a major pain in the neck, since it means 
walking the stack and trying to extract real variable usage info. Bletch. 
Even if perl 6 goes the stack route, we won't be using the system stack.

The registers will be from heap memory, but that's not a problem in and of 
itself. Cache lines are cache lines.

Anyway, I think the point's moot for now. Parrot's register based unless 
either performance is substandard and demonstrably because of the register 
architecture, or because I get bussed and my successor's more comfortable 
with stacks. (The first is certainly possible)

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 06:12 PM 9/6/2001 +0200, Paolo Molaro wrote:
>On 09/05/01 Dan Sugalski wrote:
> > >It's easier to generate code for a stack machine
> >
> > So? Take a look at all the stack-based interpreters. I can name a bunch,
> > including perl. They're all slow. Some slower than others, and perl tends
> > to be the fastest of the bunch, but they're all slow.
>
>Have a look at the shootout benchmarks. Yes, we all know that
>benchmarks lie, but...
>The original mono interpreter (that didn't implement all the semantics
>required by IL code that slow down interpretation) ran about 4 times
>faster than perl/python on benchmarks dominated by branches, function calls,
>integer ops or fp ops.

Right, but mono's not an interpreter, unless I'm misunderstanding. It's a 
version of .NET, so it compiles its code before executing. And the IL it 
compiles is darned close to x86 assembly, so the conversion's close to trivial.

For this, it doesn't surprise me that Mono would wipe the floor with perl, 
since you don't have the interpreter loop and opcode dispatch overhead to 
deal with. Heck, if we *still* beat you with Mono compiling, I'd have to 
take the T over and give Miguel a hard time. :)

> > >That said, I haven't seen any evidence a register based machine is 
> going to
> > >be (significantly?) faster than a stack based one.
> > >I'm genuinely interested in finding data about that.
> >
> > At the moment a simple mix of ops takes around 26 cycles per opcode on an
> > Alpha EV6. (This is an even mix of branch, test, and integer addition
> > opcodes)  That's with everything sticking in cache, barring task switches.
> > It runs around 110 cycles/op on the reasonably antique machine I have at
> > home. (A 300MHz Celeron (the original, with no cache))
>
>Subliminal message: post the code... :-)

Anon CVS and surrounding tools (bug tracking system and such) being set up 
even as I type. (Though not by me, I don't have that many hands... :) 
Expect code to check out and build sometime early next week.

> > You're also putting far too much emphasis on registers in general. Most of
> > the work the interpreter will be doing will be elsewhere, either in the
> > opcode functions or in the variable vtable functions. The registers are
>
>That is true when executing high-level opcodes and a register or stack
>machine doesn't make any difference for that. It's not true for
>the low-level opcodes that parrot is supposed to handle according to the 
>overview
>posted by Simon.

Sure, but there'll be a mix of high and low level code. Yes, we're going to 
get hosed with low-level ops because the interpreter loop overhead. No way 
around that as long as we're an interpreter. (FWIW, the benchmark I posted 
was all low-level ops, and I'm not really unhappy with a 26 cycle/op number 
because of that. I'd like it smaller, and I think we have some ways around 
it (we can cut out the function call overhead with sufficient cleverness), 
but I'm not currently unhappy) So just because we're going to be able to 
add integers doesn't mean we're not also going to be adding full-blown 
variables. Or executing a single map or grep opcode.

The low-level ops are the places where we'll win the most when going either 
the TIL or straight compile route, since the loop and function call 
overhead will be cut out entirely.

> > It'll be faster than perl for low-level stuff because we'll have the 
> option
> > to not carry the overhead of full variables if we don't need it. It should
> > be faster than perl 5 with variables too, which will put us at the top of
> > the performance heap, possibly duking it out with Java. (Though I think
> > perl 5's faster than java now, but it's tough to get a good equivalence
> > there)
>
>Rewriting perl will leave behind all the cruft that accumulated over the 
>years,
>so it should not be difficult for parrot to run faster;-)

Boy I hope so. (Try benchmarking perl 5.004_04 against 5.6.1. I did, the 
results were embarrassing)

>Java is way faster than perl currently in many tasks:

Only when JITed. In which case you're comparing apples to oranges. A better 
comparison is against Java without JIT. (Yes, I know, Java *has* a JIT, but 
for reasonable numbers at a technical level (and yes, I also realize that 
generally speaking most folks don't care about that--they just want to know 
which runs faster) you need to compare like things)

>it will be difficult
>to beat it starting from a dynamic langauge like perl, we'll all pay
>the price to have a useful language like perl.

Unfortunately (and you made reference to this in an older mail I haven't 
answered yet) dynamic languages don't lend themselves to on-the-fly 
compilation quite the way that static languages do. Heck, they don't tend 
to lend themselves to compilation (certainly not optimization, and don't 
get me started) period as much as static languages. That's OK, it just 
means our technical challenges are similar to but not the same as for 
Java/C/C++/C#/Whatever.

> > >

Re: An overview of the Parrot interpreter

[Paolo Molaro]

On 09/05/01 Hong Zhang wrote:
> I think we need to get some initial performance characteristics of register
> machine vs stack machine before we go too far. There is not much points left
> debating in email list.

Unfortunately getting meaningful figures is quite hard, there are
so many thing to take into account that we'd spend a lot of time
only in evaluating the differences (it might be an interesting thesis
for a CS student, though:-).

lupus

-- 
-
[EMAIL PROTECTED] debian/rules
[EMAIL PROTECTED] Monkeys do it better

Re: An overview of the Parrot interpreter

[Ken Fox]

Paolo Molaro wrote:
> If anyone has any
> evidence that coding a stack-based virtual machine or a register one
> provides for better instructions scheduling in the dispatch code,
> please step forward.

I think we're going to have some evidence in a few weeks. I'm not
sure which side the evidence is going to support though... ;)

Eric Raymond posted on python-dev that he's doubtful, but has
a "wait and see" approach. Seems sensible. I think even Dan would
say he's just hopeful, not commited.

> I believe that a stack-based machine will have roughly the same
> performance when interpreted as a register-based machine, but
> it easily allows to take a step further and JIT compile the bytecode
> to machine code.

I don't really see much difference. You don't have to map the VM
registers to hardware registers to pick up a lot of speed. If the
JIT wanted to, it could have an optional peep-hole optimization
pass. That actually sounds easier to do with a register-based VM
than a stack-based one. (Of course the run-time environment is a
big wild-card here. We need a fast interface between the dispatcher
and the run-time. That's going to want registers too.)

> With the difference that the registers are malloc()ed while the eval
> stack in a stack machine is in the actual cpu stack.

Is there really a difference in memory access between the heap
and the stack? I've alway thought a page is a page and it doesn't
matter where in memory the page is. I'm not a hardware guy though...

Allocating register pools on the heap (making sure that malloc()
is used sensibly), might be faster if you want your VM to handle
continuations and co-routines. Check out stackless Python for
a good example. I'm not sure if Appel was the first, but he has
written quite a bit about the advantages of allocating activation
records on the heap. (He also points out that a garbage collector
can make heap allocation as fast as stack allocation.)

- Ken

Re: An overview of the Parrot interpreter

[Paolo Molaro]

On 09/05/01 Dan Sugalski wrote:
> >It's easier to generate code for a stack machine
> 
> So? Take a look at all the stack-based interpreters. I can name a bunch, 
> including perl. They're all slow. Some slower than others, and perl tends 
> to be the fastest of the bunch, but they're all slow.

Have a look at the shootout benchmarks. Yes, we all know that
benchmarks lie, but...
The original mono interpreter (that didn't implement all the semantics
required by IL code that slow down interpretation) ran about 4 times
faster than perl/python on benchmarks dominated by branches, function calls,
integer ops or fp ops.

> >That said, I haven't seen any evidence a register based machine is going to
> >be (significantly?) faster than a stack based one.
> >I'm genuinely interested in finding data about that.
> 
> At the moment a simple mix of ops takes around 26 cycles per opcode on an 
> Alpha EV6. (This is an even mix of branch, test, and integer addition 
> opcodes)  That's with everything sticking in cache, barring task switches. 
> It runs around 110 cycles/op on the reasonably antique machine I have at 
> home. (A 300MHz Celeron (the original, with no cache))

Subliminal message: post the code... :-)

> You're also putting far too much emphasis on registers in general. Most of 
> the work the interpreter will be doing will be elsewhere, either in the 
> opcode functions or in the variable vtable functions. The registers are 

That is true when executing high-level opcodes and a register or stack
machine doesn't make any difference for that. It's not true for
the low-level opcodes that parrot is supposed to handle according to the overview
posted by Simon.

> It'll be faster than perl for low-level stuff because we'll have the option 
> to not carry the overhead of full variables if we don't need it. It should 
> be faster than perl 5 with variables too, which will put us at the top of 
> the performance heap, possibly duking it out with Java. (Though I think 
> perl 5's faster than java now, but it's tough to get a good equivalence 
> there)

Rewriting perl will leave behind all the cruft that accumulated over the years,
so it should not be difficult for parrot to run faster;-)
Java is way faster than perl currently in many tasks: it will be difficult
to beat it starting from a dynamic langauge like perl, we'll all pay
the price to have a useful language like perl.
Most of us are here because they wouldn't program with a strongly typed
language more than for perl's speed. Note also that while java is faster than
perl most of the time, this advantage is completely wasted when you realize
you need 20 megs of RAM to run hello world:-)

> >The only difference in the execution engine is that you need to update
> >the stack pointer. The problem is when you need to generate code
> >for the virtual machine.
> 
> Codegen for register architectures is a long-solved problem. We can reach 
> back 30 or more years for it if we want. (We don't, the old stuff has been 

... when starting from a suitable intermediate representation (i.e., not
machine code for another register machine).

> push 0
>  pushaddr i
> store
> foo:  | push i
>   | push 1000
>   | branchgt end
>   | push 7
>   | push i
>   | add
>   | pushaddr i
>   | store
>   | jump foo
> end:
> 
> 
> with the ops executed in the loop marked with pipes. The corresponding 
> parrot code would be:
> 
>getaddr P0, i
>store   P0, 0
>store   I0, 1000
> foo: | branchgt end, P0, I0
>  | add P0, P0, 7
>  | jump foo
[...]
> So, best case (combined store, branch with constant embedded) the stack 
> based scheme has 7 opcodes in the loop, while parrot has 3. With the likely 
> case (what you see above) it's 9.

Well, it would be up to us to design the bytecode, so I'd say it's likely 7.

> Do you really think the stack-based way will be faster?

The speed of the above loop depends a lot on the actual implementation
(the need to do a function call in the current parrot code whould blow
away any advantage gained skipping stack updates, for example).
Also, this example doesn't take into account the convention to do
a function call: where do you put the arguments for a call? Will
you need to push/copy them?

As I said in another mail, I think the stack-based approach will not
be necessarily faster, but it will allow more optimizations down the path.
It may well be 20 % slower in some cases when interpreted, but if it allows 
me to easily JIT it and get 400 % faster, it's a non issue.

lupus

-- 
-
[EMAIL PROTECTED] debian/rules
[EMAIL PROTECTED] Monkeys do it better

Re: An overview of the Parrot interpreter

[Paolo Molaro]

On 09/05/01 Nick Ing-Simmons wrote:
> >It's easier to generate code for a stack machine 
> 
> True, but it is easier to generate FAST code for a register machine.
> A stack machine forces a lot of book-keeping either run-time inc/dec of sp, 
> or alternatively compile-time what-is-offset-now stuff. The latter is a real 
> pain if you are trying to issue multiple instructions at once.

There is an issue that is at the roots of all these discussions:
should parrot execute also low-level opcodes or not?
We all know from the paper that instruction decoding/dispatch is
a bottleneck in interpreter's execution speed and that it's better to
execute few heavy opcodes than many smaller ones.
The current perl has high-level opcodes and when most of the time
is spent in the opcode implementation it's quite fast (the regex engine
for example). However perl5 falls short when you need to perform integer/fp 
operations and subroutine calls.
Now, the proposal for parrot is also to handle low-level opcodes.
This is all well and good and the proposed architecture to handle it
is a register machine. If the register machine is implemented in sw
any talk about issuing multiple instructions at once is moot, it's
not under our control, but of the compiler. If anyone has any
evidence that coding a stack-based virtual machine or a register one
provides for better instructions scheduling in the dispatch code,
please step forward.

I believe that a stack-based machine will have roughly the same
performance when interpreted as a register-based machine, but
it easily allows to take a step further and JIT compile the bytecode
to machine code. If we are going to execute low-level opcodes,
no matter what architecture you choose for the interpreter,
JIT code runs faster:-)

> is a pain.) Explicit stack ops are going to give them indigestion.
> The P-III+ model is that most things are "on the C stack" i.e. offsets
> from the few "base" registers. The hardware then "aliases" those offsets 
> into its real registers. I don't think Parrot's register files will give 
> it much trouble, but throwing away the right inc/dec-of-pointer ops that
> a stack machine implies will (there are obviously HW special cases for x86's

With the difference that the registers are malloc()ed while the eval
stack in a stack machine is in the actual cpu stack. A good compiler
will put the stack pointer on a register, anyway.

lupus

-- 
-
[EMAIL PROTECTED] debian/rules
[EMAIL PROTECTED] Monkeys do it better

Re: An overview of the Parrot interpreter

[Simon Cozens]

On Thu, Sep 06, 2001 at 10:46:56AM -0400, Ken Fox wrote:
> Sure. I can do that while *waiting patiently* for Parrot to be
> released. ;)

Don't tell Nat I said this, but we're hoping for around the
beginning of next week.

Simon

Re: An overview of the Parrot interpreter

[Ken Fox]

Simon Cozens wrote:
> I want to get on with writing all the other documents like this one, but
> I don't want the questions raised in this thread to go undocumented and
> unanswered. I would *love* it if someone could volunteer to send me a patch
> to the original document tightening it up in the light of this thread.

Sure. I can do that while *waiting patiently* for Parrot to be
released. ;)

- Ken

Re: An overview of the Parrot interpreter

[Simon Cozens]

On Sun, Sep 02, 2001 at 11:56:10PM +0100, Simon Cozens wrote:
> Here's the first of a bunch of things I'm writing which should give you
> practical information to get you up to speed on what we're going to be doing
> with Parrot so we can get you coding away. :) Think of them as having a
> Apocalypse->Exegesis relationship to the PDDs. 

I want to get on with writing all the other documents like this one, but
I don't want the questions raised in this thread to go undocumented and
unanswered. I would *love* it if someone could volunteer to send me a patch
to the original document tightening it up in the light of this thread.

Anyone fancy doing that?

Simon

Re: An overview of the Parrot interpreter

[Piers Cawley]

Dan Sugalski <[EMAIL PROTECTED]> writes:

> At 10:32 AM 9/4/2001 +0100, Piers Cawley wrote:
> > > * Methods get their parameters passed in as a list in PMC register 0,
> > > * unless we can unambiguously figure out their prototype at
> > > * compilation time
> >
> >Will the subroutine know how it was called? (ie: Through method
> >dispatch or through straightforward symbol table lookup. I'm really
> >hoping the answer to this is 'yes'.) Or will methods and subroutines
> >be distinct now?
> 
> I suppose we could, and I don't know.
> 
> Can you see any use of a sub knowing it was called via a method call?

Yes. Especially if that comes with knowledge of what symbol table the
sub was found in. Then I could write HYPER.pm, a runtime equivalent of
SUPER::, and I believe that Damian's very lovely NEXT.pm could become 
substantially more reliable too.

-- 
Piers Cawley
www.iterative-software.com

RE: An overview of the Parrot interpreter

[Dan Sugalski]

At 11:17 AM 9/5/2001 -0700, Hong Zhang wrote:
>Howerver, I like to point out one hidden overhead of register opcode is
>decoding the parameter. The add instrction of stack machine does not have
>args, but for register machine, it has 3 arguments.

I skipped the decoding step in the machine design on purpose. Each opcode 
sort of does its own decoding. The way it works is you get an instruction 
stream that looks like:

1
0
1000

for "integer_store constant 1000 in register I0". The integer_store 
function gets a pointer to the start of the instruction (1 in this case) 
and looks like:

   IV *int_store(IV *opstream, Perl_Interp interpreter) {
   interpreter->int_regs[opstream[1]] = opstream[2];
   return opstream + 3;
   }

more or less. (It's not quite a cut'n'paste from the current parrot source, 
but close, after macro substitution)

There's still more dereferencing going on than I'd like, but at least we 
only have a single write (to the register) not a pair (the stack top and 
the stack pointer) and we don't have to check the stack pointer to make 
sure we're not extending past the end of our stack.

Fewer writes, fewer branches, and higher instruction density is where the 
register-based system should buy us a win. If anyone wants to cobble 
together a simple stack machine we can compare against, that'd be fine.

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

RE: An overview of the Parrot interpreter

[Hong Zhang]

> If you really want a comparison, here's one. Take this loop:
> 
>  i = 0;
>  while (i < 1000) {
>i = i + 7;
>  }
> 
> with the ops executed in the loop marked with pipes. The corresponding 
> parrot code would be:
> 
> getaddr P0, i
> store   P0, 0
> store   I0, 1000
> foo: | branchgt end, P0, I0
>   | add P0, P0, 7
>   | jump foo

I think dan gave a straight forward translation, since it does not really
use the int register. The optimized code will be faster.

store i1, 0;
store i2, 1000;
jump L2;
L1:
add i1, 7 => i1;
L2:
branchlt i1, i2 => L1;
getaddr i => P0;
store i1 => P0;

Howerver, I like to point out one hidden overhead of register opcode is 
decoding the parameter. The add instrction of stack machine does not have
args, but for register machine, it has 3 arguments.

Hong

RE: An overview of the Parrot interpreter

[Hong Zhang]

> True, but it is easier to generate FAST code for a register machine.
> A stack machine forces a lot of book-keeping either run-time inc/dec of
sp, 
> or alternatively compile-time what-is-offset-now stuff. The latter is a
real 
> pain if you are trying to issue multiple instructions at once.

I think we need to get some initial performance characteristics of register
machine vs stack machine before we go too far. There is not much points left
debating in email list.

I believe we have some misunderstanding here. The inc/dec of sp cost
nothing,
the sp is almost always a register variable, the cost of arithmetics on it
is 
mostly likely hidden by dispatch loop. The main cost is useless memory copy
like: push local #3. The register machine can only avoid copy between local 
variables and expression stack. If a sub uses a lot of globals and fields,
the register machine has to load/store them (in/out register file), which is
exactly the same as push/pop stack.

I think the performance gain of a register machine comes from several areas:

1) avoid copy between local and stack, but it can not speed up global/field
  access.

2) complex op reduce dispatch overhead
add i1, i2, i3;
  vs
push local 1;
push local 2;
add
pop local 3
  This is likely the biggest gain.

3) special registers (32 ints, 32 floats, 32 strings) simplify gc and speed
  up common opcodes. In order to achieve this, we must enable some type
system.
  I remember Perl6 is going to have unified int/bigint, num/bignum, multi
  encoding/charset string. I wonder how the special registers can handle
this
  feature, since there may be overflow/underflow problem.

Hong

Re: An overview of the Parrot interpreter

[Dan Sugalski]

[I'm answering these out of order--sorry. Already answered elsewhere bits 
snipped]
At 02:28 PM 9/5/2001 +0200, Paolo Molaro wrote:
>On 09/04/01 Dan Sugalski wrote:
> > > More on this point later in the mail.
> > >There's a reason for that: register virtual machines are more complex
> > >and more difficult to optimize.
> >
> > You'd be surprised there. The core of a register VM and a stack VM are
> > equivalent in complexity. A register VM makes reordering ops easier, tends
> > to reduce the absolute number of memory accesses (there's a *lot* of stack
> > thrash that goes on with a stack machine), and doesn't seem to have much
> > negative impact on things.
>
>When done in sw, the main difference is that stack-based machines have a 
>linear stack
>and the logic is simple, with register based machines you need to care for
>register windows.

This is a bit misleading.

If you assume a contiguous stack for both the register frames and the stack 
machine, then actually switching frames is cheaper on the register system 
since you only do it occasionally, as opposed to once per op.

If you assume a non-contiguous stack for the register frames and the stack 
machine, then switching frames gets proportionately more expensive for the 
stack machine, since the cost per switch goes up and you have far more 
switches.

Non-contiguous stacks make threading easier, which is a not-insignificant 
side benefit. You don't need to allocate X bytes in stack per thread and 
either waste memory or die because you ran out of stack.

Yes, the compiler needs to emit window change opcodes, but that's also a 
long-solved problem. In some ways we have it easier, since the compiler 
doesn't have to go pushing individual registers around in most cases. (We 
have bulk-renaming at hand essentially)

>As for memory accesses, stack based machines access
>always the top items of the stack (that fit in 1-2 cache lines) while
>
> add_i N1, N15, N31
>
>may touch a lot more memory (especially if the int registers are int64).
>Also, since the indexes for the add_i ops can be any integer, the compiler
>can't optimize much, while in a stack based machine they are hardcoded
>(0 and 1, for example).

We can ignore register sizes, since for a fair comparison we'll be looking 
at the same size data on both the stack and register machines. With the 
register system you do pop between cache lines more, but the cost is the 
same once you touch them.

It may look like we touch more lines since we cover a larger spread in one 
go, while stack systems tend to jitter on a few, but that's not the case. 
The stack machine tends to do more named_memory<->stack transfers. In the 
code I've rolled by hand, the register model generally accesses a small 
number of cache lines a lot and a large number of lines very rarely. Stack 
machines, on the other hand, access a smaller number of lines even more 
frequently and a large number of lines occasionally.

Locality of reference works out to be about the same. With more than a 
half-dozen cache lines most code works out the same both ways, with a minor 
win towards register systems. (Minor enough that I'm willing to chalk it up 
to personal style) However, the stack system does *far* more bookkeeping 
access (that darned stack pointer gets updated every op) and executes more 
opcodes.

If we were targeting machines with tiny or non-existent caches, I'd say 
stack machines would get the nod. Nobody's built one of those in several 
years, though--even the Pentium II meets our criteria last I looked. D'you 
really think using consumer grade CPUs made no later than 1997 (or was it 
'96?) is worthwhile? My sweet spot's newer than that. Given the expected 
first release delivery date of sometime 2002, I don't see using "normal" 
consumer grade hardware made in 1998 as a minimum requirement as unreasonable.

Which is to say, if it runs well on my Celeron at home (the machine dates 
to October 1998, and was one of Compaq's presario consumer grade machines. 
The thing cost all of $700 at the time. It was *not* high-end, or even 
medium-end, hardware for the time) I'm fine with it. Older hardware can cope.

> > What, you mean the x86? The whole world doesn't suck. Alpha, Sparc, MIPS,
> > PA-RISC, and the PPC all have a reasonable number of registers, and by all
> > accounts the IA64 does as well. Besides, you can think of a register
>
>I would expect that from a CS guy! ;-)

I'll find one for 'ya. I'm an engineer. :-P

>My point is: optimize for the common
>usage patterns/environments and that, as much as we may not like it, is
>32 bit x86. Parrot may run super-fast on alpha, but if people have x86 
>machines
>and servers that won't be any good for them. The engine needs to run well
>on all the archs, but don't optimize for the special cases.

You underestimate 32-bit x86 systems, I think. But choosing between a model 
that runs OK everywhere and one that runs OK some places but better others, 
well, the choice isn't t

Re: An overview of the Parrot interpreter

[Uri Guttman]

> "DS" == Dan Sugalski <[EMAIL PROTECTED]> writes:

  >> stack machine -> post-order walk of the tree
  >> 
  >> reg machine -> instruction selection -> register allocation ->

  DS> So what? That happens exactly once, in the compilation phase. Yes, it means 
  DS> compilation will be somewhat slower, but not by much.

  DS> As for simplicity, I think Uri was looking at it from the
  DS> standpoint of someone writing assembly for the machine by hand,
  DS> which is definitely easier.

i was actually referring to writing the op code functions that are in
the vtables. passing registers in and out of them is simpler coding than
munging a stack. i have coded both types in assembler and having
registers makes for cleaner code. and that is a big win for the
internals. 

  DS> You underestimate the numbers, I think. Even still, so what? I
  DS> have two targets, crippled CPUs (x86) and non-crippled CPUs
  DS> (everyone else). No matter what I do, I'm not going to get better
  DS> than good performance out of an x86. Period. The architecture gets
  DS> in the way, and there's not a damn thing I can do about it. On the
  DS> other hand, I do have a choice with the rest of the CPUs--I can
  DS> get either good or great performance. Seems a bad choice to trade
  DS> off great performance on some CPUs for what's likely to be no gain
  DS> on the rest.

and the 86's days are numbered with ia64 coming out now. sure x86 will be
around for years to come but it is not the only target out there. 

  >> Besides I think in the later alphas they added some opcodes to deal
  >> with the problem.

dunno about that. i worked on alpha compilers several years ago. OSF-1
was just out then :-)

  DS> You'll notice a rather significantly smaller number of register
  DS> based opcodes because we don't have to keep pushing stuff over and
  DS> over again.  There's also much less memory activity. Even if we
  DS> make the store operation in the stack-based scheme a single op
  DS> (store i) rather than a pair (pushaddr/store) and make the
  DS> branch-on-gt operation take a constant (which nobody does to the
  DS> best of my knowledge) there's still a lot more thrash going on,
  DS> and a lot more opcode overhead. And every opcode has overhead,
  DS> there's no way to skip it.

that is why CISC won over stack/accumulator based CPU's. RISC didn't
remove the register concept either. stack based are easier to build (the
freshman CS thing) and simpler to describe. but they require many more
ops to get the same work done. CISC's win was fewer instructiuon fetches
(the major bottleneck in those days). in perl5 the op code loop is the
bottleneck so fewer and more powerful ops will speed that up. dan's
assembler example illustrates that well.

uri

-- 
Uri Guttman  -  [EMAIL PROTECTED]  --  http://www.sysarch.com
SYStems ARCHitecture and Stem Development -- http://www.stemsystems.com
Search or Offer Perl Jobs  --  http://jobs.perl.org

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 03:19 PM 9/5/2001 +0200, Paolo Molaro wrote:
>On 09/04/01 Uri Guttman wrote:
> > does it really matter about comprehension? this is not going to be used
> > by the unwashed masses. a stack machine is easier to describe (hence all
> > the freshman CS projects :), but as dan has said, there isn't much
> > mental difference if you have done any serious assembler coding. is the
> > pdp-8 (or the teradyne 18 bit extended rip off) with 1 register (the
> > accumulator) a register or stack based machine?
>
>It's easier to generate code for a stack machine

So? Take a look at all the stack-based interpreters. I can name a bunch, 
including perl. They're all slow. Some slower than others, and perl tends 
to be the fastest of the bunch, but they're all slow.

>  and parrot is supposed to
>be a target for several languages: make it hard and only perl6 will target 
>parrot.

You underestimate us. :) Support for other languages generally won't 
require codegen work--parser rules should be sufficient for most languages, 
combined with libraries for variable vtables. Neither of which need to 
touch registers.

And even if it *does* take compiler work, so what? Very few people are up 
to it anyway. Why should we take a direction that has more memory accesses 
just to accommodate the naive way the interpreters are written now? You 
want fast, you pay the price.

Yes, dealing with a register system requires more sophisticated code. Code 
that, for the most part, will be provided with parrot. I really doubt 
anyone writing a front end for another language will get deeper than 
"here's the list of temps for this scope. Handle the register renaming".

>That said, I haven't seen any evidence a register based machine is going to
>be (significantly?) faster than a stack based one.
>I'm genuinely interested in finding data about that.

At the moment a simple mix of ops takes around 26 cycles per opcode on an 
Alpha EV6. (This is an even mix of branch, test, and integer addition 
opcodes)  That's with everything sticking in cache, barring task switches. 
It runs around 110 cycles/op on the reasonably antique machine I have at 
home. (A 300MHz Celeron (the original, with no cache))

You're also putting far too much emphasis on registers in general. Most of 
the work the interpreter will be doing will be elsewhere, either in the 
opcode functions or in the variable vtable functions. The registers are 
taking the place of the stack, and most of the activity even on a 
stack-based interpreter doesn't involve the stack.  (And no, this isn't a 
good argument to switch over to a stack-based system, since

> > but it doesn't matter what the underlying hardware machine is. that is
> > the realm of the c compiler. there is no need to think about the map of
> > parrot to any real hardware. they will all have their benefits and
>
>I brought the topic up because it was given as a benefit of the parrot
>register architecture.

It is--I think Uri's skipping some bits there. It won't matter as much for 
the interpreter, but it will for the bytecode->native code compiler.

>An issue is that, if parrot is going to run
>also low-level opcodes, it better know about the underlying arch

To some extent that's true. There's a limit to what we can do for speed 
tuning without knowledge of the underlying hardware.

>(well, it would be faster than the current perl anyway, but
>that's for another reason).

It'll be faster than perl for low-level stuff because we'll have the option 
to not carry the overhead of full variables if we don't need it. It should 
be faster than perl 5 with variables too, which will put us at the top of 
the performance heap, possibly duking it out with Java. (Though I think 
perl 5's faster than java now, but it's tough to get a good equivalence there)

> > that more than one temp slot is a big win IMO. with stack based you
> > typically have to push/pop all the time to get anything done. here we
> > have 32 PMC registers and you can grab a bunch and save them and then
> > use them directly. makes coding the internal functions much cleaner. if
> > you have ever programmed on a register cpu vs. a stack one, you will
> > understand. having clean internal code is a major win for register
> > based. we all know how critical it is to have easy to grok internals. :)
>
>The only difference in the execution engine is that you need to update
>the stack pointer. The problem is when you need to generate code
>for the virtual machine.

Codegen for register architectures is a long-solved problem. We can reach 
back 30 or more years for it if we want. (We don't, the old stuff has been 
long superceded, but this is nowhere near a new problem)

> >   DS> No. Absolutely not. The primary tenet is "Keep things fast". In my
> >   DS> experience simple things have no speed benefit, and often have a
> >   DS> speed deficit over more complex things. The only time it's a
> >   DS> problem is when the people doing the actual work on the system
> >   DS>

Re: An overview of the Parrot interpreter

[Paolo Molaro]

On 09/04/01 Uri Guttman wrote:
> does it really matter about comprehension? this is not going to be used
> by the unwashed masses. a stack machine is easier to describe (hence all
> the freshman CS projects :), but as dan has said, there isn't much
> mental difference if you have done any serious assembler coding. is the
> pdp-8 (or the teradyne 18 bit extended rip off) with 1 register (the
> accumulator) a register or stack based machine?

It's easier to generate code for a stack machine and parrot is supposed to
be a target for several languages: make it hard and only perl6 will target parrot.
That said, I haven't seen any evidence a register based machine is going to
be (significantly?) faster than a stack based one.
I'm genuinely interested in finding data about that.

> but it doesn't matter what the underlying hardware machine is. that is
> the realm of the c compiler. there is no need to think about the map of
> parrot to any real hardware. they will all have their benefits and

I brought the topic up because it was given as a benefit of the parrot
register architecture. An issue is that, if parrot is going to run
also low-level opcodes, it better know about the underlying arch
(well, it would be faster than the current perl anyway, but
that's for another reason).

> that more than one temp slot is a big win IMO. with stack based you
> typically have to push/pop all the time to get anything done. here we
> have 32 PMC registers and you can grab a bunch and save them and then
> use them directly. makes coding the internal functions much cleaner. if
> you have ever programmed on a register cpu vs. a stack one, you will
> understand. having clean internal code is a major win for register
> based. we all know how critical it is to have easy to grok internals. :)

The only difference in the execution engine is that you need to update
the stack pointer. The problem is when you need to generate code
for the virtual machine.

>   DS> No. Absolutely not. The primary tenet is "Keep things fast". In my
>   DS> experience simple things have no speed benefit, and often have a
>   DS> speed deficit over more complex things. The only time it's a
>   DS> problem is when the people doing the actual work on the system
>   DS> can't keep the relevant bits in their heads. Then you lose, but
>   DS> not because of complexity per se, but rather because of programmer
>   DS> inefficiency. We aren't at that point, and there's no reason we
>   DS> need to be. (Especially because register machines tend to be
>   DS> simpler to work with than stack machines, and the bits that are
>   DS> too complex for mere mortals get dealt with by code rather than
>   DS> people anyway)
> 
> amen. i fully agree, register machines are much simpler to code with. i
> don't know why paolo thinks stack based is harder to code to.

stack machine -> post-order walk of the tree

reg machine -> instruction selection -> register allocation -> 

> on some machines like the alpha, getting single bytes is slower than
> fetching 32 bits. 

Too bad less than 1 % of the people that will use parrot have
an alpha or a Cray. Optimize for the common case. Besides I think
in the later alphas they added some opcodes to deal with the problem.

lupus

-- 
-
[EMAIL PROTECTED] debian/rules
[EMAIL PROTECTED] Monkeys do it better

Re: An overview of the Parrot interpreter

[Paolo Molaro]

On 09/04/01 Dan Sugalski wrote:
> Regardless, it's the way we're going to go for now. If it turns out to be a 
> performance dog then we'll go with a stack-based system. Initial 
> indications look pretty good, though.

Care to share some numbers/code for that?

> >You're right that optimization research on stack based machines
> >is more limited than that on register machines, but you'll also note
> >that there are basically no portable interpreters/runtimes based
> >on register machines:-)
> 
> Yes, but is this because:
> 
> A) Register machines are really bad when done in software
> B) People *think* register machines are really bad when done in software
> C) People think stack machines are just cleaner
> D) Most people writing interpreters are working with a glorified CS 
> freshman project with bells and whistles hung on it.
> 
> From looking at the interpreters we have handy (and I've looked at a 
> bunch), my bet is D.

Well, if it may help, I'm not a CS student :-)
I think a register machine doesn't give any benefit over a stack machine
and I'm looking for evidences that could prove me wrong.

> > More on this point later in the mail.
> >There's a reason for that: register virtual machines are more complex
> >and more difficult to optimize.
> 
> You'd be surprised there. The core of a register VM and a stack VM are 
> equivalent in complexity. A register VM makes reordering ops easier, tends 
> to reduce the absolute number of memory accesses (there's a *lot* of stack 
> thrash that goes on with a stack machine), and doesn't seem to have much 
> negative impact on things.

When done in sw, the main difference is that stack-based machines have a linear stack
and the logic is simple, with register based machines you need to care for
register windows. As for memory accesses, stack based machines access
always the top items of the stack (that fit in 1-2 cache lines) while

add_i N1, N15, N31

may touch a lot more memory (especially if the int registers are int64).
Also, since the indexes for the add_i ops can be any integer, the compiler
can't optimize much, while in a stack based machine they are hardcoded
(0 and 1, for example).

> What, you mean the x86? The whole world doesn't suck. Alpha, Sparc, MIPS, 
> PA-RISC, and the PPC all have a reasonable number of registers, and by all 
> accounts the IA64 does as well. Besides, you can think of a register 

I would expect that from a CS guy! ;-) My point is: optimize for the common
usage patterns/environments and that, as much as we may not like it, is
32 bit x86. Parrot may run super-fast on alpha, but if people have x86 machines
and servers that won't be any good for them. The engine needs to run well
on all the archs, but don't optimize for the special cases.

> machine as a stack machine where you can look back in the stack directly 
> when need be, and you don't need to mess with the stack pointer nearly as 
> often.

In a sw stack machine you can look back at any stack position just fine,
you just don't have to care about register windows:-)

> > Literature is mostly concerned
> >about getting code for real register machines out of trees and DAGs and
> >the optimizations are mostly of two types:
> >1) general optimizations that are independed on the actual cpu
> >2) optimizations specific to the cpu
> >
> >[1] can be done in parrot even if the underlying virtual machine is
> >register or stack based, it doesn't matter.
> 
> Actually it does. Going to a register machine's generally more 
> straightforward than going to a stack based one. Yes, there are register 

What is easier than a post-order walk of a tree? A related point
is that if parrot is meant to run code from different high level
languages, it needs also to be simple for those languages to
generate parrot bytecode.

> usage issues, but they're less of an issue than with a pure stack machine, 
> because you have less stack snooping that needs doing, and reordering 
> operations tends to be simpler. You also tend to fetch data from variables 
> into work space less often, since you essentially have more than one temp 
> slot handy.

I'm not proposing a pure stack machine; besides you can have local variables
in a function and access to them is as fast as access to the registers in a 
register machine.

> Why on earth are you assuming we're going to toss the optree, DAGs, or even 
> the source? That's all going to be kept in the bytecode files.
> 
> Also, even if that stuff is tossed, parrot bytecode makes a reasonable MIR. 
> And some recent research indicates that even without all the intermediate 
> stuff saved you can buy a win. (There are currently executable translators 
> that go from one CPUs machine language to another directly. The resulting 
> executables run as fast or faster in most cases. I've even heard reports of 
> one of the translators taking 386 executables and translating it out and 
> back into 386 executables that ran faster. I have no first-hand proof of 
> t

Re: An overview of the Parrot interpreter

[Benjamin Stuhl]

--- Dan Sugalski <[EMAIL PROTECTED]> wrote:
> At 03:48 PM 9/4/2001 -0400, Uri Guttman wrote:
> > > "DS" == Dan Sugalski <[EMAIL PROTECTED]> writes:
> >
> >
> >   DS> Ah. I've always wanted to do that with tied
> hashes. Okay, even
> >   DS> more reason to pass the data in! (We're going to
> end up with a
> >   DS> WANT register by the time we're done...)
> >
> >that is not a bad idea. we could allocate a PMC register
> (e.g. #31)
> >permanently to store WANT info (in a hash i assume like
> the RFC
> >implies).
> 
> I don't think I'd want to soak up a PMC register that
> way. Maybe an integer 
> one.

Maybe not a general purpose PMC register, but what about a
special one? Since the proposal was to lazily update it, it
doesn't need to be part of the standard register frame.
Besides, I though we were going with having a few "special"
PMC registers (PL_sv_yes, PL_sv_no, PL_sv_undef, etc.) to
reduce the size of the constants section?

-- BKS

__
Do You Yahoo!?
Get email alerts & NEW webcam video instant messaging with Yahoo! Messenger
http://im.yahoo.com

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 03:48 PM 9/4/2001 -0400, Uri Guttman wrote:
> > "DS" == Dan Sugalski <[EMAIL PROTECTED]> writes:
>
>
>   DS> Ah. I've always wanted to do that with tied hashes. Okay, even
>   DS> more reason to pass the data in! (We're going to end up with a
>   DS> WANT register by the time we're done...)
>
>that is not a bad idea. we could allocate a PMC register (e.g. #31)
>permanently to store WANT info (in a hash i assume like the RFC
>implies).

I don't think I'd want to soak up a PMC register that way. Maybe an integer 
one.


Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter

[Uri Guttman]

> "DS" == Dan Sugalski <[EMAIL PROTECTED]> writes:


  DS> Ah. I've always wanted to do that with tied hashes. Okay, even
  DS> more reason to pass the data in! (We're going to end up with a
  DS> WANT register by the time we're done...)

that is not a bad idea. we could allocate a PMC register (e.g. #31)
permanently to store WANT info (in a hash i assume like the RFC
implies). this only needs to be updated when a sub call is made which
has a WANT call in it. so those subs will be compiled to save the WANT
register and load their WANT values into it.  so a sub which doesn't
call WANT, never looks at nor touches that register.

uri

-- 
Uri Guttman  -  [EMAIL PROTECTED]  --  http://www.sysarch.com
SYStems ARCHitecture and Stem Development -- http://www.stemsystems.com
Search or Offer Perl Jobs  --  http://jobs.perl.org

Re: An overview of the Parrot interpreter

[Uri Guttman]

> "DS" == Dan Sugalski <[EMAIL PROTECTED]> writes:

  DS> I don't buy that there's a higher bar on comprehension,
  DS> either. Register machines in general aren't anything at all
  DS> new. Granted, lots of folks grew up with the abomination that is
  DS> x86 assembly, if they even bothered hitting assembler in the first
  DS> place, but picking up a new, relatively straightforward,
  DS> architecture's not tough. Anyone who can manage a stack machine
  DS> can handle a register one and, having programmed in both 68K
  DS> assembly and Forth at the same time, I can say that for me a
  DS> register system is *far* easier to keep a handle on.

does it really matter about comprehension? this is not going to be used
by the unwashed masses. a stack machine is easier to describe (hence all
the freshman CS projects :), but as dan has said, there isn't much
mental difference if you have done any serious assembler coding. is the
pdp-8 (or the teradyne 18 bit extended rip off) with 1 register (the
accumulator) a register or stack based machine?

  >> You say that, since a virtual register machine is closer to the actual hw
  >> that will run the program, it's easier to produce the corresponding
  >> machine code and execute that instead. The problem is that that's true
  >> only on architectures where the virtual machine matches closely the
  >> cpu and I don't see that happenning with the current register starved
  >> main archs.

  DS> What, you mean the x86? The whole world doesn't suck. Alpha,
  DS> Sparc, MIPS, PA-RISC, and the PPC all have a reasonable number of
  DS> registers, and by all accounts the IA64 does as well. Besides, you
  DS> can think of a register machine as a stack machine where you can
  DS> look back in the stack directly when need be, and you don't need
  DS> to mess with the stack pointer nearly as often.

but it doesn't matter what the underlying hardware machine is. that is
the realm of the c compiler. there is no need to think about the map of
parrot to any real hardware. they will all have their benefits and
disadvantages running parrot depending on whatever. we can't control
that. our goal is a VM that is simple to generate for and interpret as
well as being powerful. stack based VM's aren't as flexible as a
register design. dan mentions some of the reasons below.

  >> Literature is mostly concerned
  >> about getting code for real register machines out of trees and DAGs and
  >> the optimizations are mostly of two types:
  >> 1) general optimizations that are independed on the actual cpu
  >> 2) optimizations specific to the cpu
  >> 
  >> [1] can be done in parrot even if the underlying virtual machine is
  >> register or stack based, it doesn't matter.

  DS> Actually it does. Going to a register machine's generally more
  DS> straightforward than going to a stack based one. Yes, there are
  DS> register usage issues, but they're less of an issue than with a
  DS> pure stack machine, because you have less stack snooping that
  DS> needs doing, and reordering operations tends to be simpler. You
  DS> also tend to fetch data from variables into work space less often,
  DS> since you essentially have more than one temp slot handy.

that more than one temp slot is a big win IMO. with stack based you
typically have to push/pop all the time to get anything done. here we
have 32 PMC registers and you can grab a bunch and save them and then
use them directly. makes coding the internal functions much cleaner. if
you have ever programmed on a register cpu vs. a stack one, you will
understand. having clean internal code is a major win for register
based. we all know how critical it is to have easy to grok internals. :)

  >> [2] will optimize for the virtual machine and not for the
  >> underlying arch, so you get optimized bytecode for a virtual
  >> arch. At this point, though, when you need to actually execute the
  >> code, you won't be able to optimize further for the actual cpu
  >> because most of the useful info (op trees and DAGs) are gone and
  >> there is way less info in the literature about emulating CPU than
  >> generating machine code from op-trees.

  DS> Why on earth are you assuming we're going to toss the optree,
  DS> DAGs, or even the source? That's all going to be kept in the
  DS> bytecode files.

also we are not directly targeting any real machines. you have to
separate the VM architecture from any cpu underneath. other than for TIL
or related stuff, parrot will never know or care about the cpu it is
running on.

  >> Another point I'd like to make is: keep things simple.

  DS> No. Absolutely not. The primary tenet is "Keep things fast". In my
  DS> experience simple things have no speed benefit, and often have a
  DS> speed deficit over more complex things. The only time it's a
  DS> problem is when the people doing the actual work on the system
  DS> can't keep the relevant bits in their heads. Then you lose, but
  DS> not because of complexity per se, but r

RE: An overview of the Parrot interpreter

[Garrett Goebel]

From: Graham Barr [mailto:[EMAIL PROTECTED]]
> On Tue, Sep 04, 2001 at 03:03:04PM -0400, Dan Sugalski wrote:
> > At 01:58 PM 9/4/2001 -0500, Garrett Goebel wrote:
> > >From: Dan Sugalski [mailto:[EMAIL PROTECTED]]
> > > > At 10:32 AM 9/4/2001 +0100, Piers Cawley wrote:
> > > > Can you see any use of a sub knowing it was called via 
> > > > a method call?
> > >
> > >So that attributes which cause code to be executed before 
> > >or after a subroutine implementation's execution might
> > >behave differently depending on whether the sub were
> > >executed as a function or a method?
> > 
> > Okay. I'll see about finding a spot to squirrel away call 
> > type somewhere.
> 
> Hm, interesting. Is this a method or function call ?
> 
>  $ref = $obj.can('foo');
>  $ref.($obj);

I'm still fairly shaky on Perl6 syntax, but in Perl5

>perldoc UNIVERSAL

gives:

can ( METHOD )
`can' checks if the object has a method called `METHOD'. If it does
then a reference to the sub is returned. If it does not then *undef*
is returned.

`can' can be called as either a static or object method call.

The fact that the above isn't exactly true (subroutines are not checked for
verify that the :method attribute is set) is beside the point.

I'd hope that $ref.method would return a true value. And that $ref would be
executed as a method.

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 08:05 PM 9/4/2001 +0100, Graham Barr wrote:
>On Tue, Sep 04, 2001 at 03:03:04PM -0400, Dan Sugalski wrote:
> > At 01:58 PM 9/4/2001 -0500, Garrett Goebel wrote:
> > >From: Dan Sugalski [mailto:[EMAIL PROTECTED]]
> > > > At 10:32 AM 9/4/2001 +0100, Piers Cawley wrote:
> > > > Can you see any use of a sub knowing it was called via a method call?
> > >
> > >So that attributes which cause code to be executed before or after a
> > >subroutine implementation's execution might behave differently 
> depending on
> > >whether the sub were executed as a function or a method?
> >
> > Okay. I'll see about finding a spot to squirrel away call type somewhere.
>
>Hm, interesting. Is this a method or function call ?
>
>  $ref = $obj.can('foo');
>  $ref.($obj);

Good question. Ask Larry or Damian, and when they say I'll tell the parser. :)

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter

[Graham Barr]

On Tue, Sep 04, 2001 at 03:03:04PM -0400, Dan Sugalski wrote:
> At 01:58 PM 9/4/2001 -0500, Garrett Goebel wrote:
> >From: Dan Sugalski [mailto:[EMAIL PROTECTED]]
> > > At 10:32 AM 9/4/2001 +0100, Piers Cawley wrote:
> > > Can you see any use of a sub knowing it was called via a method call?
> >
> >So that attributes which cause code to be executed before or after a
> >subroutine implementation's execution might behave differently depending on
> >whether the sub were executed as a function or a method?
> 
> Okay. I'll see about finding a spot to squirrel away call type somewhere.

Hm, interesting. Is this a method or function call ?

 $ref = $obj.can('foo');
 $ref.($obj);

Graham.

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 03:04 PM 9/4/2001 -0400, Uri Guttman wrote:
>for sure. one case i saw recently in c.l.p.m was someone who wanted to
>chain method calls together like this:
>
> $obj->meth1()->meth2() ;
>
>this is easy assuming you return the object in each method call. but he
>ALSO wanted:
>
> $bar = $obj->meth1() ;
>
>to return something other than $obj.

Ah. I've always wanted to do that with tied hashes. Okay, even more reason 
to pass the data in! (We're going to end up with a WANT register by the 
time we're done...)

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter

[Uri Guttman]

> "DS" == Dan Sugalski <[EMAIL PROTECTED]> writes:

  DS> At 10:32 AM 9/4/2001 +0100, Piers Cawley wrote:

  >> Will the subroutine know how it was called? (ie: Through method
  >> dispatch or through straightforward symbol table lookup. I'm really
  >> hoping the answer to this is 'yes'.) Or will methods and subroutines
  >> be distinct now?

  DS> I suppose we could, and I don't know.

damian's new want (RFC 21) will be able to tell the difference. there is
a method context that is returned if called via a method.

  DS> Can you see any use of a sub knowing it was called via a method
  DS> call?

for sure. one case i saw recently in c.l.p.m was someone who wanted to
chain method calls together like this:

$obj->meth1()->meth2() ;

this is easy assuming you return the object in each method call. but he
ALSO wanted:

$bar = $obj->meth1() ;

to return something other than $obj.

so it would be easy to check that with want and return the desired
thing.


i am sure damian will be able to come up with more examples. in any case
it is specified in his want RFC and i will bet it will be in the
language. the whole want thingie is very cool.

uri

-- 
Uri Guttman  -  [EMAIL PROTECTED]  --  http://www.sysarch.com
SYStems ARCHitecture and Stem Development -- http://www.stemsystems.com
Search or Offer Perl Jobs  --  http://jobs.perl.org

RE: An overview of the Parrot interpreter

[Dan Sugalski]

At 01:58 PM 9/4/2001 -0500, Garrett Goebel wrote:
>From: Dan Sugalski [mailto:[EMAIL PROTECTED]]
> > At 10:32 AM 9/4/2001 +0100, Piers Cawley wrote:
> > > > * Methods get their parameters passed in as a list in
> > > > * PMC register 0, unless we can unambiguously figure
> > > > * out their prototype at compilation time
> > >
> > >Will the subroutine know how it was called? (ie: Through method
> > >dispatch or through straightforward symbol table lookup. I'm really
> > >hoping the answer to this is 'yes'.) Or will methods and subroutines
> > >be distinct now?
> >
> > I suppose we could, and I don't know.
> >
> > Can you see any use of a sub knowing it was called via a method call?
>
>So that attributes which cause code to be executed before or after a
>subroutine implementation's execution might behave differently depending on
>whether the sub were executed as a function or a method?

Okay. I'll see about finding a spot to squirrel away call type somewhere.

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 12:38 PM 9/4/2001 +0200, Paolo Molaro wrote:
>I'm not convinced the register machine is the way to go.

Well, neither am I, and I came up with the plan.

Regardless, it's the way we're going to go for now. If it turns out to be a 
performance dog then we'll go with a stack-based system. Initial 
indications look pretty good, though.

>You're right that optimization research on stack based machines
>is more limited than that on register machines, but you'll also note
>that there are basically no portable interpreters/runtimes based
>on register machines:-)

Yes, but is this because:

A) Register machines are really bad when done in software
B) People *think* register machines are really bad when done in software
C) People think stack machines are just cleaner
D) Most people writing interpreters are working with a glorified CS 
freshman project with bells and whistles hung on it.

 From looking at the interpreters we have handy (and I've looked at a 
bunch), my bet is D.

The Inferno VM uses a different approach entirely, and the 68K VM is, of 
course, register based. (Though it's directly targeted at the PPC as an 
execution host)

Not to say that register machines are right, just that I don't think 
there's any evidence they're worse than stack machines. Hopefully parrot 
won't prove me wrong.

>  More on this point later in the mail.
>There's a reason for that: register virtual machines are more complex
>and more difficult to optimize.

You'd be surprised there. The core of a register VM and a stack VM are 
equivalent in complexity. A register VM makes reordering ops easier, tends 
to reduce the absolute number of memory accesses (there's a *lot* of stack 
thrash that goes on with a stack machine), and doesn't seem to have much 
negative impact on things.

I don't buy that there's a higher bar on comprehension, either. Register 
machines in general aren't anything at all new. Granted, lots of folks grew 
up with the abomination that is x86 assembly, if they even bothered hitting 
assembler in the first place, but picking up a new, relatively 
straightforward, architecture's not tough. Anyone who can manage a stack 
machine can handle a register one and, having programmed in both 68K 
assembly and Forth at the same time, I can say that for me a register 
system is *far* easier to keep a handle on.

>You say that, since a virtual register machine is closer to the actual hw
>that will run the program, it's easier to produce the corresponding
>machine code and execute that instead. The problem is that that's true
>only on architectures where the virtual machine matches closely the
>cpu and I don't see that happenning with the current register starved
>main archs.

What, you mean the x86? The whole world doesn't suck. Alpha, Sparc, MIPS, 
PA-RISC, and the PPC all have a reasonable number of registers, and by all 
accounts the IA64 does as well. Besides, you can think of a register 
machine as a stack machine where you can look back in the stack directly 
when need be, and you don't need to mess with the stack pointer nearly as 
often.

>The point about the literature is flawed, IMHO.

Yup, YHO. Mine differs. :)

>  Literature is mostly concerned
>about getting code for real register machines out of trees and DAGs and
>the optimizations are mostly of two types:
>1) general optimizations that are independed on the actual cpu
>2) optimizations specific to the cpu
>
>[1] can be done in parrot even if the underlying virtual machine is
>register or stack based, it doesn't matter.

Actually it does. Going to a register machine's generally more 
straightforward than going to a stack based one. Yes, there are register 
usage issues, but they're less of an issue than with a pure stack machine, 
because you have less stack snooping that needs doing, and reordering 
operations tends to be simpler. You also tend to fetch data from variables 
into work space less often, since you essentially have more than one temp 
slot handy.

>[2] will optimize for the virtual machine and not for the underlying arch,
>so you get optimized bytecode for a virtual arch. At this point, though, when
>you need to actually execute the code, you won't be able to optimize 
>further for
>the actual cpu because most of the useful info (op trees and DAGs) are gone
>and there is way less info in the literature about emulating CPU than
>generating machine code from op-trees.

Why on earth are you assuming we're going to toss the optree, DAGs, or even 
the source? That's all going to be kept in the bytecode files.

Also, even if that stuff is tossed, parrot bytecode makes a reasonable MIR. 
And some recent research indicates that even without all the intermediate 
stuff saved you can buy a win. (There are currently executable translators 
that go from one CPUs machine language to another directly. The resulting 
executables run as fast or faster in most cases. I've even heard reports of 
one of the translators taking 386 executables and translating

RE: An overview of the Parrot interpreter

[Garrett Goebel]

From: Dan Sugalski [mailto:[EMAIL PROTECTED]]
> At 10:32 AM 9/4/2001 +0100, Piers Cawley wrote:
> > > * Methods get their parameters passed in as a list in
> > > * PMC register 0, unless we can unambiguously figure
> > > * out their prototype at compilation time
> >
> >Will the subroutine know how it was called? (ie: Through method
> >dispatch or through straightforward symbol table lookup. I'm really
> >hoping the answer to this is 'yes'.) Or will methods and subroutines
> >be distinct now?
> 
> I suppose we could, and I don't know.
> 
> Can you see any use of a sub knowing it was called via a method call?

So that attributes which cause code to be executed before or after a
subroutine implementation's execution might behave differently depending on
whether the sub were executed as a function or a method?

On the language list some time ago, Damian mentioned Pre and Post subroutine
handlers that might act differently depending upon whether the subroutine
was called as a function or a method. I.e., on methods they would act like
Design-By-Contract conditions: providing for conditional assertions, but
unable to modify pre/post execution or the argument list. Whereas 'Pre' and
'Post' attributes on functions might be used to massage arguments into a
required format, supply clean-up code, or even replace the implementation.

Certainly this could be avoided by naming the properties differently... but
perhaps there are other uses that might be similar?

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 10:53 AM 9/4/2001 +0300, Ariel Scolnicov wrote:
>What happens when I call a prototyped sub with a code ref?

We call the "I've been called with a single list" entry point. One that, 
until recently, I hadn't planned on. :)

That, I expect, will extract the elements from the list into registers, 
possibly check them, then call into the sub as if it'd been called with the 
parameters in registers. (At which point we'll probably apply the checks 
for type)

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 10:32 AM 9/4/2001 +0100, Piers Cawley wrote:
> > * Methods get their parameters passed in as a list in PMC register 0,
> > * unless we can unambiguously figure out their prototype at
> > * compilation time
>
>Will the subroutine know how it was called? (ie: Through method
>dispatch or through straightforward symbol table lookup. I'm really
>hoping the answer to this is 'yes'.) Or will methods and subroutines
>be distinct now?

I suppose we could, and I don't know.

Can you see any use of a sub knowing it was called via a method call?

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 09:06 AM 9/4/2001 +0100, Simon Cozens wrote:
>On Mon, Sep 03, 2001 at 09:53:11PM -0400, Dan Sugalski wrote:
> > Might as well just promote the things to PMCs and pass in a list of them.
>
>I anticipate that, especially for Perl, in a lot of cases we'll be dealing
>with PMCs more often than the "scalar" data types.

Of that I have no doubt. The int/string/num registers are really for the 
interpreter's internal use, along with a potential for optimization. I 
doubt we'll see sub calls to user subs that use them in parameter lists.

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter

[Paolo Molaro]

On 09/02/01 Simon Cozens wrote:
> =head1 The Software CPU
> 
> Like all interpreter systems of its kind, the Parrot interpreter is
> a virtual machine; this is another way of saying that it is a software
> CPU. However, unlike other VMs, the Parrot interpreter is designed to
> more closely mirror hardware CPUs.
> 
> For instance, the Parrot VM will have a register architecture, rather
> than a stack architecture. It will also have extremely low-level
> operations, more similar to Java's than the medium-level ops of Perl and
> Python and the like.
> 
> The reasoning for this decision is primarily that by resembling the
> underlying hardware to some extent, it's possible to compile down Parrot
> bytecode to efficient native machine language. It also allows us to make
> use of the literature available on optimizing compilation for hardware
> CPUs, rather than the relatively slight volume of information on
> optimizing for macro-op based stack machines.

I'm not convinced the register machine is the way to go.
You're right that optimization research on stack based machines
is more limited than that on register machines, but you'll also note
that there are basically no portable interpreters/runtimes based
on register machines:-) More on this point later in the mail.
There's a reason for that: register virtual machines are more complex
and more difficult to optimize.

You say that, since a virtual register machine is closer to the actual hw
that will run the program, it's easier to produce the corresponding
machine code and execute that instead. The problem is that that's true
only on architectures where the virtual machine matches closely the
cpu and I don't see that happenning with the current register starved
main archs.

The point about the literature is flawed, IMHO. Literature is mostly concerned
about getting code for real register machines out of trees and DAGs and
the optimizations are mostly of two types:
1) general optimizations that are independed on the actual cpu
2) optimizations specific to the cpu

[1] can be done in parrot even if the underlying virtual machine is
register or stack based, it doesn't matter.
[2] will optimize for the virtual machine and not for the underlying arch,
so you get optimized bytecode for a virtual arch. At this point, though, when
you need to actually execute the code, you won't be able to optimize further for
the actual cpu because most of the useful info (op trees and DAGs) are gone
and there is way less info in the literature about emulating CPU than
generating machine code from op-trees.

If you have bytecode for a stack machine, instead, you can easily reconstruct
the tree, apply the optimizations and generate the efficient machine code
required to make an interpreter for low-level ops useable.

The flow for a register machine will look basically like this:

perl code
op tree
tree optimization
instr selection
reg allocation
byte code
sw cpu emulation on hw cpu
or
translation of machine code to real machine code
exec real machne code

Note that on the last steps there is little (shared) research.

The flow for a stack machine will look instead like this:

perl code
op tree
tree optimization
byte code
interpret byte code
or
instr selection
reg allocation
exec machne code

All the steps are well documented and understood in the research 
(and especially open source) community.

Another point I'd like to make is: keep things simple.
A stack machine is easy to run and write code for. A virtual
register machine is much more complicated, no matter how many
registers you have, you'll need register windows (i.e., you'll
use the registers as a stack).
A simple design is not necessarily slow: complex stuff adds
dcache and icache pressure, it's harder to debug and optimize
(but we know that from the perl5 experience, don't we?).

> Operations will be represented by several bytes of Parrot machine code;
> the first C will specify the operation number, and the remaining
> arguments will be operator-specific. Operations will usually be targeted
> at a specific data type and register type; so, for instance, the
> C takes two Cs as arguments, and decrements contents of the
> integer register designated by the first C by the value in the
> second C. Naturally, operations which act on C registers will
> use Cs for constants; however, since the first argument is almost
> always a register B rather than actual data, even operations on
> string and PMC registers will take an C as the first argument. 

Please, reconsider also the size of the bytecode: a minumun of 8 bytes
for a simple operation will result in large cache trashing:

Consider:

sub add ($a, $b) {
return $a+$b;
}

Assuming the args will be already in registers, this becomes something
like:

add_i R1, A1, A2 (16 bytes)
ret (4 bytes)

RE: An overview of the Parrot interpreter

[Brent Dax]

Simon Cozens:
# On Mon, Sep 03, 2001 at 04:05:26PM -0700, Brent Dax wrote:
# > In other words, when you have sub foo {} in your code, it will be
# > assigned an opcode number in the 'private' section.  The
# global section
# > is for things that are built-in to Parrot, while the
# private section is
# > for stuff you write.  (Right?)
#
# That's a better explanation than I managed, thanks.
#
# > Perl *scalars* are PMCs.  Those PMCs may hold strings within them.
# > However, string manipulation is done in special string
# registers, which
# > are *not* PMCs.
#
# That's also a better explanation than I managed, thanks.

Hey, I'm a trained professional in Cozens-to-English, what do you
expect?  :^)

--Brent Dax
[EMAIL PROTECTED]

"...and if the answers are inadequate, the pumpqueen will be overthrown
in a bloody coup by programmers flinging dead Java programs over the
walls with a trebuchet."

Re: An overview of the Parrot interpreter

[Piers Cawley]

Dan Sugalski <[EMAIL PROTECTED]> writes:
> At 08:19 PM 9/3/2001 -0400, Sam Tregar wrote:
> >Speaking of soubroutines, what is Parrot's calling conventions?  Obviously
> >we're no long in PUSH/POP land...
> 
> Up until now, I didn't know, so consider yourself the first to find out. :)
> 
> * Integer, String, and Number registers 0-x are used to pass
> * parameters when the compiler calls routines.
> 
> 
> * PMC registers 0-x are used to pass parameters *if* the sub has a
> * prototype. If the sub does *not* have a prototype, a list is created
> * and passed in PMC register 0.
> 
> 
> * Subs may have variable number, or unknown number, of PMC parameters.
> * (Basically Parrot variables) They may *not* take a variable or
> * unknown number of integer, string, or number parameters.
> 
> 
> * Subs may not change prototypes
> 
> * Sub prototypes must be known at compile time. (I.e. by the end of
> * the primary compilation phase, and before mainline run time.
> * Basically the equivalent to the end of BEGIN or beginning of CHECK
> * phase)
> 
> 
> * Methods get their parameters passed in as a list in PMC register 0,
> * unless we can unambiguously figure out their prototype at
> * compilation time

Will the subroutine know how it was called? (ie: Through method
dispatch or through straightforward symbol table lookup. I'm really
hoping the answer to this is 'yes'.) Or will methods and subroutines
be distinct now?

-- 
Piers Cawley
www.iterative-software.com

Re: An overview of the Parrot interpreter

[Simon Cozens]

On Mon, Sep 03, 2001 at 09:53:11PM -0400, Dan Sugalski wrote:
> Might as well just promote the things to PMCs and pass in a list of them.

I anticipate that, especially for Perl, in a lot of cases we'll be dealing
with PMCs more often than the "scalar" data types.

Simon

Re: An overview of the Parrot interpreter

[Simon Cozens]

On Mon, Sep 03, 2001 at 08:19:32PM -0400, Sam Tregar wrote:
> I'm still not sure I understand why Parrot is doing string ops at all.  Do
> all our target languages have identical semantics for string operations?

Nope. But that's OK, because they won't have identical vtables.

(The string vtable functions will be very VERY low level, so the extent
that you can argue that the semantics are shared between all languages
BUT are different between encodings. An example would be "I have n characters,
how many bytes should I allocate?".)

Everything language-specific gets done in vtables, and you can plug in
Perl or Python vtables depending on whether you're executing Perl or Python.

Re: An overview of the Parrot interpreter

[Simon Cozens]

On Mon, Sep 03, 2001 at 04:05:26PM -0700, Brent Dax wrote:
> In other words, when you have sub foo {} in your code, it will be
> assigned an opcode number in the 'private' section.  The global section
> is for things that are built-in to Parrot, while the private section is
> for stuff you write.  (Right?)

That's a better explanation than I managed, thanks.

> Perl *scalars* are PMCs.  Those PMCs may hold strings within them.
> However, string manipulation is done in special string registers, which
> are *not* PMCs.

That's also a better explanation than I managed, thanks.

Re: An overview of the Parrot interpreter

[Simon Cozens]

On Mon, Sep 03, 2001 at 06:33:19PM -0400, Ken Fox wrote:
> Thanks for the info. If you guys maintain this level of documentation
> as the code develops, Perl 6 will be easy for first-timers to work on.

That's exactly the idea. :)

> > To be more specific about the software CPU, it will contain a large
> > number of registers.
> 
> The register frames store values, not pointers to values? 

Values. Except in the case of PMC's, of course, where there will be a
pointer into the heap.

> This seems to limit the implementation possibilities a lot. Won't a
> TIL use direct goto's instead of returning the next op address?

No. There'll be goto ops as well.

> I'd like to see a description of *just* the opcode stream and have a
> second section describe the protocol for implementing the ops.

Wait for opcodes.pod, which should be with you by the end of the week.
I have thought of this.

> Won't we have separate implementations of the opcode interpreter
> that are optimized for certain machines? (I'd at least like to see
> that possibility!)

Yes.

> Damian's proposals for multi-methods have got me thinking there
> should be one very fast implementation of multi-method dispatching
> used at the opcode level.

Method despatch opcodes are a can of worms. Don't go there.

Simon

Re: An overview of the Parrot interpreter

[Ariel Scolnicov]

Dan Sugalski <[EMAIL PROTECTED]> writes:

[... stuff I probably don't understand but at least I don't know WHY ...]

> * Integer, String, and Number registers 0-x are used to pass
> * parameters when the compiler calls routines.
> 
> 
> * PMC registers 0-x are used to pass parameters *if* the sub has a
> * prototype. If the sub does *not* have a prototype, a list is created
> * and passed in PMC register 0.
> 
> 
> * Subs may have variable number, or unknown number, of PMC
> * parameters. (Basically Parrot variables) They may *not* take a
> * variable or unknown number of integer, string, or number parameters.
> 
> 
> * Subs may not change prototypes
> 
> * Sub prototypes must be known at compile time. (I.e. by the end of
> * the primary compilation phase, and before mainline run
> * time. Basically the equivalent to the end of BEGIN or beginning of
> * CHECK phase)

OK, this bit I think I *know* exactly how I don't understand.


What happens when I call a prototyped sub with a code ref?


In other words, say I have 

sub intfoo($x : int, $y : Foo) { ... }

or whatever the syntax should have been.


Then the compiler writes foo so that it gets a parameter in Int
register 0 and a (Foo) parameter in PMC register 0, right?


Now suppose I say (you smelled it coming a mile away, I know)

my $myFoo : Foo;
my $rf = &intfoo;
$rf.(2,$myFoo)

(I hope Conway isn't reading this, I'm just suffering from Exegesis
Collapse and Extreme Apocalypse syntax syndromes).


There's no way the compiler can reliably work out $rf is pointing to a
prototyped code ref (not if I try hard enough), so it compiles code to
pass $rf parameters in a list in PMC register 0.  Oops.


Ways out:

1. "Ariel, you didn't understand anything..."

2. The $rf gets assigned some weird trampoline that does the
   translation from a list in PMC register 0 to Int register 0 and a
   Foo in PMC register 0.

3. intfoo has another entry point that does #2, and $rf points to
   that.

[...]

-- 
Ariel Scolnicov|"GCAAGAATTGAACTGTAG"| [EMAIL PROTECTED]
Compugen Ltd.  |   +++ THIS SPACE TO LET +++\ We recycle all our Hz
72 Pinhas Rosen St.|Tel: +972-3-7658117 (Main office)`-
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555http://3w.compugen.co.il/~ariels

Re: An overview of the Parrot interpreter

[Uri Guttman]

> "ST" == Sam Tregar <[EMAIL PROTECTED]> writes:

  >> * Integer, String, and Number registers 0-x are used to pass parameters
  >> when the compiler calls routines.

  ST> s/compiler/interpreter/, right?

nope. he means when the compiler generates op codes. the compiler will
generate code to put the op code params in registers (this is done with
other op codes). then the interpreter will get an op code and fetch the
registers and actually call the op code function via the vtable.

it is tricky to keep track of what the compiler does and generates and
then what the interpreter sees and does.

  >> * Subs may have variable number, or unknown number, of PMC parameters.
  >> (Basically Parrot variables) They may *not* take a variable or unknown
  >> number of integer, string, or number parameters.

  ST> I don't understand this restriction.  Won't it make implementing
  ST> variadic functions more difficult?

nope. that would be handled by multiple dispatch. it will compare the
subprototypes and call the best/right sub. someone else said that we
could do it just as easily for regular subs as for methods.

for variable list of args, then either all the args are in one list
which is passed (by ref) in register 0. or if the sub has a prototype
with the last arg being an array (which will slurp all the rest of the
args) then that param will be an array ref and get the rest as a single
list. this is so all calls will have a known and fixed number of args at
the opcode level.

uri

-- 
Uri Guttman  -  [EMAIL PROTECTED]  --  http://www.sysarch.com
SYStems ARCHitecture and Stem Development -- http://www.stemsystems.com
Search or Offer Perl Jobs  --  http://jobs.perl.org

Re: An overview of the Parrot interpreter

[Uri Guttman]

> "BD" == Brent Dax <[EMAIL PROTECTED]> writes:

  BD> # s/rather than/as well as/;  # we've got a stack of register
  BD> # frames, right?

  BD> IIRC, that's mostly for when we run out of registers or we're changing
  BD> scopes or whatever.  For the most part, it's a register architecture.

as dan has said there will be multiple stacks but the architecture is
not stack based. :)

that means the opcodes doesn't operate directly with data on the/a
stack. the ops (other than stack related ones) only operate directly on
registers. but there will be a call stack, a register stack (for
register usage overflow), etc. and all the stacks will be segmented so
they can grow without limit, unlike typical thread stacks which have
preallocated limits.

an official list of the stacks is not done yet. dan mentioned a list of
them a couple of times but it is not in concrete (as nothing else is
either). i assume that the segmented stack management code would be
shared among all the stacks.

a nice side benefit of the segemnted stack design is that you don't have
to reclaim any old stacke frames. all you do is rest the stack pointer
to the previous frame (probably linked from the current frame) and let
the GC reclaim the memory later. since stacks are non-contiguous this
works out well.

uri

-- 
Uri Guttman  -  [EMAIL PROTECTED]  --  http://www.sysarch.com
SYStems ARCHitecture and Stem Development -- http://www.stemsystems.com
Search or Offer Perl Jobs  --  http://jobs.perl.org

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 09:41 PM 9/3/2001 -0400, Sam Tregar wrote:
>On Mon, 3 Sep 2001, Dan Sugalski wrote:
>
> > I'm not entirely sure how much this'll be used, but I really, *really* want
> > to be able to call any sub that qualifies as an op rather than as a sub.
>
>What would a sub have to do (be?) to qualify?

It'd have to have a single return value, and a fixed, known number of 
parameters, probably less than three, though I suppose there's no real 
reason not to allow any number that'd fit in the register file.

> > >I don't understand this restriction.  Won't it make implementing variadic
> > >functions more difficult?
> >
> > Varadic functions that take actual integers, floats, or strings, yes.
> > Varadic functions that take parrot variables (i.e. PMCs) no.
>
>Right, so why make the former hard?  Is there an upside to the
>restriction?

Sure. We already have an aggregate PMC data type--the list. (The four base 
PMC types are scalar, array, hash, and list. Lists can hold multiple lists, 
arrays, hashes, and scalars, while arrays and hashes can only hold scalars) 
We don't have anything similar for integer, string, or float registers, so 
we'd have to build some thing or other to do it. Might as well just promote 
the things to PMCs and pass in a list of them.

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter

[Sam Tregar]

On Mon, 3 Sep 2001, Dan Sugalski wrote:

> I'm not entirely sure how much this'll be used, but I really, *really* want
> to be able to call any sub that qualifies as an op rather than as a sub.

What would a sub have to do (be?) to qualify?

> >I don't understand this restriction.  Won't it make implementing variadic
> >functions more difficult?
>
> Varadic functions that take actual integers, floats, or strings, yes.
> Varadic functions that take parrot variables (i.e. PMCs) no.

Right, so why make the former hard?  Is there an upside to the
restriction?

-sam

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 09:26 PM 9/3/2001 -0400, Sam Tregar wrote:
>On Mon, 3 Sep 2001, Dan Sugalski wrote:
>
> > >avoid using a "call" opcode all over the place, right?
> >
> > No, more a "try and leave the bytecode sections read-only" hack.
> >
> > Imagine, if you will, building LWP and bytecode compiling it. It uses
> > private opcodes 1024-1160. Then you later build, say, MIME::Lite, which
> > uses opcodes 1024-1090.
>
>I was referring to the practice of having compilation units create private
>opcodes.  Am I wrong in thinking this is a new technique deserving of an
>excuse for existence?

Not as such, no. Larry's idea is that calling most subs should be pretty 
much the same as calling most ops, in which case there's no reason for them 
to be different. It also means that we can yank out great chunks of what 
perl currently considers ops (socket functions are the big example) into 
loadable modules (read: extensions) that can be loaded and used as needed.

It also means that, if sub calls still end up being more expensive than op 
calls, that modules which add new ops are possible. Load 'em in and they 
patch the parser and add their op functions to the op table.

I'm not entirely sure how much this'll be used, but I really, *really* want 
to be able to call any sub that qualifies as an op rather than as a sub.

> > * Integer, String, and Number registers 0-x are used to pass parameters
> > when the compiler calls routines.
>
>s/compiler/interpreter/, right?

Yup. Thinko there.

> > * Subs may have variable number, or unknown number, of PMC parameters.
> > (Basically Parrot variables) They may *not* take a variable or unknown
> > number of integer, string, or number parameters.
>
>I don't understand this restriction.  Won't it make implementing variadic
>functions more difficult?

Varadic functions that take actual integers, floats, or strings, yes. 
Varadic functions that take parrot variables (i.e. PMCs) no. That's what 
many perl functions'll be doing anyway. Those are unprototyped and just get 
a list passed as their first (and only) parameter in PMC register 0.

> > Don't consider this list final until I've had a chance to run it past
> > Larry. He might be thinking of allowing prototypes to change, or spring
> > into existance relatively late in the game. (In which case we probably get
> > a call_in_list and call_in_registers form of sub call)
>
>Or those other language designers you're wooing, right?  The prototype
>stuff sounds pretty Perl specific.

The prototype stuff's actually non-perl-specific in a lot of ways, 
'specially considering how lax perl tends to be about calling conventions 
and such. Most languages define a fixed set of named parameters rather than 
a varadic list. (Which they tend to handle badly--like, say, C, whose 
vararg handling sucks dead badgers through 12" metal conduit)

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter

[Sam Tregar]

On Mon, 3 Sep 2001, Dan Sugalski wrote:

> >avoid using a "call" opcode all over the place, right?
>
> No, more a "try and leave the bytecode sections read-only" hack.
>
> Imagine, if you will, building LWP and bytecode compiling it. It uses
> private opcodes 1024-1160. Then you later build, say, MIME::Lite, which
> uses opcodes 1024-1090.

I was referring to the practice of having compilation units create private
opcodes.  Am I wrong in thinking this is a new technique deserving of an
excuse for existence?

> Up until now, I didn't know, so consider yourself the first to find out. :)

I'm honored...

> * Integer, String, and Number registers 0-x are used to pass parameters
> when the compiler calls routines.

s/compiler/interpreter/, right?

> * Subs may have variable number, or unknown number, of PMC parameters.
> (Basically Parrot variables) They may *not* take a variable or unknown
> number of integer, string, or number parameters.

I don't understand this restriction.  Won't it make implementing variadic
functions more difficult?

> Don't consider this list final until I've had a chance to run it past
> Larry. He might be thinking of allowing prototypes to change, or spring
> into existance relatively late in the game. (In which case we probably get
> a call_in_list and call_in_registers form of sub call)

Or those other language designers you're wooing, right?  The prototype
stuff sounds pretty Perl specific.

-sam

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 08:19 PM 9/3/2001 -0400, Sam Tregar wrote:
>On Mon, 3 Sep 2001, Dan Sugalski wrote:
>
> > Basically chunks of perl code can define opcodes on the fly--they might be
> > perl subs that meet the proper critera, or opcode functions defined by C
> > code with magic stuck in the parser, or wacky optimizer extensions or
> > whatever. There won't be a single global table of these, since we can
> > potentially be loading in precompiled code. (Modules, say) Each
> > "compilation unit" has its own table of opcode number->function maps.
> >
> > If you want to think of it C-ishly, each object module would have its own
> > opcode table.
>
>Ok, I think I understand.  This is some kind of code-compression hack to
>avoid using a "call" opcode all over the place, right?

No, more a "try and leave the bytecode sections read-only" hack.

Imagine, if you will, building LWP and bytecode compiling it. It uses 
private opcodes 1024-1160. Then you later build, say, MIME::Lite, which 
uses opcodes 1024-1090. (Since they know nothing of one another there's no 
reason they should coordinate their opcode # usage, and whatever case 
someone might make for coordinating I can shoot too-large holes in, alas) 
If there's only one table, you collide. Or you renumber the opcodes, which 
means the module bytecode can't be read-only. Both are icky.

>Speaking of soubroutines, what is Parrot's calling conventions?  Obviously
>we're no long in PUSH/POP land...

Up until now, I didn't know, so consider yourself the first to find out. :)

* Integer, String, and Number registers 0-x are used to pass parameters 
when the compiler calls routines.

* PMC registers 0-x are used to pass parameters *if* the sub has a 
prototype. If the sub does *not* have a prototype, a list is created and 
passed in PMC register 0.

* Subs may have variable number, or unknown number, of PMC parameters. 
(Basically Parrot variables) They may *not* take a variable or unknown 
number of integer, string, or number parameters.

* Subs may not change prototypes

* Sub prototypes must be known at compile time. (I.e. by the end of the 
primary compilation phase, and before mainline run time. Basically the 
equivalent to the end of BEGIN or beginning of CHECK phase)

* Methods get their parameters passed in as a list in PMC register 0, 
unless we can unambiguously figure out their prototype at compilation time

* The callee is responsible for saving any registers he/she/it messes with

* If the return is a list, it goes into PMC register 0. If the return is 
prototyped it uses the same rules as for calling.

Don't consider this list final until I've had a chance to run it past 
Larry. He might be thinking of allowing prototypes to change, or spring 
into existance relatively late in the game. (In which case we probably get 
a call_in_list and call_in_registers form of sub call)

> > >Or not!  Are Perl strings PMCs or not?  Why does Parrot want to handle
> > >Unicode?  Shouldn't that go in a specific language's string PMC vtables?
> >
> > Strings are a step below PMCs.
>
>I feel like I almost understand this.  So when you call the length()
>vtable method on a PMC representing a Perl scalar, the length op is
>eventually going to call another length() op, this time on an underlying
>Parrot string.  Right?

Right. Not an op, really, just the length function in the string's table of 
functions.

>I'm still not sure I understand why Parrot is doing string ops at all.  Do
>all our target languages have identical semantics for string operations?
>When you bring Unicode into the mix I start to wonder.

All our target languages don't have identical semantics, hence the 
abstraction. Generally speaking there are a few things that can be 
abstracted (comparison and casing, say), and a lot where the details of the 
string data is mostly irrelevant (regex matching is pretty much string 
neutral--a character is a character, and all it needs is the info on how 
big each character is).

We aren't going to have a perfect interface. That much I'm positive of. 
(This is engineering--there is no perfection. You weigh the costs and 
tradeoffs, and get the mix that works as best you can for your target 
problem) We will have a reasonably OK one, though, and one that'll deal 
with string data as well as, or better than, what we have now.

I could rant about the fun inherent in string encoding, character sets, and 
language issues for a while if you like. :)

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

Re: An overview of the Parrot interpreter

[Sam Tregar]

On Mon, 3 Sep 2001, Dan Sugalski wrote:

> Basically chunks of perl code can define opcodes on the fly--they might be
> perl subs that meet the proper critera, or opcode functions defined by C
> code with magic stuck in the parser, or wacky optimizer extensions or
> whatever. There won't be a single global table of these, since we can
> potentially be loading in precompiled code. (Modules, say) Each
> "compilation unit" has its own table of opcode number->function maps.
>
> If you want to think of it C-ishly, each object module would have its own
> opcode table.

Ok, I think I understand.  This is some kind of code-compression hack to
avoid using a "call" opcode all over the place, right?

Speaking of soubroutines, what is Parrot's calling conventions?  Obviously
we're no long in PUSH/POP land...

> >Or not!  Are Perl strings PMCs or not?  Why does Parrot want to handle
> >Unicode?  Shouldn't that go in a specific language's string PMC vtables?
>
> Strings are a step below PMCs.

I feel like I almost understand this.  So when you call the length()
vtable method on a PMC representing a Perl scalar, the length op is
eventually going to call another length() op, this time on an underlying
Parrot string.  Right?

I'm still not sure I understand why Parrot is doing string ops at all.  Do
all our target languages have identical semantics for string operations?
When you bring Unicode into the mix I start to wonder.

-sam

Re: An overview of the Parrot interpreter

[Bryan C . Warnock]

On Monday 03 September 2001 08:06 pm, Sam Tregar wrote:
> I think I understand this.  What I don't understand is how this relates to
> the next section about Parrot's special relationship with strings.  If
> Parrot has a "string" type and string handling functions, why use a PMC
> to implement a string?  What does it mean to have a PMC that "implements a
> string" and also have a "string type" in Parrot?

An opcode may call a vtable method on a PMC that is string manipulation 
intensive.  That vtable code could then use the string registers for 
efficiency.

-- 
Bryan C. Warnock
[EMAIL PROTECTED]

Re: An overview of the Parrot interpreter

[Sam Tregar]

On Mon, 3 Sep 2001, Nathan Torkington wrote:

> > Ok, so one example of a PMC is a Perl string...
>
> If you grok vtables, think of a PMC as the thing a vtable hangs off.
>
> Another way to think of it is that a PMC is an object.  To the outside
> (the interpreter that is manipulating data values) its contents are
> opaque.  All you can do is call methods (vtable entries) on it.
>
> So if you have an object/PMC that implements a string, the "length"
> method/vtable-entry will return the length of the string.  An
> object/PMC that implements an array, the "length" method/vtable-entry
> will return the number of things in the array.

I think I understand this.  What I don't understand is how this relates to
the next section about Parrot's special relationship with strings.  If
Parrot has a "string" type and string handling functions, why use a PMC
to implement a string?  What does it mean to have a PMC that "implements a
string" and also have a "string type" in Parrot?

-sam

Re: An overview of the Parrot interpreter

[Nathan Torkington]

Sam Tregar writes:
> > If our PMC is a string and has a vtable which implements Perl-like
> > string operations, this will return the length of the string. If, on the
> > other hand, the PMC is an array, we might get back the number of
> > elements in the array. (If that's what we want it to do.)
> 
> Ok, so one example of a PMC is a Perl string...

If you grok vtables, think of a PMC as the thing a vtable hangs off.

Another way to think of it is that a PMC is an object.  To the outside
(the interpreter that is manipulating data values) its contents are
opaque.  All you can do is call methods (vtable entries) on it.

So if you have an object/PMC that implements a string, the "length"
method/vtable-entry will return the length of the string.  An
object/PMC that implements an array, the "length" method/vtable-entry
will return the number of things in the array.

Nat

Re: An overview of the Parrot interpreter

[Dan Sugalski]

At 06:37 PM 9/3/2001 -0400, Sam Tregar wrote:
>On Sun, 2 Sep 2001, Simon Cozens wrote:
>
> > For instance, the Parrot VM will have a register architecture, rather
> > than a stack architecture.
>
>s/rather than/as well as/;  # we've got a stack of register frames, right?

Well, register in the sense that most cpus are register machines. They've 
still got stacks, but...

> > There will be global and private opcode tables; that is to say, an area
> > of the bytecode can define a set of custom operations that it will use.
> > These areas will roughly map to compilation units of the original
> > source; each precompiled module will have its own opcode table.
>
>Side note: this isn't making sense to me.  I'm looking forward to further
>explanation!

Basically chunks of perl code can define opcodes on the fly--they might be 
perl subs that meet the proper critera, or opcode functions defined by C 
code with magic stuck in the parser, or wacky optimizer extensions or 
whatever. There won't be a single global table of these, since we can 
potentially be loading in precompiled code. (Modules, say) Each 
"compilation unit" has its own table of opcode number->function maps.

If you want to think of it C-ishly, each object module would have its own 
opcode table.

> > If our PMC is a string and has a vtable which implements Perl-like
> > string operations, this will return the length of the string. If, on the
> > other hand, the PMC is an array, we might get back the number of
> > elements in the array. (If that's what we want it to do.)
>
>Ok, so one example of a PMC is a Perl string...

Nope. Perl scalar. Strings are lower-level, and a little different.

> > Parrot provides a programmer-friendly view of strings. The Parrot string
> > handling subsection handles all the work of memory allocation,
> > expansion, and so on behind the scenes. It also deals with some of the
> > encoding headaches that can plague Unicode-aware languages.
>
>Or not!  Are Perl strings PMCs or not?  Why does Parrot want to handle
>Unicode?  Shouldn't that go in a specific language's string PMC vtables?

Strings are a step below PMCs. And Parrot knows about Unicode because it's 
the least sucky common denominator.

We're not forcing unicode everywhere on purpose. Tried that with perl 5, 
worked OK, but it has some expense, and forces some rude cultural issues.

Most of the non-US world has their own private data encoding methods they 
like just fine. Big5 Traditional, Big5 Simplified, Shift-JIS, EBCDIC, and 
any of a half-zillion variants of ASCII (all with a different set of 
characters in the high 128 slots) work fine for people. If we abstract 
things out a bit so that perl doesn't have to care much, we win in places 
we don't know. This code:

   while (<>) {
 s/$foo/$bar/;
print;
   }

is cheap on an ASCII machine, but imagine how expensive it'll be if ARGV 
has shift-JIS data sources. We need to transform to Unicode then back 
again, and risk mangling the data in the process. Bleah.

"Everything Unicode" more or less says to the non-Unicode world (i.e. 
everyone except maybe Western Europe and North America) "Boy you suck, but 
I guess we'll make some token accommodations for you."

You can imagine how well that one will go over...

Dan

--"it's like this"---
Dan Sugalski  even samurai
[EMAIL PROTECTED] have teddy bears and even
  teddy bears get drunk

RE: An overview of the Parrot interpreter

[Brent Dax]

Note: this is my understanding of the situation; I could be wrong.

Sam Tregar:
# On Sun, 2 Sep 2001, Simon Cozens wrote:
#
# > For instance, the Parrot VM will have a register
# architecture, rather
# > than a stack architecture.
#
# s/rather than/as well as/;  # we've got a stack of register
# frames, right?

IIRC, that's mostly for when we run out of registers or we're changing
scopes or whatever.  For the most part, it's a register architecture.

# > There will be global and private opcode tables; that is to
# say, an area
# > of the bytecode can define a set of custom operations that
# it will use.
# > These areas will roughly map to compilation units of the original
# > source; each precompiled module will have its own opcode table.
#
# Side note: this isn't making sense to me.  I'm looking
# forward to further
# explanation!

In other words, when you have sub foo {} in your code, it will be
assigned an opcode number in the 'private' section.  The global section
is for things that are built-in to Parrot, while the private section is
for stuff you write.  (Right?)

# > If our PMC is a string and has a vtable which implements Perl-like
# > string operations, this will return the length of the
# string. If, on the
# > other hand, the PMC is an array, we might get back the number of
# > elements in the array. (If that's what we want it to do.)
#
# Ok, so one example of a PMC is a Perl string...

>From what I've seen, PMCs will represent SVs, AVs, and HVs at the opcode
level.  (When you get down to C, it's really SVs and AVs and HVs, but in
bytecode it's all PMCs.)

# > Parrot provides a programmer-friendly view of strings. The
# Parrot string
# > handling subsection handles all the work of memory allocation,
# > expansion, and so on behind the scenes. It also deals with
# some of the
# > encoding headaches that can plague Unicode-aware languages.
#
# Or not!  Are Perl strings PMCs or not?  Why does Parrot want to handle
# Unicode?  Shouldn't that go in a specific language's string
# PMC vtables?

Perl *scalars* are PMCs.  Those PMCs may hold strings within them.
However, string manipulation is done in special string registers, which
are *not* PMCs.

--Brent Dax
[EMAIL PROTECTED]

"...and if the answers are inadequate, the pumpqueen will be overthrown
in a bloody coup by programmers flinging dead Java programs over the
walls with a trebuchet."

Re: An overview of the Parrot interpreter

[Sam Tregar]

On Sun, 2 Sep 2001, Simon Cozens wrote:

> For instance, the Parrot VM will have a register architecture, rather
> than a stack architecture.

s/rather than/as well as/;  # we've got a stack of register frames, right?

> There will be global and private opcode tables; that is to say, an area
> of the bytecode can define a set of custom operations that it will use.
> These areas will roughly map to compilation units of the original
> source; each precompiled module will have its own opcode table.

Side note: this isn't making sense to me.  I'm looking forward to further
explanation!

> If our PMC is a string and has a vtable which implements Perl-like
> string operations, this will return the length of the string. If, on the
> other hand, the PMC is an array, we might get back the number of
> elements in the array. (If that's what we want it to do.)

Ok, so one example of a PMC is a Perl string...

> Parrot provides a programmer-friendly view of strings. The Parrot string
> handling subsection handles all the work of memory allocation,
> expansion, and so on behind the scenes. It also deals with some of the
> encoding headaches that can plague Unicode-aware languages.

Or not!  Are Perl strings PMCs or not?  Why does Parrot want to handle
Unicode?  Shouldn't that go in a specific language's string PMC vtables?

-sam

Re: An overview of the Parrot interpreter

[Uri Guttman]

> "KF" == Ken Fox <[EMAIL PROTECTED]> writes:

  KF> Simon Cozens wrote:
  >> To be more specific about the software CPU, it will contain a large
  >> number of registers.

  KF> The register frames store values, not pointers to values? If
  KF> there's another level of indirection with registers, I'm not sure
  KF> what the advantage is over just pointing into the heap. Also, heap
  KF> based activation records might be faster and more compact than
  KF> register files.

the registers are the way to make op code args be simple and small
integers which is portable and clean. with a direct heap, you need
pointers or large integers and complex code generation.

the point of registers is to make the op code tree simple to generate
and to use all the older compiler tricks for register machines. there
are no classic heap based compilers to steal from.

  >> As in Perl, Parrot ops will return the pointer to the next operation in
  >> the bytecode stream. Although ops will have a predetermined number and
  >> size of arguments, it's cheaper to have the individual ops skip over
  >> their arguments returning the next operation, rather than looking up in
  >> a table the number of bytes to skip over for a given opcode.

  KF> This seems to limit the implementation possibilities a lot. Won't a
  KF> TIL use direct goto's instead of returning the next op address?

TIL is a different beast. the code layer directly called by the op code
dispatch will be gone in TIL. how goto's and stuff will be handled is
not clear yet. and TIL is not an issue with the register machine, it is
a different back end effectively. it will use the real op functions to
do most of its work along with in line real machine code to call them.

  KF> I'd like to see a description of *just* the opcode stream and have
  KF> a second section describe the protocol for implementing the ops.
  KF> Won't we have separate implementations of the opcode interpreter
  KF> that are optimized for certain machines? (I'd at least like to see
  KF> that possibility!)

there will be support for custom op code dispatch loops. in particular a
event loop version will be made without checking the event flag between
each op. instead it will do that check when event callbacks return. it
should be somewhat faster and more tuned for event style design.

uri

-- 
Uri Guttman  -  [EMAIL PROTECTED]  --  http://www.sysarch.com
SYStems ARCHitecture and Stem Development -- http://www.stemsystems.com
Search or Offer Perl Jobs  --  http://jobs.perl.org

Re: An overview of the Parrot interpreter

[Ken Fox]

Thanks for the info. If you guys maintain this level of documentation
as the code develops, Perl 6 will be easy for first-timers to work on.
One goal down, N-1 to go... ;)

Simon Cozens wrote:
> To be more specific about the software CPU, it will contain a large
> number of registers.

The register frames store values, not pointers to values? If
there's another level of indirection with registers, I'm not sure
what the advantage is over just pointing into the heap. Also, heap
based activation records might be faster and more compact than
register files.

> As in Perl, Parrot ops will return the pointer to the next operation in
> the bytecode stream. Although ops will have a predetermined number and
> size of arguments, it's cheaper to have the individual ops skip over
> their arguments returning the next operation, rather than looking up in
> a table the number of bytes to skip over for a given opcode.

This seems to limit the implementation possibilities a lot. Won't a
TIL use direct goto's instead of returning the next op address?

I'd like to see a description of *just* the opcode stream and have a
second section describe the protocol for implementing the ops.
Won't we have separate implementations of the opcode interpreter
that are optimized for certain machines? (I'd at least like to see
that possibility!)

> =head1 Vtables
> 
> The way we achieve this abstraction is to assign to each PMC a set of
> function pointers that determine how it ought to behave when asked to do

Damian's proposals for multi-methods have got me thinking there
should be one very fast implementation of multi-method dispatching
used at the opcode level. It might help solve some of our math and
string problems dealing with mixed operand types.

- Ken

Re: An overview of the Parrot interpreter

[Ken Fox]

Dan Sugalski wrote:
> For those of you worrying that parrot will be *just* low-level ops,
> don't. There will be medium and high level ops in the set as well.

I was going to cite ,
but you guys have already read that, eh? ;)

One thing I was expecting was "bytecode subroutines are given opcodes."
Will there be a difference? Can we replace "built-in" opcodes with Perl
subs?

- Ken

Re: An overview of the Parrot interpreter

[Dave Mitchell]

Simon Cozens <[EMAIL PROTECTED]> wrote:
> Firstly, a magic number is presented to identify the bytecode file as
> Parrot code.

Hopefully this is followed by a header that has a version number and
lots of useful stuff like flags and offsets and things, just like wot
real object files have :-)

> Next comes the fixup segment, which contains pointers to
> global variable storage and other memory locations required by the main
> opcode segment. On disk, the actual pointers will be zeroed out, and
> the bytecode loader will replace them by the memory addresses allocated
> by the running instance of the interpreter.

Er, are we really having a section of the file full of zeros? Surely
we just need a "BSS size" field in the header that tells the loader how
many bytes to mmap("/dev/zero")?
 
> Similarly, the next segment defines all string and PMC constants used in
> the code. The loader will reconstruct these constants, fixing references
> to the constants in the opcode segment with the addresses of the newly
> reconstructed data.

Will the constants in the file be stored as serialised PMCs or as raw values?

Re: An overview of the Parrot interpreter

[Dan Sugalski]

On Sun, 2 Sep 2001, Simon Cozens wrote:

> For instance, the Parrot VM will have a register architecture, rather
> than a stack architecture. It will also have extremely low-level
> operations, more similar to Java's than the medium-level ops of Perl and
> Python and the like.

For those of you worrying that parrot will be *just* low-level ops,
don't. There will be medium and high level ops in the set as well. (call
method, start thread, and start dead-object detection, for example) We'll
compile down to what we need to do things fastest.

Dan

An overview of the Parrot interpreter

[Simon Cozens]

Here's the first of a bunch of things I'm writing which should give you
practical information to get you up to speed on what we're going to be doing
with Parrot so we can get you coding away. :) Think of them as having a
Apocalypse->Exegesis relationship to the PDDs. 

I haven't yet finished writing the other documents this refers to yet, but
I'll do those as soon as I can.

As usual, this is a draft, this is not sacred or inviolate. If this raises
more questions than it answers, ask them, and I'll put the answers in the
next release.

---

=head1 An overview of the Parrot intepreter

This document is an introduction to the structure of and the concepts 
used by the Parrot shared bytecode compiler/interpreter system. We will
primarily concern ourselves with the interpreter, since this is the
target platform for which all compiler frontends should compile their
code.

=head1 The Software CPU

Like all interpreter systems of its kind, the Parrot interpreter is
a virtual machine; this is another way of saying that it is a software
CPU. However, unlike other VMs, the Parrot interpreter is designed to
more closely mirror hardware CPUs.

For instance, the Parrot VM will have a register architecture, rather
than a stack architecture. It will also have extremely low-level
operations, more similar to Java's than the medium-level ops of Perl and
Python and the like.

The reasoning for this decision is primarily that by resembling the
underlying hardware to some extent, it's possible to compile down Parrot
bytecode to efficient native machine language. It also allows us to make
use of the literature available on optimizing compilation for hardware
CPUs, rather than the relatively slight volume of information on
optimizing for macro-op based stack machines.

To be more specific about the software CPU, it will contain a large
number of registers. The current design provides for four groups of 32
registers; each group will hold a different data type: integers,
floating-point numbers, strings, and PMCs. (Parrot Magic Cookies,
detailed below.)

Registers will be stored in register frames, which can be pushed and
popped onto the register stack. For instance, a subroutine or a block
might need its own register frame.

=head1 The Operations

The Parrot interpreter has a large number of very low level
instructions, and it is expected that high-level languages will compile
down to a medium-level language before outputting pure Parrot machine
code.

Operations will be represented by several bytes of Parrot machine code;
the first C will specify the operation number, and the remaining
arguments will be operator-specific. Operations will usually be targeted
at a specific data type and register type; so, for instance, the
C takes two Cs as arguments, and decrements contents of the
integer register designated by the first C by the value in the
second C. Naturally, operations which act on C registers will
use Cs for constants; however, since the first argument is almost
always a register B rather than actual data, even operations on
string and PMC registers will take an C as the first argument. 

As in Perl, Parrot ops will return the pointer to the next operation in
the bytecode stream. Although ops will have a predetermined number and
size of arguments, it's cheaper to have the individual ops skip over
their arguments returning the next operation, rather than looking up in
a table the number of bytes to skip over for a given opcode. 

There will be global and private opcode tables; that is to say, an area
of the bytecode can define a set of custom operations that it will use.
These areas will roughly map to compilation units of the original
source; each precompiled module will have its own opcode table.

For a closer look at Parrot ops, see L.

=head1 PMCs

PMCs are roughly equivalent to the C, C and C (and more
complex types) defined in Perl 5, and almost exactly equivalent to
C types in Python. They are a completely abstracted data
type; they may be string, integer, code or anything else. As we will see
shortly, they can be expected to behave in certain ways when instructed
to perform certain operations - such as incrementing by one, converting
their value to an integer, and so on.

The fact of their abstraction allows us to treat PMCs as, roughly
speaking, a standard API for dealing with data. If we're executing Perl
code, we can manufacture PMCs that behave like Perl scalars, and the
operations we perform on them will do Perlish things; if we execute
Python code, we can manufacture PMCs with Python operations, and the
same underlying bytecode will now perform Pythonic activities.

=head1 Vtables

The way we achieve this abstraction is to assign to each PMC a set of
function pointers that determine how it ought to behave when asked to do
various things. In a sense, you can regard a PMC as an object in an
abstract virtual class; the PMC needs a set of metho