Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Perl 5 Optimizing Compiler, Part 4: LLVM Backend?

by Will_the_Chill (Pilgrim)
on Aug 27, 2012 at 08:18 UTC ( #989940=perlmeditation: print w/ replies, xml ) Need Help??

I just e-mailed this to Nick Clark, let's see what Perl Monks thinks...

Nick,

Are you familiar with LLVM? Here's a technical link about how to incrementally port Perl 5 to use LLVM as an optimizing backend. Apparently this approach can be done by incrementally converting the pp_*() Perl 5 guts functions into some theorized r_*() format to emit LLVM assembly code, while maintaining 100% backward compatibility with all existing Perl 5 code and XS too! (In other words, NOT a subset of Perl 5 like Perlito and C'Dent/Perl5i, but the whole of Perl 5.)

https://www.socialtext.net/perl5/llvm

Some choice quotes from the link:

"I was guessing 1-2 months until we can have certainty whether or not it'll work at all, that is having a functional proof of concept with no real performance goals yet, but which has all the right pieces in place.I think a more realistic time frame for this whole project is something like 6 months to get a first version out with the various pains dealt with, and then another endless potential for incremental performance improvements by tweaking the emitted LLVM assembly code."

"I suspect the main benefit would actually be in marketing (look how excited we're getting about python being '5x faster'), and in demonstrating that the runtime is able to adapt and be modernized, perhaps paving the path to more ambitious language and runtime improvements."

"Advantages of this plan compared to other approaches of jitting perl 5:
1. No code changes, the same intricate definitions of all of perl's opcodes are reused. this means that all the accumilated wisdom is not lost, the data structures are the same, and in theory the system is still binary compatible with compiled XS modules.
2. This means a lot less work than developing a real vm backend for perl 5 llvm's C interoperability features are key to this.
3. llvm is backed by many organizations, it's stable, well funded and has a lively community so it is unlikely to die off. This provides us with a real, feature complete jit system with very advanced optimizations that can target many platforms, without any maintenance burden on the p5 developers."


...

I eagerly await your interpretation of this potential project.

Thanks,
~ Will

Comment on Perl 5 Optimizing Compiler, Part 4: LLVM Backend?
Re: Perl 5 Optimizing Compiler, Part 4: LLVM Backend?
by bulk88 (Priest) on Aug 27, 2012 at 17:33 UTC

      LLVM is quite different to any other compiler.

      It (can) compiles to a platform-independent Intermediate Form (a sort of bytecode), that targets an idealised Virtua; Machine. Kind of like Java.

      That IF can then be converted to platform dependent machine code at compile time, or link time, or even runtime (JIT).

      It is extremely clever technology and quite unlike anything else you want to try and compare it to. It's well worth a read and a play.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.

      RIP Neil Armstrong

