Calyptus Life

There are a couple of well-known micro optimization techniques when you need that extra speed within an expensive loop. It generally comes down to eliminating function calls and flattening the closure scope.

Intuitively you don’t want to bloat your download size with repeated code. You also want a clear separation of concerns to make your code understandable and managable. You want to separate common code into sub-routines (functions).

Intra-object method calls

I’ve done a number of tests on repeated calls within a single object. This is typically where an expensive loop would occur.

Now you might think that property look-ups are expensive and should be avoided. Since in a naive implementation they would be continued hash-table look-ups. However, traversing closure scopes and .call(bind) invocations tend to be more expensive in real world engines. Generally, you are better off invoking the function, by property name, on the same prototype – continuously. Engines optimize for this pattern. In the tests you can see that this is even more prevalent in recent optimizations.

Super/base method calls

In Class-oriented/OOP patterns, you often see the need to override an inherited method. However, while doing so you wish to call the overridden (super/base/parent) function from within the new one.

The most common way of doing this is by storing a reference to the prototype object, then invoking the function using .call() or .apply() to set the “this” context to the right value. However, as I’ve shown, navigating a closure and invoking the function using .call() is more expensive than invoking prototype methods.

The benefit of storing a reference to the prototype is that you get a live property that can be monkey patched with a new super function on the fly. However, relying on this pattern can be tricky.

You’re better off having a module system that supports proper file ordering of monkey patches. Where monkey patches are applied before any child modules inherit from their parent. This will enable better optimization on engines that depend on declaration order to optimize their hidden classes (like V8). It also enables monkey patching of mixins that are copied. I.e. has no live inheritance (since JS doesn’t support multiple inheritance).

If we can assume that we don’t need on-the-fly updates of super functions, then we can optimize this further. Again, my tests show, that it’s faster to invoke a method on the same prototype than finding a function reference and invoking .call().

I’ve toyed with some syntax experiments to make this prettier.

Just Inline It

Daniel Steigerwald pointed out that once you make the assumption that we don’t need on-the-fly monkey patches, you should just inline the code. This is always faster.

Let’s take a look at some nonsensical code. The function bar calls the function foo four times.

function foo(state){
    var my = 'code';
    for (var i = 0, l = my.length; i < l; i++)
        if (i % 10 == 2)
            state.push(my[i]);
        else if (i == 1)
            state.push(my[0]);
        else if (l == 2 && i == 3)
            state.push('foo');
        else
            state.push('else');
    return my;
}
 
function bar(condition, state){
 
    var complexCondition = !condition && state.length == 3;
 
    var value = state[0];
 
    while (condition){
        value = foo(state);
        if (complexCondition){
            state.push('someData');
            value = foo(state);
        } else if (value.length == 5){
            value = foo([]);
        } else if (value == 'else'){
        	value = foo(state)
        	state.push('test');
        }
        condition = (value == 'foo');
    }
 
}

This file weighs in at about 300 bytes gzipped.

If we instead inline (copy) the foo code into all four places in the bar function. We get something like this.

function bar(condition, state){
 
    var complexCondition = !condition && state.length == 3;
 
    var value = state[0];
 
    while (condition){
            var stack = state;
			var my = 'code';
			for (var i = 0, l = my.length; i < l; i++)
				if (i % 10 == 2)
					stack.push(my[i]);
				else if (i == 1)
					stack.push(my[0]);
				else if (l == 2 && i == 3)
					stack.push('foo');
				else
					stack.push('else');
			value = my;
        if (complexCondition){
            state.push('someData');
            var stack = state;
			var my = 'code';
			for (var i = 0, l = my.length; i < l; i++)
				if (i % 10 == 2)
					stack.push(my[i]);
				else if (i == 1)
					stack.push(my[0]);
				else if (l == 2 && i == 3)
					stack.push('foo');
				else
					stack.push('else');
			value = my;
        } else if (value.length == 5){
            var stack = [];
			var my = 'code';
			for (var i = 0, l = my.length; i < l; i++)
				if (i % 10 == 2)
					stack.push(my[i]);
				else if (i == 1)
					stack.push(my[0]);
				else if (l == 2 && i == 3)
					stack.push('foo');
				else
					stack.push('else');
			value = my;
        } else if (value == 'else'){
            var stack = state;
			var my = 'code';
			for (var i = 0, l = my.length; i < l; i++)
				if (i % 10 == 2)
					stack.push(my[i]);
				else if (i == 1)
					stack.push(my[0]);
				else if (l == 2 && i == 3)
					stack.push('foo');
				else
					stack.push('else');
			value = my;
        	state.push('test');
        }
        condition = (value == 'foo');
    }
 
}

This file weighs about 290 bytes gzipped. Wait, what? We more than doubled the original file size but the result is smaller?

Yes, the GZIP compression uses the LZ77 algorithm to find repeated byte sequences. This means that inlining your code may actually result in smaller download sizes since some plumbing code is removed.

