MoarVM: A virtual machine for NQP and Rakudo

Over the course of the last year, we’ve been working to make both NQP and Rakudo more portable. This has primarily been done to enable the JVM porting work. While the JVM is an important platform to target, and initial work suggests it can give us a faster and more stable Rakudo, there are some use cases, or users, that the JVM will not cater to so well. Startup time will likely remain a little high for one-liners and quick scripts. Other potential users simply don’t want to use the JVM, for whatever reason. That’s fine: there’s more than one way to do it, and our strategy has been to enable that by adding support for the JVM without breaking support for Parrot. Additionally, pmurias will be working on a JavaScript backend for a GSoC project.

Today I’d like to introduce some work that, all being well, will lead to an additional “way to do it” arriving over the next several months. A small team, composed of myself, diakopter, japhb and masak, have been quietly working on taking the design of the 6model object system and building a runtime around it. Thus, we’ve created the “Metamodel On A Runtime” Virtual Machine, or the “MOAR VM”, which we’ve taken to writing as “MoarVM”.

This is not a release announcement. At present, MoarVM runs neither NQP nor Rakudo, though a cross-compiler exists that allows translating and passing much of the NQP test suite. We’re revealing it ahead of YAPC::NA, so it can be openly discussed by the Perl 6 team. The goal from the start has been to run NQP, then run Rakudo. The JVM porting work has established the set of steps that such an effort takes, namely:

  1. Build an NQP cross-compiler that targets the desired platform. Make it good enough to compile the MOP, built-ins and the classes at the heart of the regex/grammar engine. Make it pass most of the NQP test suite.
  2. Make the cross-compiler good enough to cross-compile NQP itself.
  3. Close the bootstrap loop, making NQP self host on the new platform.
  4. Do the Rakudo port.

At the moment, the JVM work is well into the final step. For MoarVM, we’ve reached the second step. That is to say, we already have a cross-compiler that compiles a substantial range of NQP language constructs into MoarVM bytecode, including the MOP, built-ins and regex-related classes. Around 51 of the NQP test files (out of a total of 62) pass. Work towards getting the rest of NQP to cross-compile is ongoing.

Since anybody who has read this far into the post probably has already got a whole bunch of questions, I’m going to write the rest of it in a question-and-answer style.

What are the main goals?

To create a VM backend for Rakudo Perl 6 that:

  • Is lightweight and focused on doing exactly what Rakudo needs, without any prior technical or domain debt to pay off.
  • Supports 6model and various other needs natively and, hopefully, efficiently.
  • Is a quick and easy build, with few dependencies. I was rather impressed with how quick LuaJIT can be built, and took that as an inspiration.
  • Enable the near-term exploration of JIT compilation in 6model (exploring this through invokedynamic on the JVM is already underway too).

What’s on the inside?

So far, MoarVM has:

  • An implementation of 6model. In fact, the VM uses 6model as its core object system. Even strings, arrays and hashes are really 6model objects (which in reality means we have representations for arrays and hashes, which can be re-used by high-level types). This is the first time 6model has been built up from scratch without re-using existing VM data structures.
  • Enough in place to support a sizable subset of the nqp:: op space. The tests from the NQP test suite that can be translated by the cross-compiler cover a relatively diverse range of features: the boring easy stuff (variables, conditionals, loops, subs), OO stuff (classes, methods, roles, mixins, and, naturally, meta-programming), multiple dispatch, most of grammars (including LTM), and various other bits.
  • Unicode strings, designed with future NFG support in mind. The VM includes the Unicode Character Database, meaning that character name and property lookups, case changing and so forth can be supported without any external dependencies. Encoding of strings takes place only at the point of I/O or when a Buf rather than a Str is requested; the rest of the time, strings are opaque (we’re working towards NFG and also ropes).
  • Precise, generational GC. The nursery is managed through semi-space copying, with objects that are seen a second time in the nursery being promoted to a second generation, which is broken up into sized heaps. Allocations in the nursery are thus “bump the pointer”, the copying dealing with the resulting fragmentation.
  • Bytecode assembly done from an AST, not from a textual format. MoarVM has no textual assembly language or intermediate language. Of course, there’s a way to dump bytecode to something human-readable for debugging, but nothing to go in the opposite direction. This saves us from producing text, only to parse it to produce bytecode.
  • IO and other platform stuff provided by the Apache Portable Runtime, big integer support provided by libtommath, and re-use of existing atomic ops and hash implementations. We will likely replace the APR with libuv in the future. The general principle is to re-use things that we’re unlikely to be able to recreate ourselves to the same level of quality or on an acceptable time scale, enabling us to focus on the core domain.

What does this mean for the Rakudo on JVM work?

Relatively little. Being on the JVM is an important goal in its own right. The JVM has a great number of things in its favor: it’s a mature, well-optimized, widely deployed technology, and in some organizations the platform of choice (“use what you like, so long as it runs on the JVM”). No matter how well Moar turns out, the JVM still has a couple of decades head start.

Additionally, a working NQP on JVM implementation and a fledgling Rakudo on JVM already exist. Work on making Rakudo run, then run fast, on the JVM will continue at the same kind of pace. After all, it’s already been taking place concurrently with building MoarVM. :-)

What does this mean for Rakudo on Parrot?