Re: Perl 5 Optimizing Compiler, Part 4: LLVM Backend?
by davido (Archbishop) on Aug 27, 2012 at 18:14 UTC

    The link you posted and quoted from is interesting, but it seems like a lead that has gone cold. Way back in 2009, Nicolas Clark already commented on the concept, here: http://www.nntp.perl.org/group/perl.perl5.porters/2009/04/msg145436.html, where he explained that it might be an interesting project for an intern, but would probably require too much of a time commitment from the intern's mentor (paraphrasing).

    But the reason I say it's gone cold is because the github repo is gone, and the original blog author's own URL at the bottom of the page is now dead. Without code, you're starting over again. But more importantly, it would be good to discuss with the original author why he believes it fizzled out. Maybe his wife had a baby and he got too busy to work on it. May be he didn't have enough experience or understanding. Maybe he wasn't able to show enough of a benefit to convince others to join the project and share the enthusiasm. Or maybe it was just a dead end. But it would be worth finding out before investing too much time starting over again.


    Dave

      A particular quote from that article that you cited:

      Furthermore, IMHO most apps are not even bound by those limitations, but rather by programmer laziness/sloppiness.   If better performance is a low hanging fruit that remains unpicked, JIT is really not going to make much of a difference.   Even if it runs 2x faster, it doesn’t mean it'll be 2x cheaper to run. This is the “you are not google” axiom of scalability.   Even if people want this performance, for most of them it won’t actually help their business.

      I remain unconvinced that an “optimizing compiler” would actually deliver useful results as expected, i.e. enough to justify the project.   And here’s why...   Consider a program which did 100,000 hash-table insertions followed by 10 million lookups.   How much of the time will be spent in the Perl-guts, versus the amount of time spent getting to those guts?   I suspect that the performance of this hypothetical application would be determined almost exclusively by the performance of the hash-table code within the “guts,” such that time spent generating the parse-trees and then iterating through them would be negligible.   If an edge-case situation were proffered as “justification” for this effort, I would feel obliged as a program manager to require proof that the edge-case was usefully large ... and that there existed a “project in great pain” with a substantial existing source-code base in Perl.

      Otherwise, it would be an academic exercise.   “See?   I did it!   (But so what?)”

        I've got the significant edge-case Perl code base, and I am the one "in great pain", thus my personal interest in running down this particular dream.
        I suspect that the performance of this hypothetical application would be determined almost exclusively by the performance of the hash-table code within the “guts,” such that time spent generating the parse-trees and then iterating through them would be negligible.

        And I suspect that, once again, you haven't a clue what you are talking about. Have you ever bothered to look into hv.c?

        Each Perl "opcode" has to deal with a complex variety of different possibilities.

        • Is the (hash) tied?
        • Are the hash keys unicode?
        • Does it have shared keys?
        • Is it a stash?
        • Is it a glob?
        • Does it have magic attached?
        • More ...

        With runtime compilation (or jit), it would be possible for 'simple hash' accesses/inserts/updates to bypass all of the myriad checks and balances that are required for the general case, which could yield significant gains in hash heavy code. Ditto for arrays. Ditto for strings. Ditto for numbers. (Do a super search for "use integer" to see some of the possibilities that can yeild.)

        Then there is the simple fact that perl's subroutines/methods are -- even by interpreter standards -- very slow. (See: 488791 for a few salient facts about Perl's subcall performance.)

        Much of this stems from the fact that the way the perl sources are structured, C compilers cannot easily optimise across compilation unit boundaries, because they mostly(*) do compile-time optimisations. However, there are a whole class of optimisations that can be done at either link-time or runtime, that would hugely benefit Perl code.

        (*)MS compiler have the ability to do some link-time optimisations, and it would surprise me greatly if gcc doesn't have similar features. It would also surprise me if these have ever been enabled for teh compilation of Perl. They would need to be specifically tested on so many platforms, it would be very hard to do.

        But, something like LLVM, can do link-time & runtime optimisations, because it (can) targets not specific processors, but a virtual processor (a "VM") which allows its optimiser to operate in that virtual environment. And only once the VM code has been optimised is it finally translated into processor specific machine code.That means you only need to test each optimiation (to the VM) once; and independently, the translation to each processor.

        Not the combinatorial product of all optimisations on all processors.

        What would these gains be worth? It is very hard to say, but if it gave 50% of the difference between (interpreted, non-JITed Java & perl running an recursive algorithm (Ackermann), that does a few simple additions (11 million times):

        So 83.6 seconds for Perl, and 1.031 seconds for Java!

        Perl's productivity and (1/2) Java's performance!

        That would be something worth having for vast array of genomists, physicists, data miners et al.

        Heck. It might even mean that hacks like mod_perl might become redundant; making a whole bunch of web monkeys happy. Moose might even become usable for interactive applications. Parse::RecDescent might be able to process document in real time rather than geological time. DateTime might be able to calculate deltas as they happen rather than historically.

        There are three fundamental limitations on an interpreters performance:

        1. Subroutine/method call performance.
        2. Memory allocation/deallocation performance.
        3. Parameter passing performance.

        Whilst Perl is faster than (native code) Python & Ruby, it sucks badly when compared to Java, LUA etc. And the reasons are:

        1. Perl's particular brand of preprocessor macro-based, Virtual Machine was innovative and way ahead of its time when it was first written.

          But many different hands have been lain upon that tiller in the interim, without (in many cases) understanding the virtues of simplicity that it had for in-lining, and the optimisations that came from that.

          The result is that now, many of the macros are so complex, and so heavily nested and asserted, that the best compiler in the world cannot optimise the twisted morass of code that results, from what looks like a few simple lines, prior to the preprocessor doing its thing.

          The result is that each line of the perl source is so heavily macroised, that very few people realise that the five or six lines of code that are required to construct a minimal subroutine at the perl source level, expand to dozens -- even hundreds of lines once the preprocessor has run. And that those expanded lines are so heavily blocked and nested, that they blow the optimiser stack of pretty much every C compiler available.

        2. Perl's current memory allocator has so many layers to it, that it is neigh impossible to switch in something modern, tried and tested, like the Bohiem allocaotor.

          Much less enable the recognition that the future is 64-bit, and utilise the 8TB of virtual address space to allow each class (of fundamental and user) object to use a dedicated array of exact-sized objects with a simple free list chain.

        3. It eshews the hardware optimise push/pop of parameters to the processor (c) stack (1 opcode each) in favour of (literally) hundreds of opcodes required by each push and pop of its software emulation of those hardware instructions using multiple heap-based stacks.

          Parrot suffers from a similar problem. Someone decided that rather than use the hardware optimised (and constantly re-optimised with each new generation) hardware stack for parameter passing, it was a good idea to emulate the (failed) hardware-based, register-renaming architecture of (the now almost obsolete) RISC processors, in software.

        In a nutshell, your "suspicions" are so out of touch with reality, and so founded upon little more than supposition, that they are valueless.


        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

        RIP Neil Armstrong

      Dave,

      Please see my reply to the main thread for info directly from Yuval, the author of the Perl5-to-LLVM article from 2009.

      Long story short, we're still seriously considering this as a viable development path.

      Thanks,
      ~ Will
Re: Perl 5 Optimizing Compiler, Part 4: LLVM Backend?
by Will_the_Chill (Pilgrim) on Aug 27, 2012 at 21:16 UTC
    Here, see what I've been talking about with Yuval and Reini, the authors of the original Perl5-to-LLVM link I posted...



    Yuval & Reini,

    Thank you both very much for your enlightened and informative responses copied below.

    I am quite excited about the possibility of these ideas you have proposed, in regards to Perl 5 and LLVM.

    My important goals are:

    1. Significantly Faster Perl 5 Runtime
    2. 100% Backward Compatibility w/ All Existing Perl 5 & XS Code
    3. Psychological & Political Feasibility For Adoption Into Perl 5 Core

    Am I correct in my understanding that your LLVM ideas would, at least, stand a fighting chance of achieve these goals?

    Thanks, ~ Will



    On Monday, August 27, 2012 at 5:29 AM, Reini Urban <rurban@x-ray.at> wrote:
    It's not a LLVM problem. Perl is not jit friendly, even less than python. Yuval and my idea was to split up 20% of some important generic ops into typed and directly callable ops. With LLVM it would be easy to optimize it then. But there are also other possibilities.

    On Aug 27, 2012 11:24 AM, "Will Braswell" <wbraswell@hush.com> wrote:
    Reini,

    Tell Yuval I said "howdy from Texas"! I just sent him an e-mail at his nothingmuch@woobling.org account.

    Here is a link I just got from Nick Clark, saying that LLVM was not good as a backend for dynamic languages like Perl...

    http://qinsb.blogspot.co.uk/2011/03/unladen-swallow-retrospective.html

    Maybe I should ask the LLVM people directly, what is needed to upgrade LLVM to work with dynamic languages?

    Thanks, ~ Will





    On Monday, August 27, 2012 at 6:37 AM, Yuval Kogman <nothingmuch@woobling.org> wrote:
    Well, in the while that had passed since I wrote that rant not much has changed.

    The most pressing issue is to determine really how much it's worth it, what can it give us.

    In my opinion there are two things a high quality optimizer can give us, the less important one is to give decent performance to code for which Perl is considered inappropriate now. The second is psychological and is derived from the first Good Thing™, which is that the barriers towards writing clean code (the misconception that slow is necessarily bad or that certain things are too expensive to really work) can be brought down (optimize microoptimizations out of the community ;-)).

    In short, I believe the most effective optimizer for Perl would do very effective microoptimizations across the board, favouring things that are perceived to be a problem. I don't think these are actual problems because you can always reach for embedded C, PDL, or another language to work around Perl's weaknesses, using the right tool for the job is part of the Perl philosophy, and Perl is just not the right tool for crunching lots of numbers for example.

    I'd really like to hear your thoughts on this dillema, I think when people say "optimizer" they often have very different ideas for what they'd expect, but people don't really notice how their ideas are different...

    Anyway, getting to the practical... To vet my idea we'd need some examples of the first and the second type of code we'd think would benefit. For example arithmetic benchmarks for the first (but really it should be a broader scope than just arithmetic) and stuff that is currently considered a bit taboo in Perl but that we'd like to be fast enough (for example instantiating a ton of small objects or dividing code up into really tiny functions).

    Then we can check how much of a positive impact LLVM can have by hand-refactoring only the necessary opcode PP functions for the benchmarks.

    I think this won't take very long, and by the end of it we can get a better idea of the potential of LLVM to optimize perl code only by refactoring perl core, without any incompatible changes.

    Generally speaking for any JIT implementation, Perl's stack operations and extra indirection necessitated by the current implementation of opcodes and the runloop are going to be a bottleneck so this would be a worthy endeavor even if not targetting LLVM.

    If we decide LLVM is worth it, I think the most effective way would be to write code to refactor the PP operations for us as necessary. It shouldn't be too hard and should probably handle most of the trivial cases (i.e. consistent use of macros in just the top scope with no conditionals on stack manipulation) leaving the humans to handle the complex cases.

    Anything that happens later is a total crapshoot, so I think that would be a good start.
