Dead Code Elimination for Beginners

http://blog.mozilla.com/rob-sayre/2010/11/17/dead-code-elimination-for-beginners/

by kinetik • 16 years ago

121 57 16 years ago

blog.mozilla.com

ashish01• 16 years ago

Follow up on : http://news.ycombinator.com/item?id=1913102

kenjackson• 16 years ago

I highly recommend reading this article.

Although it does point out one reason that JS is a poor language to be the foundation for client-side web computing: It's extremely difficult to optimize a language this dynamic. I honestly think we could be leaving 50% perf improvement on the floor due to the dynamic nature of the language.

And this is on top of the fact that you already have to reduce the amount of time spent optimizing since you don't compile the code ahead of time (most optimistically using a JIT of some sort).

Can we please move away from JS and move to a nice IL?

jbjohns• 16 years ago

>Can we please move away from JS and move to a nice IL?

A thousand times this. The web is playing a bigger and bigger role in computing but IMO it's hamstrung a bit by having it's "assembler" Javascript. I think a lot of developers are just going to use some other language that compiles to Javascript anyway, why not give us an "assembler" option.

xiongchiamiov• 16 years ago

Well, Silverlight claims to give me the ability to write client-side Ruby and Python, but the last time I tried Moonlight it consistently crashed Firefox...

rbanffy14• 16 years ago

> I think a lot of developers are just going to use some other language that compiles to Javascript anyway

That's a disgusting thought...

What happens is usually developers who don't want to program in more than one language (or One True Language, as many of them may think) rely on such tools to generate an unreadable, sub-optimal and utterly messed up tangle of JavaScript code that kills a baby jesus every time it runs.

And who then blame JavaScript for their problems. And downvotes anyone who disagrees with them ;-)

nickik3• 16 years ago

You don't get the problem that needs solving. JS is hard to optimize so even if you compile to it from a other language you going to end slow because of the bottelnack of JS. If we had a IL that is good to optimize language that compile to we could get to much faster speeds in the browser.

liuliu• 16 years ago

I don't think that it is possible to replace JS with a nice IL in near future due to the momentum it gathered all these years. However, is it possible to suggest a strict subset of JS that is easier for interpreter to optimize on? If that can be done, I am happy to write code with less flexibility but can run thousands faster.

evanrmurphy• 16 years ago

Neat idea. Which subset of the language could be better optimized by interpreters?

JoachimSchipper• 16 years ago

You can get most of the benefits of not being ridiculously dynamic without switching to a new language. Take a look at http://www.iro.umontreal.ca/~gambit/doc/gambit-c.html#Defini...: Gambit Scheme (a Lisp) has a (declare (block)) form to tell the compiler that all variables defined in the current file will not be overwritten outside the current file, and a (declare (standard-bindings)) form to tell the compiler that the standard Scheme functions are not overwritten. With proper use of these options, Gambit is quite fast.

Javascript could have a "fixate foo bar qux" command that did something similar. Of course, for best results, it would need to fixate the current foo bar qux, as Javascript frameworks seem quite keen on overriding the standard functions. I'm sure it would be a pain to implement, but...

rbanffy14• 16 years ago

> JS is a poor language to be the foundation for client-side web computing

> I honestly think we could be leaving 50% perf improvement on the floor

Unfortunately, humans have not got significantly faster (or smarter) in the last couple thousand years, as opposed to computers, that get twice as fast every 18 months or so.

Dynamic languages, by placing the burden of optimization on the compiler/runtime are making the right bet. Static-typing is little more than a human doing the machine's work, often at the expense of introducing subtler bugs (the compiler catches the obvious mistakes and that may leave programmers with a false sensation of security).

> Can we please move away from JS and move to a nice IL?

As for moving to precompiled, possibly obfuscated scripts, I would much rather concede a little less dynamism on the language and move the compiler into the browser. You could, conceivably, declare the type of arguments and return values and rather easily, in that case, perform some optimization as the code is parsed.

I have no love for JavaScript. It's a little tortured language that I am sure passed through a lot more marketing specialists than needed before taking its current form and bears the scars from that process. It has, however, some good parts that are very good.

sid09• 16 years ago

> Static-typing is little more than a human doing the machine's work

Interesting. I look at (good: e.g. ML or Haskell) static typing as the machine doing the work that a human would have to do in a dynamic language. Especially type inference.

jerf• 16 years ago

This is a false dichotomy. You can have a dynamic language that isn't as insane to optimize for as Javascript (or Python).

Do you really need to be able to override the valueOf method on an integer?

