Monday, July 18, 2011

Overoptimizing my JavaScript stack implementation for fun

Davy Brion made a comment on my JavaScript stack/queue implementation on Twitter last night: Any reason why you don't immediately set elements to [] at declaration in your stack/queue example?

var elements;
 
this.push = function(element) {
    if (typeof(elements) === 'undefined') {
        elements = [];   
    }                            
    elements.push(element);
}

Yes, I made an overoptimization, and a bad one. In this implementation, you save a few bytes in memory if you initialize the stack, but don't push elements. This might have made some sense 15 years ago, but today a few bytes are very negligible compared to the cost of evaluating the elements reference on every push call.

Anyway, thinking about this driving home, I thought of another optimization, which meets both arguments and is far more fun.

this.push = function(element) {                        
    elements = [];   
    elements.push(element);                            
    this.push = function(element) {
        //Rewriting self. Overoptimization ftw!
        elements.push(element);                                   
    }                                                 
}

The first time the push function is executed, the elements array is initialized. In the same function, the function rewrites itself to no longer initialize the elements array. So the second time the push function is called, it will no longer initalize the array, but only push a new item to the existing elements array.

Dynamilicious!

6 comments:

  1. should we worry about thread-safety?

    ReplyDelete
  2. No, JavaScript in the browser is single threaded.

    ReplyDelete
  3. Could you optimize the initialization so that you avoid a call to push the first time round:

    elements = [element];

    ReplyDelete
  4. What if someone saves a reference to the push function?

    ReplyDelete
  5. @Jim: Good idea.

    @Anonymous: Then they have a problem. It will never get optimized and the array will be reïntialized every function call.

    ReplyDelete
  6. Thanks for sharing your info. I really appreciate your efforts and I will be waiting for your further write ups thanks once again.
    html5 converter

    ReplyDelete