Looking back, looking forward

So, 2012 is here, and here’s my first Perl 6 post of the year. Welcome! :-)

Looking Back

2011 brought us a faster Rakudo with vastly improved meta-programming capabilities, the first work on exploring native types in Perl 6, the start of a powerful type-driven optimizer and many other bits. It also took me to various conferences and workshops, which I greatly enjoyed. I’d like to take a moment to thank everyone involved in all of this!

This was all great, but slightly tainted by not managing to get a Rakudo Star distribution release out based on a compiler release with all of these improvements. I’d really hoped to get one out in December. So what happened? Simply, there were a certain set of things I wanted to get in place, and while many of them got done, they didn’t all happen. While the compiler releases are time based – we do one every month – the distribution releases are more about stability and continuity. By the time I headed back to the UK to spend Christmas with family, we were still missing a some things I really wanted before a Star release was done. Given the first thing that happened when I started relaxing a little was that I immediately got unwell, I figured I should actually use my break as, well, a break – and come back recharged. So, I did that.

So, let’s try again

So, the new goal is this month. I’m happy to report that in the week since I’ve got back to things, one of the things I really wanted to sort out is now done: Zavolaj, the native calling library, now does everything the pre-6model version of it did. In fact, it does a heck of a lot more. It’s even documented now! It’s also far cleaner; the original implementation was built in the space of a couple of days with mberends++ while I was moving apartment, and was decidedly hacky in places. The missing bits of the NativeCall library were important because they are depended on by MiniDBI, and I really didn’t want to ship a Rakudo Star that can’t connect to a database. So, next up is to make sure that is in working order. I’m not expecting that to be difficult.

That aside, there were some things to worry about in Rakudo itself. I’ve dealt with some of those things in the last week, and perhaps the one important remaining thing I want to deal with before Star is a nasty regex engine backtracking related bug (I’ve been hoping pmichaud++, the regex engine guru, might appear and magic it away, but it seems it’s going to fall on my plate). But overall, we’re well on track to cut the Star release this month.

What’s the direction for the year ahead?

During 2011, Rakudo underwent a significant overhaul. It was somewhat painful, at times decidedly not much fun, but ultimately has been very much worth it: many long standing issues have been put to rest, performance has been improved and many things that were once hard to do are now relatively easy or at least accessible.

I think it goes without saying that we won’t be doing any such wide-ranging overhaul in 2012. :-) The work in 2011 has opened many doors that we have yet to walk through, and 2012 will see us doing that.

At a high level, here’s what I want:

• Less bugs, more stability: mostly this is about continuing to work through the ticket queue and fix things, adding tests as bugs are fixed to ensure they stay fixed.
• Better error reporting: there are things in STD, the Perl 6 standard grammar, that allow it to give much more informative error reports on syntax errors than we often can in Rakudo today. I want us to bring these things into Rakudo. Additionally, there’s plenty of improvements to be made in runtime errors. Furthermore, I want to expand the various bits of static analysis that I have started doing in the optimizer to catch a much wider range of errors at compile time.
• Run programs faster: this process is helped by having decent profiling support these days. There’s a lot more to be done here; the optimizer will help, as will code generation improvements.
• Compile programs faster: this will come from more efficient parsing and greatly improving the quality of the code NQP generates (NQP is the language we write much of the compiler in)
• Shorter startup time: this mostly involves finishing the bounded serialization work up. I think the best way to describe this stuff is “fiddly”.
• Use less memory: Rakudo has got faster in no small part thanks to being able to understand its performance through profiling. Our understanding of its memory consumption is much more limited, which makes it harder to target improvements. That said, I’ve some good guesses, and some ideas for analyzing the situation.
• More features: while being able to do the things Rakudo can do today faster and with less bugs would give a very usable language for quite a lot of tasks, there’s still various features to come. In particular, Rakudo’s support for S05 and S09 needs work.
• VM Portability: we’ve made good progress towards being able to make a serious stab at this over the last year, while at the same time also managing to perform vastly better on Parrot too. With help from kshannon++, I’m currently working on completing the switch to QRegex (a regex engine with NFA-powered LTM, and written in NQP rather than PIR), which should carry on a pattern of simultaneously increasing performance and portability. Beyond that will be an overhaul of our AST and code generation, with the same goal in mind.

So, lot’s of exciting things coming up, and I look forward to blogging about it here. :-)

A way to help

There are many ways to get involved, depending on what you’re interested in. One way is to take a look at our fixed bugs that need tests writing. At the time of writing, just short of 100 tickets are in this state. No guts-y knowledge needed for this – you just need to understand enough Perl 6 (or be willing to learn enough) to know what the ticket is about and how to write a test for it. Drop by #perl6 for hints. :-)

Rakudo: this week’s release, and the next Rakudo Star

On Thursday, tadzik++ cut release #46 of Rakudo. This time, we named it for the London Perl Mongers, organizers of this year’s outstanding and very well attended London Perl Workshop. I’d not been to one for a couple of years, and I’d forgotten what a fun event it is. This one felt better than ever. So, thanks folks! :-)

So, what was in the Thursday release?

