64
votes

I'm using a modified version of the jQuery UI Autocomplete Combobox, as seen here: http://jqueryui.com/demos/autocomplete/#combobox

For the sake of this question, let's say I have exactly that code ^^^

When opening the combobox, either by clicking the button or focusing on the comboboxs text input, there is a large delay before showing the list of items. This delay gets noticeably larger when the select list has more options.

This delay doesn't just occur the first time either, it happens every time.

As some of the select lists on this project are very large (hundreds and hundreds of items), the delay/browser freezing up is unacceptable.

Can anyone point me in the right direction to optimise this? Or even where the performance problem may be?

I believe the issue may be to do with the way the script shows the full list of items (does an autocomplete search for an empty string), is there another way to display all items? Perhaps I could build a one off case for displaying all items (as it is common to open the list before starting to type) that doesn't do all the regex matching?

Here is a jsfiddle to fiddle with: http://jsfiddle.net/9TaMu/

5
you would probably see the biggest speed increases by doing all of regex and manipulation before the widget is created so only simple array/object lookups are performed when the widget is being used.Alec Gorge

5 Answers

79
votes

With the current combobox implementation, the full list is emptied and re-rendered every time you expand the dropdown. Also you are stuck with setting the minLength to 0, because it has to do an empty search to get the full list.

Here is my own implementation extending the autocomplete widget. In my tests it can handle lists of 5000 items pretty smoothly even on IE 7 and 8. It renders the full list just once, and reuses it whenever the dropdown button is clicked. This also removes the dependence of the option minLength = 0. It also works with arrays, and ajax as list source. Also if you have multiple large list, the widget initialization is added to a queue so it can run in the background, and not freeze the browser.

