OCD is the path to the dark side

6 01 2015

A while back I had to wrap a built in JavaScript function, this is pretty simple thanks to the fact that JavaScript is a dynamic prototype based language. Here’s an example of how this can be done (not the actual function or functionality in question):

(function wrapAddEventListener() {
  var orig = HTMLElement.prototype.addEventListener;
  function wrapper(name, handler, capture) {
    console.log("Added a handler for " + name + ' on ' + this); 
    orig.call(this, name, function(ev) { 
      console.log("Got Event " + ev.type); 
      handler(ev); 
    }, capture);
  };

  HTMLElement.prototype.addEventListener = wrapper;	
})();

The problem was that then my OCD kicked in because now if I type document.body.addEventListener in the console I get the function’s body instead of function addEventListener() { [native code] }. For some reason this bothered me (why?) enough in order to add the following line to the function wrapping code

wrapper.toString = function() { 
    return orig.toString() 
}

Now this is deceitful and worthless since it doesn’t really achieve anything, debugging into the function will show the wrapper code. Still I felt that for aesthetic reasons this is preferable.

I’m not sure if covering your tracks like this is evil (since it’s deceitful) or acceptable since it isn’t hiding any semantic changes. I’ll just hope its the worst of my sins for the upcoming year…

Advertisements




Formal parameters and the arguments object in JavaScript

24 07 2011

Say you’re writing a function which takes a function name as an argument and passes the rest of its arguments to the named function. Your unit test for such a function may look like this:

assertEquals('add', 5, calculate('add', 3, 2));
assertEquals('mul', 6, calculate('mul', 3, 2));

We would like to splice off the first element and pass the rest to another function but since arguments isn’t a real Array it doesn’t support the splice method. Never mind, that’s easily treated by calling splice with arguments as this.

function calculate(operation)
{
    // Remove `operation' from arguments leaving only `a' and `b'
    Array.prototype.splice.call(arguments, 0, 1);
    var funcs = {
        add: function(a, b) { return a + b; },
        mul: function(a, b) { return a * b; }
    }
    return funcs[operation].apply(this, arguments);
}

So why are we getting an Uncaught TypeError: Cannot call method ‘apply’ of undefined? Looking at things in Chrome’s debugger everything looks OK. operation is “add” and funcs[operation] is a function.

View in Chrome developer tools
It dawned on me that the debugger is lying (Firebug and IE’s debugger don’t have this problem), splice removed the first parameter from arguments and now the value of operation is 3. How come 3? Well operation was the first parameter and the first element in arguments is now 3, it’s obvious really(?).

Now I picked up JavaScript on my own (as I assume many do) so I’m no expert and this took me by surprise (it’s probably not trivial even for real JavaScript developers if Chrome’s debugger has this defect).

After meditating about the facts it makes sense that formal parameters and the elements in the arguments object are aliases so that if you do arguments[2]++ the formal parameter  ‘b’ changes too but this behaviour means that that these references are more like Perl’s much vilified symbolic references than most languages’ references. This means that using a formal parameter in JavaScript is semantically equivalent to indexing into the arguments object, writing  operation in (this example) is just syntactic sugar for arguments[0]. If you want to remove an argument from the arguments object and still used the named parameter you must first cache the value in a separate variable.

Here’s the fixed version of calculate:

function calculate(operation)
{
     var op = operation; // Save value of `operation'
    // Remove `operation' from arguments leaving only `a' and `b'
    Array.prototype.splice.call(arguments, 0, 1);
    var funcs = {
        add: function(a, b) { return a + b; },
        mul: function(a, b) { return a * b; }
    }
    return funcs[op].apply(this, arguments);
}

Edit: as strager said in the reddit thread:

Takeaway:
Do not modify the arguments object.
Ever.

Now that I’m older and slightly less ignorant I think this would be a better solution:

function calculate(operation)
{
    var funcs = {
        add: function(a, b) { return a + b; },
        mul: function(a, b) { return a * b; }
    }
    return funcs[operation].apply(this,
                       Array.prototype.slice.call(arguments, 1));
}

Edit January 2012: The Chrome defect has been fixed (verified on Chrome 16).





timeoutSort

19 06 2011

A recent post in 4chan introduced Sleep Sort. The reddit thread that ensued ported it to many languages (from the original bash) but I didn’t see anyone port it to JavaScript yet. So without further ado here’s my port to JavaScript called timeoutSort

