Ralph Sommerer's Budget Wisdom

Tales of Mystery and Evaluation

Updated below

For reasons that I don't want to talk about right now I've read the JavaScript specification (ECMA-262, 3rd edition) when I stumbled upon a small mystery. It'd be more of a challenge than a mystery if the major Web browsers and their JavaScript engines didn't totally disagree on what is the correct answer.

Here's the problem. If you want to compile JavaScript to native code (see one of my earlier blog posts on why you would want to do this) you need at one point to decide where to put all the data, especially the local variables, so the CPU can find the stuff when it's executing the code. It's like the table of content in a book (no, it isn't but for the sake of argument let's pretend it is). If value can't be found in the local scope of a function it must be in either an intermediary scope (because function definitions can be nested) or in the global top-most scope. Where the values are at run-time can be determined at compile time, i.e. the compiler can (and will) generate code (the "table of content", if you will) to locate the value.

The problem is that there's a JavaScript feature called eval that evaluates a JavaScript text piece handed to it as argument. What happens if the text piece contains a variable declaration? Note that by the time the processor executes the code and calls the eval function all variables and values are set in stone (or code, rather). Or are they?

Variable instantiation is performed using the calling context's variable object and using empty property attributes. [ECMA-262 3rd ed. p 39]

This cryptic language means that variables declared in an eval call are to be added to the calling context's table of content. Ouch! How do you change at run-time what is supposedly fixed at compile time? Let's take some JavaScript code, execute that within all major browsers and see what they do.

var a=3;
function w(e,r)
{
  var c=2;
  e(r);
  return c+a;
}

I print the result of the following calls, followed by the value of a:

w(eval,"var a=5;")
w(eval,"c=1")
a

Note that w is just a intricate way of calling eval without the compiler or interpreter knowing. Here's the fun bit: All major Web browsers and their respective JavaScript engines produce different results.

This explains everything. Apparently, even the demigods at Mozilla or Google don't know how to implement eval correctly. On the other hand, IE rocks! Albeit very slowly ...

Update

Well, it appears that the Firefox people do the right thing after all, albeit by taking the easy way out, that is to say, by implementing the ECMAScript standard's fifth edition. According to ECMA-262 5th ed.

indirect calls to the eval function use the global environment as both the variable environment and lexical environment for the eval code. In Edition 3, the variable and lexical environments of the caller of an indirect eval was used as the environments for the eval code.

That sounds much more reasonable, and is far easier to implement. Kudos to ECMA. Firefox now rocks, too, admittedly.

On JavaScript performance in IE8

