Blog Closed

This blog has moved to Github. This page will not be updated and is not open for comments. Please go to the new site for updated content.
Showing posts with label Lorito. Show all posts
Showing posts with label Lorito. Show all posts

Saturday, July 10, 2010

Lorito: A Design

Cotto has been putting together a really great checklist for Lorito, the new microcoding approach that the Parrot developers are hoping to implement soon. The first step on the checklist, creating a proper compiler for our ops code DSL is already complete. Today at #parrotsketch Allison also mentioned some things about Lorito, and how we should start focusing more effort on it. I, for one, am very happy about that.

In this post I'm going to play architect and spell out a vision for Lorito. At the very least, this will be a good play-excercise. I don't expect everybody to like all the things I say here, but I do expect this post to generate some thought and discussion.

On the ground floor, Lorito needs to be able to do what C code does now. Actually, it really needs to be able to do much of what the underlying hardware machine does now. C is just a useful abstraction over the hardware, one that people are familiar with. What we don't want to be doing is creating our own ABI, or creating new low-level calling conventions or anything like that. Those kinds of problems are already resolved and if we want to be able to tap into the myriad of existing libraries we will want to stay compatible with existing conventions.

We want Lorito to interact with raw integers and pointers, including pointer dereferences and pointer arithmetic. This is important so that we can easily work with C-level arrays and pointers. I can't think of a modern architecture where pointers and integers are different sizes and are treated differently, but I can't say I'm familiar with every architecture in current use. I don't foresee any huge problems with creating an opset that works transparently with integers and pointers.  We also want Lorito to be able to call C-level functions, including indirect calls through a function pointer. There's no hard requirement yet stated that Lorito needs to be binary compatible with compiled C code, but I think we can all agree that such would be a major benefit. In fact, if we had a utility that could compile Lorito directly into C code, that would be the best intermediate step we could take. As I will discuss next, such a tool would make the conversion of Parrot to using Lorito easier in the long run. We probably don't want Lorito-to-C conversion to be a permanent part of our build, but it does get us moving now.

The PASM ops are currently written in C. If Lorito does everything that C can do, eventually they could all be rewritten in Lorito instead. That raises the interesting idea that groups of Lorito ops can be composed into more complex higher-level ops. PASM then becomes little more than a set of predefined convenience compositions, though it certainly does not represent the complete set of possible compositions. Dynops would just be custom predefined Lorito compositions and, since they wouldn't be defined in machine-code libraries, their definitions could be included directly in bytecode for later use.

In fact, while we are moving down this though path, we get to the idea that we could identify repeated patterns of Lorito ops at compile time, and define custom compositions on the fly. This allows us to compress packfiles for size without really adding all the overhead of general-purpose compression algorithms. When optimizing code, if we can apply an optimization to any composed op, even those identified on the fly, those optimizations can be immediately used anywhere the composition op is. This allows us to prune branches out of the parse tree when optimizing quickly.

Any language for which a compiler exists to convert it to Lorito can be considered an "overlay" language for Lorito. We can then use any overlay language any place where we can use Lorito. For instance, if NQP is converted to output Lorito (and composition ops) directly, we can then use NQP to define all the PASM ops, all the core PMCs, and several parts of Parrot's core. That would be quite the turnaround from how NQP is used currently.

Conversely, almost any C code can be rewritten in Lorito, so long as we have a step in the build to preprocess Lorito back into valid C code. In fact, I see no reason why we cannot interleave code written in both languages, in a manner analogous to how the Q:PIR construct allows PIR code to be written in NQP source. If we had a preprocessor that scanned code files and converted Lorito ops into equivalent C code line-by-line, we could start slowly rewriting much of Parrot, if not all of it, in Lorito. Then, once we have converted all the code over that we need, we could change the build process to convert those code files to bytecode instead of machine code, and run large parts of Parrot's code through the runcore.

Alternatively, instead of writing core code in Lorito directly, we could write core code in any Lorito overlay language. NQP comes to mind here.

The huge benefit to be had is that if user programs are written in a Lorito overlay, and Parrot itself is written primarily in Lorito or an overlay, our eventual JIT can record traces across the API boundary, and optimize hot sections of the Parrot core on the fly at runtime.

Here ends the part of the blog post concerned with overarching architecture discussions. Let's get down to the nitty-gritty details.

Lorito is going to want some basic arithmetic operations: addition, subtraction, multiplication and division on integers (pointers) and floating point numbers. We're also going to want modulus, address-of (C &) and pointer dereference (C unary *) for integer/pointer types, int-to-float and float-to-int cast operations. Logical operations are probably essential as well: and, or, xor, not. Logical inversion (C unary !) would probably be necessary as well. Assuming we can find a way to share ops for int/pointer and float operands (which I doubt we can do in an elegant way), that's still about 20 ops we're going to want to even perform basic manipulations on numbers. I can't imagine any modern, robust, mature virtual machine which doesn't perform these operations readily.

On top of basic mathematical operations, we're going to need some important operations for calling subroutines: Passing and retrieving arguments, calling subroutines, returning with values. I don't know how low-level Lorito intends to get, but let's face the reality of the world: Hardware machines are stack-based. Every library function we want to call is probably going to be passing arguments on the system stack. If we want to be defiant and call these ops "pass_arg" and "retrieve_arg" to hide the fact that Parrot is using the system stack, that's fine by me. The "stacks are evil" mantra, while occasionally misguided, is definitely firmly ingrained in Parrot culture.

In a minimalist world, the only ops we would really need are ops to call functions with passed arguments. We could implement every other op as a huge library of functions to call. Of course this would be extremely sub-optimal, but it does open a new possible avenue: Any operation which is sufficiently uncommon could be turned into a function call instead of having a dedicated op. We could encapsulate the call in a composite op. There are lots of options here, we have to weigh the desire to have a smaller op set against the need to have ready access to a huge myriad of low-level operations.

Having ops to do basic ops is necessary but not sufficient. I don't think we can sit back on our laurels and be happy with an op set that only does a subset of what C can do. That's worthless. Parrot needs to provide access to it's PMC and STRING types, and also to its interpreter. We want ops to load registers with values from the constants table in the bytecode file. We want to treat PMCs and STRINGs as opaque pointers at the user-level. They aren't like other pointers which can be manipulated, they are GCable objects that Parrot treats specially. We don't, for instance, want to be passing a PMC pointer willy-nilly to an arithmetic operation. We also don't want such a mistake to imply a call to one of the addition VTABLEs.