• Big Integer Support: the Int and Rat type now support very large values without loss of precision/coercing to floating point. This means you can do such things as compute factorial to 1000 (which stringifies to 2568 characters, by the way :-)). You don’t need to get any libraries set up for this – we bundle a slightly extended libtommath with NQP, and it’s exposed by some ops and an extra 6model representation, which the Int type inlines into its body (so Int is still a single garbage collectable object at the VM level). Thanks go to moritz++ for doing much of the work on this.
• Protoregexes with LTM: it’s taken us a lot longer to get protoregexes back into the nom development branch than we’d initially hoped. Here’s the story. A while ago, pmichaud++ worked on real Longest Token Matching support – driven by an NFA – in a re-development of the regex engine. We’d only ever had “cheating” protoregexes in Rakudo before – ones that could work on literal prefixes, but nothing more. The improved engine is a really nice piece of work – amazingly little code for what it does, and very elegant. Sadly, pmichaud has not been able to work so much on Rakudo of late, so the work lay not-quite-done and unmerged for a while. Just ahead of the release, I picked it up, and found it was far enough along and sufficiently easy to get in to that I could get a first cut integrated in time for this month’s release. Since the release, along with diakopter++, I’ve been hacking away at regexy bits, so there’ll be many improvements in this area in next month’s release. It was nice to get something in place for this month’s, though.
• CATCH improvements: mls++ did a bunch of work that made our handling of CATCH blocks far, far more in line with the Perl 6 specification. Naturally, this makes them much more useful; you now can write when blocks in your CATCH, and any exceptions you don’t match will get re-thrown to the next handler. Write a default block to swallow everything. We also do the stack unwinding at the correct point now. Great work!
• Improved MAIN argument parsing: japhb++ has been leading the way on improving our support for the MAIN subroutine, including nice usage message generation. This is a really nice Perl 6 feature for writing command line applications, so it’s good to see work here. :-)
• 6model REPR API 2: this is very much a behind the scenes thing, and deserves a post of its own for those who follow the blog in order to know more about metamodel design. However, in short: I re-worked the REPR API in 6model somewhat, and updated the various representations to use it. The immediate result was that we could efficiently have Perl 6′s Int type do big integer stuff. However, it’s also the foundation for some forthcoming work on compact structs and packed arrays. Hopefully at a user level, though, you’ll notice nothing at all about this change; it’s all guts. :-)
• Various other fixes and improvements: bugs fixed, performance improved, missing stuff implemented…we had quite a few smaller, but very worthwhile things done in this release too.

So, this is great, but the next question on everybody’s mind is: when is a nom-based Rakudo Star release coming out? The answer – epic disasters aside – is “December”. Yes, next month. Two big things have happened in the last week: grammar support in the nom development branch drastically improved, and this unblocked tadzik++ to get our ecosystem tools (for module build and installation) working with it. The focus from here is…

• Native call support: get our support for loading and calling into C libraries re-established. The NativeCall module basically worked…apart from it made a load of guts-y assumptions that don’t hold true any more, and was somewhat restricted in what it could handle (for multiple reasons). Now we have 6model and native type support, we can do far better. My task for over the next week is to get our native call support back in shape, all being well with a bunch more features.
• More regex work: while we’ve come a really long way in recent days – we have many things working that never worked in the previous development branch – there are still some issues to address, including one nasty backtracking issue.
• Fixing Modules: quite a few modules already work just fine on nom. Some block on native call support, others on the remaining regex stuff. Others will point to bugs or will be using outdated semantics or relying on previous bugs. tadzik++ has figured out how to automatically run through the module ecosystem, build modules and run their tests, so we can get a good sense of what needs doing.

And, of course, the usual round of feature addition, bug fixing and performance work.

And, with that, it’s back to the hacking. :-)

Slides from my Optimizing Rakudo Perl 6 talk

Over the weekend, I visited to Bratislava for a few days, the beautiful city I once called home. It felt oddly familiar, and I found myself noticing all kinds of little changes here and there – where one shop had given way to another, or a statue had appeared or changed. Happily, my favorite eating and watering holes were still there, and my sadly somewhat rusted Slovak language skills were still up to decoding menus and ordering tasty beer, and I did plenty of both. :-)

I was there was to attend the Twin City Perl Workshop. I repeated my Perl 6 grammars talk, and gave a new one about optimizing Rakudo. This included both the optimization work myself and others have been doing, but also some details about the optimizer. I also made a couple of nice diagrams of Rakudo’s overall architecture and what it does with a program.

You can get the slides here, or if you’re heading to the London Perl Workshop this coming Saturday, I’ll be delivering it there too. Enjoy! :-)

An optimizer lands, bringing native operators

For some weeks now, I’ve been working on adding an optimizer pass to Rakudo and implementing an initial set of optimizations. The work has been taking place in a branch, which I’m happy to have just merged into our main development branch. This means that the optimizer will be included in the October release! :-) In this post, I want to talk a little about what the optimizer can do so far.

When Optimization Happens

