Perl 5 Optimizing Compiler

[Will_the_Chill]

Howdy Monks,

I'm the CTO of an Austin-based company with some significant Perl 5 code, and the new President of the Austin Perl Mongers.

I'm in the process of reviving efforts to create a real Perl compiler, with the explicit goal of making Perl run at speeds within an order of magnitude of optimized C.

This could be achieved any number of ways, with possible ideas taken from PONIE, Blizkost, Inline::C, Parrot/Tornado VMs, perlcc, B:CC, etc.

I'm not particularly tied to any one method of achieving the Perl speedup, as long as we end up with some successful optimizing and compiling mechanism I will be happy.

Of course I realize this is a massive undertaking that many people have wanted over the years. I'd love to get it done and released at YAPC 2013, which will hopefully be held here in Austin.

What are your thoughts about how this might most effectively and efficiently be achieved?

Thanks,
~ Will

PS - I just e-mailed a copy of this posting to Ingy, Dan Sugalski, Artur Bergman, and Nick Clark. Who else should I try to contact directly?

[moritz]

I'm mostly involved with Perl 6 development, and in many ways unfamiliar with the existing Perl 5 compiler. So I'd like to give a very high level answer. You might already know most or all of it, in which case I'd like to apologize for wasting your time. But it's a topic that comes up quite often, so I think a broad answer can't hurt.

Why is Perl 5 slower than C?

In one word, flexibility. Perl gives you much more flexiblity, for example in what you can place into a variable, what operations you can perform (for example string concatentation on a number, not just on strings), and you pay for that flexiblity with lots of run time checks and indirection.

Or to rephrase, Perl lets you omit some gory details that you have to handle yourself in C code (type conversions, memory management, validity checks on data), and you pay for that with runtime and memory overhead.

On the #perl6 IRC channel, people regularly ask if there will be a compiler that translates Perl 6 code to C, seeming to think that such a compiler magically leads to C-like speed. That's false, of course, because the generated C code would still need to take care to allow all that flexiblity that you don't have in "plain" C.

In summary, flexiblity gives you some essential overhead that is not easy to get rid of (distinguished from superficial overhead that stem from less-than-perfect implementation).

How to speed it up?

Superficial Overhead

First you can work on removing superficial overhead. But that won't give you a factor of 10 over the existing implementation, and I hear that the Perl 5 code base is already quite well micro-optimized.

Maybe hackers like Nicholas Clark, Dave Mitchell and Sprout can point you to some known overhead that is worth removing, and if it's in a hot path or often-used data structure, it might very well pay off. But not a factor 10, more like 5%. If you are lucky.

Restricting Flexibilty

If you pay for flexibility, an obvious way to pay less is to restrict that flexiblity where you don't need it.

An obvious example are type constraints. If you know that a variable will always be a 32 bit integer, you don't need to store a full SV for it, a 32 bit integer will do. But beware, that means you need to be able to store more data (for the type annotations) in the optree/bytecode, which might mean that all programs pay a penalty for that, even if they don't use that feature.

Other ideas for what flexibility you could give up, in the context of Perl 5, all of which might be useful for optimized code paths:

• Declare that some data or variables have no magic attached
• Declare that introspecting the call stack (via caller and backtraces) is allowed to return incorrect results (important for inlining and such)
• Declare that symbol tables should be considered immutable after compile time.
• Assume that no eval will be called from the current dynamic scope (for optimizing away variables, for example)

I don't know the perl 5 guts well enough to find out which of those can be exploited with reasonable effort.

Let the Compiler Determine Restricted Flexibility

Some things (like that a variable will only be an integer, ever) can be determined by the compiler, but it probably can only do so with external help (like under the assumption that no eval will change the variable)

That would be the ideal solution, because it would speed up code without requiring any (or only very little) changes to the code that is sped up.

Optimize for the Common Case

A technique often used in JIT compilers (but available to "normal" ahead-of-time compilers too) is to optimize for the common case.

For example a compiler could determine that a variable starts out as an integer, and simply guess that it will always hold and integer, and generated an optimized code path for that case. Of course the guess will go wrong some time, so it also needs to emit code for the unoptimized general case, and some kind of fallback mechanism that transfers control flow to the general case if the guess turns out to be false.