Is it cheating to compare gzipped file size instead of originals? No. You should always send your static uncompressed content using the GZIP compression. It’s cheap. This is the real world baseline. You should optimize for this.

There are some quirks to look out for. Some minifiers rename variables inconsistently. This may result in inconsistent sequences. You should look out for this, since that would cause a larger file size.

The larger code base may cause a slightly slower start up, since the JS engine needs to parse and compile more code. This should be very very minimal though. Remember, we’re optimizing for tight loops here.

JS-to-JS Compilers

Our inlined code is ugly and unmaintainable. Luckily there are tools that can inline pretty source code for us. E.g. the Google Closure Compiler. Unfortunately the Closure Compiler doesn’t seem to inline functions that are called more than once. Neither does it use these optimization techniques for super calls. Perhaps there are settings that I’m not aware of.

Recursive functions may be difficult to inline but there are tools that can rewrite these and do tail call optimizations as well.

However, this is just a hint of the awesomeness that could be achieved by using a custom JS-to-JS compiler. More on that later.

UPDATED: The demos are now updated to work around some bugs in the ANGLE implementation currently in Chrome 9 beta and Firefox 4 beta 8.

Those of you who are following me on Twitter know that I’ve been really getting into WebGL lately. Basically it’s 1:1 JavaScript bindings to OpenGL ES 2.0 including GLSL (OpenGL Shading Language). This will allow you to access the power of GPU hardware directly in your website.

Safari, Chrome and Firefox all have WebGL enabled in their latest betas/nightly builds. Opera is on the working group as well. Additionally modern iOS and Android devices have OpenGL ES support so mobile support is probably not far away. Firefox already has WebGL support on Maemo.

Microsoft is not yet on board

While Microsoft is constantly bragging about the fully hardware accelerated rendering in IE9 using DirectX. They’re the only one of the major players not yet in the WebGL working group. WebGL is supposedly designed so that it can be implemented on top of DirectX. This allows for stronger implementations on Windows where OpenGL support is poor. Mozilla and Google are already doing this in their implementations.

Microsoft obviously have a lot invested in DirectX and may not want to support an API so close to the competing OpenGL. However, given their recent effort to support standards I’m hopeful they’ll get on board for IE 10.

Fallbacks

Given that no browser supports WebGL yet, other than in beta versions. We will obviously need some fallback.

Mr. Doob is doing some great progress on a 3D API with Canvas 2D and SVG fallback support – called three.js. However, I think this will be of limited use in most real-world scenarios.

For any proper 3D beyond gimmicks you’ll want to use hardware acceleration. The exception being data visualization.

Flash and Silverlight already have pixel shader support. This doesn’t help 3D much but they do help for 2D special effects etc. Although these are not hardware accelerated, they can run multi-core and they’re faster than anything you can do with 2D canvas.

Additionally Adobe has announced hardware accelerated 3D support through the Molehill APIs. I’m sure Microsoft is not far behind with Silverlight. Once these get out to IE users, we’ll have direct hardware capabilities on all the major platforms.

Abstractions

WebGL is a horrible looking API. It’s intentionally a direct translation of the C interface. The intension is that people will provide abstractions on top of it. E.g. a general game engine or a data visualization API built on top of it.

Some have tried to make thin wrappers around it. Like MooTools or jQuery wraps the DOM in a thin API abstraction. I think that is a mistake. You really need to optimize for performance and to do that you need a higher level abstraction that works directly to the WebGL API.

I have no intension of making a thin GL wrapper nor a single generic 3D API. Although…

It’s not just for 3D

Those of you following me on GitHub know that I’ve been doing a lot of work on the MooTools vector graphics library – ART. We already have great SVG and VML support. Next for me is to focus on high performance scenarios.

To start off, I’ve implemented two 2D use cases that are otherwise difficult to do properly using CPU only.

Diffusion Curves

A Diffusion Curve is a new vector primitive. To understand what they are and why they’re incredibly cool, I recommend watching the video from the authors of the original research paper. Implementing a rasterizer of Diffusion Curves involves a diffusion and blur step that are both very computationally expensive. However, using a clever implementation you can take advantage of GPU hardware acceleration to get acceptable performance. There have been talks about introducing diffusion curves in SVG 2.0. But until that gets into browsers, we can already use it through the power of WebGL.

Page Curl Effect

A page curling effect can be implemented many different ways. However, to get a smooth realistic effect on dynamic content you really need some acceleration. This applies to many special effects that you can apply to 2D content.

Safari doesn’t implement SVG filters yet. Such filters can be implemented in terms of WebGL and extended further to advanced blending effects and crazy transforms.

Computation

WebGL is a great complement to JavaScript. JavaScript can be used to implement business logic and UI components while WebGL is used for computationally expensive tasks. Many of the use cases of NaCi (Native Client) goes out the window. You can even use WebGL to performance non-graphics tasks such as audio signal analysis/transformation.