Re: Perl 5 Optimizing Compiler, Part 4: LLVM Backend?
by bulk88 (Priest) on Aug 27, 2012 at 22:26 UTC
    Here is an -O1 Visual C Perl 5.17 disassembly of pp_add. I chose to compare pp_add to C/Asm since in C an add is typically 1 asm op. now for preprocessor output. until this whole function is reduced to a single fadd, lea, or add machine opcode, your performance will never be anywhere near C's speed. Simply using B::CC/B::C with LLVM wont work. Removing and optimizing out the Perl from perl is required. Once magic/tied and eval are added, removing Perl from Perl becomes very hard. You can't eliminate any variable access expressions, since they are tied. If I write
    #psuedo code probably sub NewUser{ $Users{$_[0]}{'Locations'} = $magicHash{'NewRecord'}->AddClientLocatio +ns($magicHash{'NewRecord'}->AddLocation($magicHash{'NewRecord'})); }
    Can you eliminate dereferencing %magicHash thrice?

    On sub entry do you scan @_ for magic? What if you make a call to another sub and it decided to tie your lexical now knows as $_[0]? What about eval (I presume any sub with an eval simply stay as legacy Perl opcodes, unoptimized to "C speed")?

    Rather than use LLVM, why not write a Perl to Javascript compiler and let the platitudes of Javascript engines duke it out? JS engines nowadays receive massive amounts of pressure and money from the public and from project managers to quickly handle larger and more bloated AJAX JS libraries every day. Some of the modern JS engines claim to do what LLVM already does with JIT to machine code.

    edit: fixed broken tags
      bulk88,
      Perlito already does this (converting Perl 5 to Javascript), and is thus on our short list of possible solutions.
      http://perlito.org/