In the short term, until MoarVM runs Rakudo well, this shouldn’t really impact Rakudo on Parrot. Beyond that is a more interesting question. The JVM is widely deployed and battle-hardened, and so is interesting in its own right whatever else Rakudo runs on. That’s still not the case for Parrot. Provided MoarVM gets to a point where it runs Rakudo more efficiently and is at least as stable and feature complete, it’s fairly likely to end up as a more popular choice of backend. There are no plans to break support for Rakudo on Parrot.

Why do the initial work in private?

There were a bunch of reasons for doing so. First and foremost, because it was hard to gauge how long it would take to get anywhere interesting, if indeed it did. As such, it didn’t seem constructive to raise expectations or discourage work on other paths that may have led somewhere better, sooner. Secondly, this had to be done on a fairly limited time budget. I certainly didn’t have time for every bit of the design to be bikeshedded and rehashed 10 times, which is most certainly a risk when design is done in a very public way. Good designs often come from a single designer. For better or worse, MoarVM gets me.

Why not keep it private until point X?

The most immediate reason for making this work public now is because a large number of Perl 6 core developers will be at YAPC::NA, and I want us to be able to openly discuss MoarVM as part of the larger discussions and planning with regard to Perl 6, NQP and Rakudo. It’s not in any sense “ready” for use in the real world yet. The benefits of the work being publicly known just hit the point of outweighing the costs.

What’s the rough timeline?

My current aim is to have the MoarVM backend supported in NQP by the July or August release of NQP, with Rakudo support to come in the Rakudo compiler release in August or September. A “Star” distribution release, with modules and tools, would come after that. For now, the NQP cross-compiler lives in the MoarVM repository.

After we get Rakudo running and stabilized on MoarVM, the focus will move towards 6model-aware JIT compilation, improving the stability of the threads implementation (the parallel GC exists, but needs some love still), asynchronous IO and full NFG string/rope support.

We’ll have a bunch of the right people in the same room at YAPC::NA, so we’ll work on trying to get a more concrete roadmap together there.

Where is…

Posted in Uncategorized | 5 Comments

Rakudo on JVM progress update, and some questions answered

It’s time for another progress update on the ongoing JVM work. Last time I posted here, we’d reached the point of having a self-hosting NQP ready to merge into the master branch of the NQP repository. That has now happened, so the May release of NQP will come with support for running on the JVM (note, this does not mean the May release of Rakudo will come with this level of capability, and a JVM-based Star release with modules is further still!) . In this post, I will discuss some of the things that have happened in the last few weeks and also try to answer some of the questions left behind in the comments last time.

The Rakudo Port

With NQP pretty well ported (there are some loose ends to tie up, but it’s pretty capable), the currently ongoing step is porting Rakudo. At a high level, Rakudo breaks down into:

  • The core of the compiler itself: the grammar (for parsing), actions (which assign semantics to the things we parsed), world (which takes care of the declarative aspects of programs), optimizer (tries to cheat without getting caught) and a few other small pieces to support all of this. This is written in NQP.
  • The Perl 6 MOP (meta-object protocol) implementation, which defines what classes, roles, enums, subsets and so forth mean. This is also written in NQP.
  • The bootstrap, which uses the MOP to piece together various of the core Perl 6 types. It does Just Enough to let us start writing Perl 6 code to define the rest of the built-ins. Also written in NQP.
  • The core setting, which is where the built-in types, operators and methods live. This is written in Perl 6.
  • A chunk of per-VM code that does lower-level or performance-sensitive things.

The first 3 of these need…an NQP compiler. And, it turns out that we have one of those hosted on the JVM these days. But could it handle compiling the Perl 6 grammar? It turns out that, after some portability improvements to the various bits of Perl 6 compiler code, the answer was a resounding “yes”. In fact, the grammar was compiled down to JVM bytecode sufficiently accurately that I didn’t encounter a single parse failure on the entire CORE.setting (though there were lots of other kinds of failures that took a lot of work – more on that in a moment). As for the rest of the compiler code, there were bits of lingering Parrot-specific stuff throughout it, but with a little work they were abstracted away. By far the hardest was BOOTSTRAP, which actually runs a huge BEGIN block to do its setup work and then pokes the results into the EXPORT package. This is kinda neat, as it means the setup work is done once when building Rakudo and then serialized. Anyway, onto the next pieces.

Compiling the Perl 6 setting depends on the Perl 6 compiler working. Since the first thing the setting does is use the bootstrap, which in turn uses the MOP, it immediately brings all of the above three pieces together. While we talk about “compiling” the setting, there’s a little more to it than that. Thanks to various BEGIN time constructs – such as traits, constant declarations and, of course, BEGIN blocks – all of which show up in the CORE setting – we actually need to run chunks of the code during the compilation process. That’s right – we run bits of the file we’re in the middle of compiling while we’re compiling it. Of course, this will be nothing new to Perl folks – it’s just most Perl programmers probably don’t worry about how on earth you implement this. :-) Thankfully, it’s a solved problem in the NQP compiler toolchain, and the stuff that makes NQP BEGIN blocks work largely handles the Rakudo ones too.