Now all we need is a JavaScript based OpenCL like API for running GPU accelerated workers. There are already several projects doing something similar with Python.

Learning more about WebGL

The best way to learn WebGL is to head over to Learning WebGL and check out Giles Thomas‘ excellent introductory lessons.

Coming Up

Lessons Learned – WebGL

Lessons Learned – Diffusion Curves

You can introduce AOP interception patterns by either changing the original instance or by using additional proxy objects. The later can introduce confusion among instances if not treated correctly. Skip to “Leaky this” if you’re already familiar with proxies in ECMAScript Harmony.

Rewriting vs. Wrapping

Intercepting normal program flows using aspect oriented and other meta-programming patterns can be used for a variety of advanced tricks. Object-relational mapping, logging, security, customized APIs etc.

You can do this by rewriting the methods of the original class/prototype/instance, effectively providing a single instance. You can also do this by providing wrapper objects. That way you have two or more instances.

Rewriting instances or prototypes is easy to do in JS by overriding the functions on existing objects with your own wrapper functions. Although it’s not always possible on the magical host objects. It can also be a problem when these objects have different requirements in various contexts. Such as in a secured sandbox vs. host environment.

Wrappers allow you to leave the original object intact while providing the wrapper to a specific context as if it’s the real object.

Wrappers in ECMAScript 5

In ECMAScript 5 you can already do seemingly perfect wrappers by getting all the properties of an object. Then you define those properties on the wrapper – called a proxy. These are custom getters and setters that delegate to the original object – called the subject.

var subject = new Node();
 
var proxy = Object.create();
 