That said, we want to be able to get the VTABLE structure from a PMC, introspect information about that, and be able to call the various VTABLE interface functions there without having to calculate pointer offsets. This might make a good use of composite ops, where we can still do the pointer derefs in Lorito, but hide the nonsense behind some PASM-levle composite ops. We already have most of these ops already, but I think we're going to want to rework some of them. We definitely need to radically reduce the number of VTABLE interface functions, or else interacting with all of them from Lorito will be extremely ungainly.

So far as we are talking about a major redesign of the system, maybe it's time to start considering an idea chromatic has been talking about with making all vtables into methods so we can share a common lookup mechanism, common dispatch mechanism, common MMD behaviors, common inheritance behaviors, etc. That's not a bad idea, but we either need dramatic improvements to PCC performance, or we need to create a PCC fast-path for calls which are made without constructing a call object and without doing too many marshalling operations to get arguments where they need to be.

In fact, on a tangentially-related topic, I definitely think PCC should have a fast-path for functions which do not participate in MMD and which have fixed argument lists containing only positional args (no :optional, no :slurpy, no :named, no :call_sig, etc). This is, I think, an extremely common case and there are plenty of optimizations to be had here if we want them.

To round out the low-level opset, we need ops to move data between registers, between registers and memory, and maybe even ops to move data between memory locations directly, without moving them to a register first.


That's my conception for Lorito: probably 64 ops or less, a capability to add composite ops, treating PASM as a series of common composite ops, and the ability to write low-level code interchangably in C or Lorito. I think this plan for it provides a great development path without too many abrupt stops or course changes. We are quickly going to find ourselves in desperate need of a robust, modern JIT. We are going to be able to move to a proper precise GC since all the Lorito code will be using Parrot's registers to store working values, not relying on stack space which will need to be traced.

I am highly interested in hearing what other people have to say about Lorito, and what changes Parrot should be considering so long as we are writing this blank check for a massive refactor.

Thursday, March 18, 2010

Lean and Mean Parrot.

I got a comment from old-time Parrot contributor Melvin the other day in response to my criticisms of the PDD23 Exceptions system. He had a few things to say that really echo points that I've been trying to make in the past few months. I would like to reprint his comment here, in full (with some minor copyedits), and address it directly.

If IMCC needs to look into the op lib during lexical analysis, there is probably a design flaw. The opcode should probably only be checked during the parse / semantic check phase. If you want to tweak that much more performance out of IMCC you'd probably be better autogenerating the short op-list into imcc.l before calling lex so the token list is built directly into the scanner. As to your die vs. exit, I agree. This is where there is too much Perl influence in the VM. Things like 'die' semantics are better implemented in high level. Give the VM a simple opcode for termination, let all other things (printing messages, etc.) be implemented on top of the core op. I was arguing this in 2001/2002. If I had it my way, the core ops would be lean, and all the PMC grunge would have been implemented on top of those lean ops, not in the wacky .pmc/VTABLE mechanism that exists now. 99% of the Parrot lib would be written in a single, consistent HLL, and the JIT would be manageable. Right now, even as an original Parrot developer, I cannot wade in. Parrot requires a mix of Perl, PIR, C and custom build macros. PMCs are not Objects and Objects are not PMCs. There are still multiple cores for the fun of it. etc. etc. If Parrot is to ever really be done, seriously, someone needs to take a scalpel to about 50% of the "sacred" parts of the codebase and cut the amount of busy work and maintenance that has to be done, and remove some of the "multiple options" for accomplishing the same thing. Examples of projects that succeeded much faster than us are Mono. They built a canonical compiler (C#) and then proceeded in implementing the platform using the C# compiler. I was arguing that this would have been Cola at the time, and was my intent when I wrote PIR and the simple Cola compiler. But 8 years later, there is no JIT and Parrot is looking at using projects that started well after itself. I cringe when I look at all the hand-written .pir files in the distro. This was not the intent of PIR. Anyway, good luck. Don't take my comments the wrong way, hopefully they'll spark some debate. I'll check in in 2012. :)

I don't know how actively Melvin has been following IRC discussion, the mailing list, or this blog. I assume that he hasn't been following too closely, and we really can't expect a person to be following discussion for a project he's not really involved in actively. One of the big points we've been pushing for in recent months is Lorito, the lean set of low-level ops that we are going to use to rewrite large swaths of the codebase. In fact, seeing Melvin discuss this very idea is encouraging and validating: If other people come to the same conclusions that we come to internally, that means they are at least common ideas and maybe even good ones.

Lorito gives us the opportunity to move the abstraction layer down, and reduce context switches that occur by moving from one side of the line to the other. You don't have to look far in the PCC system, for instance, to see the machinations we have to go through to manage method calls from C. There are complicated structures of function pointers to access parameters from variadic argument lists. There are all sorts of complicated serialization paths to marshal arguments into the CallContext PMC, make the call, and then marshal the arguments back out of it again.

If we didn't have to worry about making calls from C, or if we at least didn't have to worry about making them regularly, we could avoid all this nonsense and delete several hundred lines of code, and the code we had left would be faster.

Another fact that comes up regularly is that the VTABLE interface is lousy. We've optimized for VTABLE access even though it's an extremely limited interface. There are simultaneously too many functions in the list, too few to support certain PMC types, and not nearly enough flexibility to support the kinds of interoperation mechanisms that we need. Ask this: How many mathematics-related VTABLEs exist? Now ask how many of them are even remotely useful outside the handful of numerical PMC types? Why does every single PMC type need to carry around pointers to all these functions that never get used? Why don't VTABLEs support proper MMD? Why don't all VTABLEs do any kind of MMD, even if it's wrong? Why do we have so much trouble inheriting VTABLEs between core PMC types and user-defined objects?

If we re-write the whole PMC system in Lorito, we can improve VTABLE dispatch semantics, maybe unify VTABLEs and METHODs, and expand the list of VTABLEs to hold any operations that we need. If we make the distinction that a VTABLE is like a method but only has a fixed number of positional arguments and can only be called from Lorito code, we could use a separate streamlined dispatch path that would be far faster than VTABLE overrides in PIR are now, only marginally slower than C-level VTABLES are, with the flexibility to plug into Parrot's MMD system for proper dispatch, and significantly more powerful and flexible than what we currently have. Plus, using hashes and named lookups, types could define a Sub of any arbitrary name to be a VTABLE, look up by any name we want to use with any arity we need for that operation, and we would only need one "VTABLE not found" handler to fall back to if a suitable one hasn't been found.