Anyway, all of this means that even getting the setting to finish the parse/AST phase requires doing enough to run the various traits and so forth. And that in turn brings in the fifth piece: the per-VM runtime support. This includes signature binding, container handling and a few other bits. Thankfully, it no longer involves multiple dispatch, since that is written in NQP these days (apart from some caching infrastructure, which is shared with NQP’s multiple dispatch, and thus was already done). Getting through the parse/AST phase of the setting doesn’t need all of the runtime support to be implemented, but it did require a decent chunk of it. Of course, at the start everything is missing, so getting from line 1 to line 100 was O(week), from 100 to 1000 O(day) and each thousand or so from there O(hour). It’s 13,000 or so lines in all.

The parse/AST step is just the first (though biggest) phase of compiling Perl 6 code, however. Next comes the optimizer, followed by code generation. In theory, the optimizer could have been bypassed. I planned to do that, then discovered it basically worked for the set of optimizations that didn’t need signature binding to participate in the analysis, so I left it in. Code generation is part of the backend, and so is shared with NQP. So it shoulda just worked, right? Well, yes, apart from code generation is the place where nqp:: ops get resolved to lower level stuff. And Perl 6 uses a lot more of them than NQP. Note that they only have to be mapped to somewhere; the JVM is late bound enough that it won’t complain unless you actually hit the code path that tries to use something that is not yet implemented. In reality I did a bit of both: implementing those that would surely be hit soon or that were trivial, and leaving some others for later.

So, some time yesterday, I finally got to the point of having a CORE.setting.class. Yup, a JVM bytecode file containing the compiled output of near enough the entire Perl 6 core setting. So, are we done yet? Oh, no way…

Today’s task was trying to get the CORE setting to load. How hard could that be? Well, it turns out that it does a few tasks at startup, most of which hit upon something that wasn’t in place yet. Typically, it was more of the runtime support, though in some cases it was unimplemented nqp:: ops. Of course, there were a handful of bugs to hunt down in various places to.

Anyway, finally, this evening, I managed to get the CORE setting to load, at which point, at long last, I could say:

perl6 -e "say 'hello world, from the jvm'"
hello world, from the jvm

Don’t get too excited just yet. It turns out that many other simple programs will happily explode, due to hitting something missing in the runtime support. There’s still plenty of work to go yet (to give you an idea, trying to say a number explodes, and a for loop hits something not yet implemented), but this is an important milestone.

Interop

A couple of the comments in response to my last post asked about interop with Java. There’s two directions to consider here: using Java libraries from Perl 6, and using Perl 6 code from Java. Both should be possible, with some marshalling cost, which we’ll no doubt need to spend some time figuring out how to get cheap enough it’s not a problem. It may well be that invokedynamic is a big help here.

The Java stuff from Perl 6 direction can probably be made fairly convenient to use by virtue of the fact that Perl 6 has a nice, extensible MOP. The fact the object you’re making a call on lives in Java land can be just a detail; we can hide it behind the typical method call syntax, and should even be able to populate a 6model method cache with delegation methods that do the argument mapping. I’m sure there will be plenty of interesting options there. I suspect we’ll want to factor it a little like NativeCall – some lower level stuff in the runtime, and some higher level sugar.

Going the other way will be more “fun”. I mean, on the one hand the marshalling is just “in the other direction”, which we’d need to do for values coming back from Java land anyway. But trying to work out how to make it feel nice from Java land could be trickier. I don’t believe the “.” operator is very programmable, which probably leaves us with string lookups or code-generated proxy thingies. Or maybe somebody will come up with a Really Great Solution that I hadn’t thought of.

My JVM related Perl 6 dev focus for now will be getting Rakudo to work decently and start getting Perl 6 modules working on the JVM also, but interop with Java land is certainly on the roadmap of things I think should happen. As with all things, I’m delighted to be beaten to it, but will work on it if it goes undone for too long. :-)

Performance?

The first thing to say on this is that it’s too early to have a really good idea. The final pieces of the gather/take transform (which has global consequences) have yet to land, which will certainly have some negative impact and will need to happen soon. At the same time, I’ve been very much focused on making things work on the JVM at all over making them especially clever or optimal. Numerous things can be done in ways that will not only perform better in a naive sense, but that will also be much easier for the JVM’s JIT to do clever stuff with. There are many, many things we will be able to do in this area.

Since I only have a sort-of-working Perl 6 compiler, I can’t say that much about Perl 6 performance. The only result I have to share is that the CORE setting parse completes in around a third of time that it does on Parrot (noting it’s not only about parsing, but also some code generation and running of stuff). This is not especially great – of course, we need to do better than that – but it’s certainly nice that the starting point before I really dig into the performance work is already a good bit faster.

The other result I have is NQP related. nwc10++ has been doing performance testing with a Levenstein benchmark of each commit to the NQP JVM work, which is really great in so far as it gives me a rough idea if I accidentally regress (or improve ;-)) something performance wise. There, we saw a larger factor performance win, around 15 times faster than the same program running in NQP on Parrot.

The big negative news on performance is startup time. Part of this is just the nature of the JVM, but I know another enormous part of it is inefficiencies that I can do something about. I’ve plenty of ideas – but again, let’s make things work first.

From Here

Things will be a little quieter from me over the next week and a bit, due to a busy teaching schedule. But now we have a fledgling Rakudo on JVM, and from here it’s going to be making it gradually more capable, first passing the sanity tests, then moving on to the spectests and the ecosystem. There are ways to help for the adventurous. Some ideas:

  • Profile the code generation phase, which is one of the pieces that is slower than expected. Try to figure out why.
  • Have a look at how multiple dispatch stuff is currently set up, and see if the dispatch logic could possibly be shuffled off behind invokedynamic.
  • Try something. See how it explodes. See if you can fix it. (Yes, generic I know. :))
  • Have a look at a “make install” target for Rakudo on JVM.