When you feed a Perl 6 program to Rakudo, it munches its way through your code, simultaneously parsing it and building an AST for the executable bits, and a bunch of objects that represent the declarative bits. These are in various kinds of relationship; a code object knows about the bit of as-yet uncompiled AST that corresponds to its body (which it needs to go and compile just in time should it get called at BEGIN time), and the AST has references to declarative objects (types, subs, constants). Normally, the next step is to turn this AST into intermediate code for the target VM (so for Parrot, that’s PIR). The optimizer nudges its way in between the two: it gets to see the fully constructed AST for the compilation unit, as well as all of the declarative objects. It can twiddle with either before we go ahead and finish the compilation process. This means that the optimizer gets to consider anything that took place at BEGIN and CHECK time also.

Using The Optimizer

The optimizer has three levels. The default level is 2. This is “optimizations we’re pretty comfortable with having on by default”. It’s possible to pass –optimize=3, in which case we’ll throw everything we’ve got at your program. If it breaks as a result, please tell us by filing an RT ticket; this is the pool of candidate optimizations to make it into group 2. After an optimization has had a while at level 2, combined with a happy and trouble-free history, we’ll promote it into level 1. Using –optimize=1 at the moment gets you pretty much nothing – the analysis but no transformations. In the long run, it should get you just the optimizations we feel are really safe, so you won’t lose everything if you need to switch down from –optimize=2 for some reason. Our goal is that you should never have to do that, of course. However, it’s good to provide options. My thanks go to pmichaud++ for suggesting this scheme.

Compile Time Type Checking of Sub Arguments

One thing the optimizer can do is consider the arguments that will be passed to a subroutine. If it has sufficient type information about those arguments, it may be able to determine that the call will always be successful. In this case, it can flag to the binder that it need never do the type checks at run time. This one can actually help untyped programs too. Since the default argument type is Any, if you pass a parameter of one subroutine as an argument to another, it can know that this would never be a junction, so it never has to do the junction fail-over checks.

Compile Time Multiple Dispatch Resolution

While the multiple dispatch cache current Rakudo has is by some margin the best it has ever had in terms of lookup performance, it still implies work at run time. Given enough information about the types of the arguments is present, the optimizer is able to resolve some multiple dispatches at compile time, by working out cases where the dispatch must always lead to a certain candidate getting invoked. Of course, how well it can do this depends on the type information it has to hand and the nature of the candidates. This is a double saving: we don’t have to do the multiple dispatch, and we don’t have to do the type checks in the binding of the chosen candidate either.

Basic Inlining

In some (currently very constrained) cases, if we know what code is going to be called at compile time, and we know that the types of arguments being passed are all OK, we can avoid making the call altogether and just inline the body of the subroutine right into the caller. Of course, this is only beneficial in the case where the work the subroutine does is dominated by the overhead of calling it, and there are some cases where inlining is impossible to do without causing semantic differences. For now, the focus has been on doing enough to be able to inline various of the setting built-ins, but it’s in no way restricted to just doing that. With time, the inline analysis will be made much smarter and more capable.

Native Operators

As part of getting the optimizer in place, moritz++ and I have also worked on native operators (that is, operators that operate on native types). This boils down to extra multiple dispatch candidates for various operators, in order to handle the natively typed case. However, something really nice happens here: because you always have to explicitly declare when you are using native types, we always have enough type information to inline them. Put another way, the native operator multis we’ve declared in the setting will always be inlined.

We’ve some way to go on this yet. However, this does already mean that there are some nice performance wins to be had by using native types in your program (int and num) where it makes sense to do so.

As an example, with –optimize=3 (the maximum optimization level, not the default one), we can compare:

my $i = 0; while $i < 10000000 { $i = $i + 1 }; say $i

Against:

my int $i = 0; while $i < 10000000 { $i = $i + 1 }; say $i

On my box, the latter typed version completes in 4.17 seconds, as opposed to the untyped version, which crawls in at 33.13 (so, a factor of 8 performance gain). If you’re curious how this leaves us stacking up against Perl 5, on my box it does:

my $i = 0; while ($i < 10000000) { $i = $i + 1 }; say $i

In 0.746 seconds. This means that, with type information provided and for this one benchmark, Rakudo can get within a factor of six of Perl 5 – and the optimizer still has some way to go yet on this benchmark. (Do not read any more into this. This performance factor is certainly not generally true of Rakudo at the moment.)

We’ll be continuing to work on native operators in the weeks and months ahead.

Immediate Block Inlining

We’ve had this in NQP for a while, but now Rakudo has it too. Where appropriate, we can now flatten simple immediate blocks (such as the bodies of while loops) into the containing block. This happens when they don’t require a new lexical scope (that is, when they don’t declare any lexicals).

That Could Never Work!

There’s another nice fallout of the analysis that the optimizer does: as well as proving dispatches that will always work out at compile time, it can also identify some that could never possibly work. The simplest case is calling an undeclared routine, something that STD has detected for a while. However, Rakudo goes a bit further. For example, suppose you have this program:

sub foo($x) { say $x }
foo()

This will now fail at compile time:

CHECK FAILED:
Calling 'foo' will never work with no arguments (line 2)
    Expected: :(Any $x)

It can also catch some simple cases of type errors. For example:

sub foo(Str $s) { say $s }
foo(42)

Will also fail at compile time:

CHECK FAILED:
Calling 'foo' will never work with argument types (int) (line 2)
    Expected: :(Str $s)