Although I'm not technically a Microsoft employee anymore (I left Microsoft Research, Cambridge, at the end of 2006), I still consider myself friendly with Microsoft and have, for various reasons (including stock), a certain residual interest in the well-being of the company. Also, to be honest, while I didn't regret leaving Microsoft Research all too much (it wasn't quite the MSR I joined in 1998), I liked being with Microsoft, and would, if the circumstances were right, return without too much hesitation. That's why I'll keep adding to this blog until it gets shut down for the reasons stated in the first sentence.

In the course of my being "friendly with Microsoft", I read somewhere that when IE8 was released in beta 2 somebody said that performance benchmarking(...) was a secondary priority. Then Google's Chrome browser and Firefox started bragging about their JavaScript performance and hitting one another over their heads with benchmarks that proved their respective engines to be orders of magnitudes faster than anything seen before, including IE8, and I thought the bit about "secondary priority" a bit awkward. I'm not a compiler expert, but I have some experience in that field that enables me to make a few mildly informed guesses about what you can do - even without too much effort. And even without making performance first priority, there's something called state of the art, and both Chrome and Firefox have just established what that entails. And it rhymes with "native code".

Firefox (TraceMonkey)

Firefox' next generation JavaScript implementation employs a technique called Trace Trees to compile JavaScript "just-in-time" into native code. The unit of compilation is neither a function (as it is common in Java JITs), nor a code file (as in C), but a trace, i.e. a sequence of instructions that the interpreter has been executing several times. Usually, this constitutes the body of a loop, or, more precisely, a specific path through a loop. Thus, frequently taken paths through a JavaScript program will be executed in native code, while the remainder is still interpreted. Specific properties of such a trace render it suitable for certain optimizations, mainly to eliminate common sub-expressions. The bulk of the speedup, however, is due to the execution of significant (or important, rather) parts of the program in native code.

Chrome (V8)

As far as I understand, the V8 runtime features a compiler that compiles all JavaScript code (the contents of an external file or the stuff between <script> tags) into native code. That's where the bulk of its perfomance is coming from: there's no interpreter, just native code. Furthermore, it employs an optimization technique to speed up member accesses of objects (methods or fields), by creating some sort of "classes" behind the scene whenever an object's field is written. By constructing these "classes" the compiler can generate (static) offsets to access fields instead of requiring runtime-lookups in the object's dictionary.

SquirrelFish Extreme

Webkit's "extreme" JavaScript engine employs several techniques to improve performance, including bytecode optimizations (within and across bytecodes), a so called Polymorphic Inline Cache to speed up member accesses similar to the technique employed by the V8 engine above, and also a context threaded JIT compiler. While you can get significant improvements by optimizing interpreted bytecode, both by optimizing the codes themselves, and by providing special bytecodes for frequent bytecode combinations, I suspect that the biggest performance increment is due to the JIT compiler and, hence, parts of the program running in native code. Note that compiling to native code above all gets rid of the interpreter loop which constitutes a significant portion of the instructions a processor needs to execute.

IE8

Despite what they appear to perceive as impressive performance gains in IE8's (beta 2) JavaScript engine, compared to Chrome's V8 or Firefox' TraceMonkey, these gains cannot reasonably be called anything but fiddling around the edges. Unless the JavaScript engine used in IE (and elsewhere) employs some sort of compilation to native code, it will always lag behind its competitors with respect to performance. From what I gather in their Channel9 appearance they have made improvements in bytecode execution, but their main targets were JavaScript native objects (Array, String, ...) and JavaScript-DOM-interaction. That leaves the matter of compilation to native code unresolved. With the formidable competition racing for the top spot in their tailored-for-their-engine benchmarks, I believe it's time for Microsoft to do what it does best: compete to kill win!

To that end, I'm proposing adding a one-pass compiler to Microsoft's JavaScript engine. That's neat and simple and should restore Microsoft's standing within the JavaScript engine competition. There's really no reason not to try, but as I expect objections galore, here's a (p)rebuttal of the most common ones:

• Compiling all JavaScript to native code is too slow (startup-time wise)
  Wrong. First, V8 does it, too, and it beats the hell out of IE's JS engine. Also, as any compiler builder knows, a non-optimizing compiler spends easily 60% of the compilation time in the tokenizer, and tokenizing is what you have to do anyway, even in an interpreter. Nonetheless, I remember one of the Oberon compilers built by one of the graduate students at ETH for a HP Unix workstation that compiled itself in some 2.2 seconds. That's 2.2 seconds to compile the whole compiler, and that was 12 years ago when a 133 MHz PC was considered state of the art.
• Building a compiler is complicated. You cannot hurry it
  That's why I'm proposing a single-pass compiler. Get one of the Visual Studio compiler people(preferably one of the back-end crowd), hand her the source code of the JavaScript engine which, I presume, generates some sort of intermediary code to be interpreted, and have her change it to produce native code instead. I'd be surprised if it takes her more than 4 weeks to do it. It needn't be optimized. Above Oberon compiler wasn't, and... well ... 2.2 seconds!!!
• If we even think of doing it, we should do it right
  Oh, well. That's the pretext not to do it at all. So much for the 80/20 rule. Couldn't they just do it first, and then do it right? I guess a simple single-pass compiler would bring IE within 80 to 90 per cent of V8, and perhaps equal TraceMonkey in generic, i.e. non-optimized-for-TraceMonkey benchmarks, because, after all, TM compiles only parts of the program, albeit these maybe slightly better. As I've highlighted above, the bulk of the performance of above engines can be attributed to their running native code, and not necessarily the kinds of extra optimizations that each performs in addition (although these can be significant, too).

So, even if the actual JavaScript performance may not be the most significant contributor to the overall performance of an AJAX application (DOM access, string performance, etc. are perhaps equally significant) I tend to consider this a matter of pride, and would like my engine to be the fastest on the planet, or at least within the league of all competitors'. Hence my challenge. Any takers?

Target JavaScript: GWT, Script# and Oberon Script

The paper on Oberon Script that I submitted to the Joint Modular Languages Conference (JMLC 2006), and that I wrote about in my last post was accepted. Thank you! In the mean time, two toolkits were announced to the public that allow developing AJAX-style Web Client Applications (WCAs) in a high-level language which is then compiled to JavaScript as a high-level object code. The two are Google's Web Toolkit (GWT), based on Java, and ASP.NET architect Nikhil Kothari's Script#, based on C# (snappy name, by the way, isn't it. "GWT" looks rather clumsy next to it, and too close to GWB for comfort). I haven't tried any of them yet, but the code examples look promising (in particular the JavaScript translations). I can see a few problems developing in a "foreign" i.e. non-script environment, but perhaps that's just superficial.

Anyway, the main difference between GWT and Script# on the one hand, and Oberon Script on the other (apart from the language) is that they are offline compilers while Oberon Script is a load-time i.e. online compiler. Also, Oberon Script is a proof-of-concept whereas the other two are production systems (that they are both still beta quality does not negate that). The offline-online distinction is significant. You certainly don't want to compile a full application client-side into JavaScript. This makes Oberon Script in the current form a loser. However, there are situations where it makes perfect sense to generate a few bits of JavaScript on-the-fly:

• Mobile code. There may be situations where one wants to transmit a few bits of code together with a blob of data, e.g. as part of an XML message. Surely, you dont want to execute arbitrary JavaScript code within the context of your application. But, instead of trying to validate the mobile code it can make sense to limit what can be expressed in the first place by specifying some sort of mobile language and compiling that into JavaScript.
• Component wiring. A composition of Web Controls is a static arrangement of high-level objects (components), of input and output connections, customizations etc. It is more natural to express such a composition using a descriptive method than using code. The description can be, say, an XML document specifying what component uses what other component, and which outgoing interface feeds which ingoing interface. Such a static description can then be compiled on-the-fly into a JavaScript program that actually creates and establishes this arrangement.

The Oberon Script project can be seen as an attempt to stake off the limits of what can be reasonably accomplished on-the-fly. In any case, I think we can expect to see more development in this area of compilation to JavaScript, and some of it certainly also client-side.

JavaScript = Portable Object Code

A few days ago I submitted a short paper to a small conference on modular programming languages and systems describing a small experiment that I did in my series of "Cool Things You Can Do With JavaScript".

I was just about leaving my office before heading to .ch, and before finally closing my Web browser and locking my PC I entered the name of said conference into Google. Perhaps I shouldn't say that. I should be using MSN Search, but unfortunately "goo" + autocomplete is just too convenient. Maybe MSN should think of something that autocompletes fast, too. Anyway, I found the conference, and - gosh! - that the submission date was just 3 weeks away. [Profanity], I said, because I wanted to submit something to this conference for ages, but now 3 weeks seemed a rather [more profanity] short time. OK, I said, calming myself, there's this idea that you (=me, as I was talking to myself) had been contemplating a while ago: A compiler that would compile a certain simple programming language into JavaScript! This would enable you to "do" Ajax in this, or by extension, any language! With browsers slowly becoming runtime environments for Web applications, this made perfect sense. Also, that should be simple enough to hack and write about in 3 weeks, I thought.

I knew that you can create script on-the-fly and run it through eval, but I had yet to see anyone transforming one scripting language using script into another (hence using JavaScript as a portable "object code"), and all within the browser and without installing anything. To cut a long tale short, the conclusion of which you already know (if you don't: re-read the first sentence of this post), it worked, and after 3 weeks of tinkering and scribbling, I had done it. Most of the time was obviously spent on the compiler proper (I chose Oberon, a simple yet powerful language that you can write a to-JavaScript-compiler for in about one and a half weeks). The following functions are the glue to make it work:

function findScriptType(scp,typ)
{
  var code=[];
  for(var i=0;i<scp.length;++i){
    if(scp[i].type.toLowerCase()==typ){
      code.push(scp[i].text)
    }
  }
  return code
}

function addScript(par,code)
{
  var scp=document.createElement("script");
  scp.text=code;
  par.appendChild(scp)//this will also execute the code
}

function compileAll(typ,comp)
{
  var scp=document.getElementsByTagName("script");
  if(scp.length>0){
    var par=scp[0].parentNode;
    var code=findScriptType(scp,typ);
    for(var i=0;i<code.length;++i){
      addScript(par,comp(code[i]))
    }
  }
}

function myCompiler(code)
{
  return code //or some transformation thereof
}

compileAll("text/x-mylang",myCompiler);

The meat is in the myCompiler function that does the transformation (not shown here). To see what was required to compile Oberon into JavaScript I have to refer you to my paper (if it is accepted, or alternatively an MSR Technical Report that I posted recently). Compiling one scripting language on-the-fly into another is not the fastest way of doing stuff, but as a proof of concept it works a treat.

Google innovates

IE Can what? Canvas Element for Internet Explorer

I've just finished a simple implementation of a canvas element for Microsoft Internet Explorer using VML. I needed a way to do simple line graphics for a project I'm working on, and that I want to run in both IE and Firefox. While I could have used either Java or Flash to do line graphics, now that we’re in Web 2.0 (or World 2.0, rather) and Ajax is the word, both seem a bit ... obsolete.

Here's a demo page showing what works and what doesn't. As I’ve implemented what I need and very little more, there's more of the latter than the former. Still, most of the basic stuff works:

• Outlining and filling of paths work fine. Clipping is not supported. Quadratic curves are implemented but VML does not draw them unless they are closed. There’s a lot that VML doesn’t do right.
• VML does not support gradients the way they are defined by the canvas feature. I have spent only very little time trying to simulate them, and have mostly failed. It does something, but wrong. Patterns work better, but only a little.
• Transformations work for line figures but not for patterns and images. Arcs degrade if you rotate and scale them but you may not always notice (work-around because VML is rubbish).
• Image drawing works if the source is an image. I have contemplated doing canvas sources but then didn't do them because I don't need them. That's not to say that they're difficult (*), they're just unnecessary (to me, for now).
  (*) You can copy the children of the source canvas into a div and insert that into the destination canvas.

To use it, you only need to add a call to the global __initCanvas() function in the document's onload event handler, preferably before you use any of the canvas functions. It'll do no harm in Firefox, but in IE, it will replace all canvas elements in the document by div elements with the same id and size (and all other attributes). You can then request a drawing context using getContext the same way you would in Firefox.

Implementing the canvas element using VML poses a few problems (in addition to those that VML poses on its own). A canvas is a pixelmap. A VML figure, however, is a data structure. As long as you’re doing "shapes" you're fine, but if you start doing "pixels" - and lots of them - you get yourself into trouble quite rapidly. On a pixelmap you can keep painting the same spot over and over, and it'll still be "one pixel deep", if you know what I mean. On a VML figure, however, you just pile shapes on top of each other until IE explodes (Literally! Believe me, I've done it). Because of VMLs anti-aliasing feature IE needs to inspect all shapes underneath the last shape added to compute its proper color -- even if you don't use transparency. That's o(n²) if there ever was. You could, of course, optimise the figure by deleting all shapes that are completely obscured by a newly added non-transparent shape. I didn't do it, though. Only the clearRect function of my canvas implementation clears the figure by deleting shapes, but only if the full canvas is cleared (otherwise, more stuff is actually added). If you're doing animations you may want to clear the full canvas sooner rather than later.

A final note: I'm aware that whatever you do, someone on the vast expanses of the Internet will have done it already, so don't bother telling me. There are reasons why I don't (indeed, mustn't) even look too closely at stuff lying about on the Internet. To comfort anyone's hurt feelings (or rub salt in their wounds, whichever): It is a pretty obvious idea, once you inspect the canvas feature and also happen to know VML.

I've switched to Linux, and it's never been so easy!

I've had enough! This weekend, I've finally made the switch, and I'm now one of the many thousands of satisfied Linux users. I know I shouldn't say this so frankly -- and I won't apologize for this -- but the other crap can stay on the shelves for good! My only regret is not having switched sooner! Right now, my machine is doing its cycles with Linux, and it's never been so easy and less troublesome in my life. No more sitting in sweaty shirts trying to figure things out! Mine will be fresh and clean with Linux! I'm doing all my laundry with it!

Some people with a major software company got slightly irritated about this post. For their benefit and everybody else's who needs it rubbed into his/her face here comes a ...

DISCLAIMER: THIS IS A JOKE! EACH AND EVERY INSTANCE OF THE TERM "LINUX" MENTIONED IN THIS POST REFERS TO A LAUNDRY DETERGENT ("VOLLWASCHMITTEL") MANUFACTURED BY RÖSCH COMPANY IN SWITZERLAND. ALL OTHER POSSIBLE MEANINGS OF THE TERM "LINUX" ARE PURELY COINCIDENTAL AND ARE HEREWITH STRICTLY BANNED WITH RESPECT TO THIS POST. IF ANY OF THEM KEEPS RESURFACING IN READERS' MINDS A BRAINWASH IS URGENTLY ADVISED.

At las(t)

I haven't checked out all the details of the new Atlas Web Client Framework yet, therefore I don't know whether I like it or not. What I certainly like is that -- finally -- there has been some progress in the field of interactive Web services since I built my first Web service in 1995 and shook my head in astonishment that it was necessary to reload a complete Web page when all you wanted was to swap an image. Not anymore! Since Google's GMail (if you're faith-based) or MSDN's left-hand navigation bar (if you're closer to the reality-based community) Web pages are truly interactive!