I’ll be speaking on the JVM work at the Polish Perl Workshop the weekend after next, and hope to have something a bit more interesting than “hello world” to show off by then.

Posted in Uncategorized | 9 Comments

NQP on JVM bootstrapped, soon will land in NQP master

The work to get NQP running and bootstrapped on the JVM has reached an interesting milestone, and I thought I’d take a few moments from working on it to talk about what has taken place since my last post here, as well as taking a look at what will be coming next.

Getting NQP on JVM Bootstrapped

When I last posted here, I had reached the point of having an NQP cross-compiler to the JVM that covered quite a lot of NQP’s language features. Cross-compilation meant using NQP on Parrot to parse NQP source, build an AST, and then turn the AST into a kind of JVM assembly language. This in turn was then transformed into a JVM bytecode file by a small tool written in Java, which could then be executed on the JVM.

Since the last post, the cross-compiler became capable of cross-compiling NQP itself. This meant taking the NQP source files and using the cross-compiler to produce an NQP that would run on the JVM – without depending on Parrot. This also enabled support for eval-like scenarios. I reached this stage last month; the work involved tracking down a range of bugs, implementing some missing features, and doing a little more work to improve NQP’s portability. So, we had an NQP that ran on the JVM. Port done? Well, not quite.

A little vacation later, I dug into the next stage: making NQP on the JVM able to compile (and thus reproduce) itself. While I’d already implemented the deserialization used to persist meta-objects (representing classes, grammars and so forth), for this next step I had to implement the serialization side of things. Thankfully, there are a bunch of tests for this, so this was largely “just” a matter of working through making them pass. Finally, it was time to work through the last few problems, and get NQP on JVM able to build the NQP sources – and therefore able to compile new versions of itself. I decided to do this work as part of moving the JVM support into the main NQP repository.

Since we’ve only had NQP running on one backend (Parrot) up until now, certain aspects of the repository structure were not ideal. Before starting to bring in the JVM support, I first did a little bit of reorganization to segregate the VM specific components from the VM independent ones. Happily, much of NQP’s implementation falls into the latter category. Next came gradually building up the bootstrapping build process, working a file at a time, tracking down any issues that came up. This was a little tedious, especially given a couple of the problems were separate compilation leakages (where things from the running compiler would get confused with the version of the compiler that it was compiling). It was pretty clear that this was the problem from the errors I was seeing, but such problems show up long after things actually go wrong, requiring some careful analysis to hunt down. With those leaks plugged, and a few other relatively small bugs fixed, I had a working NQP on JVM…compiled by NQP on JVM.

The work from there has been to fill out the rest of the build process, adding in the second bootstrap stage and the test targets. The good news: the NQP produced by NQP on JVM passes all the tests that the original cross-compiled version did, so we’ve got no regressions there as a result of the bootstrap.

This work is currently sat in the jvm-support branch of the NQP repository. After the upcoming NQP release, it will be merged.

Supporting invokedynamic

Amongst all of this progress, we’ve also gained infrastructure to support using the invokedynamic instruction. This is a mechanism that enables those implementing non-Java languages on the JVM to teach its JIT about how their dispatch works. Most of the hard work here was done by donaldh++. I’d initially built things using BCEL in order to do code generation. While it served well up to a point, it turns out that ASM has much better support for invokedynamic, as well as being a little faster. So, donaldh got things switched over, and I soon was able to emit invokedynamic.

So far, we are not using it a great deal (just for making QAST::WVal compile to something a bit – or potentially a lot – cheaper), but in the future it will be used for things you’d typically think of as invocations (sub and method calls). I’ll write in more detail about it as things evolve.

What next?

With NQP now ported, the focus will fall on Rakudo itself. Quite a lot of preparations have already been made; for example, many pir:: ops have been replaced with nqp:: ones, multiple dispatch has been ported to NQP from C (fixing some bugs along the way), the way HLL boundaries work has been updated to cope with a fully-6model world (this also let me fix a long-standing introspection bug).

The path through getting Rakudo ported will largely follow the build order. This means starting with the module loader, then the compiler, followed by the MOP and its bootstrapping. After that comes the setting – the place where the built-ins live. There’s around 13,650 lines worth of that, so of course I expect to take it a little at a time. :-) I’ll try to remember to get a progress update here in a couple of weeks time.

Posted in Uncategorized | 6 Comments

NQP on JVM gets Grammars, Multiple Dispatch

Having just reached an interesting milestone, I thought I’d blog a quick progress update on my work to port NQP to the JVM, in preparation for also doing a port of Rakudo Perl 6.

The big news is that the grammar and regex engine is pretty much ported. This was a sizable and interesting task, and while a few loose ends need to be wrapped up I think it’s fair to say that the hard bits are done. The port includes support for the basics (literals, quantifiers, character classes, positional and named captures, calls to other rules, and so forth) as well as the more advanced features (transitive Longest Token Matching for both alternations and protoregexes, and embedded code blocks and assertions). Missing are anchors, conjunctions and a small number of built-in rules; none of these are particularly demanding or require primitives that don’t already exist, however. It’s also worth pointing out that the NQP code to calculate the NFAs used in Longest Token Matching also runs just fine atop of the JVM.