Object.getOwnPropertyNames(subject).forEach(function(name){
  Object.defineProperty(proxy, name, {
    get: function(name){
      // interception code
      return subject[name];
    }
  }
});

(For simplicity I’ve left out the prototype, setters, enumerations rules etc. Getters are enough to illustrate my point.)

These are fine for frozen objects. The problem is that they don’t represent later changes to the subject. E.g. adding or deleting properties. Additionally, property changes applied to the proxy aren’t propagated back into the subject.

Proxies in ECMAScript Harmony

It looks like the next version of ECMAScript will get support for proxy object that can delegate all operations dynamically – using so called “catch-all” functions.

var subject = new Node();
 
var proxy = Proxy.create({
  get: function(receiver, name){
    // interception code
    return subject[name];
  }
});

When we’re reading a property from the proxy instance, our get-function gets called with the receiver (the proxy instance itself) and the name of the property that should be loaded. We delegate this request to the subject by reading the same property. We can insert any intercepting code as we choose.

This is more efficient and allows for dynamic evaluation of intercepting code. Many ORM patterns – such as Active Record – often use this technique in dynamic environments.

“Leaky this”

However, a problem occurs when these two instances get confused. Imagine this scenario:

var Node = function(){
  var self = this, children = [];
  self.addChild = function(child){
    children.push(child);
    child.parent = self;
    return self;
  };
};

If we wrap an instance of Node in a proxy. Then call:

proxy.addChild(child).addChild(childOther);

We first call addChild through the proxy instance. Our child.parent property is set to the subject instance. The subject instance is returned and we next call addChild directly on the subject instance. Bypassing the proxy.

This is a well-known problem in languages that strongly binds the “this” keyword to a specific instance. Roger Alsing calls this “leaky this” which I find to be an appropriate term since the abstraction is leaking.

However, imagine this JavaScript code:

var Node = function(){
  this.children = [];
};
 
Node.prototype.addChild = function(child){
  this.children.push(child);
  child.parent = this;
  return this;
};

The addChild function now references the “this” keyword. If we repeat the same call in this scenario we get a different result. We call addChild while passing the proxy as the “this” reference. We set the parent property of child to the proxy instance. The proxy instance is returned, and the process is repeated on the second call. This shows the beauty of not having the “this” keyword bound to specific instances.

Although, sometimes you don’t want to use the proxy instance in internal functions. You could use this hybrid to use the subject for whatever use internally, while exposing any proxies externally:

var Node = function(){
  var self = this, children = [];
  self.addChild = function(child){
    children.push(child);
    child.parent = self;
    return this;
  };
};

Conclusion

Brendan Eich points out that unaware consumers of a proxy should be able to treat it just as any other object. This is only true if the provider of both the proxy and the subject have carefully considered the implications of two instances and made sure that no leaking occurs. Code that can be wrapped needs to carefully consider what instance it is currently working with.

Not all code can be wrapped using a proxy indiscriminately.

This is a follow up to my earlier post about the Reactive Extensions (Rx) for JavaScript by Microsoft’s DevLabs. This is also in response to Matthew Podwysocki’s post on jQuery integration (which deserves some credit for putting it out there).

I will assume some familiarity with Rx.

Just like any other DOM library, MooTools has a way of working with native and custom passive DOM events. We can easily give Element object and the Elements collection a method to provide these events as “Observables”. In the jQuery example the method name “ToObservable” was added to the jQuery object, accepting an event type parameter, which was my initial reaction as well. But I’m going to call mine getEvent as in “getting a stream of events given the event type“.

var observableFromEvent = function(type){
  var self = this;
  return Rx.Observable.Create(function(observer){
      var fn = function(event){
          observer.OnNext(event);
      };
      self.addEvent(type, fn);
      return function(){
        self.removeEvent(type, fn);
      };
  });
};
 
Window.implement('getEvent', observableFromEvent);
Document.implement('getEvent', observableFromEvent);
Element.implement('getEvent', observableFromEvent);
Elements.implement('getEvent', observableFromEvent);

These are infinite Observables but we could also make .destroy() trigger onComplete to make them finite as well.

Flickables Example

Instead of the canonical Drag and Drop example I thought I show a twist. Let’s say we want to listen to a mouse flick. The mouse position have to move over 100px in 200ms. Then we want the angle of the flick.

var angleFromPosition = function(position, center){
    var diffX = position.x - center.x, diffY = position.y - center.y;
    var distance = Math.sqrt(diffX * diffX + diffY * diffY);
    var angle = Math.atan2(diffY + distance, diffX) * 360 / Math.PI;
    return { distance: distance, angle: angle };
};
 
var distanceReached = function(angle){ return angle.distance > 100; };
 
var timeLimit = Rx.Observable.Timer(200);
 
var mousePositions = document.getEvent('mousemove')
                     .Select(function(event){ return event.page; });
 
var flicks = document.getElements('.flickable')
             .getEvent('mousedown')
             .SelectMany(function(event){
                 return mousePositions
                     .Select(angleFromPosition.bindWithEvent(null, event.page))
                     .TakeUntil(document.getEvent('mouseup'))
                     .TakeUntil(timeLimit)
                     .Where(distanceReached)
                     .Take(1);
             });
 
// ...
 
flicks.Subscribe(function(current){
    console.log('Flicked in direction: ' + current.angle + '°');
});

Events Mixin

MooTools has a very strong benefit compared to many other libraries. The publish/subscribe pattern is made explicit even for custom classes, using the Events mixin. By implement our “getEvent” method on this class we can use Rx on all custom MooTools classes that provide passive events.

Events.implement('getEvent', observableFromEvent);

Side-effects

Rx allows for the act of subscribing to an event to trigger an action/side-effect. Think of the Request object for example. You can use the act of subscribing to it, to issue a HTTP request. Then we can turn the subsequent events like success and failure into the Observable interface. This means that Request is a complete Observable in it self. This is what I was saving the conversion name toObservable for.

Request.implement({
 
  toObservable: function(){
    var self = this;
    return Rx.Observable.create(function(observer){
 
      var listeners = {
 
        success: function(result){
          self.removeEvents(listeners);
          observer.OnNext(result);
          observer.OnCompleted();
        },
 
        cancel: function(){
          self.removeEvents(listeners);
          observer.OnCompleted();
        },
 
        failure: function(xhr){
          self.removeEvents(listeners);
          observer.OnError(xhr);
        }
 
      };
 
      if (!self.running || self.options.link == 'cancel'){
        self.addEvents(listeners).send();
        return function(){
          self.removeEvents(listeners).cancel();
        };
      }
 
      if (self.options.link == 'chain'){
        var disposed, running;
        self.chain(function(){
          running = true;
          if (!disposed) self.addEvents(listeners).send();
        });
        return function(){
          if (running) self.removeEvents(listeners).cancel();
          disposed = true;
        };
      }
 
      observer.OnComplete();
      return function(){};
 
    });
  }
 
});

This creates a finite stream of events – only one response to be exact. However, since the act of subscribing to it causes it to occur we can have it trigger repeatedly as part of a composite stream of events.

MooTools’ Fx provides a similar concept but slightly different. Even though we don’t get an event for each tick, we still get an asynchronous complete event. This means we can insert Fx as part of a composite stream of events.

Fx also requires from/to arguments to be passed at the start. So we add the option “defaultArgs” to allow us to pass those at initialization.

Fx.implement({
 
  toObservable: function(){
    var self = this;
    return Rx.Observable.create(function(observer){
 
      var listeners = {
 
        complete: function(){
          self.removeEvents(listeners);
          observer.OnCompleted();
        },
 
        cancel: function(){
          self.removeEvents(listeners);
          observer.OnCompleted();
        }
 
      };
 
      if (!self.running || self.options.link == 'cancel'){
        self.addEvents(listeners).start.run(self.options.defaultArgs, self);
        return function(){
          self.removeEvents(listeners).cancel();
        };
      }
 
      if (self.options.link == 'chain'){
        var disposed, running;
        self.chain(function(){
          running = true;
          if (!disposed)
            self.addEvents(listeners).start.run(self.options.defaultArgs, self);
        });
        return function(){
          if (running) self.removeEvents(listeners).cancel();
          disposed = true;
        };
      }
 
      observer.OnComplete();
      return function(){};
 
    });
  }
 
});

Of course since there are a lot of other classes extending the Request and Fx classes, you get the same benefits on them. This is one of the true benefits of MooTools’ modular extensibility.

That is one of the benefits of using the class(ical) pattern in JavaScript. More on that next time…

Side-effects Example

var popup = document.id('popup');
var showPopup = new Fx.Morph(popup, { property: 'opacity', defaultArgs: 1 });
var feed = new Request.JSON({ url: 'mydata.json', method: 'get' });
 
var showFeed = feed.toObservable()
               .Do(function(data){ popup.set('text', data); })
               .Concat(showPopup.toObservable());
 
// ...
 
showFeed.Subscribe(); // loads mydata.json into #popup and displays it

Using Arrays in Unit Tests

Since natives are allowed to be extended within the MooTools theorem, we can add a convenience method to turn an Array into an observable stream of content.

Array.implement('toObservable', function(){return Rx.Observable.FromArray(this);});

We can use this to fake the “flicks” event stream in our earlier example. We avoid having to include complex asynchronous tests or user action tests.

var flicks = [
               { angle: 0, distance: 100 },
               { angle: 45, distance: 100 },
               { angle: 90, distance: 100 }
             ]
             .toObservable();
 
// Unit tests
// Synchronously testing code that's depending on a flick event stream

Web Sockets and Web Workers

Now imagine this on a stream of events coming in from Web Sockets or Web Workers.

You could set up a web socket to asynchronously feed you JSON objects, and easily hook that up to the rest of you UI just as easily as the Request example above.

I’ve been following the work on the Reactive Extensions for .NET (Rx) by Eric Meijer and others over at Microsoft. At first look I was intrigued but didn’t really understand the purpose of it. However, at a second look, I realized that it had the potential to solve every major problem I’ve had with advanced UI development in JavaScript.

Asynchronous Programming – Composable Events

Modern UI development forces us to use asynchronous patterns for user actions, animations and data load. But to make UI development easy you can think of each operation as sequential. You can even artificially lock down the user interface – by disabling or hiding UI elements – while an operation is occurring.

If you want to optimize your user experience, you will need to start dabble in the complicated art of event composition. The problem occurs when you have complex interactions that depend upon other interaction or state.

You can solve this using various state machine patterns. However, I think you will find it quite difficult at times. Even if you do solve it, it’s probably going to be for a specific purpose which is not easily generalizable nor extensible.

Various tools have tried using patterns like Futures and Promises. I think those patterns need to be applied at the language level to be really useful though.

Reactive Programming in an Object Oriented World

JavaScript has introduced the map/filter/reduce methods on arrays to allow collection operations using a sequenced composition of functions.

There’s one minor thing that JavaScript developers should note. In LINQ these operations are lazy iterables. The map/filter operations aren’t actually executed until an .each() starts iterating over them. This avoids having to create duplicates of the result in memory. It also means that the underlying array can change after we call filter and map. This is similar to “live” collections in the DOM. But they can also be infinite in length just like Mozilla’s Iterators. The .each() call is still essentially a synchronous operation though.

Erik Meijer and team simply decided to make that iteration execution asynchronous.

This means that the source data can be asynchronous. So instead of thinking of Events as independent, think of them as a stream of data with an unknown length… (or an asynchronous list/array).

This means that you can now apply the same type of function composition to streams of events. Enter the Reactive Extensions for .NET.

Supposedly this could solve the problem of Event composition in the UI space.

The Reactive Extensions for JavaScript

To my surprise, Matthew Podwysocki recently started a blog series about the Reactive Extensions for JavaScript (also Microsoft to be clear). Apparently the benefits of this tool in the JS world has not gone unnoticed.

There are no bits officially released yet. However, considering Matthew Podwysocki’s recent posts and Eric Meijer’s upcoming talk at the Mix conference… I wouldn’t be surprised if something was released at Mix on March 17th.

Learning More

I have since been interested in learning more about various alternative models. There’s a research project called Arrows which provides a different model that’s more purely functional. There’s also a framework called Flapjax which is more of a DOM library aiming to provide reactive concepts to JavaScript.

To learn more about the Reactive Extensions, take a look at the videos about the .NET version posted by the team over at Channel 9.

Concerns

I’m not sure the first implementation of the Reactive Extensions is going to be the one to solve all these problems.

I think that many developers will have a difficult time thinking about these concepts in the terms of event streams. That could make it difficult to use the current method naming. In this sense, I think Arrows might be easier to get started with. It will allow you to think about events as sequential operations. However, I also see benefit in the model employed by the Reactive Extensions, IF we can all wrap our heads around it.

Another issue is the “Let” method. This may be difficult to know when to use for many developers. That’s true even for LINQ. However, in the Reactive Extensions I have a feeling those issues will become even more prevalent. Hopefully there will be better syntactical sugar to solve this issue.

Rx has yet to prove itself in real world complex applications that goes well beyond single subscription examples. I may try to extend the canonical drag and drop examples to my own HTML5 based Drag and Drop model and plugins to stress test it.

Naming Conventions

There’s also the issue of upper camel case in method names. LINQ for JavaScript is also using this convention. I’m guessing they’re trying to be compatible. However, the JavaScript convention is to use lower camel case method names, which also the new ASP.NET AJAX library is doing. So I don’t understand why.

In dynamic languages with limited auto-completion (IntelliSense) support, naming conventions are very important to follow.

Although, I do like the names Select/Where/OrderBy better than map/filter/sort since given the arguments, that tends to read better as a grammatical sentence.

UPDATE: Event DSLs

I should mention that the MooTools 2.0 team has been working on a DSL based on the CSS selector syntax. This is an extension of the Element.Delegation plugin.

The idea is to use event names and pseudos in combination to create custom composite event listeners. This example would listen to the first click event:

element.addEvent('click:flash', firstClick);

This could enable a lot more powerful combinations of custom events. However, it doesn’t enable passing of parameters and the composability of Rx and Arrows.

I was researching various options of traversing nodes for Slick and the DOM Range for MooTools. I realized that the nodeName property is incredibly slow to access in WebKit browsers. This is because it is working with qualified names (with namespaces and stuff) internally.

if (node.nodeName == 'A') // do something with anchor tag

If you add case insensitive matching to that it will be even slower.

Instead I decided to try to check the constructor of the node to determine what type it is. For example for the anchor (A) tag, modern browsers will use the prototype of HTMLAnchorElement. This can potentially speed up these checks if you’re looking for a known node type.

if (node.constructor === HTMLAnchorElement) // do something
// OR...
if (node instanceof HTMLAnchorElement) // do something

I ran this performance test in various browsers. It traverses all nodes in a large HTML documents and checks which ones are anchor nodes. It first does a blank run to eliminate any initialization quirks. Then it does a control run without the anchor check. Then it tests each of the above models.

IE6 and IE7 will obviously fail since they don’t support the HTMLAnchorElement constructor/prototype. For that case you would have to fall back to the nodeName property.

IE8 will be slightly slower with the constructor check than the nodeName check. But the difference is marginal in the overall scope of IE’s slowness.

WebKit will gain significant performance using the constructor check. The difference is relatively small to the overhead of manually walking the tree. However, if you take the control value from the blank run into account, the difference of just the node type checks will be significant (several times faster). The slow part is the WebKit DOM API, so you will see this with both JavaScriptCore and V8 (Safari and Chrome respectively).

Firefox will be slower on the first run for some weird reason. But in subsequent runs the constructor check will be faster than the nodeName check.

As a side note, node.tagName is no different. That is just an alias for node.nodeName.

In John Resig’s case sensitivity he discusses the case inconsistencies of the nodeName property in various contexts and the impact on performance. For example, in IE, the value of nodeName of unknown elements (like the new HTML5 elements) keeps it original case as in the markup.

This means that any proper CSS selector search for such elements would have to run a case-insensitive match against the nodeName property. Unfortunately the little trick I’ve shown above doesn’t remedy this problem because unknown elements will be lacking a known constructor. However, known Elements can still utilize this trick as a slight performance boost, while letting unknown element fallback to a case insensitive match.

UPDATE: I added a case-insensitive match to the performance tests using regular expressions – showing the added overhead compared to constructor checking.

Let’s say I have a link (anchor tag with href), and I wish to attach an event listener to it.

<ul>
  <li><a id="mylink" href="http://...">my link</a></li>
</ul>

document.id('mylink').addEvent('click', function(){
  console.log('hello world');
});

Now, if I click the link it will log the message but the browser window will also visit the location of the link. There are a bunch of such default behaviors to pretty much every event in the DOM. If we’re implementing custom behavior, we typically want to prevent this default behavior. A common practise is to have the method return false as such:

document.id('mylink').addEvent('click', function(){
  console.log('hello world');
  return false;
});

THIS IS BAD! Don’t. To understand the reason for this, you need to understand event bubbling and the difference between preventDefault and stopPropagation.

Event bubbling and stopPropagation

When an event is dispatched, it first fires the listeners of the ‘mylink’ element (not quite true, but we don’t use capture). But then it propagates (bubbles) up to the LI-element, UL-element, BODY-element etc.  So for every click on any element, the ‘click’ event is triggered on the BODY-element. After all of that, the default behavior of the browser is triggered.

In most browsers bubbling continues to the document and window objects, but that’s not always true for IE.

This is a powerful model. It allows us to do things like Event delegation. You can place a listener on the UL-element to catch any events triggered on the LI-elements without adding listeners to all the existing or any new LI-elements.

Sometimes we don’t want bubbling to occur. Let’s say for example that I wanted to have a ‘click’ event handler on the UL-element that handles clicks on the UL area outside of any A-element. Then I could accept the Event object as the first parameter, use stopPropagation during the click event on the A-element to stop the event before it reaches the UL.

document.getElements('ul').addEvent('click', function(){
  console.log('You clicked within the UL but outside of any link.');
});
 
document.getElements('a').addEvent('click', function(event){
  console.log('You clicked a link.');
  event.stopPropagation();
});

preventDefault

In my example above the browser would still visit the href of the link. Stopping propagation (bubbling) doesn’t actually prevent the default browser action. So we also need to call preventDefault during the click event to prevent the default operation of clicking a link.

document.getElements('a').addEvent('click', function(event){
  console.log('You clicked a link.');
  event.stopPropagation();
  event.preventDefault();
});

Now since this is fairly common MooTools has a shortcut for doing both stopPropagation AND preventDefault. Namely the stop() method:

document.getElements('a').addEvent('click', function(event){
  console.log('You clicked a link.');
  event.stop();
});

So, why is return false bad?

In the standard browser DOM model it’s equivalent to calling event.preventDefault(); but in MooTools it’s equivalent to calling event.stop(); i.e. it also calls stopPropagation.

This is a problem. If you use this model routinely you may not notice that you actually prevent plugins attached to elements higher up in the bubbling chain.

Let’s say I want to use the ‘mouseleave’ event to hide the UL-element when the mouse leaves. If I also return false on the ‘mouseout’ event on the A-element, I may not get the ‘mouseleave’ event because the A-element stops it. OR maybe I have a plugin higher up that requires that my events bubble. It’ll be even more prevalent as more plugins makes use of Event delegation.

Therefore you need to be very explicit about when you stop propagation and not.

Second of all, the “return false” API doesn’t make sense. The function isn’t failing. It isn’t canceled. In fact, it’s canceling a DIFFERENT function.

Therefore you should ALWAYS be explicit by calling either event.preventDefault(), event.stopPropagation() or event.stop(); instead of relying on an implicit convention that differs between frameworks.

Returning a false value is a relic from the old days when we only had a single listener per event.

Binding Parameters

Sometimes you need to bind parameters that you wish to pass to an event listener. A common practise is to use bind.

document.getElements('a').addEvent('click', function(paramA, paramB){
  // do something with this, paramA and paramB
  return false;
}.bind(someObj, [objA, objB]));

In this case you can’t accept an Event object since you’ve bound your parameters to other objects. In this case you can use bindWithEvent to let the first parameter (the event object) get through, while binding the remaining parameters.

document.getElements('a').addEvent('click', function(event, paramA, paramB){
  // do something with this, paramA and paramB
  event.stop();
}.bindWithEvent(someObj, [objA, objB]));

$lambda(false)

“But I don’t want to type out all of that just to stop an event. I like $lambda(false) to easily block events.”

People sometimes use the $lambda method to create a function that returns false to easily stop an event without doing anything else: el.addEvent(‘click’, $lambda(false));

So you need a method that does nothing other than accepts an Event object and calls preventDefault, stopPropagation or stop? Thanks to MooTools generics you can easily do that like this:

element.addEvent('click', Event.preventDefault); // OR...
element.addEvent('click', Event.stopPropagation); // OR...
element.addEvent('click', Event.stop);

For you that think “return false;” saves bandwidth… “e,” and “e.stop();” is two bytes shorter.

Additional Event Listeners on the same Element

Neither preventDefault or stopPropagation or even an error prevents any additional handlers/listeners on the same element. So if you have two handlers listening to the same event, then both will be triggered regardless of the result of either function.

That should be true for all Events, even Class events. More on that in MooTools 2.0…

The other day David Walsh was experimenting with rendering images in the browser using regular tags as pixels. Valerio picked up the idea and made some enhancements. A server-side script transformed PNG files into a JSON image format for easy parsing on the client. That raised the question… How difficult would it be to do that parsing on the client instead?

Why PNG? Well, other than becoming the new defacto standard for graphics it’s a very simple format. It’s also free of patents and uses only simple well known techniques. It makes it very easy to work with. This post is about parsing raw PNG image data in pure JavaScript. It has nothing to do with built in browser support for the format.

Base64 Encoding

JavaScript doesn’t allow us to work with binary data directly. Even with XHR we can’t work with the raw binary data because JavaScript doesn’t currently have a concept of raw bytes. Instead we have to get the bytes from a character representation of the data.

Luckily there’s already a standard transfer encoding already heavily in use in various places of the W3C standards… Base64! You can use the data: URI scheme to embed image data in your HTML or CSS documents. It’s also heavily used for binary data in e-mails.

We can get the data either from an XHR request, from a src attribute or just statically embedded in your JavaScript file. So, now we have our data as Base64 encoded string.

To work with the raw data we need a way to represent bytes. If you’re working with ASCII data you can just stick to string representations. But since we’re going to be working binary data the most useful way seems to be simple Numbers. That allows you to do bitwise operations and easily convert them to and from ASCII. It’s also provides better performance than representing the bytes as Objects.

Now we need a parser. I went with a sample parser by some guy named notmasteryet. There are others but this seems like a pretty solid implementation and allows us to work with bytes as Numbers. It also works as a reader that lets us read our data piece by piece instead of filling our memory.

DEFLATE

The current PNG standard only uses the DEFLATE algorithm for compression. It’s the same algorithm used in ZIP, GZIP, zlib, etc. So it’s a very common format.

Luckily for us, notmasteryet’s sample also includes a DEFLATE decompressor. It also works as a piece by piece reader which makes it more memory efficient to work with. The reader pattern is a great way to read data in nested formats.

PNG

The PNG format consists of a set of named chunks. A set of “IDAT” chunks makes up the main image data. The total data stream is compressed using DEFLATE. The uncompressed data is filtered using one of 5 simple delta compression filters for each line of pixels.

Notice that we haven’t yet touched any image-processing specific logic. DEFLATE and delta compression is used for text and other data as much as anything else.

The raw data consists of a color for each pixel. This can be either grayscale, RGB or a reference to a palette color. This is what we really want.

The PNG format is open and well documented. So I’m not going to cover it in any more detail.

Proof of Concept

Since we’re doing a lightweight JavaScript parser and probably have some control over the image data, we can skip some of the more outlandish features of the specification. We can also skip the verification parts. We’ll just skip the file headers and CRC checks.

I decided on an a simple API that reads each line of pixels as an array of RGB colors represented as a number.

var image = new PNG(base64data);
image.width; // Image width in pixels
image.height; // Image height in pixels
var line;
while(line = image.readLine()){
  for(var x = 0;x < line.length;x++){
    var px = line[x]; // Pixel RGB color as a single numeric value
    // white pixel == 0xFFFFFF
  }
}

I then took that RGB data and inserted the pixels into my document as DIV tags with a background-color.

In less than 3 hours I had a working Proof of Concept of a format I had never worked with before.

I skipped interlacing, alpha and some of the filters for the demo. It’s not meant to be a fully working prototype nor a reference library in any way.

Now What?

You could…

• Display the image using a regular rendering method but use the PNG parser to extract colors using a Color Picker.
• Add obfuscation or cryptographic layers to render images that can’t be easily ripped by bots or downloaded by users.
• Render embedded PNG images using VML in Internet Explorer (which lacks data: URI support) with full alpha support.

Don’t expect this method to become the new hack for PNG or embedded images in Internet Explorer. The rendering methods here are probably too slow for that. You could do some nice stuff with CANVAS though.

However, I have demonstrated that it is possible to work with binary formats in JavaScript. We shouldn’t be afraid of utilizing existing binary standards (PNG, GZIP, SVGZ, SWF, TTF…). We shouldn’t always fallback to our comfortable old JSON format and reinvent the wheel for every client-side need.

Relevant Projects

The MooTools team is working on a tool set for vector graphics in the web browser, A.R.T. You could use binary formats to embed your vector based graphics in formats like… TrueType!

The APE (Ajax Push Engine) project brings socket programming to the JavaScript platform.

Digg’s MXHR stream parses multipart encoded data and extracts the parts for various uses. This could provide a packaging model for various widgets or data packets.

The HTML 5 working draft is continuing it’s development of the future support for HTML 5. This includes new tags, attributes and a strong specification of how clients should interact with old and new elements. What I find even more intriguing, is the standardization of many advanced JavaScript DOM features (such as editable content, drag and drop). Most of which has been available to IE users for more than a decade. This is one area that standards has been particularly slow to adopt. With the current beta versions of Safari, Chrome and Firefox these new browsers are finally ready to leave IE behind (yes, even IE 8).

Many people are still frightened of implementing code according to a working draft. Especially since it’s not scheduled to be complete until 2012. In my opinion, those fears are largely unfounded at this point. The primary reason for this is that many of the features have been available in IE for many years and the HTML 5 specification centers around keeping some historical compliance. So the primary threat for lagging cross browser functionality has already been eliminated. It is also the WHATWG’s estimate that browsers will have full compliance and people will have started utilizing this new standard long before it is finalized. For these reasons, by the time you read this, you may already be a late adopter.

However, there are still some quirks that you need to be aware of. I’ve been working on cross browser layers of the HTML 5 specifications since 2007 including backwards compatible code for older browsers. This code has been used in production and little of it has changed since mid-2008. Therefore I’ve started work on introducing these features to my JavaScript framework of choice, MooTools. While I refactor my code for this purpose I thought I might introduce some of the quirks that you might come across in your own endeavors.

Coming up

Part 2 – Drag and Drop, Copy and Paste

Part 3 – Range and Selection

Part 4 – ContentEditable and ExecCommand