So, at last, there's Altas! Besides all the bells and whistles required to build graphical Web UIs the framework also simulates non-JavaScript language features such as namespaces, classes, and interfaces. I'd have to play with it (build a small Weblication) to experience myself whether these extensions make life easier or only the framework more complex. But so far I haven't.

However, I have (like on similar occasions before) provided pretty-printed, color coded and InScript™-enhanced listings of some of the the various Atlas files drawn from the Atlas Quickstart Guide. To that end, I have extended (as in "hacked") the InScript Code Listing Enhancer technology :-) to "recognize" namespaces, and to allow folding and unfolding of the various classes.

• AtlasCompat.js
• AtlasCore.js
• AtlasUI.js
• AtlasUIDragDrop.js
• AtlasControls.js
• AtlasRuntime.js

If you can't guess from the names above what's likely to be found in the various files there's perhaps little point in your going there anyway (and my telling you, for that matter).

There's some overlap in the various code files. In particular the AtlasRuntime contains parts of the AtlasCore. As I said, I don't know in detail what's in all the files but that doesn't mean that you shouldn't have the tools to find out yourself. Hence this post!

You may also want to see the video of MSN Web Experience architect Scott Isaac unveiling the MSN DHTML Foundation over on Channel 9.

Who put the mob in mobile phones?

Last time I was in Switzerland I bought one of the stylish new M-Budget Mobile phones by Migros, the biggest retailer in Switzerland. Not that I particularly needed another one, but when I heard that the two biggest retailers (Migros and Coop) were each about to offer a budget mobile phone service I couldn't resist.

Also, Migros' line of budget products with its cheap(ish) styling has become sort of a cult in Switzerland. Affluent people used to shy away from those products because buying Budget might make them look poor but now it's hip. There are even rumours that the Budget style is being pilfered to style Web sites and Blogs.

Anyway, so I went with the mob and bought an M-Budget Sony Ericsson T290i with SIM card and CHF 10.- worth of calls for only CHF 58.80. Calls cost CHF 0.44 per minute, and an SMS only CHF 0.10. Hover for currency conversion

The whole launch business, by the way, was quite funny because the two retailers announced their intentions about the same time, however Coop's rate was initially lower than that of Migros, so the latter had to lower theirs in turn before the ink on their adverts was even dry. So there you go. I've got two mobile phones now when I rarely need even one.