Another interesting feature that I ported a little while ago is multiple dispatch. This was some effort to port, since the original implementation had been done in C. While it’s sensible to have a close-to-the-VM dispatch cache, there’s little reason for the one-off candidate sorting work (not a hot path) to be done in C, so I ported the code for this to NQP. This meant that on the JVM side, I just needed to implement a few extra primitives, and could then run the exact same candidate sorting code.

I think it’s worth noting again that I’m really doing two things in parallel here: hunting down places where NQP couples too tightly to Parrot and loosening the coupling, and also doing the porting to the JVM. The first half of this work is relevant to all future ports. In many cases, I’m also finding that the changes give us architectural improvements or just cleaner, more maintainable code. I wanted to point this out especially because I’m seeing various comments popping up suggesting that Rakudo (or even Perl 6) is on a one-way road to the JVM, forsaking all other platforms. That’s not the case. The JVM has both strengths (mature, a solid threading story, widely deployed, the only allowed deployment platform in some development shops, increasing attention to supporting non-Java languages through things like invokedynamic) as well as weaknesses (slow startup time, lack of native co-routine support, and the fact that it was originally aimed at static languages). Rakudo most certainly should run on JVM – and it most certainly should run on other platforms too. And, as I wrote in my previous post, we’ve designed things so that we are able to do so. Perl has always been a language where There’s More Than One Way To Do It. Perl also has a history of running on a very wide range of platforms. Perl 6 should continue down this track – but the new reality is that a bunch of the interesting platforms are virtual, not hardware/OS ones.

By now, the JVM porting work is fast approaching a turning point. Up until now, it’s been about getting a cross-compiler and runtime support in place and working our way through the NQP test suite. This phase is largely over. The next phase is about getting NQP itself cross-compiled – that is, cross-compiling the compiler, so that we have an NQP compiler that runs on the JVM, supporting eval and able to run independently.

Posted in Uncategorized | 9 Comments

A look at the preparations behind the JVM port, and a progress update

After my last post giving a status update on the JVM porting of NQP and the compiler toolchain Rakudo builds upon, hercynium++ left a comment suggesting that I also blog about the design work behind this effort. I liked the idea, and in this post I’ll attempt to describe it a bit. I can’t possibly capture all of the interesting things in a single post, so if this doesn’t cover aspects that are particularly interesting to anybody reading, let me know and I’ll try and find time to write something on them. :-)

It started long ago…

The first commit to the repository where I’m doing the initial porting work to the JVM may have been back in November, but that isn’t where the journey really started. We’ve known for multiple years now that we would want Rakudo and NQP to target backends besides Parrot. In that time, we’ve had to build a lot of technology in order to be able to build Rakudo at all. Some things we’ve had to build more than once because the first time didn’t produce something satisfactory (where satisfactory means “actually meets our needs”, not “is the most awesome thing ever possible”). Software is, fairly often, as much about learning as it is about building. The more complex the domain you’re working in, there more this applies, and the more likely it is that you’ll have to build one to throw away. By now we’ve thrown away a parser engine, an AST, and about 3 implementations of roles. :-)

Of course, there’s the build/buy thing, where buy in open source really means “buy into”, as in use an existing library. We’ve done a bunch of that too, such as libtommath for our big integer support and dyncall for NativeCall support. But the closer something is to the “core domain” – the thing that makes your product distinctive and special – the less able you are to use something off the shelf. Parsing Perl 6 really needs to be done with a Perl 6 grammar, using Longest Token Matching. Its object system really needs something that supports meta-programming, representation polymorphism and gradual typing. Getting BEGIN/eval right and supporting compilation and having the possibility for lexical and anonymous types and packages, which can be dynamically constructed and exported, also left us with something to build (this is the work that led to bounded serialization).

Eventual portability has been a design factor in what we’ve built for quite a while. While the only 6model implementation to have become complete enough to support all of Rakudo’s object needs so far is the one running on Parrot, the initial prototypes of 6model were done on the .Net CLR. This was in no small part to make sure that there was a feasible way to implement it on such a VM. Granted, what I actually discovered was a less than awesome way to build it on the CLR (and what I’m doing on the JVM this time around fits in far better with the JVM’s world view). But it was a design consideration from the start.

When we updated PAST, the previous AST representation, to QAST (Q is just P++ :-)) then once again portability was a concern; the VM specific bits were all placed under a QAST::VM node type. This makes it easy to escape to the underlying VM where needed or where it is most expedient, but it’s both explicit and done in a way that allows specification of what to do on other backends. As part of this work we also build support for the nqp::op abstraction directly into the AST format. The nqp::ops form an opcode set independent of any particular VM. These get mapped as part of turning a QAST tree into code for the target backend (thus meaning there’s no overhead for them in the generated code). They may map directly to the VM’s opcodes, a function or method call in the VM, or do some more complex code generation.

The other important piece of the groundwork for portability is that we implemented Rakudo in a mixture of Perl 6 and NQP, and over time have got NQP to the point where it is also written in NQP (and thus can compile itself). This has been a gradual thing; the earliest NQP editions were written directly in PIR, and with time we’ve migrated those bits to NQP – usually at the same point we were doing other improvements already. For example, pmichaud++ wrote the latest edition of the regex engine, with LTM support, in NQP. PAST, written in PIR, was replaced by QAST, written in NQP. And 6model’s meta-objects were, from the start, expressed in NQP too. It’s pretty neat that NQP’s definition of things so fundamental as classes is actually written in NQP. It means that we don’t have to port classes and roles, just the primitives they are made out of.