Runcores that don't build on every platform and are not well-tested by default should disappear. Sure, there is some benefit to having them as an academic exercise. Sure, it's cool to say we have an obscure and complicated dispatch mechanism with fun properties. But the reality is this: We're not using them. When we create a fakecutable binary for HLL projects like Rakudo, it generally hard-codes in the name of the runcore to use. So if our primary users can't select their own runcore, and if the primary way to use Parrot should be through HLLs (because I'll be damned if we want people in general to be writing PIR directly forever), then having multiple runcores is a huge waste.

Slow core? It does do bounds checking, but those bounds checks have never been seen to fail in my tenure as a Parrot coder. Drop it.

Computed-Goto and Predereferenced-Computed-Goto cores? Not all compilers even support these, and they require much more than their fair share of support code to operate at all.

Switch core? It's available everywhere and it's pretty speedy, but performance decreases pretty dramatically when used with dynops.

There has been some effort to make runcores pluggable using libraries, so a migration effort to move some of the uncommon ones out of core would be beneficial. I don't think we need them in core, but if other people would like to maintain them elsewhere, I won't complain about it at all.

Let's get one thing straight: including unused or rarely-used code in your program is not free. There are costs associated with having that code in memory. There are costs associated with the branches and decisions that choose to avoid it. There are costs associated in loading and dynamically linking exported symbols. There are costs associated with compiling all this code These things may not be super-expensive, but they are not free. And keeping code that has no practical benefit for developers or end users without a good reason to have it is not good practice.

Unnecessary opcodes need to disappear as well. We have well over 1300 opcodes now, probably closer to 1400 at this point. All of these add overhead in terms of memory footprint and lookup effort. It's a huge waste, and I suspect that if we did some actual profiling work we would find only about 200 of them were used with any regularity and about half would be almost completely unused except for one or two calls in obscure tests in the Parrot repo. If PGE and NQP don't use particular ops, and if there is no compelling need to keep them for particular HLLs, or if those HLLs can reasonably turn them into dynops, they should be removed.

Adding more ops is not a case of "it's a small added convenience with no downside". There are very real downsides.

Having too many core PMCs is a problem too. Parrot currently has 86 core PMC types by my count. I think we can drop this number to 60 without having to make any cuts that are too painful. If we wanted to be aggressive I think we could go even lower, but we do hit a point where we need to start weighing proportionally-smaller performance gains against the lost utility of removing PMC types that we're dependent on. In any case, I think we can definitely stand to move the following PMC types into dynpmc libraries or even delete them entirely: AddrRegistry, BigInt, BigNum, Boolean, Capture, CPointer, File, 9 of the array types, Key (to be replaced with an array type), Opcode, OpLib, OrderedHash, Pointer, Scalar, and Timer. This would bring us down to 63 PMC types, and several of these that I've listed are already either deprecated or are listed as experimental.

We as a community have definitely been moving in this direction. Allison especially has been helping to spread a "less is more" philosophy to the design of Parrot and I do appreciate that effort on her part. Making a switch over to Lorito, and then using Lorito to implement Ops, PMCs, and a few other core systems would be a major benefit. chromatic has been a major pusher for the Lorito effort as well, and having somebody of his stature behind the effort lends major credence to it. The effort to slim down the number of ops and PMCs doesn't have as much momentum but there is real evidence that we could be moving in that direction in the near future. I welcome all these changes and hope to see them come to fruition.

Tuesday, November 10, 2009

Planning for Lorito

I had an interesting conversation with plobsing this morning about Lorito. He has been wrapping up his work on the libjit-based framebuilder, and is looking to break ground on another project. Specifically, he wanted to start putting together a prototype for Lorito.

I had, along with chromatic and some other people, been thinking about Lorito as a very very low-level language, similar to an assembly language. The idea being that each Lorito op would share a close correspondence with an operation in the JIT engine, and would therefore be trivially easy to compile at runtime.

Plobsing was taking a different approach: He's thinking about a higher-level structured language that we would parse down into native JIT format at build time. There are some merits to this idea and since he mentioned it to me I've been thinking about it more and more. Let's take a look at things in more detail, focusing on LLVM specifically.

First, LLVM uses it's own platform-neutral LLVM bytecode format natively. High-level code is parsed and compiled down to LLVM bytecode which can then be optionally optimized before conversion to machine code. That first part ("parsed and compiled") is expensive: We don't want to be parsing and compiling to LLVM bytecode at runtime, that would eat up any potential gains we could get from JIT in the first place. What we want is for the Lorito code to be compiled only once: during the Parrot build. From there we will have LLVM .bc files which contain the raw bytecode definitions for each op, which can be combined together into large methods or traces and compiled to machine code in one go.

Ops are defined in .ops files, which are currently written in a preprocessed C-like language but which will eventually be rewritten in Lorito. During the build, we want two things to happen: First, we want to compile the Lorito down into machine code, as we currently do with our ops, for interpretted cores (fast core, switch core, etc). Second, we want to compile down the ops into LLVM bytecode for use with the JIT at runtime. By comparison:

Interpretted: Good startup time, Reasonable execution time
JIT'd: Slower startup time, better execution time. Many tradeoffs available between the two (usually in terms of adding/removing optimization stages)

For long running programs, costs necessary to startup the JIT engine can be amortized over the entire execution time, which produces benefits overall.

But, I'm digressing. The goal of Lorito was to produce a language that would be trivially easy to JIT at runtime. I was assuming that what we needed was a very small language to perform the job. However, what's really the most trivial to JIT is LLVM's native bytecode format. If we generate that bytecode at compile time, the runtime costs will stay to a minimum. This means that we can have Lorito be any language of any complexity: The only requirements are that we be able to compile it down to LLVM bytecode, hopefully in a process that isn't overly complex or fraught with error possibilities. So long as the conversion only happens once at build time, it doesn't really matter how complicated it is.

Any parser for anything that's more complicated than assembly language will take development effort. The tradeoff is reduced development effort when we start rewriting the ops in Lorito, and increased inclination to write more things in Lorito than just ops. For instance, rewriting PMCs and their VTABLEs in Lorito means that we can start exposing those to the JIT as well. The more of Parrot that we expose to the JIT, the more gains there are to be had from it.

Assuming Lorito is going to now be a relatively high-level structured language as plobsing suggests, the question now is what should it look like? Should it be C, or like C? Should it be NQP, or like NQP? NQNQP?

As a thought experiment, consider the case where Lorito is C. In that case, our ops and VTABLEs are already all written in Lorito, and we already have a Lorito compiler available (LLVM). In this case, there are only a handful of steps to do before Parrot has a working (if naive) JIT:
  1. Add a configure probe to detect LLVM
  2. During the build, compile down ops to LLVM Bytecode, in addition to everything else we already do with them
  3. Add a utility function to compile a stream of bytecode (such as an entire Sub) to machine code using the LLVM bytecode.
  4. Add a way (such as in the Sub invoke VTABLE) to cache methods that have already been compiled, and add a switching mechanism to invoke that instead of the bytecode
There are a few more necessary details, of course, but if we take this approach Parrot isn't too far away from a working, proof-of-concept JIT.

I'm sure this idea won't jive well with chromatic's "welcome to the new millenium" general distaste for C. I'm not 100% sure about it all myself. However, it is interesting and worthy of some consideration. It certainly does seem like a path of least resistance

Thursday, July 2, 2009

Writing PMCs in NQP

So the question has arisen lately, what is L1 going to look like, and how hard is it going to be to write ops and PMCs in it? The answer is that we aren't going to be writing in L1 directly, we have PCT and will be writing it in a higher level language and compiling it down directly to Parrot bytecode. Here is an example of what the FixedPMCArray PMC type will look like rewritten in NQP:

class FixedPMCArray :need_ext :provides('array') {
has $.size as int;
has @.pmc_array as pmc;

vtable elements() as int {
return $this.size;
}

vtable destroy() {
if $this.pmc_array != null
Parrot::mem_sys_free($this.pmc_array);
}

vtable get_integer() as int {
return $this.elements();
}

vtable get_bool() as bool {
return $this.elements() != 0;
}

vtable get_integer_keyed_int($idx as int) as int {
my $intval as int = +( $this.pmc_array[$idx] );
return $intval;
}

vtable set_integer_keyed_int($idx as int, $val as pmc) {
if $this.elements < $idx
$this.set_integer_native($idx);
$this.pmc_array[$idx] = $val;
}

vtable get_string_keyed_int($idx as int) as str {
my $strval as str = ~( $this.pmc_array[$idx] );
return $strval;
}

vtable mark() {
for(my $i = 0; $i < $this.size; $i++) {
my $pmc = $this.pmc_array[$i];
if !Parrot::PMC_IS_NULL($pmc)
Parrot::Parrot_gc_mark_PObj_alive($INTERP, $pmc);
}
}

vtable set_integer_native($size as int) {
if $this.size >= $size
return;

my $pmc_size = Parrot::sizeof_pmc_ptr();
my @new_pmc_array = Parrot::mem_sys_allocate($size * $pmc_size);
loop (my $i = 0; $i < $this.size; i++) {
@new_pmc_array[$i] = $this.pmc_array[$i];
}
$this.size = $size;
$this.pmc_array = new_pmc_array;
}
}


There are a few points to note here: First, I know this isn't perfect Perl 6 and I'm sure I screwed up some syntax here and there. I apologize for that, but I'm not really interested in going back line-by-line to fix it. This is just a thought experiment after all, and the important point isn't getting the syntax correct but instead proving the efficacy of this method. Second, I'm treating NQP here as just a particular syntax over very low-level semantics. The code has @.pmc_array as pmc is going to be equivalent to the C-ish code ATTR PMC** pmc_array. That is, we just assume that everywhere we see as pmc, that will become the equivalent C code PMC* and the @ sigil just adds another * to it.

One more thing worth noting is that I am assuming the management of the ATTR structure will be automated. The PMC compiler will recognize that this PMC type has attributes and will automatically allocate them on initialization and automatically deallocate them on destruction.

Since NQP is going to be compiled down into a very low-level bytecode that should be capably equivalent to C code, it is going to have direct access to C functions in libparrot. It will not be calling functions through NCI, it will be constructing machine-level call frames and executing functions directly. I show this using the syntax Parrot::FUNCNAME. The $INTERP contant is a reference to the current interpreter. This helps to differentiate functions which must be called with C semantics (pushing arguments onto the system stack) and those functions which can be called with L1 semantics instead (and I'm not entirely sure what those will look like anyway, but they won't be stack-based you can be sure of that). Instead of writing Parrot::, we could easily write C:: instead

So that's a quick look at what a basic core PMC could look like in NQP. If we all remember that in this particular case the NQP is going to be compiled down to low-level code and not into higher-level PIR/PASM, this all starts to make a lot more sense. Think of it like writing C but with slightly different syntax (and different underlying semantics), and without any of the high-level features that you would expect from Perl6.

Friday, June 26, 2009

L1: Let's Review FAQ

Buzz has been steadily increasing about this whole L1 idea, especially after some initial information about it was loaded onto the Parrot website. We had a big conversation last evening on #parrot, and I've received a few emails and blog comments about it as well. I would like to go through and try to address some of the common questions and concerns that I've been hearing.

Question 1: Why Is L1 Better Then PASM?

Another common rephrasing of the question would be "Why don't we just extend PASM to do what we want L1 to do?". I would turn the tables and ask "What is so good about PASM that we can't even conceive of a replacement?". Popular lore has it that Thomas Edison churned through 10,000 failed designs before he came up with the working lightbulb. We should not be so foolhardy as to think that we can't have made a fundamental mistake with PASM.

The problem with PASM is that it's the wrong level of abstraction. Frankly, it's too high level and is focused more on ease of use by the programmer then ease of execution by the VM. Don't believe me? I suggest you look at all the hundreds of files that are currently written in PIR: Main programs for HLLs, runtime libraries in HLLs, NCI wrappers for libraries, the entire test suite, etc. If PIR wasn't so great for people to be writing, it would long ago have been identified as a pain point and replaced with something better. Writing PIR is currently a required part of building an HLL compiler, and very few people are complaining about that, or complaining enough to have it changed! This in and of itself is proof that PIR (which is just PASM in disguise) is more suited for use by humans then by the machine.

And it's not like we don't have the tools or the skills necessary to write a replacement language compiler. In Parrot world you can't shake a stick without hitting somebody who has written one. If PIR was too low-level, we would have a compiler for a replacement language prototyped in less then 5 hours. Seriously.

L1 is better then PASM/PIR in this case because we can specially design it from the ground up with the purpose that it should be easy and fast for the machine to execute. We can take lots of steps to make it easy and fast to execute, a lot of steps that the designers of PASM didn't take because they didn't know. Back when Parrot was first being designed, how could the developers have know about the amazing performance of JavaScript engines such as SquirrelFish or TraceMonkey that have come out recently? The answer is that they couldn't have known what we know now about VM design.

We can focus on execution performance to the exclusion of human readability because people shouldn't be writing it directly. Let me repeat: we have the tools, the expertise, and the experience as a community to write a higher-level language compiler to do the hard work for us. Regardless of what intermediate language we end up with on Parrot, I don't expect humans will have to be manually writing any of it.

Question 2: Won't another layer make things slower?

Here's what we have right now:



People assume that I'm planning about just adding another compiler step and then another target interchange format for L1 at the end of this list. Not so. PCT has the potential (though it hasn't been implemented yet) to output code in any format. Why don't we do this instead:



And if you see that image and ask "Why do we need PIR/PASM in this case at all?", now you're thinking along the right lines. Imagine a world where we never ever need to write anything in PIR or PASM by hand again. Now imagine that same world where our tools like PCT don't output PIR as an intermediate form but, unbeknownst to you the programmer, directly outputs executable bytecode like L1. In such a world as we are imagining here, do we need to keep PIR or PASM around? Do they serve any purpose? Maybe as a very small bootstrapping layer to build PCT in the first place, in which case there is a lot of bloat that we could throw away, and we would only need a PIR compiler for the miniparrot build step and wouldn't need to build IMCC into libparrot or the Parrot executable.

It's not that we're adding a new layer of complexity, we're starting to realize that PASM is the wrong level of abstraction for our needs in Parrot, so we are replacing it wholesale with L1.

Now obviously there are intermediate steps betwen here and there where things are going to be slower and more complicated: We will need to use PIR as an intermediate step until PCT is capable of outputting L1 directly. But let me ask this: Do we want PCT to output something that executes slowly, or something that executes more quickly, when all the necessary work is done?

Question 3: L1 is going to be lower-level then programmers like

No question that PASM/PIR are far more friendly to the programmer then any conception of L1 is going to be. PIR and PASM are supposed to be sufficiently low-level that people don't want to program in them, but at the same time they aren't enough of a pain point that we made a replacement language into a priority. If L1 is such a pain point for programmers as I think it will be, we will write a compiler for a better language so we never need to write L1 directly.