Re: Perl 5 Optimizing Compiler, Part 4: LLVM Backend?
by Anonymous Monk on Aug 28, 2012 at 04:56 UTC

    The fundamental problem with your dream is that Perl is not standardized. Perl has no immutable compliance suite. The definition of Perl is what P5P wants it to be. There are no exceptions to this. There is no industry body that sets the standard. P5P does not work for you and will not cooperate with you or anyone else. The same way that C# is owned by Microsoft, Perl's corporate overlord is booking.com. In former years, Perl's corporate overload was ActiveState, but their toy got old and they threw it away, then booking.com purchased it. Your creation will be a fork of Perl, and the history of Perl is littered with non-compatible offshoots such as PHP, Ruby, and Kurila.

    Creating any sort of compiler, besides what passes for a compiler in Larry's Perl, enables closed source software to be written in Perl. Inasmuch as this is a great unforgivable sin in the open source world; you have made great enemies with P5P. P5P will subtly ensure that you will never be 100% compliant with P5P's Perl implementation. If your improved VM becomes a successful threat to the goals of P5P and its owner, TPF will litigate you for trademark infringement and prevent you from claiming compatibility with Perl 5. Take a lesson from Larry Wall who is the creator of Perl 5, and its stack-based architecture. He abandoned it because it was fatally flawed and the cabal behind it was resistant to change. You should follow his example.

      I hope everyone interprets this as satire.

      Anonymous Monk,

      Could you please clarify what you mean by Booking.com being Perl's corporate overlord?

      My goal is to find a solution that will be politically and philosophically acceptable to P5P so it can be adopted into the Perl 5 core.

      My goal for compilation is not to write closed source software, my goal is only to optimize runtime performance.

      Thanks,
      ~ Will