So digging into the JVM port itself…

With all of the above mentioned things in place, it was possible to form a fairly concrete roadmap for porting NQP, then Rakudo, over to the JVM. Being comfortable that the result would enable us to get a fully functional Rakudo on the JVM and an idea of how to get there was important. It’s easy to implement a subset, but if it isn’t factored in a way that lets you do the rest afterwards then you’re in bother and it’ll be time for re-work. My hope was that, after some years of learning about things that don’t work and replacing them with things that do, this time much of the re-work could be avoided. A starting point for this was taking a good look at the JVM’s instruction set, as well as considering what JVMs are typically good at doing.

The JVM is a stack machine. This is in contrast to Parrot, which is a register machine. Thankfully, this is mostly a code generation detail rather than being especially deep. As well as the stack, a given method can have local variables (note that everything that contains code on the JVM is called a method, even subroutines, but they call them static methods because it sounds so much more OO :-)). These can hold longer-lived things, so in a sense could be used a bit like Parrot registers. In general, the code generation from QAST uses the stack where possible and falls back to locals where needed. This is because stack usage fits well with what a JVM expects to be doing, and also what its bytecode format expresses most compactly.

Locals have an important restriction: they can only be accessed directly in the scope where they are declared. There is no notion of nested methods at the JVM level. This means that locals are not suitable for implementing lexical variables. Thankfully, there is a well established solution: promote such things onto the heap, keeping them in some kind of invocation record. This is what happens with closures in C# on the CLR, for example. There are a bunch of ways to do this transform, with various trade-offs. I’ve done one that was fairly fast to implement, but also enables lookup by array indexing rather than needing a named (hash) lookup in the vast majority of cases. As well as an array index being algorithmically cheaper than a hash lookup, the JVM supports array indexing natively in its opcode set, but not hash lookups.

Talking of allocating things on the heap brings us nicely to think about objects. JVMs are very good at fast allocation and collection of objects, because they have to be; there is no stack allocation in Java of anything non-trivial. Of course, that doesn’t mean the VM can’t do escape analysis and stack allocate under the hood. That the VM is really good at object allocation and GC means we don’t need to worry too much about lexicals leading to invocation records on the heap; there’s plenty of performant uses of this approach in the wild. Furthermore, most records will be very short lived, nicely meeting the generational hypothesis (which is that most objects are either short lived or long lived, and so we can optimize separately for each through doing generational garbage collection).

While invocation records are relatively internal, of course NQP and Perl 6 involve lots of user-visible objects. From the things you think about as objects (and call “new” on) to things like scalar containers, strings, boxed integers and so forth, both NQP and Perl 6 lead to plenty of allocations. While some things are quite predictably shaped, most come from user class definitions. Ideally, we’d like it if a Perl 6 class definition like:

class Point {
    has $!surface;
    has num $!x;
    has num $!y;
}

Was to use memory similarly to if you wrote something in Java like:

class Point {
    private Object surface;
    private double x;
     private double y;
}

At the same time, we know that the JVM’s idea of type is some way off the Perl 6 notion of type, so we can’t simply turn Perl 6 classes into JVM classes. Thankfully, 6model has from the start been designed around the idea of representation polymorphism. Really, this is just a separation of concerns: we decouple the details of memory representation and access from the notion of being a type and dispatch. The former is handled by a representation, and the latter two by a meta-object. One early but important observation I made when designing 6model is that the representation will always couple closely to the underlying runtime (and thus would need to be implemented for each runtime we wanted to run on), whereas the other bits can be expressed in a higher level way, with the common cases made efficient by caching. Thus there’s no reason to re-implement classes and roles per VM, but there is a need to provide a different, VM-specific way to do P6opaque (the default representation for NQP and Perl 6 objects).

The C implementation of P6opaque on Parrot works by calculating a memory layout – essentially, figuring out a struct “on the fly”. What’s the JVM equivalent of that? Well, that’s just creating a JVM class on the fly and loading it. Is the JVM capable of doing that? Sure, it’s easily dynamic enough. Furthermore, once we’ve done that little bit of bytecode generation, it’s a perfectly ordinary JVM class. This means that the JIT compiler knows what to do with it. Does doing any of this require changes to the meta-objects for classes in NQP and Rakudo? No, because these details are all encapsulated in the representation. Things like these are good signs for a design; it tends to show that responsibilities are correctly identified and segregated.

So, how’s the cross-compiler going?

Things are going nicely. Having got much of the way there with the NQP MOP, I turned to ModuleLoader and started to get together a basic setting (the setting being the place where built-ins are defined). With those in place, work has moved on to trying to pass the NQP test suite.

The build process cross-compiles the MOP, module loader and setting. To run the test suite, each test is taken and cross-compiled against those, then the result of compiling it is run on the JVM. The fact we invoke NQP, then invoke the JVM twice in order to run each test gives quite a bit of fixed overhead per test; once we have NQP itself (that is, the compiler) cross-compiled and self-hosting on the JVM it’ll be down to a single invocation.