We already have NQP which is a thin Perl6-like language that works well with Parrot's execution model. We also have Close in development which is going to be a C-like language that does almost the same thing. Assuming both these two languages have all the capabilities, why wouldn't we use these to do all our coding and never use PIR, PASM, or L1 again? Remember, I keep saying this: We have PCT, one of the most powerful compiler construction tools ever conceived. We should be using that to make languages that insulate us from whatever intermediate language Parrot uses. We should be reaching a point where we never ever ever have to write or even read another line of PIR or PASM ever again. Ever.

And when we do reach that point where we are so completely insulated from it, it won't matter to the programmer what intermediate language Parrot uses, because we won't be seeing it.

Question 4: A lot of development effort is going to be wasted

This is a good concern, that a lot of things people have spent a lot of effort to develop are basically going to become obsolete. But I have to also ask the question: "Why don't we all just write in Fortran, considering that so many people have spent so much energy on that compiler?". The effort isn't all wasted, we did learn a lot of important lessons about Parrot and the right way forward, and we've used all the things we've developed to bootstrap the creation of better tools and better ideas.

PIR and PASM got us to a place where we have PCT and several HLLs in active development. That doesn't mean we need to be trapped underneath these languages forever. We use them as a bootstrapping layer to build better tools, and use those instead.

Question 5: How does L1 compare to C?

Alternatively, why are we rewriting all our C code in L1? Let me ask what is the difference between C code and Assembly code? Everything you can do in assembly you can do in C. You will probably need to call a library to do some things, but if you can do it in ASM, you can do it in C. A compiler converts both down to the same machine code that is executed by the same hardware. You can say that one is "faster" then the other, because your average compiler isn't always smart enough to generate "good" machine code, but given the proper optimizations, there should be no speed difference. In other words, given the exact same machine code, it doesnt matter to the processor whether that code was written by a human in assembly and assembled to machine code, or written in C and compiled into machine code.

All that information out of the way, let's conceive of L1 as being a portable assembly language with all the same exact capabilities as C. Given the same exact capabilities and a good compiler (for our purposes, a JIT engine is just a "compiler"), both sets will be able to do the same stuff, and can be converted down into the same machine code for execution by the hardware at the same speed.

So given that the two are equivalent, why have L1 at all, and why not keep everything in C? The difference is semantics and algorithmic complexity. It's a difference of where the primary control flow happens. Right now we have a register-based system (PIR) running on top of a stack-based system (C). Switching between the two is slow, and unfortunately we switch pretty often because neither one supports all the semantics we need. L1 gives us an opportunity to access the low-level details that C has (calling native functions, accessing memory pointers, etc) but to use the high-level semantics that PIR requires (register-based operation, etc). We gain the ability to keep control flow executing in only a single context, and to eliminate all the algorthmic complexity of switching between semantic contexts.

An L1 dispatcher handles all control flow, able to call C functions directly as needed and redirect to offsets in bytecode. It can handle function calls, exception throwing, vtable overrides, and other CPS magic without having to recurse down the C system stack. And we gain all sorts of potential for optimizations because we have a unified environment like this.

In short, L1 allows us to design a language with the power and flexibility of C and the semantics of PIR, which in turn will let us reduce algorithmic complexity at the global level.

Question 6: Why not just fix PASM/PIR?

We can't really fix PASM in place because we have conflicting needs: We simultaneously need to extend it in order to match all the power of C, and shrink it to make it easier to analyze, optimize and JIT compile it. What we would end up doing is growing PASM to include what I now think of as being "L1", and then we would need to shrink away most of what we now think of as being "PASM", and we would be essentially left with only L1.

