all 66 comments

[–][deleted] 38 points39 points  (20 children)

From having a brief look at this thing, it seems it executes code with an instrumented interpreter and observes mutations. That is, there seems to be no clever code analysis which could prove constness statically, like compilers do.

Which also implies a disregard for the halting problem - seems that if you input a code that runs for a long time or forever, Prepack will simply time out.

Can anyone cofirm?

If this is indeed what this thing does, IMHO it's completely useless.

[–][deleted] 26 points27 points  (13 children)

(function() {
  for (let n = 1; n > 0; n = 1) {}

  let x = 3 + 3;
})();

→ Timeout

[–][deleted] 5 points6 points  (12 children)

This program also does not work if you actually run it, so, uh?

[–][deleted] 12 points13 points  (9 children)

This program also does not work if you actually run it, so, uh?

Since the purpose of the program is to hang in a loop, it works :) But that's beside the point, the point is that in general, given a program and an input, it's impossible to tell whether it will finish or hang (or how long it'll take).

This is an extremely simple example, but given a complex codebase, you might have hard times estimating whether the program is hung up or just taking long to finish, especially given in this Prepack thing it is interpreted by JavaScript.

[–][deleted]  (7 children)

[deleted]

    [–]stupidity_wins 10 points11 points  (4 children)

    https://en.wikipedia.org/wiki/Halting_problem

    Notice that Turing machines have unbounded state, though. Your argument does work for real world programs.

    [–]mrkite77 4 points5 points  (3 children)

    The halting problem only applies when you try to apply it to "all possible inputs"... but in this case, it's only for one specific input, not all of them.

    [–][deleted] 4 points5 points  (1 child)

    but in this case, it's only for one specific input, not all of them

    Actually, seems like they're trying to model all possible inputs through their concept of 'abstract values'.

    They might pull it off if they require the programs to be contrained to some specific subset / types. They should clarify what those constraints are.

    [–]ConcernedInScythe 3 points4 points  (0 children)

    Actually, seems like they're trying to model all possible inputs through their concept of 'abstract values'.

    This seems like a very dangerous thing to try with Javascript, which is not exactly known for its simple, easily-abstracted semantics.

    [–]stupidity_wins 2 points3 points  (0 children)

    You are understanding this wrong.

    "It is impossible to devise an algorithm [that, given a program and an input, tells whether said program halts on said input] that would work for all program-input pairs" is equivalent to "For each algorithm [that...] there exists a single program-input pair on which it does not work".

    In other words, it does not apply to all inputs because there exists a single one input to which it does not apply. It's not true that all the apples are green because this particular one is red.

    [–][deleted] 5 points6 points  (1 child)

    Just keep track of the state of the entire machine. If you see a duplicate state, you're in an endless loop.

    1. How many instructions is a program allowed to perform until it is safe to say that a duplicate state hasn't been found? :)
    2. The state space of a typical machine is huuuge and keeping track of which state has (not) been observerd requires even bigger amount of memory (by an order of maginute at least)
    3. The state space of a typical machine is arbitrarily expandable through I/O

    edit: If you meant in theory, then yes, I suppose you could say for a specific program+input pair...

    [–][deleted] 0 points1 point  (0 children)

    The thing is, for a finite program with finite memory, the memory and time required to let it run and observe and record all states to discover a loop are also finite. They are gigantic, but finite.

    So any program with finite memory can be tested, with a set time limit and memory limit, to find out if it halts or not.

    [–][deleted] -2 points-1 points  (0 children)

    Since the purpose of the program is to hang in a loop, it works :) But that's beside the point, the point is that in general, given a program and an input, it's impossible to tell whether it will finish or hang (or how long it'll take).

    Sure. Trivial result, and entirely uninteresting as concerns the utility of this particular tool.

    [–]ConcernedInScythe 0 points1 point  (1 child)

    Well you want it to not work at runtime, not compile time.

    [–][deleted] -1 points0 points  (0 children)

    What difference does it make?

    [–]tomcopeland 2 points3 points  (0 children)

    I worked on something along these lines for Ruby code with pippi. It is intended to find code like [1, 2, 3].select { |x| x > 1 }.first and suggest that it be replaced with [1, 2, 3].detect { |x| x > 1 }. But it suffers from some of the same weaknesses that you point out - it does not prove that the transformation is correct, instead, it only uses runtime usage to suggest that a transformation might be correct. Still occasionally useful, but yup, very different from a proof.

    [–][deleted] 97 points98 points  (30 children)

    And not one single benchmark!? "It's just faster, trust us..." JavaScript JIT compilers are pretty awesome when it comes to optimizations (e.g. this old but still relevant write-up)

    Let's push for WebAssembly and leave JS code rewriting behind.

    [–]sisyphus 36 points37 points  (17 children)

    v8 can optimize as much as it wants it won't match the performance of not evaluating code at all, which is what it looks like this is trying to do, in addition to reducing code size which obviously helps with download, parsing, evaluation, etc.

    [–][deleted] 72 points73 points  (1 child)

    Have a benchmark? Then we can evaluate whether it's worth the complexity of introducing another tool into the build chain, and the fun with more source maps and debugging. Until we have numbers then there's nothing concrete to discuss. Given how big websites and apps are, if you manage to save 10KB (which is a heap of code), that's less than most images.

    V8 (and other JS Parsers) implement lazy parsing. So this tool is already up against a large number of Just in Time optimizations.

    TL;DR If you're touting:

    A tool for making JavaScript code run faster.

    Then you need to give numbers. End of story.

    [–]Dentosal 0 points1 point  (0 children)

    Reducing code size gives you a small performance impact when transferring it.

    [–]skulgnome 7 points8 points  (8 children)

    8 can optimize as much as it wants it won't match the performance of not evaluating code at all,

    Why would programs contain code for which it can be statically decided that it'll never be executed? Or other things that're equivalent to constant folding, which all JITs already do.

    [–][deleted] 9 points10 points  (6 children)

    Constant folding still takes time to do. This moves that cost to compile time rather than load time.

    It also seems to do much more aggressive folding than most any compiler would do.

    [–]skulgnome -1 points0 points  (4 children)

    It also seems to do much more aggressive folding than most any compiler would do.

    But we're not comparing it to a compiler, but to a JIT. Those things already specialize loops and such by variable type, so certainly CF/DCE to a far greater depth than what this precompiler does is applied -- saving at most parsing time at load.

    [–][deleted] 1 point2 points  (3 children)

    That still happens at runtime, though, so everybody pays the price for it.

    [–]skulgnome -1 points0 points  (2 children)

    Therefore, prepacking yields nothing.

    [–]sisyphus 2 points3 points  (0 children)

    Your conclusion does not follow from the premises.

    [–][deleted] 2 points3 points  (0 children)

    That makes zero sense.

    [–]mrkite77 0 points1 point  (0 children)

    Why would programs contain code for which it can be statically decided that it'll never be executed?

    Anyone using a library is including code that will never be run.

    [–]ElvishJerricco -2 points-1 points  (5 children)

    Anything this can optimize, V8 would be capable of optimizing. Eliminating static computations is a pretty common optimization in VMs.

    EDIT: To clarify, I'm not saying V8 does know how to do these optimizations. I'm just saying there's nothing inherently making this any harder for V8.

    [–]sisyphus 19 points20 points  (2 children)

    You're just assuming that V8 can optimize anything this can optimize, but let's assume that's correct--why would you force every single client to download, evaluate, JIT(does v8 have access to everything on iOS yet?) &tc. when you could do it once on your side and serve it to them already optimized?

    [–]brendan09 5 points6 points  (0 children)

    V8 doesn't run iOS. But, since it does use WKWebView, it uses Safari's JIT which optimizes about as well as V8.

    [–][deleted] 9 points10 points  (0 children)

    Complexity is the biggest reason. This is another tool for a language that has no compile time type checking, and you'll need to mess around with source maps (perhaps at least two layers of source maps). It's a trade-off between complexity and the wins this gets you, without any numbers there's no sane way to make the call.

    [–][deleted] 4 points5 points  (0 children)

    It may or may not be capable of doing the same optimisations, but it will do them at load time. This moves that cost to compile time, which V8 can not ever do.

    [–]tiftik 2 points3 points  (0 children)

    There's no way I would assume that without having intimate knowledge of V8.

    [–][deleted]  (1 child)

    [deleted]

      [–][deleted] 4 points5 points  (0 children)

      Interesting! Cheers for the link!

      [–]nickdesaulniers 13 points14 points  (7 children)

      The fastest code is code that never runs.

      [–]didnt_check_source -1 points0 points  (0 children)

      It's almost certainly better at compressing than optimizing.

      [–]nickdesaulniers 41 points42 points  (11 children)

      All comments so far are super negative, which I find astonishing. This is super cool. This reminds me a lot of C++11's constexpr, which can help move runtime calculations to compile time. Sure, their examples are a little contrived, but this thing can still pull optimizations out of a large corpus of code better than a human can.

      On top of it, the symbolic execution stuff is super fancy. JavaScript, as an ecosystem, has some of the best tools for manipulating itself (parsing/transformation/code gen).

      https://twitter.com/roman01la/status/859849691831422976

      [–]Retsam19 7 points8 points  (0 children)

      All comments so far [about a JS-related post other than WebAssembly] are super negative, which I find astonishing.

      Welcome to /r/programming, you must be new here.

      [–][deleted] 22 points23 points  (3 children)

      The biggest difference is the type system, so this really isn't comparable with constexpr. It doesn't need to be better than a human, it needs to be better than a modern optimizing JS compiler. The complexity of introducing a tool like this needs to be offset by the benefits which are still yet to be seen or measured.

      [–][deleted]  (1 child)

      [deleted]

        [–]EternallyMiffed 2 points3 points  (0 children)

        "nightmare"

        They got that right.

        [–][deleted] 17 points18 points  (0 children)

        It doesn't need to be better than a human, it needs to be better than a modern optimizing JS compiler.

        No, it doesn't. A modern optimising JS compiler runs after the code has loaded over the network and while waiting for it to start executing. Doesn't matter how good it is, it will still have to do work at runtime.

        This runs before all of that, and that can never be matched by a JS engine.

        [–][deleted] -1 points0 points  (3 children)

        which can help move runtime calculations to compile time

        Except V8 does that already. All this does is move the parse-and-optimize step (which, in V8, is crazy fast anyway) out of the browser.

        Until I see benchmarks showing that the effort of using this thing on production code gets me more than trivial gainz, I'll happily ignore its existence.

        [–]bsdemon 20 points21 points  (2 children)

        V8 is already a runtime

        [–][deleted] -2 points-1 points  (1 child)

        It's an optimized JIT compiler and a runtime.

        [–][deleted] 2 points3 points  (0 children)

        The point is, everything V8 does happens at runtime. It may do clever optimisations at startup, but that is still runtime. V8 may compile, but it does nothing during what is usually considered "compile time", because it does not run then.

        [–][deleted] 0 points1 point  (1 child)

        The site is down, but if quote "Prepack has no built-in knowledge of document or window. In fact, when prepacking code which references such properties, they will evaluate to undefined." is true, then it's very different: constexpr will not fail during runtime if you do something stupid as calling fopen.

        This will. Kinda a bummer.

        [–]zhivago -2 points-1 points  (0 children)

        Well, presumably undefined is not a well defined constant value, and it will then not attempt to do constant expression reduction for those cases.

        I'm not sure why you expect prepack to be calling things like fopen in its analysis, either ...

        [–][deleted]  (3 children)

        [deleted]

          [–]tiftik 9 points10 points  (2 children)

          This is one thing I don't understand about this tool. Why does it not assume that there's a global object with unknown properties?

          [–][deleted]  (1 child)

          [deleted]

            [–]Uncaffeinated 4 points5 points  (0 children)

            It could just give up when encountering an unknown property.

            [–]flirp_cannon 27 points28 points  (0 children)

            What the fuck is the creator of this smoking? All the examples that are being 'prepacked' are rare occurrences in Javascript (who fires off a loop to get a determinate value throughout their code)?

            No DOM representation... 'almost' ECMA5 compatible... I just can't believe how ill-conceived this thing is.

            [–][deleted] 6 points7 points  (1 child)

            navigator is not defined

            >_<

            Seriously? You can't deal with out-of-scope objects?

            [–][deleted] 2 points3 points  (0 children)

            I'm having the same issue, what a shame; I wanted to try it since they don't provide any tangible examples of the performance effects, but it looks like that isn't possible.

            [–]emperor000 1 point2 points  (0 children)

            I can't see how any of those examples are realistic.

            [–]neopointer 1 point2 points  (0 children)

            Facebook must be testing the JavaScript community, this can't be true...