It can handle some basic cases of this with multiple dispatch too.

Propagating Type Information

If we know what routine we’re calling at compile time, we can take the declared return type of it and use it in further analysis. To give an example of how this aids failure analysis, consider the program:

sub foo() returns Int { 42 }
sub bar(Str $s) { say $s }
bar(foo())

This inevitable failure is detected at compile time now:

CHECK FAILED:
Calling 'bar' will never work with argument types (Int) (line 3)
    Expected: :(Str $s)

The real purpose of this is for inlining and compile time multi-dispatch resolution though; otherwise, we could never fully inline complex expressions like $x + $y * $z.

Optimizing The Setting

Since we have loads of tests for the core setting (many of the spectests cover it), we compile it with –optimize=3. This means that a bunch of the built-ins will now perform better. We’ll doubtless be taking advantage of native types and other optimizations to further improve the built-ins.

Gradual Typing

Many of these optimizations are a consequence of Perl 6 being a gradually typed language. You don’t have to use types, but when you do, we make use of them to generate better code and catch more errors for you at compile time. After quite a while just talking about these possible wins, it’s nice to actually have some of them implemented. :-)

The Future

Of course, this is just the start of the work – over the coming weeks and months, we should gain plenty of other optimizations. Some will focus on type-driven optimizations, others will not depend on this. And we’ll probably catch more of thsoe inevitable run time failures at compile time too. In the meantime, enjoy what we have so far. :-)

This is not enough!

The time for some shiny new hardware came around. Sat next to me, purring decidedly more quietly that its predecessor, is my new main development machine: a quad core Intel Core i7, pimped out with 16 GB of RAM and a sufficiently generous SSD that it can hold the OS, compiler toolchain and projects I work most actively on. It’s nice having a $dayjob that likes keeping their hackers…er, consultants…well kitted out. :-)

So, the question I had to ask was: how fast can this thing run the Rakudo spectests? I tried, and with –jobs=8 (the sweet spot, it seems) it chugged its way through them in 220s. That’s vastly better than I’d ever been able to do before, and I could immediately see it was going to be a boon for my Rakudo productivity. 3 minutes 40 seconds. Not so long to wait to know a patch is fine to push. But…what if it was less? It’s fast but…this is not enough!

A while ago, moritz++ showed how the nom branch of Rakudo ran mandelbrot 5 times faster than master. This was a fairly nice indicator. Around the time my new hardware arrived, an update was posted on #perl6: mandelbrot was now down to 2 minutes on the same machine the original tests were done. Again, I was happy to see progress in the right direction but I couldn’t help but feel…this is not enough!

So, I took a few days break from bug fixing and features, and decided to see if things could get faster.

Faster Attribute Access

One of the things I’ve had planned for since the early days of working on 6model is being able to look up attributes by index in the single inheritance case, rather than by name. I finally got around to finishing this up (I’d already put in most of the hooks, just not done the final bits). It’s not an entirely trivial thing to make work; at the point we parse an attribute access we don’t know enough about how the eventual memory layout of the object will be, or whether an indexed lookup will even work. Further, we have to involve the representation in the decision, since we can’t assume all types will use the same one. Mostly, it just involves a later stage of the code generation (PAST => POST in this case) having the type object reachable from the AST and asking it for a slot index, if possible.

Since I implemented it at the code-gen level, it meant the improvement was available to both NQP and Rakudo, so we get compiler and runtime performance improvements from it. Furthermore, I was able to improve various places where the VM interface does attribute lookups (for example, invocation of a code object involves grabbing the underlying VM-level thingy that represents an executable thing, and that “grabbing” is done by an attribute access on the code object). Attribute lookups never really showed up that high in the (C-level) profile, but now they’re way, way down the list.

The P6opaque Diet

P6opaque is by far the most common object representation used in NQP and Rakudo. It’s generally pretty smart; it has a header, and then lays out attributes – including natively typed ones – just like a C structure would be laid out in memory. In fact, it mimics C structures well enough that for a couple of parts of the low-level parts of Rakudo we have C struct definitions that let us pretend that full-blown objects are just plain old C structures. We don’t have to compromise on having first class objects in order to write fast low-level code that works against them any more. Of course, you do commit to a representation – but for a handful of built-in types that’s fine.

So, that’s all rainbows and butterflies, so what was the problem? Back last autumn, I thought I knew how implementing mix-ins and multiple inheritance attribute storage was going to look; it involved some attributes going into a “spill hash” if they were added dynamically, or all of them would go there apart from any in a common SI prefix. Come this spring when I actually did it for real, a slightly smarter me realized I could do much better. It involved a level of indirection – apart from that level already existed, so there was actually no added cost at all. Thing is, I’d already put the spill slot in there, and naughtily used the difference between NULL and PMCNULL as the thing that marked out whether the object was a type object or not.

This week, I shuffled that indicator to be a bit in the PMC object header (Parrot makes several such bits available for us to use for things like that). This meant the spill slot in the P6opaque header could go away. Result: every object using the P6opaque representation got 4 (32-bit) or 8 (64-bit) bytes lighter. This has memory usage benefits, but also some speed ones: we get more in the CPU cache for one, and for another we can pack more objects into fixed sized pools, meaning they have less arenas to manage. Win.