Lua manages to be both dynamic, and to play with the big compiled boys on the Compiler Shootout with its JIT. I don't know the details but I suspect it is because its dynamicity is carefully designed with an eye to the cost/benefit tradeoffs, instead of always choosing to make things dynamic regardless of the costs. How much time does a straightforward implementation of a conformant Javascript interpreter actually need to spend looking up and executing "valueOf", anyhow? The vast bulk of those will be wasted.

With the nature of Javascript even "optional type declarations" are easier said than done; you not just to specify "an int", but "an int that you have not mucked with the prototype of, or any of the prototypes of the parent objects", and that's actually a declaration that intrinsically fights against the nature of the language. Actually propagating such things out will eventually create an implicit dichotomy matching the much-maligned Java difference between objects and primitive types, only in a language where it was bolted on a decade after the fact instead of at least being in there since day one (of public release).

It's an interesting enough language but it's not really suitable for use as the base level of a tech stack. Nevertheless, it will be forced into that role. (It's not like there's actually a choice of a really well-designed tech stack out there that can replace the web, it's all various incoherent pieces bashed on by monkeys until it mostly works most of the time. Not really trying to be sarcastic here, this is a realistic assessment, IMHO.)

shadowfox• 16 years ago

> Dynamic languages, by placing the burden of optimization on the compiler/runtime are making the right bet.

It is a good idea to let the compiler/runtime do work for you.

But highly dynamic structures make some kinds of static analysis (which the compiler needs to do to optimize) really hard and often undecidable. We need a pretty good (hotspot like) JIT in the runtime to compensate.

jsvaughan4• 16 years ago

this is pretty damning for ie9 js performance isn't it? they are going to have to rework their static code analysis and it sounds like they don't have the js knowhow - what else might they incorrectly be optimizing?

rbanffy14• 16 years ago

> this is pretty damning for ie9 js performance isn't it?

I think the whole point of the post is to poke fun at how Microsoft is cheating the benchmark and how it was caught. The part on the definition of Angles and that the "optimizer" should throw an exception it doesn't (most probably because it's not optimizing anything) is hilarious.

sid09• 16 years ago

The part on the definition of Angles and that the "optimizer" should throw an exception it doesn't (most probably because it's not optimizing anything) is hilarious.

What are you talking about? That code is getting optimized away into a no-op when it shouldn't be, which is why no exception is thrown. This means that

a. the optimization is definitely happening

b. it is unsound

jsvaughan4• 16 years ago

Mmm but this goes beyond cheating on the benchmark - that func(1,2) example is atrocious. You could (possibly) understand them having a direct match on the math-cordic benchmark to deliver a super-optimization, but they've also got general dead code removal wrong.

larsch• 16 years ago

What are the real benefits of dead code elimination on actual production code in real applications? Seems to me that only synthetic tests contain dead code (by intend) whereas dead code in production code is by definition unnecessary and, by most coding standards, a bug.

nickik3• 16 years ago

Not true, a compiler can find deadcode where a developer could not find it.

kd0amg• 16 years ago

The compiler itself may introduce a fair amount of dead code related to temporary variables created during code generation, and some optimizations can reveal dead code that previously looked live.

saucetenuto• 16 years ago

It's important to be able to delete dead code even if your developers never write any, because earlier compiler optimization passes can create dead code. For example, consider this simple function written in a hypothetical dynamic language:

  function add(a,b) { return a + b }

Our hypothetical compiler turns this function into some IL that looks like this:

  function add1(a,b)
  {
    if(is_null(a)) throw ArgumentNullException()
    if(is_null(b)) throw ArgumentNullException()
    low_level_generic_add(a,b)
  }

...where low_level_generic_add sums a and b if they're integers, or looks for a suitable overloaded operator+ and invokes it if they're not.

Suppose further that our hypothetical language has a tracing JIT, and that most of the time when a and b are called, they're both integers. In that case, the compiler might perform the following transformation:

  function add2(a,b)
  {
    if(is_integer(a) && is_integer(b)) return add_integers(a,b)
    else return add_generic(a,b)
  }

...where add_generic is just a copy of add1 above, and add_integers is a copy of add1 with low_level_generic_add() replaced by the less-expensive perform_integer_addition()

  function add_integers(a,b)
  {
    if(is_null(a)) throw ArgumentNullException()
    if(is_null(b)) throw ArgumentNullException()
    perform_integer_addition(a,b)
  }

But suppose one more thing: let's say integers in this language are value types; that is, that is_null(some_integer) is never true. Then you can get another performance win in add_integers by removing the two null checks - but you can only find out about that if you have a dead code detector.

This has been your woefully incomplete dynamic compilation moment.

Dead Code Elimination for Beginners

Related Stories