Array.prototype.timeoutSort = function(f) {
    this.forEach(function(n) {
        setTimeout(function() {
            f(n)
        }, 5*n)
    })
}

It can be used thus:

[1,9,8,7,6,5,4,3,2,0].timeoutSort(alert)

Or thus:

[1,6,4,3,5,2,0].timeoutSort(function(n){ document.write(n+'<br>')})

Share and enjoy 🙂





Meaningless Benchmark Redux

27 03 2011


A year ago I wrote a post called Yet Another Meaningless JavaScript Benchmark, in which I examined how different browsers behave in regards to an atypical JavaScript program (hence the meaningless part of the title). The last thing I expected was for someone to actually use this as  part of a benchmark suite.

Since I published the post both IE and Firefox have released a new major version (and Chrome has released 7 major versions, but who’s counting?) so I guess now is as good a time as any to see how the new versions fare for the same test. Just re-running the test is rather boring so I’ve added two additional sections to this post in which I experiment with some of HTML5’s features.

  1. Using the canvas tag to create a visualization of a Collatz orbit [Jump there]
  2. Use Web Worker threads in order to solve the same problem [Jump there]

I should note that I’m not a web developer, I’m just playing around with HTML5 (and blogging) so if you are a web developer some of this may seem obvious. If you’re not a web developer you probably don’t much care about HTML5 so I’m not really sure who the audience of this post is…

All the code is available to play with right here.

Rematch!

When I originally run this test with IE8 Firefox 3.5 and Chrome 3 (yes 3) I got the following results:

Re-running the same test now gives very different results. Again I’m using the latest released versions of the browsers, IE9, Firefox 4 and Chrome 10 (on the same computer).

The first thing we can see is that the playing field has been levelled, IE is no longer pulling the Y axis into the triple digits, in fact it’s planted firmly in the single digits. Chrome is unique in taking more time to perform the optimized version in more time than it did 7 versions ago (I should reiterate that this benchmark is highly specialized which means it’s not worth optimizing for and Chrome may still out perform the other browsers in real-life scenarios).

Well now we’ve got that behind us, lets look at some HTML5 features

Canvas

The canvas element gives us the opportunity to visualize what a Collatz Orbit looks like, here’s the orbit for 87:

The black dot is the starting point, odd numbers go to 3*n+1 (in red) and even numbers go to n/2 (in green), the blue dot marks where the orbit has reached 1.

The code for drawing the orbit is available here, I won’t go into it since it’s pretty trivial. All I want to add on the subject is that I calculate the whole orbit in advance so that I know how big the canvas is going to be, since it can get to be quite big a lot of the drawing may take place off screen. The orbit is drawn step by step in order to give a feeling on what’s going on (you can configure the how fast it runs).

Worker Threads

Another feature of HTML5 is Web Workers, this allows breaking out of JavaScript’s natural single threaded nature and perform calculations in separate threads. In order to prevent data races the worker threads can’t access the browser’s DOM which slightly limits their usage.

Thankfully number crunching doesn’t require access to the DOM and I had a chance to implement Collatz yet again (this is turning into a real code kata, especially counting all the different C++ implementations I wrote).

Here I launch a number of threads, each takes a sparse view of the numbers in the range. I keep track of the threads that have reported the maximal orbit for their slice and when all threads have answered I output the answer.

function parallel(limit, threads) {
    var max = [0, 0];
    var live_threads = threads;

    for (var i = 0; i < threads; ++i) {
        var worker = new Worker("euler14.js"); // Create thread object
        worker.addEventListener('message', function (e) { // This function is how the thread reports back
            var d = e.data;
            if (d.len > max[0]) {
                max = [d.len, d.num];
            }

            if (--live_threads == 0) // Done, output the result
                report("Parallel ("+ threads + ")", begin, max[1], max[0]);
        }, false);

        // Launch the thread
        worker.postMessage({ 'max': limit, 'step': threads, 'offset': i });
    }
}

The thread receives all the information it needs for the computation, when it’s done it reports its findings to the launcher (via self.postMessage) and  commits suicide.

self.addEventListener('message', function (e) {
    var limit = e.data.max;
    var add = e.data.offset;
    var step = e.data.step;
    var max = [0, 0];

    for (var i = 1; i + add < limit; i += step) {
        var length = orbit(i + add);
        if (length > max[0])
            max = [length, i + add];
    }

    self.postMessage({ 'num': max[1], 'len': max[0], 'offset': e.data.offset });
    self.close(); // Goodbye cruel wrold
}, false);