Constant Pain

In Perl 6 we have Str objects. Thanks to 6model’s capability to embed a native Parrot string right into an object, these got about three times cheaper in terms of memory already in nom. Well, hopefully. The thing is, there’s a very painful way to shoot yourself in the foot at the implementation level. 6model differentiates coercion (a high level, language sensitive operation) from unboxing (given this object, give me the native thingy inside of it). Coercion costs somewhat more (a method call or two) than unboxing (mostly just some pointer follows). If you manage to generate code that wants a VM-level string, and it just has an object, it’ll end up doing a coercion (since at that level, it doesn’t know the much cheaper unbox is possible/safe). After reading some of the compiler output, I spotted a bunch of cases where this was happening – worst of all, with constant strings in places we could have just emitted VM-level constant strings! Fixing that, and some other unfortunate cases of coercion instead of unbox, meant I could make the join method a load faster. Mandelbrot uses this method heavily, and it was a surprisingly big win. String concatenation had a variant of this kind of issue, so I fixed that up too.

Optimizing Lexical Lookup

We do a lot of lexical lookups. I’m hopeful that at some point we’ll have an optimizer that can deal with this (the analysis is probably quite tricky for full-blown Perl 6; in NQP it’s much more tractable). In the meantime, it’s nice if they can be faster. After a look over profiler output, I found a way to get a win by caching a low-level hash pointer directly in the lexpad rather than looking it up each time. Profilers. They help. :-)

Optimized MRO Compuation

The easiest optimizations for me to do are…the ones somebody else does. Earlier this week, after looking over the output from a higher level profiler that he’s developing for Parrot, mls++ showed up with a patch that optimized a very common path of C3 MRO computation. Curiously, we were spending quite a bit of time at startup doing that. Of course, once we can serialize stuff fully, we won’t have to do it at all, but this patch will still be a win for compile time, or any time we dynamically construct classes by doing meta-programming. A startup time improvement gets magnified by a factor of 450 times over a spectest run (that’s how many files we have), and it ended up being decidedly noticeable. Again, not where I’d have thought to look…profiling wins again.

Multi-dispatch Cache

We do a lot of multiple dispatch in Perl 6. While I expect an optimizer, with enough type information to hand, will be able to decide a bunch of them at compile time, we’ll always still need to do some at runtime, and they need to be fast. While we’ve cached the sorted candidate list for ages, it still takes a time to walk through it to find the best one. When I was doing the 6model on CLR work, I came up with a design for a multi-dispatch cache that seemed quite reasonable (of note, it does zero heap allocations in order to do a lookup and has decent cache properties). I ported this to C and…it caused loads of test failures. After an hour of frustration, I slept on it, then fixed the issue within 10 minutes the next morning. Guess sleep helps as well as profilers. Naturally, it was a big speed win.

Don’t Do Stuff Twice

Somehow, in the switch over to the nom branch, I’d managed to miss setting the flag that causes us not to do type checks in the binder if the multi-dispatcher already calculated they’d succeed. Since the multi-dispatch cache, when it gets a hit, can tell us that much faster than actually doing the checks, not re-doing them is a fairly notable win.

Results

After all of this, I now have a spectest run in just short of 170 seconds (for running 14267 tests). That’s solidly under the three minute mark, down 50s on earlier on this week. And if it’s that much of a win for me on this hardware, I expect it’s going to amount to an improvement measured in some minutes for some of our other contributors.

And what of mandelbrot? Earlier on today, moritz reported a time of 51 seconds. The best we ever got it to do in the previous generation of Rakudo was 16 minutes 14 seconds, making for a 19 times performance improvement for this benchmark.

This is not enough!

Of course, these are welcome improvements, and will make the upcoming first release of Rakudo from this new “nom” development branch nicer for our users. But it’s just one step on the way. These changes make Rakudo faster – but there’s still plenty to be done yet. And note that this work doesn’t deliver any of the “big ticket” items I mentioned in my previous post, which should also give us some good wins. Plus there’s parsing performance improvements in the pipeline – but I’ll leave those for pmichaud++ to tell you about as they land. :-)

What’s coming up in September/October

So, YAPC has come, been great, gone and been recovered from, I’m done with my summer visiting, the $dayjob speaking trip has taken place, I’ve shaken off the obligatory start of autumn cold and it’s time to get back to hacking on stuff. Actually, I’ve no more workshops or other trips until November and I’ve got Perl 6 time marked in my schedule, so all being well there should be plenty of time to Get Stuff Done. :-) So what have I got planned for the next couple of months?

Ship a ”nom”-based Release

This is the current priority. Day by day, we’re fixing up test files we lost in the refactor. This weekend I got most of the missing bits of parametric role support back in place (and I’m overall happy with the resulting factoring; it’s a massive amount better than what we had before). Our biggest remaining holes are in the regex and grammar handling, which pmichaud++ is on with (I’m quite excited about what’s coming here). Other than that, it’s little bits here and there. We’re getting there. :-)

A Basic Rakudo Optimizer