Keep in mind that this is not necessarily a bad development path for us to follow, but the end result is L1, not what we currently know as PASM. We can start by creating an op library for the new L1 ops, start transitioning everything over to use them, and then start deprecating away our old PIR ops (or rewriting them in terms of L1). What remains at the end of this is the small selection of L1 ops and various HLLs (I'm including PIR/PASM here as an HLL) which compile to L1, and L1 is executed directly by Parrot.

Question 7: What does L1 Buy Us?

L1 is going to give us a number of benefits:
  1. Decreased algorithmic complexity, because we're not having to shuffle data between the PIR registers and the C system stack
  2. Improved, easier, faster JIT. A "fixed" JIT
  3. Potential to plug more easily into existing JIT engines (LLVM and libJIT)
  4. Potential for trace-based JIT, where we trace out "hot spots" in the code and JIT them with type-specific information to speed up dispatch.
  5. Potential for high-level optimizations including subroutine inlining, dead code elimination, etc
  6. Potential for context threading, where we try to align the VM with the control flow of the underlying machine, to maximize branch prediction and caching at the hardware level
  7. Potential for improved GC and resource allocation performance because it will be easier to analyze where memory is allocated and where it falls out of scope. This includes "escape analysis", where we determine the lifespan of a reference and are able to deallocate it more quickly and efficiently.
  8. Potential for easier profiling, because everything will be in L1, we only need one tool to analyze L1 control flow (which we can share with the trace-based JIT and the GC escape analyzer)
It's quite an impressive list of possibilities, but I will stress that L1 doesn't get us these things for free: It does however give us the potential to do these things, a potential that we don't have right now with C/PIR.

Wednesday, June 24, 2009

YAPC: L1 Recap

On request, I have been asked to summarize some of the discussions we had about L1 at YAPC. We talked about L1 as a small group on Sunday during the PVMW unconference (Myself, cotto, particle plus two others), and again as a slightly larger group at Lulu's restaurant for Tuesday lunch (Myself, chromatic, pmichaud, particle, cotto, jhorwitz and three others). I will try, as well as I am able, to summarize what we discussed both times. I'm going to post most of this post also to the Parrot wiki so more then just my readers here will have access to it.

Microprocessor analogy

When you look at modern microprocessors, you see these complex instruction sets like x86. In traditional machine code, each bit in a machine code opcode travels down wires and acts as control signals to the actual circuit hardware. The problem with this is that the opcode structure becomes intimately tied to the architecture of the hardware: If you change one, you need to change the other (because different bits now need to travel down different wires to different circuits), and then things built on top break: Your assemblers now need to output new machine code, your pre-existing binary executables are no longer valid, etc.

In addition to this, some machine code words are very complex. x86 has hundreds of operations, and each operation can use a large number of addressing modes. Combine these together and you get hundreds, maybe millions of permutations. A single op, depending on the types of the sources and the destinations can have a number of distinct behaviors. add ax, bx is pretty far different from add [ax], bx, which is different from add ax, [bx], etc. Having to decide what behaviors to activate for each opcode from a large set of opcodes is hard to do.

Reasons for L1

Consider the idea now of converting those "high-level" machine code words into "low-level" microcode where each microcode operation is small, simple, atomic, and fast. Because each of these lower level instructions is more simple and atomic, they are easier to use in automated translation and with JIT.

Right now we have a lot of our critical code paths are written in C, and a lot of them are written in PIR. It's immensely expensive moving data between PIR registers and the C system stack to call functions in each language, and we are incurring that cost very frequently. In addition, we lose out on lots of opportunities because of the boundary between the two: We cannot easily optimize, we cannot easily inline functions, we cannot easily profile (we can typically profile C or profile PIR, not both at once), etc.

L1 is an abstraction that allows us to insert a new abstraction layer into Parrot to help reduce algorithmic complexity on the global level and give us more opportunities for optimization then we have in the PIR/C combination so far. Other projects like TraceMonkey are using cool optimization techniques such as polymorphic inline caching (which Parrot has a basic and messy implemenation of now, which has been deprecated), trace-based JIT, and context threading. These optimizations together are producing some stunning benchmark results for leading-edge javascript interpreters.

What L1 will look like

So the question invariably arises, what will L1 look like to the average programmer? Will it look like some grizzled assembly language? Will we be forced to reimplement large swaths of Parrot in some freaky home-brewed assembly? The answer, I think we are all pleased to consider now, is no. We have skills and background and tools for programming language design and we have several existing parsers for languages that we could utilize. One specific example of things that we could do, as mentioned by pmichaud, is to write core PMC types in NQP. It would have to have some extensions to allow direct register addressing, definition of vtables, and definition of attributes which may be references to arbitrary C data structures. Also, it would have to have a new backend which outputs L1 bytecode instead of PIR->PBC as PCT normally does now. We also have a new language in development by Austin Hastings called "Close", which is a very low-level language based on C that will eventually have all the capability of PIR (and therefore L1), but with familiar C-like syntax.

What this means is that there won't be a human-editable form of L1 bytecode, because we can write it in NQP, Close, or even other high-level languages which currently run on Parrot (although we will want to find one with a small runtime, or even a variant with no runtime). The short answer: L1 looks like any language we want it to look like (but probably Perl6-like in NQP or C-like in Close).

Next Steps

So what are the next steps? Well, pmichaud suggests that a good way forward is to actually start prototyping some key core PMC types in NQP now, so we can get a feel for what syntax and semantics we will actually want and need. Once we know what our needs are, we can start modifying NQP to support our new syntax for dealing with these things.

With the synatx requirements set, we can then modify the NQP parser to output normal C for now, and eventually redo the backend to output L1 instead.

chromatic suggests that with our current plug-in architecture we could create a library of L1 dynops, and create an NQP backend to target those. Once we have core PMCs as written in NQP executing only on L1 dynops, we can start the rest of the conversion process.

Here is a quick checklist:
  1. Write core PMC types in NQP, making careful note of what syntax we need to add to support all existing operations. Good candidates for this prototyping would be Integer, ResizablePMCArray, and Hash (which is soon to be renamed to AssociativePMCArray).
  2. Write existing PIR opcodes in NQP, making careful note of what syntax we need to add to support existing operations.
  3. Write a dynop lib for L1 ops
  4. Modify the NQP compiler to have all the necessary syntax from steps #1 and #2, and to output only those L1 opcodes created in step #3.
  5. Modify IMCC (or PIRC, depending on time frame) to output L1 or PBC, depending on some kind of switch
  6. Move L1 opcodes into the core instead of being a dynoplib.
  7. Make the final switch. All ops and PMCs get compiled from NQP into L1 during the normal build process (possibly using a bootstrapping step)
  8. Optimize like rabid ferrets.

Thursday, June 11, 2009

L1: The possibilities

I know a little bit about microprocessor design (it is what I focused on in gradschool), and the whole idea of L1 reminds me very much of a type of microcode. A microcode is, in this context, is a very small set of instructions, very close to the underlying hardware and blindingly fast. A processor like an Intel Pentium 4 doesn't execute the vast expansive x86 instruction set directly. In most cases, it has a translation module that converts x86 opcodes into a stream of RISC-like microcodes which are then executed by a small, super-fast microcore. In some cases the minicore that executes the microcodes even runs at a faster clock speed then the rest of the processor does, since it's operations are so simple and atomic to execute.

We talked about this issue a lot yesterday, and I forsee that we will do a lot more talking about it all in the future too.

chromatic envisions L1 as being a subset of PIR. That is, L1 opcodes are just regular PASM opcodes, but the subset of fundamental operations in which all other opcodes are defined. Only the L1 opcodes are written in C, and the rest, potentially, are written in terms of L1. I envision L1 as being a completely separate layer, and not being directly usable by the programmer. Specifically, I don't like mixing together opcodes that are written in C, and opcodes that are written in L1, and expecting Parrot to figure out the difference at runtime. I would like to see L1 that is written strictly in C, and PASM ops which are strictly written in L1. L1 not only is a small set of atomic operations, but they are very simple, easy to parse and decode, and extremely fast. I'm thinking about them being three-argument operations, which opens all sorts of doors for optimization.

Here's how I think execution would go using this kind of scheme:
  1. L1 ops are written in C and are all trivially simple: Individual operations or individual calls to internal functions, or something simple like that. They need to be trivially simple to write and trivially simple to JIT.
  2. PASM opcodes are written in terms of L1 instructions.
  3. At build time, PASM opcodes are "compiled" into a sequence of L1 byte code (L1BC) values in an array, instead of being "compiled" into standards-compliant C code and then compiled again into machine code.
  4. At execution time, user-defined L1 overlays are added so that existing ops and PMCs can be redefined or extended to add specific information if needed.
  5. At execution time, executing PIR code is converted into PBC, which in turn is used to index the sequences of L1 code that represents the ops. These sequences are strung together to form an execution stream of L1BC which is executed by the core (or JITted, or whatever).
If the mapping between PIR->L1 is simple and direct enough, the conversion process will be very speedy. pmichaud and chromatic suggested that we would have a full-fledged compiler for it, but I think something closer to a table-lookup assembler would be just fine, especially if we were using sequences three-argument ops. Of course, L1 code would only be human-readable at build time, once we compile it into L1BC it is essentially frozen that way forever and never needs to be human-readable (and therefore never compiled) again. So, it doesn't really matter how complicated the compilation process is, although I always tend towards simplicity.

Having all ops represented as frozen sequences of L1BC opens up a few options for us, some of which are very enticing indeed:
  1. A pseudo-JIT, where we convert PBC on the fly to a straight L1BC stream. This saves us from having to look up L1BC segments for each op repeatedly.
  2. We still store packfiles using PBC, because it's a more compact format (although we might consider a "super fast" frozen L1BC stream format too)
  3. Overridable and dynamically extensible ops. If you use a custom PASM op in your code (written in L1, of course), you can save that custom definition in your packfiles and then execute your custom ops on any Parrot. Currently, custom ops are written in C and form a dynamicly linked library which would need to be included with your program in order to execute properly. With L1, this mechanism all disappears. Also, you could override existing op definisions locally, by supplying a custom L1BC stream to use for it instead.
  4. Overridable and dynamically extendable PMCs. Same as above, but with PMC types instead of ops. PMC types can be defined at compile time and included in the packfile as a custom L1BC stream. No need to compile dynpmc dynamic libraries and shuffle them around, they can be included in the packfile directly.
  5. Serious optimization potential. If you're willing to spend a few cycles optimizing, a unified L1BC stream makes for quite an attractive optimization target. Right now we can't optimize much because execution is flowing between C and PIR and it's just impossible to make any predictions. As chromatic is quick to point out, we suddenly gain the ability to do escape analysis, code inlining, duplicate and unused code removal, and other optimizations that we can't do now. Plus, having more information about code execution will allow us to make a smarter garbage collector, register allocator, etc.
  6. Built-in PMCs and user-defined PMCs will have all their VTABLEs written in L1 instead of in C. the VTABLE structure contains pointers to L1 streams instead of C function pointers. Overriding a vtable method becomes transparent, and there is no functional difference at all between built-in and user-defined PMCs. Also, there is the potential that built-in PMC VTABLEs could be locally overridden and then restored later, or copied to another PMC type, or something else entirely. Lots of potential here.
  7. If PMCs and OPS are ultimately compiled into L1, there's no saying that they all have to be hand written in L1. They could be written in PIR, or NQP, or Perl6, or TCL. Imagine using Perl 6 to write parts of Parrot that run the Perl 6 compiler which itself is written in Perl 6? Bootstrapping indeed, and only the start of the potential uses!
So these are some of the enticing possibilities that arise from this method, and I think everybody will agree that some of these are very valuable indeed. As I mentioned before, I do have some differences of opinion from chromatic, and I do get the feeling that he's given more deep consideration to some points then I have, but that doesn't stop me from talking about it here. What are blogs for if not the easy dissemination of ill-informed opinions? If chromatic wanted to write a guest-post here to present his vision for what L1 is and how it works, I would be happy to have it. Or, if he posted a discussion of it on his own blog, I would definitely link it. I am definitely a congregant in the church of chromatic.

So, how do we get from here to there? This is the million dollar question, and without a solid roadmap we may never be able to implement such radical changes to Parrot. On this point, chromatic has already written a partial plan, although he mostly focuses on rewriting PMCs in something other then C. I'll adapt his basic timeline, but add a few of my specifics (which, as I've mentioned before, may be at odds with what chromatic thinks, and may actually be quite rediculous):
  1. Create a PCT-based compiler for PMCs and OPs that reads the current mismash of C-like code and emits ordinary C code, which is what our Perl5-based build system does already.
  2. Develop a compiler that converts L1 to equivalent C code.
  3. Replace the current Perl5-based build system with the PCT-based one
  4. Change the PCT-based compiler to emit L1, and use the L1 to create the C code of the PMCs and Ops
  5. Develop a runcore (nanoparrot) which executes L1 directly, including all the necessary control flow to interact ops with PMC vtables, etc.
  6. Remove the L1->C step, and have the L1 code generated by the PCT-based OP and PMC compiler(s) be executed by Parrot directly.