<script>
(function($){
    $.widget( "ui.combobox", $.ui.autocomplete, 
        {
        options: { 
            /* override default values here */
            minLength: 2,
            /* the argument to pass to ajax to get the complete list */
            ajaxGetAll: {get: "all"}
        },

        _create: function(){
            if (this.element.is("SELECT")){
                this._selectInit();
                return;
            }

            $.ui.autocomplete.prototype._create.call(this);
            var input = this.element;
            input.addClass( "ui-widget ui-widget-content ui-corner-left" );

            this.button = $( "<button type='button'>&nbsp;</button>" )
            .attr( "tabIndex", -1 )
            .attr( "title", "Show All Items" )
            .insertAfter( input )
            .button({
                icons: { primary: "ui-icon-triangle-1-s" },
                text: false
            })
            .removeClass( "ui-corner-all" )
            .addClass( "ui-corner-right ui-button-icon" )
            .click(function(event) {
                // close if already visible
                if ( input.combobox( "widget" ).is( ":visible" ) ) {
                    input.combobox( "close" );
                    return;
                }
                // when user clicks the show all button, we display the cached full menu
                var data = input.data("combobox");
                clearTimeout( data.closing );
                if (!input.isFullMenu){
                    data._swapMenu();
                    input.isFullMenu = true;
                }
                /* input/select that are initially hidden (display=none, i.e. second level menus), 
                   will not have position cordinates until they are visible. */
                input.combobox( "widget" ).css( "display", "block" )
                .position($.extend({ of: input },
                    data.options.position
                    ));
                input.focus();
                data._trigger( "open" );
            });

            /* to better handle large lists, put in a queue and process sequentially */
            $(document).queue(function(){
                var data = input.data("combobox");
                if ($.isArray(data.options.source)){ 
                    $.ui.combobox.prototype._renderFullMenu.call(data, data.options.source);
                }else if (typeof data.options.source === "string") {
                    $.getJSON(data.options.source, data.options.ajaxGetAll , function(source){
                        $.ui.combobox.prototype._renderFullMenu.call(data, source);
                    });
                }else {
                    $.ui.combobox.prototype._renderFullMenu.call(data, data.source());
                }
            });
        },

        /* initialize the full list of items, this menu will be reused whenever the user clicks the show all button */
        _renderFullMenu: function(source){
            var self = this,
                input = this.element,
                ul = input.data( "combobox" ).menu.element,
                lis = [];
            source = this._normalize(source); 
            input.data( "combobox" ).menuAll = input.data( "combobox" ).menu.element.clone(true).appendTo("body");
            for(var i=0; i<source.length; i++){
                lis[i] = "<li class=\"ui-menu-item\" role=\"menuitem\"><a class=\"ui-corner-all\" tabindex=\"-1\">"+source[i].label+"</a></li>";
            }
            ul.append(lis.join(""));
            this._resizeMenu();
            // setup the rest of the data, and event stuff
            setTimeout(function(){
                self._setupMenuItem.call(self, ul.children("li"), source );
            }, 0);
            input.isFullMenu = true;
        },

        /* incrementally setup the menu items, so the browser can remains responsive when processing thousands of items */
        _setupMenuItem: function( items, source ){
            var self = this,
                itemsChunk = items.splice(0, 500),
                sourceChunk = source.splice(0, 500);
            for(var i=0; i<itemsChunk.length; i++){
                $(itemsChunk[i])
                .data( "item.autocomplete", sourceChunk[i])
                .mouseenter(function( event ) {
                    self.menu.activate( event, $(this));
                })
                .mouseleave(function() {
                    self.menu.deactivate();
                });
            }
            if (items.length > 0){
                setTimeout(function(){
                    self._setupMenuItem.call(self, items, source );
                }, 0);
            }else { // renderFullMenu for the next combobox.
                $(document).dequeue();
            }
        },

        /* overwrite. make the matching string bold */
        _renderItem: function( ul, item ) {
            var label = item.label.replace( new RegExp(
                "(?![^&;]+;)(?!<[^<>]*)(" + $.ui.autocomplete.escapeRegex(this.term) + 
                ")(?![^<>]*>)(?![^&;]+;)", "gi"), "<strong>$1</strong>" );
            return $( "<li></li>" )
                .data( "item.autocomplete", item )
                .append( "<a>" + label + "</a>" )
                .appendTo( ul );
        },

        /* overwrite. to cleanup additional stuff that was added */
        destroy: function() {
            if (this.element.is("SELECT")){
                this.input.remove();
                this.element.removeData().show();
                return;
            }
            // super()
            $.ui.autocomplete.prototype.destroy.call(this);
            // clean up new stuff
            this.element.removeClass( "ui-widget ui-widget-content ui-corner-left" );
            this.button.remove();
        },

        /* overwrite. to swap out and preserve the full menu */ 
        search: function( value, event){
            var input = this.element;
            if (input.isFullMenu){
                this._swapMenu();
                input.isFullMenu = false;
            }
            // super()
            $.ui.autocomplete.prototype.search.call(this, value, event);
        },

        _change: function( event ){
            abc = this;
            if ( !this.selectedItem ) {
                var matcher = new RegExp( "^" + $.ui.autocomplete.escapeRegex( this.element.val() ) + "$", "i" ),
                    match = $.grep( this.options.source, function(value) {
                        return matcher.test( value.label );
                    });
                if (match.length){
                    match[0].option.selected = true;
                }else {
                    // remove invalid value, as it didn't match anything
                    this.element.val( "" );
                    if (this.options.selectElement) {
                        this.options.selectElement.val( "" );
                    }
                }
            }                
            // super()
            $.ui.autocomplete.prototype._change.call(this, event);
        },

        _swapMenu: function(){
            var input = this.element, 
                data = input.data("combobox"),
                tmp = data.menuAll;
            data.menuAll = data.menu.element.hide();
            data.menu.element = tmp;
        },

        /* build the source array from the options of the select element */
        _selectInit: function(){
            var select = this.element.hide(),
            selected = select.children( ":selected" ),
            value = selected.val() ? selected.text() : "";
            this.options.source = select.children( "option[value!='']" ).map(function() {
                return { label: $.trim(this.text), option: this };
            }).toArray();
            var userSelectCallback = this.options.select;
            var userSelectedCallback = this.options.selected;
            this.options.select = function(event, ui){
                ui.item.option.selected = true;
                if (userSelectCallback) userSelectCallback(event, ui);
                // compatibility with jQuery UI's combobox.
                if (userSelectedCallback) userSelectedCallback(event, ui);
            };
            this.options.selectElement = select;
            this.input = $( "<input>" ).insertAfter( select )
                .val( value ).combobox(this.options);
        }
    }
);
})(jQuery);
</script>
20
votes