This seems to be a very promising approach, but also one that requires signficant infrastructure.

Planning for the Future

One reason I've put so much effort into Perl 6 is that I had the feeling that in the long run (like on the scale of 10, 20 years) Perl 5 was a dead end, partially because it is not very well suited for static analysis and optimizations. After the switch to a time-based release cycle, (perceived) faster core development the p5-MOP effort, I am more hopeful.

Coming from a Perl 6 perspective, one thing I'd really love to see in Perl 5 is representation polymorphism. Which means largely decoupling the type of an object from its storage. For example you can write

class MyStruct is repr('CStruct') {
    has int    $.int;
    has num    $.num;
    has CArray $.arr;

    method init() {
        $!int = 42;
        $!num = -3.7e0;
        my $arr = CArray[int32].new();
        $arr[0] = 1;
        $arr[1] = 2;
        $!arr := $arr;
    }
}

and have objects of type MyStruct stored as a C struct, which you can pass to a C routine that expects this data structure:

typedef struct {
    long intval;
    double numval;
    long *arr;
} MyStruct;

(I should add that this is working code from a test of a module that allows calling C functions, not some future vision).

Having such a mechanism in Perl 5 would be really awesome. The current SV could be one representation, other representations could be optimized for compact storage of objects. Combine that with the works of a custom Meta Object Protocol in p5 core, and you have a winning condition.