The NQP test suite for the NQP language itself consists of 65 test files. 3 of them are specific to Parrot, so there’s 62 that are interesting to make run. As of today, we pass 46 of those test files in full. While some of those passing tests exercise relatively simple things (literals, operators, variables, conditionals, loops, closures), others exercise more advanced features (classes, roles, basic MOP functionality, runtime mixins and so forth). Of the 16 test files that remain, 9 of them depend on regexes or grammars. Getting those to run will be the focus of the next major chunk of work: porting the regex compiler and getting the NFA, Cursor and Match classes to cross-compile (which will involve some portability improvements). The other 7 relate to non-trivial, but smaller-than-grammars features (for example, 2 are about multiple dispatch, which I’m working on porting at the moment).

It was only three weeks ago when I wrote that the JVM port did not even manage “hello world” yet, and that I had little more to show than something that could turn a range of QAST trees into JVM bytecode. Three weeks later and we’re running around 75% of the NQP test files, and timotimo++ was even able to feed an almost unmodified Levenstein distance implementation written in NQP to the cross-compiler and have it run on the JVM.

So, mad amounts of coding have taken place? Well, only sorta…I’ve taught two three-day classes for $dayjob in the last couple of weeks also. :-) Mostly, progress has been fast now because the foundations it is building upon have proved fairly solid. For the backend, this is in no small part down to having grown a test suite for the QAST to JVM phase of the work as it progressed. The fact we could happily couple this new backend to the existing NQP parser is thanks to the compiler being structured as a pipeline of stages, each one strongly isolated from the others, just passing a data structure between them. In my teaching work, I often encourage automated testing and talk a lot about the importance of enforcing carefully chosen, well-defined, information-centric boundaries between components. It’s pleasing to see these things paying off well in my Perl 6 work also. :-)

Posted in Uncategorized | 15 Comments

A quick JVM backend update

Things have been moving along quite rapidly on the JVM backend since my last post. Sadly, I’m too sick to hack on anything much this evening (hopefully, this turns out to be a very temporary affliction…) but I can at least just about write English, so I figured I’d provide a little update. :-)

Last time I blogged here, I was able to compile various QAST trees down to JVM bytecode and had a growing test suite for this. My hope was that, by some inductive handwaving, being able to compile a bunch of QAST nodes and operations correctly would mean that programs made up of a whole range of them would also compile correctly. In the last week or so, that has come to pass.

Having reached the point of having coverage of quite a lot of QAST, I decided to look into getting an NQP frontend plugged into my QAST to JVM backend. In the process, I found that NQP lacked the odd VM abstraction here and there in the common prelude that it includes with every QAST tree it produces. Thankfully, this was easily rectified. Even better, I got rid of a couple of old hacks that were no longer required. With those things out of the way, I found that this common prelude depended on a couple of operations that I’d not got around to implementing in the JVM backend. These were also simple to add. And…here endeth the integration story. Yup, that was it: I now had a fledgling NQP cross-compiler. An NQP compiler running on Parrot, but producing output for the JVM.

This result is rather exciting, because…

  • It’s using exactly the same parse and action stages as when we’re targeting Parrot. No hacks, no fork. The QAST tree we get from the NQP source code that goes in is exactly the one we get when targeting Parrot. Everything that happens differently happens is beyond that stage, in the backend. This is an extremely positive sign, architecturally.
  • With a couple of small additions to handle the prelude, I was immediately able to cross-compile simple NQP programs and run them on the JVM. There’s no setting or MOP yet, but the basics (variables, loops, subroutines with parameters, even closures) Just Worked.
  • The program I wrote to glue the JVM backend work and the existing NQP frontend together was about 30 lines of NQP code.
  • This whole integration process was about an afternoon’s worth of work.

Since I got that working, my focus has been on getting nqp-mo (the NQP meta-objects) to cross-compile. This is where classes and roles are implemented, and thus is a prerequisite for cross-compiling the NQP setting, which is in turn a prerequisite for being able to start cross-compiling and running the NQP test suite. The NQP MOP is about 1500 lines of NQP code, and at this point I’ve got about 1400 of them to cross-compile. So I’m almost there with it? Well, not quite. Turns out that the next thing I need to port is the bounded serialization stuff. That’s a rather hairy chunk of work.

Anyway, things are moving along nicely. The immediate roadmap is to get the bounded serialization to the point where it’s enough for the NQP MOP, then move on to getting a minimal setting cross compiling. Beyond that, it’ll be working through the test suite, porting the regex compilation and seeing what else is needed to cross-compile the rest of NQP.

Posted in Uncategorized | 5 Comments

A Bunch of Rakudo News

Seems it’s high time for some news here. It’s not that I didn’t do any blogging about Perl 6 in December; it’s just that all of those posts were over on the Perl 6 advent calendar. Anyway, now it’s a new year, and I’m digging back into things after an enjoyable Christmas and New Year’s break in the UK with family and friends. Here’s a bunch of things that already happened but I didn’t get around to talking about here yet, and some things that will be coming up.

Better Parse Errors In 2012.12

Ever had Rakudo tell you there’s a problem on line 1, when it’s really on line 50? Or wished that even in the common case where it gets the line right, it would tell you exactly where on the line things went wrong? Or how about the time it told you “Confused” because you got a closing paren too many?

