Optimize using dictionaries

There is a jQuery plugin for simplifying access to a select box. It’s very useful and I tried to use it in a prioject where I had to show hundreds of options at once. It worked pretty well with a few options, but as soon as those many options started to come in, performance fell down.

Let’s have a look at the implementation of the addOption function.

$.fn.addOption = function() { var a = arguments; if(a.length == 0) return this; // select option when added? default is true var sO = true; // multiple items var m = false; if(typeof a[0] == "object") { m = true; var items = a[0]; } if(a.length >= 2) { if(typeof a[1] == "boolean") sO = a[1]; else if(typeof a[2] == "boolean") sO = a[2]; if(!m) { var v = a[0]; var t = a[1]; } } this.each( function() { if(this.nodeName.toLowerCase() != "select") return; if(m) { for(var i in items) { $(this).addOption(i, items[i], sO); } } else { var option = document.createElement("option"); option.value = v; option.text = t; var i; var r = false; // get options var o = this.options; // get number of options var oL = o.length; // loop through existing options for(i = 0; i < oL; i++) { // replace existing option if(o[i].value == option.value) { r = true; break; } } if(i < oL && !r) i = oL; this.options[i] = option; if(sO) { o[i].selected = true; } } } ) return this; }

Off Topic: The code above is a bit complex at first sight. The reason it seems complex is due to unneeded recursion, so common among jQuery developers. In fact the jQuery library itself makes use of unneeded recursion whenever possible…

Look at the snippet below the comment // loop through existing options. What’s going on here? A select box is treated like a database table where an option is a record and its value is the primary key. When an option is added to a select box, the everlasting dilemma arises: Is it an INSERT or an UPDATE?

The solution implemented here is to loop through existing options and break if a match is found between the new option value and the old ones. Sadly enough, this is the optimal (linear length) solution if you are adding just one option, but it’s the worst (quadratic length) one when you are adding many options at once.

Here is a replacement using a dictionary for storing and retrieving existing options. It’s an inner refactoring with no change on the interface, so it’s pretty simple to copy and use it in your own projects.

var options_dictionary; var options_count; function init_options( el ) { var o = el.options; options_count = o.length; options_dictionary = {}; for(i = 0; i < options_count; i++) { options_dictionary[ o[i].value ] = i; } } function addOneOption( el, value, text, selected ) { var option = document.createElement("option"); option.value = value; option.text = text; if( selected ) option.selected = true; var o = el.options; var i = options_dictionary[ value ]; if( typeof i == 'undefined' ) { i = options_count; options_dictionary[ value ] = i; options_count++; } o[i] = option; } $.fn.addOption = function() { var a = arguments; if(a.length == 0) return this; // select option when added? default is true var sO = true; // multiple items var m = false; if(typeof a[0] == "object") { m = true; var items = a[0]; } if(a.length >= 2) { if(typeof a[1] == "boolean") sO = a[1]; else if(typeof a[2] == "boolean") sO = a[2]; if(!m) { var v = a[0]; var t = a[1]; } } this.each( function() { if(this.nodeName.toLowerCase() != "select") return; init_options( this ); if(m) { for(var i in items) { addOneOption( this, i, items[i], sO ); } } else { addOneOption( this, v, t, sO ); } } ) return this; }

The performance improvement is huge. Here are some figures I got on my PC by means of the Firebug Profiler.

  • all INSERTs: adding 1000 options to an empty select box needed 15234.375 milliseconds using the original code and 234.375 milliseconds using the replacement code, thus accounting for a 65 times improvement
  • all UPDATEs: replacing all the 1000 options of a select box needed 16578.125 milliseconds using the original code and 796.875 milliseconds using the replacement code, thus accounting for a 20 times improvement

If you want to test it by yourself here is the simple page I used:

test dictionary

Load (Empty)

Load (Preloaded)

Leave a Reply

Your email address will not be published. Required fields are marked *