Reloading selects with JSON

My JavaScript code is slow for large inputs. However, it is especially slow in IE. The browser will freeze for about a minute while the select is being reloaded. Any ideas for how to optimize this code, especially for IE?

function reloadSelectWithJSON (elementid,query){
        /* It is assumed that the elementid passed in is
  the selected box's ID while 'available_' added to it is the available box's ID */
    var preElement = 'available_' + elementid;
    var element = document.getElementById(preElement);
    var selected = document.getElementById(elementid);

    /* Gathers a string consisting of all the selected values */
    var selectedList = '';
    for (var h = 0; h < selected.length; h++){
        selectedList = selectedList + ',' + selected.options[h].value;
    }

    selectedList = selectedList.substr(1).toLowerCase();

    //Clear select of exiting options
    element.options.length = 0;

    //Creates a blank option if the optional arguments {id,name} are passed
    if (this.reloadSelectWithJSON.arguments.length == 4) {
        var id = this.reloadSelectWithJSON.arguments[2];
        var name = this.reloadSelectWithJSON.arguments[3];
        element.options[0] = new Option(name,id);
    }

    //Loop JSON query structure and reload select
    for (var i=0; i < query.ROWCOUNT; i++){
   /* If the value is part of the selected values list then do not include it as an available column */
        if(selectedList.search(query.DATA.ID[i].toString().toLowerCase()) == -1){
            element.options[element.options.length] = new Option(query.DATA.NAME[i], query.DATA.ID[i]);

            var optionLength = element.options.length;

            optionLength--;

            if(query.DATA.title != undefined  && element.options[optionLength] != undefined){
            element.options[optionLength].setAttribute("title",query.DATA.title[i]);
            } else {
            element.options[optionLength].setAttribute('title',query.DATA.NAME[i]);
            }
        }
    }
}

Right now selectedList is a string that seems to be put together solely for searching through it. That has the potential to be a big performance bottleneck.

If you change it to an array, you can squeeze a bit more efficiency into your code by sorting the array and then using a binary search method to detect whether it contains the desired value.

Here’s an example of a binary search method.

// Accepts a sorted array, an object, and an optional comparator method
// Returns index of detected object, or a negative value if not found (binary complement of proper index)
function getIndex(arr, target, comparator) {
    var l = 0,
    h = arr.length - 1,
    m, comparison;
    comparator = comparator || function (a, b) {
        return (a < b ? -1 : (a > b ? 1 : 0));
    };
    while (l <= h) {
        m = (l + h) >>> 1;
        comparison = comparator(arr[m], target);
        if (comparison < 0) {
            l = m + 1;
        } else if (comparison > 0) {
            h = m - 1;
        } else {
            return m;
        }
    }
    return~l;
};

You’ll find that although there’s a small performance penalty resulting from the need to sort the array, you’ll be able to look up the indices of elements much faster this way. Check out the code snippet embedded below for some dramatic proof!

var log = (function (output) {
    return function (text) {
        output.insertAdjacentHTML("beforeend", text + "<br/>");
    };
})(document.getElementById("output"));
document.getElementById("RunTests").onclick = function () {
    document.getElementById("output").innerHTML = "";
    var numWords = document.getElementById("NumWords").value;
    var numTestWords = document.getElementById("NumTests").value;
    var str = "";
    var arr = [];
    log("<b>Creating a list of " + numWords + " items:</b>");
    var start = Date.now();
    for (var i = 0; i < numWords; i++) {
        var word = randomString();
        arr.push(word);
    }
    log("Time to build array: " + (Date.now() - start));
    start = Date.now();
    for (var j = 0, len = arr.length; j < len; j++) {
        var temp = randomString(); // just to be fair to testing time
        str = str + "," + arr[j];
    }
    str = str.substr(1);
    log("Time to build string: " + (Date.now() - start));
    start = Date.now();
    arr.sort();
    log("Time to sort array: " + (Date.now() - start));

    var test = [];
    for (var k = 0; k < numTestWords; k++) {
        test.push(arr[Math.random() * arr.length >>> 0]);
    }
    log("<b>Searching for " + test.length + " test words: </b>");

    var index = test.length;
    start = Date.now();
    while (index--) {
        str.search(test[index]);
    }
    log("Time to search string: " + (Date.now() - start));

    index = test.length;
    start = Date.now();
    while (index--) {
        getIndex(arr, test[index]);
    }
    log("Time to search array: " + (Date.now() - start));
}

function getIndex(arr, target, comparator) {
    var l = 0,
        h = arr.length - 1,
        m, comparison;
    comparator = comparator || function (a, b) {
        return (a < b ? -1 : (a > b ? 1 : 0));
    };
    while (l <= h) {
        m = (l + h) >>> 1;
        comparison = comparator(arr[m], target);
        if (comparison < 0) {
            l = m + 1;
        } else if (comparison > 0) {
            h = m - 1;
        } else {
            return m;
        }
    }
    return~l;
};

function randomChar() {
    return "abcdefghijklmnopqrstuvwxyz" [Math.random() * 26 >>> 0];
}

function randomString() {
    return "" + randomChar().toUpperCase() + randomChar() + randomChar() + randomChar();
}

Number of words in list:
<input type="text" value=5000 id="NumWords">
<br/>Number of tests to run:
<input type="text" value=5000 id="NumTests">
<br/>
<input type="button" value="Run Test" id="RunTests" />
<div id="output" />

To use that in your code, you’d need to change the selectedList string to an array and sort it, as in the code below.

    /* Gathers an array consisting of all the selected values */
    var selectedList = [];
    for (var h = 0; h < selected.length; h++){
        selectedList.push(selected.options[h].value.toLowerCase();
    }
    selectedList.sort();

Then your loop to check whether a given string exists in the array would look like this:

//Loop JSON query structure and reload select
for (var i=0, count = query.ROWCOUNT; i < count; i++){
    var id = query.DATA.ID[i];
    if(getIndex(selectedList, id.toString().toLowerCase()) < 0){
        element.options[element.options.length] = new Option(query.DATA.NAME[i], id);
        var optionLength = element.options.length;
        optionLength--;
        if(query.DATA.title != undefined  && element.options[optionLength] != undefined){
            element.options[optionLength].setAttribute("title",query.DATA.title[i]);
        } else {
            element.options[optionLength].setAttribute('title',query.DATA.NAME[i]);
         }
    }
}

I banged my head against this for a while, but I got it.
The culprit turned out to be this line.

element.options.length = 0;

I’m not sure why, but IE didn’t break when I did it this way.

element.innerHTML = '';

With the .length thing in mind, I then minimized my use of it in the loop:

for (var i=0; i < query.ROWCOUNT; i++){
/*If the value is part of the selected values list, do not include it as an available column*/
    if(selectedList.search(query.DATA.ID[i].toString().toLowerCase()) == -1){
        /* do not use 'i' as we are not adding to options every time */
        var optionLength = element.options.length;

        element.options[optionLength] = new Option(query.DATA.NAME[i], query.DATA.ID[i]);

        if(query.DATA.title != undefined  && element.options[optionLength] != undefined){
            element.options[optionLength].setAttribute("title",query.DATA.title[i]);
        } else {
            element.options[optionLength].setAttribute('title',query.DATA.NAME[i]);
        }
    }
}

These changes fixed the freezing issue in IE, but did not bring any significant improvements to other browsers.