I’ve started playing with this a bit, in a branch. Nothing interesting to see yet, other than an optimizer that only knows one optimization, makes a few things a little faster and regresses a couple of spectests (so, some weird bug in the analysis or transform somewhere). The good news is that it does successfully make it through applying that optimization to CORE.setting. This is an important part of developing the optimizer: if we’re going to write our built-ins in Perl 6, we really want an optimizer to go over them too. My aim is to teach this a couple more things and have it in the October release.

A Basic NQP Optimizer

NQP is the subset of Perl 6 that we write most of the compiler in. We also implement the various built-in meta-objects in it (so we want it to be fast here, and of course we want faster compiles!) It currently has no optimizer, a situation I plan to change. NQP has many restrictions that full-blown Perl 6 does not have, and as a result we’ll be able to do some more aggressive optimizations, or be able to apply them with far simpler analysis. My goal is to have some form of basic optimizer in NQP by the October release. Of course, since NQP is bootstrapped, NQP’s optimizer can be used to optimize NQP itself (yes, it can optimize the optimizer…) “So we just keep running NQP on itself until it runs crazy fast?” Er, no, sorry, it doesn’t work like that. :-)

Bounded Serialization

Currently, as we compile programs, we build up a complete “model” of the runtime environment (for example, we build Signature/Parameter objects, meta-objects to represent classes, and so forth). If we’re going to just run the program, we carry these objects over to runtime and use them. If we’re in compilation mode, like we are with the setting, then we generate a bunch of “deserialization code”. This gets run first of all when we load the setting/module in question. This introduces a couple of problems.

• It’s a lot of code to generate. In fact, it accounts for a whopping 60% of the lines of PIR in CORE.setting! This probably means that about 60% of the PAST nodes we generate and then have to process into POST and then PIR are also related to this. Assuming we could replace this process with something much faster, we’re looking at cutting compilation time in half for the setting. Note that this only really affects pre-compilation time, not “run immediately” mode.
• We have to run it all at load time. Now, having it all in one huge blob is decidedly more efficient than the thousands of little loadinit subs we had everywhere in previous generations of Rakudo. But we still have to do it, and it means that loading the setting – something we have to do every time we start Rakudo to compile or run code – pays that cost. We need better startup time.
• We have to make sure that every single change that gets made gets recorded. We cheat a bit here. This gets in the way of many things, including various optimizations and proper BEGIN time support in pre-compiled modules (note that we don’t re-run BEGIN, but we should maintain effects of it).

The solution is to find a way to efficiently serialize everything we create, and then be able to deserialize it efficiently at load time and do the few needed fixups. While in theory it’s “easy” (keeping iterating over a worklist until you’ve serialized everything, basically), there’s a bunch of really tricky things that also come up (especially any closures that got taken at compile time). I hope to dig into this before the end of the month, and my target is to have it for the November release (October one is a bit ambitious, unless it goes crazily well; in reality, I’d like to land it late October, so we have a couple of weeks before the November release to get it in shape).

Revive the CLR Backend

Running NQP on the CLR got a long, long way. At the time I last touched it, the majority of the non-regex tests in the NQP test suite were passing, and diakopter++ was making progress on the regex ones too. It’s been dormant for a while, but it’s time to get back to work on it. Getting NQP, and then Rakudo, to run on the CLR is now a vastly more tractable task to back then, since:

• Back then, I was in the process of designing 6model and doing an NQP port and working out what NQP on 6model would look like. Now I only have to worry about one of those things, not all three at the same time.
• NQP itself is 6model based now. Thus there won’t be a need for the “JnthnNQP” fork (NQP itself ended up looking much more like JnthnNQP anyway, which was the idea). If I do need tweaks that I can’t immediately reconcile with NQP on Parrot, they can be done just by subclassing NQP::Actions or so and overriding the things in question. Either way, it’ll be the same – or a slightly twiddled – version of NQP, not a vastly different one.
• Rakudo itself is now mostly written in NQP and Perl 6. We used to have a bunch of PIR builtins, but they’re long gone (along with various ugly issues they caused, like not having proper Perl 6 signatures and so forth). I’d guesstimate that about 5% – at most 10% – of the Rakudo code is backend specific. Some of it will be tricky, but a lot of it is – at least if you’re familiar with it – pretty mundane.

Of course, some problems I chose to ignore will need to be dealt with (like, how to best harness the way to CLR thinks of types in order to implement 6model representations more efficiently, and how to support gather/take). It’ll need generating IL rather than C#. And…plenty more. I’m not going to set any targets for this just yet; I’ll just dig in, have fun, and we’ll see where things land up in a month or two. I found it great fun to work on this last time – the CLR is a nice VM and well tuned – so it shouldn’t be hard to get a round tuit. :-)

Other Bits

Of course, there’s still bits of the Perl 6 spec that needs implementing, and things in module space. Amongst things I’d like to hack on soon are big integer support (so we can do Int right), natively typed operators and teaching NativeCall to handle structures.

Other 6model Bits

