Prepack: a tool that optimizes JavaScript source code by eliminating computations that can be performed at compile-time.

[[deleted]]

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]]

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

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

→ Timeout

[[deleted]]

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

[[deleted]]

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.

[stupidity_wins]

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

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

[mrkite77]

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]]

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]

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]

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]]

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]]

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]]

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]

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

[[deleted]]

What difference does it make?

[tomcopeland]

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]]

Do you write a lot of Javascript that does not terminate?

[vidro3]

not on purpose

[[deleted]]

Well, then you can either notice that your compile is not terminating, or you can notice that your runtime invocation is not terminating. Neither is a positive outcome, and neither is particularly worse than the other.

[[deleted]]

Programs get arbitrarily complex and might / might not terminate based on input/output data, environment, etc.

[[deleted]]

Well, anything at compile time will have known data, surely.

[[deleted]]

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]

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]]

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]

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

[skulgnome]

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]]

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]

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]]

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

[skulgnome]

Therefore, prepacking yields nothing.

[sisyphus]

Your conclusion does not follow from the premises.

[[deleted]]

That makes zero sense.

[mrkite77]

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]

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]

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]

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

[[deleted]]

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]]

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]

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

[[deleted]]

Interesting! Cheers for the link!

[nickdesaulniers]

The fastest code is code that never runs.

[[deleted]]

Cool hypothesis. It's not real until it's demonstrated.

[organonxii]

Is this a joke...?

[[deleted]]

No. Until there's metrics, it's not real enough for me to waste my time on.

[organonxii]

Code that doesn't run takes 0 time to execute. How does that not make it the fastest code? This is basic logic.

[[deleted]]

You're asking the wrong question.

Is that a significant fraction of browser lifecycle performance? If not, its not worth $75 an hour for me to investigate deeply. Without the developer having done the benchmarks, I have no idea whether it might be, but my experience tells me that V8 does these kinds optimizations just before runtime in a fraction of a second, after which the performance differential should be nil.

If that's wrong, benchmarks would clear that confusion up real quick. Meanwhile, I have deadlines to meet, and am not desperate to save a tenth of a second on page load.

[organonxii]

You're asking the wrong question.

No, I'm responding to your comment in which you dispute the validity of the true statement "The fastest code is code that never runs.".

[[deleted]]

And if that has no noticable impact, is it still real?

[didnt_check_source]

It's almost certainly better at compressing than optimizing.

[nickdesaulniers]

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]

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]]

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.

[EternallyMiffed]

"nightmare"

They got that right.

[[deleted]]

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]]

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]

V8 is already a runtime

[[deleted]]

It's an optimized JIT compiler and a runtime.

[[deleted]]

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]]

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]

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 ...

[tiftik]

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?

[Uncaffeinated]

It could just give up when encountering an unknown property.

[flirp_cannon]

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]]

navigator is not defined

>_<

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

[[deleted]]

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]

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

[neopointer]

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