Re: Perl 5 Optimizing Compiler, Part 4: LLVM Backend?
by MonkOfAnotherSect (Sexton) on Aug 28, 2012 at 04:56 UTC
    Will,

    You may be interested in reading up on the experiences of Unladen Swallow, which was the project which aimed to make Python "5x faster" using an LLVM backend, but ended up being abandoned (there were some good changes/additions made as a result, mind). There have been a fair few attempts at speeding up Python significantly, and many have been promising for a subset of the language, and less promising once implementing all the dynamic features come into play.

    Incidently re previous thread's comment about RPython (used for PyPy) -- it's a subset of Python, and not a separate language per se. Development was thus able to be bootstrapped on CPython. The idea of attempting to use it to implement Perl -- 5 or 6 -- in full, with its separate semantic nuances and corner cases is courageous.

      MonkOfAnotherSect,

      I am generally familiar with the Unladen Swallow saga, and what it revealed about LLVM being less-than-awesome for dynamic languages. Still, I think LLVM may be the best potential target for a Perl 5 optimizing compiler.

      I am now leaning more toward LLVM than RPython simply because it will keep everything in Perl/C instead of introducing a non-Perl/C language into the mix. Still, I think RPython is awesome and I hope to learn from their relative success.

      Thanks,
      ~ Will
Re: Perl 5 Optimizing Compiler, Part 4: LLVM Backend?
by dave_the_m (Parson) on Aug 28, 2012 at 18:58 UTC
    Having closely followed these threads, plus based on some private correspondence, my gut reaction is that there is no system discussed so far which meets all of the following criteria:

    • handles all (or practically all) existing Perl syntax and semantics;
    • doesn't require modification of existing Perl source (e.g. requiring you to add type declarations);
    • provides an order-of-magnitude speed-up for general Perl code; (e.g. 5X rather than 10%);
    • doesn't require a huge coding effort (of a similar magnitude to implementing parrot and perl6)

    I'm not saying at this point that all of the proposals definitely fail these criteria; rather that no-one has yet explained any proposal to me in such a way that I have a real "Ooh I see how that might work!" epiphany; and my suspicion is that no-one ever will.

    Dave.

      Full agreement. None of these are possible in a year without a small army of the right coders, and even then a year's a short time to produce something as reliable as Perl 5.

        dave_the_m & chromatic,

        I think BrowserUK's 3-phase idea (pasted below) and Yuval's comments are both in the same vein. I think this general Perl5-to-LLVM concept is valid, and although it might very well take more than a year to fully implement, I believe we could have some kind of initial demo ready by YAPC::NA 2013 in Austin.

        dave_the_m, discounting only the amount of work needed to fully implement Perl5-to-LLVM, would you please tell me which part of BrowserUK's 3-phase idea is not producing the "I see how that might work!" epiphany in your mind?

        Thanks,
        ~ Will


        BrowserUK wrote:

        1. There is the bit of perl that parses the source code and builds the AST from the Perl programs source. This would need to be left pretty much as is. The whole perl defines Perl thing. This would need to be compiled (back to) C and then linked into an executable.

        2. Then there is the bit that converts the AST into byte code. I believe that this would need to be separated out and converted to produce IF.

        3. Then there is the bit of perl that ordinarily runs the bytecode. Not just the runloop, but all the code the runloop dispatches to. I think that should be compiled to IF and built into an IF library (.bc) It would be "combined" with the IF from stage 2, at runtime, and given to the JIT to convert to machine code.
Re: Perl 5 Optimizing Compiler, Part 4: LLVM Backend?
by Will_the_Chill (Pilgrim) on Aug 29, 2012 at 05:02 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://989940]
Approved by bulk88
Front-paged by bulk88
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (4)
As of 2014-09-21 15:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (172 votes), past polls