IE9 does not support Web Workers and the numbers I got when running Firefox and Chrome on this varied greatly between runs but here are the best times they achieved on my ageing dual core laptop.





Yet Another Meaningless JavaScript Benchmark

18 01 2010

A while back a friend of mine introduced me to Project Euler which is a “series of challenging mathematical/computer programming problems” all of which should solved by a program that observes the “one minute rule”

“…although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.”

Even though my primary programming language is C++ I started solving these problems using Perl due to it’s faster development cycle. Another advantage Perl has over C++ (which I didn’t realize was an advantage at the time) is that it’s slow as molasses, especially when used for numeric computations. This comes from the fact that Perl, being a dynamic language, has to deduce the types of objects at run-time, e.g. when you do $i + 1, Perl has to check what type $i is in order to know if it needs to add two numbers or concatenate a number to a string.  [Correction: As Brad pointed out, Perl has a dot operator for concatenating strings which makes + unambiguous however the point stands for JavaScript and generally for many operations in dynamic languages.]

So when I got to problem 14 my naive Perl implementation violated the one minute rule. Had I used C++ it would have run in less than three seconds and you would be spared this blog post, but as it was, I tried to think of a way to make it faster.

Problem 14 goes as following:

The following iterative sequence is defined for the set of positive integers:

nn/2 (n is even)

n → 3n + 1 (n is odd)

The problem states that it’s an unproven conjecture that by iteratively feeding the result of the function to itself you’ll eventually reach 1 for all positive integers. The question then is which number (less than one million) has to be fed into the function the most times  before it reaches 1.

My brute force implementation was too slow so I tried to come up with an optimization. Consider the number 3, its chain is:

3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 : length is 8

If we look at 6 the chain is:

6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 : length is 9

Notice that we pass through a number we saw before, there’s no need to recompute the length of 3’s chain, we already know it’s 8. I had to change my implementation to be recursive rather than iterative (so that I will be able to cache the result of all the numbers I pass through).

In order to prove to myself that the difference in speed between C++ and Perl was due Perl’s being a dynamic language I rewrote this in JavaScript (the other dynamic language that I’m somewhat familiar with). My JavaScript implementation looks like this:

function next(i) {
    if (i & 1)
        return i * 3 + 1;
    return i / 2;
}

function length(n, cache) {
    if (n == 1)
        return 1;

    if (cache !== null && n in cache)
        return cache[n];  

    var ret = 1 + length(next(n), cache);
    if (cache !== null)
        cache[n] = ret;
    return ret;
}

function naive() {
    check(null, "Naive");
}

function optimized() {
    check({}, "Optimized");
}

function check(cache, msg) {
    var max = [0, 0];
    var lim = limit();

    for (var i = 1; i  max[0])
                max = [curr, i];
    }
    alert(msg + " found " + max[1] + " (chain length: " + max[0] + ")");
}

I then checked this implementation on the three browsers I have installed IE8[1], Firefox 3.5 and Chrome 3 with the following results:

IE took 168 seconds to run the naive solution while Firefox only took 101 seconds but that’s nothing compared to Chrome’s 2.8, that’s right, Chrome’s V8 Javascript implementation is 60 times faster than IE’s, more than an order of magnitude!

The second thing that struck me was how differently the same optimization manifested itself in the three browsers, in both IE and Chrome the optimization shaved off less than half the time (less than 2 fold improvement) while in Firefox the optimized version was 24 times faster than the naive one.

What I assume is happening is that JavaScript on the V8 engine behaves more like a statically typed language because it uses advanced JIT techniques such as trace trees which un-loop recursive function calls and makes (checked) assumptions about the types of variables.

<Edit>

It has been pointed out in comments to this post and on reddit that Firefox’s TraceMonkey uses trace trees while Chrome’s V8 does not. I’m not familiar with this field, I do remember reading about an optimization made by V8 and I thought that it was trace trees but I may have misremembered. In any case it’s pretty clear that V8 uses advanced JIT techniques (although trace trees may not be one of them).

Now I realise that this isn’t a characteristic use of JavaScript, most JavaScript code is not intensively numeric and thus there’s no point in optimizing for this usage. What I find more worrying from the IE perspective is how much better the optimization behaves in Firefox than in IE, this optimization depends on property lookup in objects which is an extremely  common operation in JavaScript. Why there is such a difference between IE and Firefox in this aspect escapes me.


[1] In order to get meaningful results on IE I had to disable the “Stop running this script” dialog