Hashtables in javascript

I was looking into some performance problems with knockout yesterday and starting digging into the code. In particular I was wondering why it would take their mapping plugin several seconds to wrap an array of 500 objects. Profiling lead me to look deeper into the code, and the following code stroke me as very strange:

Basically this is a hash implementation of only put and get operations using two arrays. I don’t think I need to tell you how bad the performance of this will be once you start adding lots of items 🙂

The reason why they didn’t just use an ordinary object to store their values, was that their keys were objects and not just simple strings or integers. I started wondering what other people did with this problem. There must be a library for this. And low an behold there was.

Then I started thinking, why don’t you just jsonize the object and then store that as the key in a plain js object. Both things should be really fast, since every new browser nowadays has a very fast JSON implementation.

With the 3 implementations in hand I did a simple benchmark. Generate 10.000 objects, store them in the hashtable with the object as a key. Followed by getting all the objects again.

Using Firefox 12: naive double array: 1370ms, json: 77ms, jshashtable: 170. Using Chrome 19 and IE9 the performance gap is very similar. Chrome is of course a tad faster.

Update: reran the benchmark using suggestions from Tim.


Code is available here.


On designing libraries

I recently finished up a big project at IOLA which used two major components: Javascript and c# (.NET). It was interesting for me to see the big difference in the libraries for these platforms. For Javascript we used the excellent jQuery library. For .NET we used the very buggy Devexpress library. jQuery, like Javascript, is very simple. .NET on the other hand is overload with interfaces and concepts. What is interesting of course is that this philosophy shines through in libraries build on top of both platforms.

Devexpress is overloaded with concepts and the size of the library is just insane, the latest release is 221MB excluding kitching sink. Compared to jQueries 19KB. jQuery on the other hand focuses on a simple core with just the right amount of abstractions (very lispy), and delegates specific functionality to plugins, such as flot. The difference of course in part comes from the fact that jQuery is an open source project, while devexpress is a commercial project.

You just have to look at the release notes for each of these projects in order to see the difference. jQuery focused on making their already working code faster and fixing bugs. While devexpress spend most of their time added a number of new features. The problem is that in a commercial project fixing bugs doesn’t pay up as well as implementing new features. Or at least that used to be the case. In the era of google that simply is not true. Anyone can put in devexpress and find out if the library sucks (which it to a large degree does) or if it rocks. The sooner they realise that small is the new big, the sooner we will start getting better libraries.



I had a real “aha moment” today while coding some javascript. Let me first start this post with a quote:

The venerable master Qc Na was walking with his student, Anton.  Hoping to
prompt the master into a discussion, Anton said "Master, I have heard that
objects are a very good thing - is this true?"  Qc Na looked pityingly at
his student and replied, "Foolish pupil - objects are merely a poor man's

  Chastised, Anton took his leave from his master and returned to his cell,
intent on studying closures.  He carefully read the entire "Lambda: The
Ultimate..." series of papers and its cousins, and implemented a small
Scheme interpreter with a closure-based object system.  He learned much, and
looked forward to informing his master of his progress.

  On his next walk with Qc Na, Anton attempted to impress his master by
saying "Master, I have diligently studied the matter, and now understand
that objects are truly a poor man's closures."  Qc Na responded by hitting
Anton with his stick, saying "When will you learn? Closures are a poor man's
object."  At that moment, Anton became enlightened.

When I first read this some time ago I thought I understood it. I did not I now understand and my aha moment today proved that. I have written way too little pure functional programming to really appreciate and use the power of closures. Not to say that objects are useless. That’s exactly the point of the quoted text. Just that the ability to define closures inside closures inside closures is a really really powerful concept. The idea is that sometimes code gets repeated in a function inside a class. Typically you pull that into a helper function and stick it on the class, but sometimes the function is so specialized that it has no livelihood in the class. Secondly the ability to bind local objects to closures, and use those closures as state is another aspect of closures that is immensely powerful.