Many of my contributions to the 2012.12 Rakudo release centered around improving its reporting of parse errors. STD, the standard Perl 6 grammar, has had much better error reporting than Rakudo for a while. Therefore, I spent a bunch of time aligning our error reporting more closely with what STD does. Some of this is cosmetic: you get the colored output and the indication of the parse location. But while these cosmetic changes will be the most immediately visible thing, the changes go far deeper. Of note, a high water mark is kept so we can be a lot more accurate in reporting where things came unstuck, and we track what was expected so we can produce better errors. Just doing the cosmetic stuff without being able to give it a better location to report wouldn’t have helped so much. :-)

One other change is that we don’t bail out on the first thing that’s wrong when it’s possible to survive and continue parsing. When this is possible, up to 10 errors will be reported (since that’s typically a screen worth). Of course, some things just hose the parse and we can’t continue in any sensible way.

Hopefully, these improvements will make using Rakudo feel a lot nicer. Already on channel, I can feel the feedback we’re giving about parse errors when people use the evalbot is often a lot more pleasant and informative. Of course, there’ll be more improvements in the future too, but this is a big step forward.

Faster Auto-Threading

The junction auto-threader could sometimes be insanely slow. As in, ridiculously so. After hearing a bunch of reports about this, I decided to dig in and work out why. A rewrite later, the little benchmark I was using with it ran almost 30 times faster. Not so bad… :-) This change also made it into the 2012.12 release.

JVM Backend Preparations Underway

I’ve talked plenty about plans for NQP and Rakudo to run on things besides Parrot for a while now. Over the last year or two, we’ve laid a lot of the groundwork for this. What’s been especially pleasing is that it’s also made Rakudo a better quality Perl 6 implementation on Parrot, thanks to the many architectural improvements. Of note, in many places we’ve closed semantic gaps between what Perl 6 wants and the primitives we were building it out of; the new QAST (Q Abstract Syntax Tree) is a great example.

Anyway, with NQP now being written pretty much entirely in NQP, and many of the right abstractions in place, it felt like time to start slowly picking away at getting 6model ported to the JVM and work on turning QAST trees into Java bytecode. I quietly started on this in November, and mentioned the existence of the work on #perl6 in December. I was delighted to see Coke++ jump in and start working through the Low Hanging Fruit – a file where I’m putting tasks that should be relatively easy to pick off. I actually had to re-fill it, after the last round were depleted. ;-) By now, quite a few bits of QAST are supported and the 6model on JVM implementation is coming along nicely. Yes, this means it’s already capable of doing basic meta-programming stuff.

Note that this work isn’t at the stage where it’s of use for anything yet. You can’t even write a say(“hello world”) in NQP and have it run on the JVM yet, since all the work so far is just about turning QAST trees into JVM bytecode and building the runtime support it needs. That may seem like a curious way to work, but once you do enough compiler stuff you find yourself thinking quite naturally in trees. It meant I didn’t have to worry about creating some stripped-down NQP that could emit super-simple trees to be able to test really simple things. After all, the goal is to run NQP itself on the JVM, and then Rakudo, and only then will things be interesting to the everyday user.

To address a couple of immediate concerns that some may have…

  • No, this is not a case of “stop running on Parrot, start running on JVM”. It’s adding an additional backend, much like pmurias++ has been working on adding a JavaScript backend for NQP. Of course, I expect resource allocation in the future to be driven by which backends users desire most. For some, the JVM is “that evil Oracle thing” and they don’t want to touch it. For others, the JVM is “the only thing our company will deploy on”. Thus I expect this work to matter more to some people than others. That’s fine.
  • No, targeting multiple backends doesn’t mean performance-sucking abstractions everywhere. It’s a pretty typical thing for a compiler to do. As usual, it’s about picking the right abstractions. The debugger was implemented as an additional Rakudo frontend without a single addition to Rakudo or NQP or anything anywhere in the stack. That was possible because things were designed well. I’m sure the process of getting things running on the JVM will flag up a few places where things aren’t designed as well as they need to be, but already I’m seeing a lot of places where things are mapping over very nicely indeed.
  • No, this doesn’t mean that all other Rakudo development will grind to a halt. I’ve been working on the JVM backend stuff in November and December; both months saw a huge amount of Rakudo progress too. Things will go on that way.

Type System Improvements

Rakudo does a lot of things well when it comes to supporting the various kinds of types Perl 6 offers, but there are some weak areas. Here are some of the things I plan to focus on:

  • Getting the definedness constraint stuff working better (the :D and :U annotations). At the moment, they’re supported as a special case in multiple dispatch and the signature binder. In reality, they’re meant to be first class and work everywhere. You may not think you care about these much. Actually, you probably at least indirectly do, because once the optimizer is able to analyze them, it’ll be able to do a bunch more inlining of things than it can today. :-)
  • Getting coercion types in place. Again, this is turning the special-cased “as” syntax into the much more general coercion type syntax (for example, Int(Str) is the type that accepts a Str and coerces it into an Int).
  • Getting native types much better supported. At the moment, you can use them but…there are pitfalls. Having them available has been a huge win for us in the CORE setting, where we’ve used them in the built-ins. But they’re still a bit “handle with great care”. I want to change that.
  • Implementing compact arrays.
  • Improving our parametric type and type variable support. Many things work, but there are some fragile spots and some bugs that want some attention.

I intend to have some of these things in the January release, and a bunch more in the February one. We’ll see how I get along. :-)

Posted in Uncategorized | 3 Comments