I want to vastly improve the state of 6model’s documentation. Taking a moment to look further ahead than the next couple of months, once the updated CLR implementation of it comes together, and when some other language’s object systems have been shown to be buildable on 6model, I also want to think about declaring a “6model API v1″ or so. This is so that if/when Parrot integrates 6model, or others implementations show up that I won’t have a close hand in, there’s a clear idea of what it’s expected to look like from the outside, and what are implementation details (and thus can be done in whatever way is appropriate). I also expect further extensions, refinements, and so forth, and I think it’d be best to give folks who implement 6model – myself included! – some coarser grained way of saying “we support this set of things” than just listing off implemented features. This is some way off, though I do already have a slowly forming picture of what I’d like to tackle in the area of meta-model design in the future.

So, that’s what I’ve got in mind. Oh, and I should be sure to blog as I work on this stuff! Feel free to prod me if I forget. :-)

My YAPC::EU talks

I had a wonderful time at YAPC::EU in Riga this year. Riga is a very beautiful city – there’s many nice things to look at, not to mention the excellent food and a wide range of beer at sensible prices. Once place I went had over 30 types of beer on tap! That’s the city, but then there was the YAPC itself: smooth running, well organized, nice venue, all breaks and lunches on site, and a great conference dinner. I’ve had the fortune to be at many events where Andrew Shitov has led the organization (I just checked and I think this must have been the 9th one!), and I knew he could do something excellent for YAPC::EU. He did, and was a very deserving recipient of a White Camel award this year. So, congrats to Andrew, and many thanks for the steady stream of excuses to travel to East Europe and talk about Perl. :-)

I gave a couple of talks.

• Rakudo Evolved: Speed, Feedback and Hackability covered my work on 6model and Rakudo over the last year, and laid out some of the plans for the coming year. It had some code, but was more of a wordy talk: some theory, some lessons learned, some plans.
• Debugging Perl 6 Grammars was my more hands-on talk this year. During the talk I unveiled Grammar::Debugger, a module for debugging grammars.

So, another year, another great YAPC. And now, it’s back to work on Rakudo!

A hint of meta-programming

After a few patches to deal with some meta-circularity issues, I’ve got to the point where I have at least a very basic example of a custom meta-class working in the nom branch of Rakudo. All this does is print out the name of each method that gets looked up, before deferring to the normal handling of method dispatch. However, I’m sure that now that I’m at this point, much more interesting things are already very possible, though no doubt there’s some rough edges I still need to deal with.

Anyways, to the code! Here’s a module, LoggedDispatch.pm.

my class LoggedDispatch is Metamodel::ClassHOW is Mu {
    method find_method($obj, $name) {
        note "Looking up method $name";
        nextsame;
    }
    
    method publish_method_cache($obj) {
        # Suppress this, so we always hit find_method.
    }
}

# Export this as the meta-class for the "class" package declarator.
my module EXPORTHOW { }
EXPORTHOW.WHO.<class> = LoggedDispatch;

Taking it from the top, we inherit from Metamodel::ClassHOW, which is the default implementation of Perl 6 classes. There’s actually no requirement to do this – in some future posts I’ll show you how you can easily piece together meta-classes from the ground up – but in this case all we really want to do is a small tweak to the existing behavior. For now, we also inherit from Mu. (Aside: at the moment, since ClassHOW is what defines classes, it falls “outside” of the Perl 6 type hierarchy. That’s in some ways understandable but also in some ways very awkward. I’ve more than one approach to dealing with this, but need to think more on the problem.)

Now, on to the meat of the problem. Conceptually, every method dispatch on an object gets that object’s meta-object and calls “find_method” on it, passing in the method name to find. Therefore, in order to intercept this, we need to override “find_method” – which is what we do. We simply print the name of the method to STDERR using “note”, then use “nextsame” to defer to the actual method lookup algorithm. Pretty easy. However, there’s a twist.

As you might imagine, dispatching methods is a hot-path. If we have to call a method in order to work out what method to call – and if that had to do the same in turn – things would get really very slow indeed. Thus, it’s possible to publish a method cache, which is dead fast to look in. However, it’s also going to mean that find_method never gets called – which is where we’re going to put our logging stuff. While for an optimized version of this we could compute a bunch of closures to do the logging and populate a cache with those, for now we just suppress generation of the cache.

That gets us down to the last bit. There’s a (lexical) EXPORT package for exporting symbols, but we want to do something a bit different here: we want to tell the compiler that when this module is used, it should use our meta-class whenever the user writes a class (that is, uses the package declarator “class”). For now (note, API liable to change) that’s done by installing an entry in an EXPORTHOW module.

And with that, we’re done. Here’s an example program.

use LoggedDispatch;

class A {
    method m1() { say 42 }
    method m2() { say 99 }
}

for 1..2 {
    A.m1;
    A.m2;
}

And here’s the output:

Looking up method BUILD
Looking up method m1
42
Looking up method m2
99
Looking up method m1
42
Looking up method m2
99

The first line of this may be a little surprising – something goes looking for a BUILD method at some point. But it’s maybe not such a surprise: it’s a method with special meaning to object construction, and we can imagine that at some stage during the class composition, something got interested in whether the class had one (in this case, it’s the bit of code that creates a build plan, in order to optimize object instantiation).