It would make interfacing C and other languages much easier, be very memory efficient for objects with specialized storage. Imagine writing a GTK application, and exposing all GTK objects as native Perl objects through a GObject representation (or whatever it's called these days) -- a simple, cheap mapping step is enough, no need for wrapping everything in custom Perl objects.


(My keyboard stopped responding after I've written a good deal of this post, but I planned to write more. So I submitted before I wrote the "Planning for the Future" headline to save a copy before restarting my X server (because submitting only required the mouse, which continued working), and added the rest after it.)

[eyepopslikeamosquito]

Sorry but your proposed project comes across as a bit naive. Have you done some basic feasibility research of such a project? Note that perlcc was removed from the Perl core as at Perl 5.10. See also:

• What happened to perlcc? (2007)
• perlcc compile core dump (2010)
• Why Not Translate Perl to C? (2001, perl.com article by MJD)
• How can I convert Perl to C? (2009, stack overflow)
• Resurrected perlcc B-C by Reini Urban (CPAN)

BTW, a similar project for Python, Unladen Swallow, seems to have met with overwhelming difficulties.

[rgiskard]

I think most people would like to see perlcc revived. If it is as impossible as you are making it out to be, then I for one welcome a YAPC talk on the failed persuit of reviving the compiler. Perhaps the goal is too ambitious for the time allotted, but I don't see why that should halt side-projects.

[eyepopslikeamosquito]

I too would like to see perlcc revived and it appears that it is already being revived by Reini Urban on CPAN. What I think is way too ambitious, especially for the timeframe suggested, is the OP's stated performance goal of "making Perl run at speeds within an order of magnitude of optimized C".

[chromatic]

What are your thoughts about how this might most effectively and efficiently be achieved?

Add compact, typed arrays to Perl 5.

Remove polymorphism from the Perl 5 ops and add it to SV and descendents. (C++ may be a better option here than C.)

Add a tracing JIT. Iterate on that for a few years.

I'd love to get it done and released at YAPC 2013, which will hopefully be held here in Austin.

Invent a time machine and send the code back from 2023.

Who else should I try to contact directly?

Reini Urban.

[Will_the_Chill]

Chromatic,

Thanks for the reply. Per your note, I've e-mailed Reini Urban, as well as Sisyphus and Neil Watkiss.

You mention typed arrays, polymorphism, and a tracing JIT mechanism. I assume these are serious recommendations (not sarcastic)?

Thanks,
~ Will

[Anonymous Monk]

I just want to tell you don't lose heart on what chromatic wrote

2013 isn't far away, if you sprint fast enough you can get to something and probably even fail. But you learn tons, fail fast and get something substantial.

Or you may even get there, you never know. How many it has happened people are convinced something is impossible, until somebody comes along and proves them other wise.

If you are determined. Start first. Don't get bogged down by details. Note: Well begun is half done.

[xiaoyafeng]

Invent a time machine and send the code back from 2023.

lol, perl5 is non type and too flexible, these 2 reasons lead it's hard to optimize. If we can add a brand new type and const system into perl5 and strict perl's flexibilty, it would be sped up as we think.

[bulk88]

I agree. Many optimizations that can be performed in C or other no runtime eval languages can't be done in Perl since so much context and metadata has to be kept around for a rare eval string or magic to happen. Dereferencing has to be done every time -> or {} appears in code without exception in case its a magic variable. $root{l1}{l2}{l3} really takes 4 dereferences ops every time it is written, and it can be written 7 times in a sub. Very few people (I am one of them) will make a lexical reference to the has slice "\$root{l1}{l2}{l3}" to avoid all the reference ops. I still had a dereference op every time I write "${}" but its better than "load constant on stack, do deref" times 3 opcodes. Sometimes flexibility isn't so flexible. hv_common_key_len could use some refactoring to split out all the magic support into separate function calls to keep it out of the CPU cache. Here are top 18 (actually all functions over 4 KB long) fattest functions in ActivePerl 5.12 (Visual C -O1) in machine code.

_Perl_re_compile        00001021
_Perl_gv_fetchpvn_flags 0000105F
S_scan_const            000010EB
S_regatom               000012FB
S_make_trie             0000148C
_Perl_sv_vcatpvfn       00001620
_Perl_yyparse           000016C2
S_regclass              0000177A
_Perl_do_sv_dump        00001A4D
S_reg                   00001B5F
_perl_clone_using       00001D3C
S_unpack_rec            0000231F
S_study_chunk           00002668
S_pack_rec              00002729
S_find_byclass          00002928
_Perl_keyword           0000359D
S_regmatch              0000438A
_Perl_yylex             00008095

un/pack I'm surprised it so fat. clone_using could use a couple strategically placed memcpy calls rather than 100s of double/quadword copies.

Use B::Deparse and look at your opcode trees. Reduce number of opcodes and your code is faster. Each ; has overhead (line number switching for not present debugger). Use a comma operator sometimes to reduce nextstates.

[rurban]

You are lucky, because I am free to work on this for cPanel for the next years :) At cPanel they compile perl for more than 10 years and most of their speedup is with optimizing the perl code, not so the compiler. The problem is that perl, the language, is too dynamic to be optimizable. Too much slowdown (magic, module imports, ...) and changes can happen at run-time. Also the language is not clear enough. The ops contain the needed optimizer info, not the data. So it's dealing with a lot of run-time and side-effects.

If you only need better startup time B::C is already stable and good enough. For optimized run-time more is needed.

I did some research and lobbying over the last years and came up with those approaches:

Did you see my inofficial (not yet announced) proposals on github? I'm working on const and a type system to enable future optimizations. Time-frame: 1-2 years.

perl design draft - types and const

https://github.com/rurban/perl/blob/42b0094646/pddtypes.pod

perl types pod

https://github.com/rurban/perl/blob/05514649c/pod/perltypes.pod

perldata.pod: add const and coretypes

https://github.com/rurban/perl/commit/7eb6c3584a1b

B::CC or another optimizing compiler can only profit from const and types.

After the YAPC we'll gather in Stavanger, Norway to discuss how to get the MOP proposals into perl.

http://act.yapc.eu/mtmh2012/

https://github.com/stevan/p5-mop/tree/master/extras/talks

Of course a MOP will slow down perl (other disagree), but as perl is currently hardly optimizable at all and more and more slowdown is getting introduced over the years, the MOP could be used to allow more compile-time optimizations and more efficient class, method and property handling.

Getting an optimizing compiler for YAPC::US sounds like a good plan to me, but is of course way too optimistic. B::CC already exists and passes most tests. Fixing the failures sounds like a good plan to me.

Function calls are also super-slow with perl. Getting faster functions calls by analyzing the code at compile-time and omit unnecessary exception handling, @_ handling, scope, and so on would also be a worthwile goal, up to inlining. Unfortunately it is not possible to discuss such thing on p5p. Not even the much simplier, possible XS call improvements.

The next idea will be Go-like concurrency in p5 with a changed runloop to saturate multiple native threads on multiple CPU's automatically. And some go-like language extensions for IPC communication. But I guess this vision is way too much for p5p. And even parrot is not there yet. In the current p5p process environment hardly anything could get done. It's management anti-patterns all over, as from the textbook.

[dave_the_m]

Function calls are also super-slow with perl. Getting faster functions calls by analyzing the code at compile-time and omit unnecessary exception handling, @_ handling, scope, and so on would also be a worthwile goal, up to inlining. Unfortunately it is not possible to discuss such thing on p5p.

Why not?

Dave.

[Anonymous Monk]

Of course the topic can be discussed on p5p. I believe what Reini meant to write was, "I've cried wolf so many times that most of p5p no longer trusts my judgment."

[xiaoyafeng]

because I am free to work on this for cPanel for the next years

Plz~, I can't wait 4 more months. ;)

[flexvault]

Welcome Will_the_Chill,

From my observations, Perl gets better with each new version, and if you use Perl's strengths, you can leave many 'off-the-shelf' 'C' programs in the dust.

But, I would love to see a Perl compiler, but not for speed or concealing the code from hackers, but for code security, revision control and simplicity of deployment. ( and probably a few more. )

Before Perl, I used 'C' and 'uxbasic', a 'compiler' that mimicked the Z80 based 'oasis/theos' basic from the '80s but could run on most AIX/Unix systems. It could be run from source (BASIC), from an interpreter compiled code (BASICOBJ), and from pseudo compiled code (BASICCOM). As a developer you tested with the first 2 modes and then shipped the final version as the pseudo compiled code (think bytecode). And guess what, if the run time version of 'uxbasic' was installed, the code you shipped worked.

Now I'm not comparing this '80s code to Perl, but that concept of distributing code would improve the user experience with Perl. Why?

Since the '80s, I have sold and supported software for companies, the majority of which have 10 to 100 employees. They also have 1 or more people who have used Perl to print "Hello World". Since I started shipping Perl modules, I've had some of the funniest (maybe tragic) updates to my software. For example:

• One site removed the rounding on invoices to make it faster. Why? "...don't need it for 2 decimal places..." So after 400+ invoices are incorrect, the president calls and says '...your lousy software screwed up, everyone told me to go with a 'C' or 'VB' or ... solution... FIX IT"
• One site changed one screen, and then removed 'use strict' so the code would compile.
• Another changed the copyright notice, and it stopped working. The 'expert' couldn't find the problem, and wanted us to fix it.
If you work in an environment where you control everything, then you wouldn't understand the 'user' frustrations from 'brilliant' coders.
So why can't Perl have a '-Compile' like the '-cw' compiler flags that produces a bitecode that can be shipped and run. Every one knows that someone that wants to get the code can, but the casual 'expert' would be deterred by '...It looks like 'C' to me!'

Thank you

[Anonymous Monk]

If you don't want "customers" diddling the code, you can use PerlApp/CavaPackager/PAR (with filters, crypto/whitespace, even used to be a B::Bytecode filter )

[CountZero]

Your reply wins the "most useless and clueless answer of 2012" prize.

[perlfan]

You've probably seen PDL, but their approach is to provide XS/C based Perlish interfaces that lighten the overhead of things like Perl data structures and provide access to more exotic processing environments like GPUs and threading.

I am suggesting this because what you're asking about is something that bubbles up occasionally, and it almost never ends well. In otherwords, the idea is to some how optimize the language/interpreter and creating a "real" compiler (err...Perl to "harnessed C" transformation tool), but what ends up happening is that compromises are made and things are offloaded to modules via XS.

[gregor42]

It seems that your stated goal is to improve execution speed.

Why then have you decided that compilation is the only route to this improvement?

I wonder if there are other motivations involved? (Not an accusation, a Question.)

[rurban]

Some of the mentioned performance and language changes were being outlined at the corehackers wiki.

Using XS for performance is silly, because the XS API is silly. One should not copy values to/from perl arrays for c stack arguments, perl should use the C stack as perl4 did for its argument passing. Larry just did not know the libffi or ffcall libraries then.

The pp_ API with the same perl stack API is also pretty unoptimizable, but this can be rewritten.

[bulk88]

Why would the C stack be faster than the Perl stack? Both are an array of word sized numbers/pointers.

[chromatic]

In theory, a good optimizing compiler can avoid some of the stack manipulation necessary for naïve C function calls. (Obviously for those externally visible symbols where you must adhere to a platform ABI, you can't get away with this.) Even better, because the C stack isn't heap allocated, you can avoid malloc/free pairs for stack allocated values.

You get at least two drawbacks from this. First, your calling conventions are going to end up looking a lot like C's calling conventions, so you have to go through wild contortions for things like exception handling, tail call optimizations, green threads, and continuations. Second, you're subject to the limitations of the C calling conventions, so maximum stack depth (see recursion and corecursion), thread stack limits, and the safety of extension code written with access to the C stack are concerns.

You have to be a lot more clever to write optimizable code using the heap, but you get a lot of features from avoiding the C stack. To go really fast, you have to avoid copying a lot of memory around anyway, so my preference is to figure out how to optimize heap calls to avoid allocating and freeing unnecessary memory and to put everything into processor registers and keep it there.

[rurban]

Because a stack access is 1. ~70 times faster then a heap access, 2. allocation is for free, 3. you do not need to clean up the stack, and 4. stack ptrs are thread safe. That's why normal programming languages use an ABI which puts parameters onto the stack and better align it properly to be able to use MMX. It's not only for recursion.

Compare reading or writing at %ebp+8 against any absolute ptr. It's about 5 against 150 micro instructions.

Stack accesses are also relative and hot and local, heap accesses usually not. Some heap ptrs are hot and cached, but you still have the cache overhead.

[chromatic]

(delete, duplicate of Re: Perl 5 Optimizing Compiler)

[sundialsvc4]

The common-sense assumption that “an optimizing compiler will make it significantly faster” presupposes ... I think, incorrectly, that CPU execution speed is the ruling constraint; that the code is “CPU-bound.”   In my experience, with all business applications, this is almost never actually true.   If the application is, in fact, “I/O-bound,” then it has CPU-time to burn and an optimizing compiler will do nothing useful for it.

(Bear in mind that an ordinarily CPU-bound activity will be forced into I/O-bound characteristics if it consumes so much memory working-set that it is pushed into significant virtual memory paging.)

The essential code-paths within the Perl compiler/interpreter itself are already well-identified and are optimized.   You can therefore write “almost any old thing” in Perl5 and know that it is being executed in a very efficient way.   But the software is still going to spend a preponderance of its time in either an I/O-wait or even an idle-wait.   The one-time overhead of JIT compiling, and the sustained overhead of the interpreter, is time that the CPU can afford to lose.

I therefore suggest that you need to instrument your existing programs, starting with the ones that are most business-critical and/or that seem to be causing the most business pain.   Why are they waiting, what are they waiting on, and where in the code do the waits occur.   Look most closely at the algorithms, and expect to have to redesign them.   As Kernighan & Plauger said in The Elements of Programming Style:   Don’t “diddle” code to make it faster; find a better algorithm.   Do not assume that the CPU is running “round objects to the wall” because it undoubtedly is not and never could.   Do not make the ruling assumption that an optimizing compiler will do for you diddly-squat, because it probably won’t.

Certainly, there are bona-fide edge cases, throughout the Perl system and its libraries, that are properly handled right now with “XS” code, in C or C++.   These are the hot-spots and they feature heavy bit-twiddling; exactly the sort of thing that these languages are best at.   You might find a hot-spot in your app that could be dealt with in this way, but I rather doubt it.

[BrowserUk]

In my experience, with all business applications, this is almost never actually true. If the application is, in fact, “I/O-bound,”

If your "experience" is confined solely to yet-another-shopping-cart applications bolted together coding-by-numbers style from a bunch cpan modules, that may be the case, but "business" covers a great deal more ground that a bunch of mom&pop retail outlets.

There are a huge number and variety of cpu-bound business applications in this world -- else (for example) there's be no market for about 90% of IBMs hardware offerings -- finance; insurance; oil & gas; pharmaceuticals; entertainment; shipping & logistics; aircraft manufacturer; car manufacture; genomics & agriculture; the list goes on and on.

Dismissing the need for performance because your web app can't utilise it is extremely short-sighted.

[sundialsvc4]

I think that it is well-understood where I am coming from, without disparaging comments like “mom and pop” or even “web app,” which at the very least do not advance the argument posed.   Let’s all stay on-target here, all of us, and pleasantly agree to disagree.   There is no “one” point-of-view here, and it’s possible to speak against a point-of-view without speaking against the person.

To my way of thinking, languages like Perl are most commonly but not always used in situations where raw execution speed is ... irrelevant(!).   The processing typically is (I aver...) most likely to be I/O-bound, more dependent on the speed of a network or of a drive or a SAN or what-have-you than on the pure horsepower of the CPU itself.   BrowserUK, I specifically acknowledge that your work is an exception to that statement, and very impressive work it certainly is.   Nor do I claim that no valid solutions exist for which an optimizing compiler might not be seen as useful.   But when I specify blade servers, for what I need them for, I always err on the side of “lots of RAM” and less on CPU-speed.   I am delighted to see near-100% CPU utilization but it will be widespread across many processes with my workloads, not a few, and a faster storage-channel is going to be the best buy for me.   If CPU utilization falls off, I buy more RAM or look for an I/O bottleneck.   If a process has a really-big working set size relative to the other processes in the mix, I look for algorithm-changes to reduce it.

In what I consider to be the general language case, if the speed of the Perl-based application is judged to be inferior, I would assert that an algorithm change is more likely to be successful.   Perhaps a very tightly targeted one.   Changes to the machine-code generation behavior in the general case might be of no value at all, because the system is literally “hurry up and wait.” and no optimizer can do anything for that.

[chromatic]

The essential code-paths within the Perl compiler/interpreter itself are already well-identified and are optimized.

That may be true (it isn't, but it's at least plausible) if you take into account the current design of the Perl 5 VM. Unfortunately, the current design of the Perl 5 VM makes some assumptions which preclude performance.

It's enlightening to run some of the silly microbenchmarks people use for competitive benchmarking to see exactly why Perl 5 scales so badly on some of them. (See also my response on compact, typed arrays.)

Certainly, there are bona-fide edge cases, throughout the Perl system and its libraries, that are properly handled right now with “XS” code, in C or C++.

Cases also exist where writing XS will make your code slower—and I don't mean writing inefficient XS.

[Anonymous Monk]

The common-sense assumption that “an optimizing compiler will make it significantly faster” presupposes ... I think, incorrectly, that CPU execution speed is the ruling constraint; that the code is “CPU-bound.”   In my experience, with all business applications, this is almost never actually true.   If the application is, in fact, “I/O-bound,” then it has CPU-time to burn and an optimizing compiler will do nothing useful for it.

(Bear in mind that an ordinarily CPU-bound activity will be forced into I/O-bound characteristics if it consumes so much memory working-set that it is pushed into significant virtual memory paging.)

The essential code-paths within the Perl compiler/interpreter itself are already well-identified and are optimized.   You can therefore write “almost any old thing” in Perl5 and know that it is being executed in a very efficient way.   But the software is still going to spend a preponderance of its time in either an I/O-wait or even an idle-wait.   The one-time overhead of JIT compiling, and the sustained overhead of the interpreter, is time that the CPU can afford to lose.

I therefore suggest that you need to instrument your existing programs, starting with the ones that are most business-critical and/or that seem to be causing the most business pain.   Why are they waiting, what are they waiting on, and where in the code do the waits occur.   Look most closely at the algorithms, and expect to have to redesign them.   As Kernighan & Plauger said in The Elements of Programming Style:   Don’t “diddle” code to make it faster; find a better algorithm.   Do not assume that the CPU is running “round objects to the wall” because it undoubtedly is not and never could.   Do not make the ruling assumption that an optimizing compiler will do for you diddly-squat, because it probably won’t.

Certainly, there are bona-fide edge cases, throughout the Perl system and its libraries, that are properly handled right now with “XS” code, in C or C++.   These are the hot-spots and they feature heavy bit-twiddling; exactly the sort of thing that these languages are best at.   You might find a hot-spot in your app that could be dealt with in this way, but I rather doubt it.

So basically you didn't understand that the OP is in the process of reviving efforts to create a real Perl compiler, with the explicit goal of making Perl run at speeds within an order of magnitude of optimized C.