in reply to Perl 5 Optimizing Compiler, Part 5: A Vague Outline Emerges
My overall conclusion is that this project is completely unrealistic, in terms of the technical challenge, the expected speed improvements, the timescale, and the availability of suitably qualified labour.
12 years ago, perl was at a crossroads. The experimental B:: suite had been written, and the experience gained from that showed that achieving significant performance gains was near impossible using the existing creaking perl core. After some mug throwing, the perl6 and parrot project was born. The Perl language would be redesigned to be more optimiser-friendly (e.g. optional types), while a new parser could target a proper bytecode, executed by a modern new VM. This new infrastructure would then give us the underlying system that facilitates doing all the sexy new compilerly/execution stuff like SSA, JIT, etc.
There was lots of initial enthusiasm, lots of volunteer manpower, and timescales of a year or two bandied about (IIRC). Even at the time the estimates seemed unrealistic to me, but who was I to say? Now, 12 years later (admittedly after personality clashes and fallings out etc), we still don't have a complete, production-ready system. This isn't meant as criticism of the parrot and perl6 teams, but rather to point out just how hard it is to re-implement something as complex and subtle as the perl syntax and semantics. Remember, just the lexer in perl5 is 12,000 lines of C code.
So I think we're about to repeat the same perl6 exercise (with admittedly more modest goals), with the same under-appreciation of its difficulty.
So, that was a general overview. Now onto more specifics. First, LLVM. I like LLVM, I think it's a cool system. If I was going to write perl from scratch now, I would very seriously consider using its IR as the target of the compiler. The issue here though, is how easy it would be to retro-actively make perl use LLVM in some way or another. I think you get a sliding scale, with the achievable bits giving small gains, and large gains only (possibly) possible by huge changes to the existing perl core: basically rewriting large parts of it (i.e. a project of parrot/perl6 scale).
There seem to be three ways suggested of using LLVM. First, there's the trivial sense of using it as a better C compiler. Anecdotal evidence indicates that it might give you 5-10% speedup. But that's not really what we're discussing here.
Secondly, there's Yuval's suggestion, which in its most basic (and thus 'doable' form) is to basically change the API of the pp_* functions to allow the runops loop to to be unrolled, and avoid the overhead of perl stack manipulation. It may also then allow LLVM to better optimise the resulting call tree, e.g. hefting stuff up to a higher level.
Looking at the purely loop unrolling / stack side of things, I did a rough calculation to see what improvement could be expected. I ran the following perl code: $z = $x + $y * 3; ($x and $y contain ints) in a loop under cachegrind, and used the results to estimate approximately what proportion of the execution is spent on loop/stack overhead. The answer was approx 20%. Note that the example above was chosen specifically to use simple perl ops where the overhead is most likely to dominate. Perl has a lot of heavyweight ops like pp_match(), where the relative overhead is going to be much smaller. Also, the LLVM verison will have an overhead of its own for setting up args and the current op, just hopefully less than the current overhead. So that means that overall, the loop/stack stuff is going to give us something less than 20% speedup (and probably a lot less in practice, unless all your perl code does is lots of lightweight stuff like additions). Set against this there might be improvements from LLVM being able to compile the resulting code better, but my speculation is that it won't be significant.
Yuval then listed some more speculative improvements that could then be built upon that basic stuff, but I still think the performance gains will be relatively modest. The advantage of the Yuval approach is that it should be achievable by relatively little effort and by relatively modest changes to the existing perl source.
The third thing to do with LLVM, (which is what I think BrowserUK is advocating, but I may be wrong), is the wholesale replacement of perl's current runtime, making perl's parser convert the op tree to LLVM IR "bytecode", and thus making a perl a first-class Perl-to-LLVM compiler, in the same way that clang is a first-class C-to-LLVM compiler. This would be a massive undertaking, involving understanding all the subtleties and intricacies of 25,000 lines of pp_* functions, and writing code that will emit equivalent IR - even assuming that you kept the rest of perl the same (i.e. still used SVs, HVs, the context stack, pads etc).
If you were to go the full hog and replace the latter with something "better", you're then into full perl6/parrot territory. You're at the point of rewriting most of perl from scratch: the point that I said earlier I might have started from if had to do over perl again from scratch. But I think that unless you wholesale throw away SVs, pads, etc, you're not going to see game-shifting performance gains. So I think this option can be summed up as "yes,I would have been nice if perl had originally been written to target LLVM, but wasn't, and the cost of retro-fitting is prohibitive".
Now we get onto "writing a perl compiler that targets something like javascript, which will be fast, because lots of money is being spent making javascript fast".
I see two main issues with this. Firstly, no one is ever going to write a perl parser that can fully parse perl and handle all it's subtleties. The best you can do is to parse the easy 90% and ignore the edge cases. But "Ah", I hear you think, "90% is good enough for most people. My code doesn't use ties or overloading". The problem is that within the 10% not covered, there will be 1% that your code does in fact use. "Your code uses /(?{})/? That's a shame.". If you're lucky, you'll get a compile-time error telling that feature X is unsupported. If you're unlucky (and you will be unlucky) your code will silently do the wrong thing due to some subtlety of auto-vivification, localization or stash manipulation or whatever.
Secondly, any impedance mismatch between perl and javascript is going to give you agonisingly slow performance. For example, if the full semantics or perl hashes can be provided by javascript dictionaries or objects say, then you can directly translate $foo{bar} into foo.bar or whatever. If however, the javascript facilities aren't suitable, then you might end up having to implement a Perl-style hash using javascript code, which is going to be slow. Also what tends to happen in these sorts of conversions is that the early proof-of-concept work (which uses a javascript dict say) works well and is really, really fast. Then you reach the point where you've done 50% of the work and its going really well, Then you get round to implementing the 'each' op, and suddenly realise that it can't be done using a javascript dict. So you switch to the slow route. NB: the hash is just a hypothetical example, which may or may not be a problem in javascript. The real point is that there are lots and lots of things in perl which have odd semantics, that can be superficially implemented in the "fast" way, but which may have to switch to a slow approach once a wider subset of its semantics are implemented.
That's the end of my rants about specific suggestions. I'll just add a few final general comments.
No matter what fancy tools or rewrites you use, you're always going to have some theoretical constraints on performance due to the nature of the perl language. For example, method dispatch in perl is always going to be cumbersome and un-optimisible, due to the way dispatch is based on point-in-time lookup in a stash. Yes, you can do clever tricks like caching, but perl already does this. There may be further tricks no-one's got round to thinking of yet (or at least not implementing yet), but such tricks are likely to be as applicable to the current perl code as to any LLVM or javascript variant. This really boils down to the fact that to see really significant performance changes, you have to change the perl language itself. Add a new type system, object system, or whatever.
The general experience so far of doing "clever stuff" in other languages like Python, often with considerable funding and resources, has been a catalogue or either failure, abandoned projects, or disappointing speedups. It doesn't necessarily follow from it that no-one should ever attempt such a thing again, but it does indicate that doing this sort of thing (and getting it right) is really hard. And the general impression I get from reading up about what "clever stuff" people have already been trying with perl (e.g. Yuval and LLVM), is that major performance improvements weren't the main consideration for the project.
Note that this is the last contribution I intend to make on this topic for the moment; I've already spent waaaay too much time reading up and discussing it.
PS: For anyone familiar with the "Big Talk" sketch in the UK comedy series "That Mitchell and Webb Look", I feel that this whole discussion has been rather similar to its "Come on, boffins!" ethos.
|
|---|