At the start of the post, I used the term meta-circularity. If you weren’t sure what it meant, you’re now in a position to understand it. Here, we wrote a Perl 6 class to extend the meaning of Perl 6 classes. Meta-circularity is very simply the property of being able to use a language to extend itself, rather than having to do so by going and writing some other special or lower-level language to do so. And I’m really happy that I’ve been able to tie up the last few loose ends so that we can start to do that in the nom branch now.

July: Beijing Perl Workshop, vacation and hacking

It’s been an interesting month. I started it over in Beijing, for the Beijing Perl Workshop. It’s the first Perl event that I’d been to in China, and it was a great experience. People were very friendly and welcoming, the venue was nice and cool (good job, since I had a hard time coping with the Beijing summer heat), I had a good audience and good response to my talks, and the meals before and after it were great too. I gave two full-length talks, plus a lightning talk:

• Perl 6: Quicker Hacks, More Maintainable Apps
• Rakudo: The Story of a Compiler
• Awesome Operators (Lightning Talk)

I got to see various things in Beijing. I avoided a couple of the most famous attractions – I saw them last time I was in Beijing, and they’re incredibly crowded mid-summer – and instead enjoyed some of the still wonderful, but maybe slightly lesser known ones. I managed to get a decent bit of hacking in too, mostly because I simply can’t handle being outside for too long in high temperature and humidity. Happily, I had a hotel that provided both wired and wireless internet with the room, and a couple of free beers a day too!

Anyway, that was my fun conference trip of the month. This was also the month where I took my one totally laptop-free vacation of the year. That was just the mental and physical break I needed from the hacking, though of course I couldn’t totally break away from things and ended up reading The Art of the Metaobject Protocol on the journey there and back. I’d read a couple of extracts from it before, but this was the first time through the whole book. It was decidedly worthwhile, though it shows its age a little at times too! ;-)

Amongst the trips, I’ve got some decent work in on the “nom” branch. It’s going well – a look at the excellent new compiler features page shows that there’s not too many areas left where we lack things (at least on that list) that master has. On some features, we’ve decidedly pulled ahead of master too. I’ll write up some more detailed news soon, but overall, we’re making good progress.

Excitingly, YAPC::Europe is now not far off too! Last year I had one talk, so it was relatively relaxing. This year, I’ve two talks, but also a full day teaching class on OOP in Perl 6. So, I’m busily preparing for all of that too, and of course very much looking forward to seeing lots of familiar – and new – faces there. :-)

Anyways, my patches for today are pushed, and my beer glass is empty, so I guess it’s time to take a little rest.

Another little nom update

I was gearing up to blog a bit about the progress we’re making on the nom branch of Rakudo, when pmichaud++ swooped in with a great post about that. It nicely captures how much we’re getting done putting Rakudo back together on top of 6model. Along the way, we’re also dealing with various other deeper issues, which will let us close a bunch of tickets in RT when the branch lands. Overall, the code base is now a lot more pleasant to work with, and the factoring of the OO features is far superior to what we had in master. Another really nice thing is that lexical symbol installation is far, far neater; it sounds like a small thing, but it’s made hacking on Rakudo far more pleasant.

It’s also exciting that we’ve started to get native types in place now. I’ll warn you up front: don’t expect a speed win from them yet. We’re building towards that, but it’s non-trivial and not a priority for the nom branch; it’ll come later. On the other hand, if it’s memory savings you’re after then having tens of thousands of objects having attributes that are native ints will be way cheaper than if they had been boxed ones. That said, the boxed ones consume about a third of the memory they do in master, not to mention being three times less work for the GC. So you’ll win plenty over master even without using the natives, or any type annotations at all.

The nom branch will deliver direct performance improvements as well as lay the foundations for writing a much-needed optimizer. Even without that optimizer in place, we’re getting some nice wins. In pmichaud’s post he talked about for loops being 80% faster. Here’s a couple more little micro-benchmarks. The program:

my $i = 0;
while $i < 1000000 {
    $i = $i + 1;
}
say $i

Runs in about 25% of the time that master takes (thus 4 times faster). And we do way better on a floating point version of this due to far better handling of numeric literals. This:

my $i = 0;
my $a = 0.0e1;
while $i < 1000000 {
    $i = $i + 1;
    $a = $a + 0.25e1
}
say $i;
say $a;

Runs in 4.5% of the time master does it in, or over 20 times faster.

Now, these improvements themselves aren’t that impressive, but they are just the ones that fall out of using the new object model, better handling of literals, various block and variable setup improvements and so forth. The exciting part will be when we start using the extra information we now have available at compile time in order to do things like compile-time resolution of multi candidates, inlining and type inference. Glancing the profiles to see where we spend time, I expect these will give us another order of magnitude improvement.

That’s all for now – time for me to get some rest. Tomorrow I’ll be flying to Beijing, to give some talks at the Beijing Perl Workshop and no doubt take in many of the wonderful attractions the Chinese capital has to offer, not least the awesome food. I have so many fond memories of when I spent a month backpacking around China, and I didn’t leave much time for Beijing then, so it’ll be nice to see the many things I didn’t have time for. And no, I won’t be vanishing from Rakudo hacking for a week; keen to look around as I’ll be, I suspect the cold-weather-loving me will probably also be keen to sit inside and hack a bit when the temperatures hit 35C or so. :-)