What's remarkable about all this is that we add a new layer to Parrot, but the end result will be less complexity and better performance overall. At least, that's the hope. I'm planning at least one more post about L1 to talk about what this beast may look like, although with other things on my plate and the release on tuesday, I don't know when I will be posting it.

L1: The Language of Parrot Internals

A while back I mentioned using a special-purpose small language to be used for implementing some of the Parrot internals, such as PMC VTABLEs, and OPS. Well, the idea is slowly taking shape and it's going by the name L1. I don't know the exact genesis of the name, so I can't point you to a link containing a "let's call this thing L1!" quote, but that's the name of it, and here's some discussion. By way of disclaimer, this all isn't anywhere on my personal pre-2.0 roadmap, but I do intend to offer my moral support where possible, and look very closely at this issue if it hasn't been resolved before 2.0.

cotto and bacek have been doing a lot of great work on a PCT-based PMC parser, and ultimately we hope that such a bootstrapping tool would help enable ubiquitous use of L1. I'll talk more about that later.

To understand why this is needed, and to put into context some of the things I am going to talk about in this post, let's look at a small example that comes directly from the libJIT documentation. Let's take a small function to multiply two numbers together and return a result:
int mul_add(int x, int y, int z)
{
return x * y + z;
}

If we want to compile this operation at runtime with libJIT, we would have to do this:

jit_context_t context;
context = jit_context_create();
jit_context_build_start(context);
jit_function_t function;
function = jit_function_create(context, signature);
jit_type_t params[3];
jit_type_t signature;
params[0] = jit_type_int;
params[1] = jit_type_int;
params[2] = jit_type_int;
signature = jit_type_create_signature
(jit_abi_cdecl, jit_type_int, params, 3, 1);
jit_value_t x, y, z;
x = jit_value_get_param(function, 0);
y = jit_value_get_param(function, 1);
z = jit_value_get_param(function, 2);
jit_value_t temp1, temp2;
temp1 = jit_insn_mul(function, x, y);
temp2 = jit_insn_add(function, temp1, z);
jit_insn_return(function, temp2);
jit_function_compile(function);
jit_context_build_end(context);

What this listing shows is not the function itself, but how to tell the computer to write the function itself at runtime. The computer will build and compile the function into executable code at runtime and then will be able to execute it. The benefit to JIT is that the compiled code pieces are reusable, so all the overhead of describing the function only needs to occur once and the resulting machine code can be executed over and over again. The mechanics of JIT aren't really important for this discussion, but what is important is to see that the two versions of the code are very different from each other, and if we're generating C code at runtime we potentially need to generate several different versions of each code snippet.

Currently, we do JIT by writing the opcode definitions in a C-like script in one place, and writing JIT versions of them in another place. And when one doesnt match the other, there's a problem. One thing that we absolutely need in Parrot, for our own sanity if nothing else, is the ability to specify operations using a common, simplified, non-C small language that can be converted into multiple forms and executed in multiple ways, as necessary. This, I think, is a good use for L1: An abstraction layer that enables us to write an almost behavioral description of a piece of code and have that used at build time to produce all the various pieces of C code and other code that we need.

chromatic has a slightly different conception of what L1 could be, although I don't think it's entirely incompatible from what I was talking about above. Instead of simply being a common front-end language that gets converted into other stuff for compilation and execution, chromatic suggests that it could be used in the virtual machine in the same way that microcodes are used in a hardware processor. A small, fast Parrot core (called "nanoparrot") would execute the L1 microcodes directly. There are some different ideas here about what the relationship will be between PIR/PASM and L1, but I will talk about those differences later. chromatic also hopes that a pure L1 execution environment would be self-contained and save us from the frequent switching between C and PIR calling conventions. Let's explore that idea a little bit more.

PIR code is executing and reaches a particular operation which internally calls PCCINVOKE on a PIR subroutine. This creates a new runloop to execute the new PIR function, which returns a value to PCCINVOKE, which in turn returns results back to PIR. All the while, marshaling data back and forth between two very different environments (C and PIR). Likewise, consider the case of PIR code executing and throwing an exception. Parrot searches for a handler (which itself may be PIR or C, which in turn calls a function in PIR or C again, ad infinitem), executes it, and possibly returns execution to where it was. We're jumping back and forth between C and PIR for control flow, creating runloops and shuffling data all too frequently. The situation, in short, is complex and unsustainable in the long run. Plus, there are serious performance problems associated with all this jumping between PIR and C.

Now consider the alternative of a pure L1 execution environment, where PASM opcodes are little more than named sequences of L1 opcodes. L1 code is executing, and throws an exception. A return continuation is created and passed to an L1-based hander, which returns control through the return continuation. No C code involved. Almost too good to be true. Almost. The case of calling into L1 code from C is a little bit more tricky but not impossible. Instead of passing a return continuation we pass a C-based return continuation which will probably consist of a cached image of the interpreter structure and a jump point or something. In any case we still save on performance because the arguments get passed in PIR registers and that's where they stay.

What I personally would like from L1 is a unified solution, something that meets these requirements:
  1. Has to be easy, trivially easy, to JIT.
  2. Has to be a small set of operations capable of implementing all other ops
  3. Should be suitable, at least in the long term, for implementing VTABLEs and METHODs in PMCs.
chromatic suggests that L1 should be a subset of PIR, but I'm not sure I agree with that. I am thinking right now (and I may change my mind as I think about this more) that it should be a separate assembly-level language entirely. There are a number of reasons for that, and I will discuss them later. I have plenty more to say about L1, and I'll do that in later posts.