I've modified the way the results are returned (in the source function) because the map() function seemed slow to me. It runs faster for large select lists (and smaller too), but lists with several thousands of options are still very slow. I've profiled (with firebug's profile function) the original and my modified code, and the execution time goes like this:

Original: Profiling (372.578 ms, 42307 calls)

Modified: Profiling (0.082 ms, 3 calls)

Here is the modified code of the source function, you can see the original code at the jquery ui demo http://jqueryui.com/demos/autocomplete/#combobox. There can certainly be more optimization.

source: function( request, response ) {
    var matcher = new RegExp( $.ui.autocomplete.escapeRegex(request.term), "i" );
    var select_el = this.element.get(0); // get dom element
    var rep = new Array(); // response array
    // simple loop for the options
    for (var i = 0; i < select_el.length; i++) {
        var text = select_el.options[i].text;
        if ( select_el.options[i].value && ( !request.term || matcher.test(text) ) )
            // add element to result array
            rep.push({
                label: text, // no more bold
                value: text,
                option: select_el.options[i]
            });
    }
    // send response
    response( rep );
},

Hope this helps.

15
votes

I like the answer from Berro. But because it was still a bit slow (I had about 3000 options in select), i modified it slightly so that only first N matching results are displayed. I also added an item at the end notifying the user that more results are available and canceled focus and select events for that item.

Here is modified code for source and select functions and added one for focus:

source: function( request, response ) {
    var matcher = new RegExp( $.ui.autocomplete.escapeRegex(request.term), "i" );
    var select_el = select.get(0); // get dom element
    var rep = new Array(); // response array
    var maxRepSize = 10; // maximum response size  
    // simple loop for the options
    for (var i = 0; i < select_el.length; i++) {
        var text = select_el.options[i].text;
        if ( select_el.options[i].value && ( !request.term || matcher.test(text) ) )
            // add element to result array
            rep.push({
                label: text, // no more bold
                value: text,
                option: select_el.options[i]
            });
        if ( rep.length > maxRepSize ) {
            rep.push({
                label: "... more available",
                value: "maxRepSizeReached",
                option: ""
            });
            break;
        }
     }
     // send response
     response( rep );
},          
select: function( event, ui ) {
    if ( ui.item.value == "maxRepSizeReached") {
        return false;
    } else {
        ui.item.option.selected = true;
        self._trigger( "selected", event, {
            item: ui.item.option
        });
    }
},
focus: function( event, ui ) {
    if ( ui.item.value == "maxRepSizeReached") {
        return false;
    }
},
11
votes

We found the same thing, however in the end our solution was to have smaller lists!

When I looked into it it was a combination of several things:

1) The contents of the list box is cleared and re-built every time the list box is shown (or the user types something in and starts to filter the list). I think that this is mostly unavoidable and fairly core to the way the list box works (as you need to remove items from the list in order for filtering to work).

You could try changing it so that it shows and hides items in the list rather than completely re-constructing it again, but it would depend on how your list is constructed.

The alternative is to try and optimise the clearing / construction of the list (see 2. and 3.).

2) There is a substantial delay when clearing the list. My theory is that this is at least party due to every list item having data attached (by the data() jQuery function) - I seem to remember that removing the data attached to each element substantially sped up this step.

You might want to look into more efficient ways of removing child html elements, for example How To Make jQuery.empty Over 10x Faster. Be careful of potentially introducing memory leaks if you play with alternative empty functions.

Alternatively you might want to try to tweak it so that data isn't attached to each element.

3) The rest of the delay is due to the construction of the list - more specifically the list is constructed using a large chain of jQuery statements, for example:

$("#elm").append(
    $("option").class("sel-option").html(value)
);

This looks pretty, but is a fairly inefficient way of constructing html - a much quicker way is to construct the html string yourself, for example:

$("#elm").html("<option class='sel-option'>" + value + "</option>");

See String Performance: an Analysis for a fairly in-depth article on the most efficient way of concatenating strings (which is essentially what is going on here).


Thats where the problem is, but I honestly don't know what the best way of fixing it would be - in the end we shortened our list of items so it wasn't a problem any more.

By addressing 2) and 3) you may well find that the performance of the list improves to an acceptable level, but if not then you will need to address 1) and try to come up with an alternative to clearing and re-building the list every time it is displayed.

Surprisingly the function filtering the list (which involved some fairly complex regular expressions) had very little effect on the performance of the drop down - you should check to make sure that you have not done something silly, but for us this wasn't the performance bottlekneck.

1
votes

What I have done I am sharing:

In the _renderMenu, I've written this:

var isFullMenuAvl = false;
    _renderMenu: function (ul, items) {
                        if (requestedTerm == "**" && !isFullMenuAvl) {
                            var that = this;
                            $.each(items, function (index, item) {
                                that._renderItemData(ul, item);
                            });
                            fullMenu = $(ul).clone(true, true);
                            isFullMenuAvl = true;
                        }
                        else if (requestedTerm == "**") {
                            $(ul).append($(fullMenu[0].childNodes).clone(true, true));
                        }
                        else {
                            var that = this;
                            $.each(items, function (index, item) {
                                that._renderItemData(ul, item);
                            });
                        }
                    }

This is mainly for server side request serving. But it can used for local data. We are storing requestedTerm and checking if it matches with ** which means full menu search is going on. You can replace "**" with "" if you are searching full menu with "no search string". Please reach me for any type of queries. It improves performance in my case for at least 50%.