Poor "add" performance on sorted collections

[dts]

I am having significant performance problems when adding items separately to a sorted collection. This appears to be because a whole-list sort happens every time an item is added. In my case, I cannot roll all of the additions into a single addition operation (which would trigger only one sort).

Performance could be improved by using binary search to find the insertion point (unfortunately not with underscore's sortedIndex, as this does not take a comparator), and inserting the record at the appropriate location instantly.

[jabberfest]

You can always pass the {sort:false} option into the add call if you are using it in some type of loop. Then after you exit the loop call sort once on the collection.

[megawac]

Is it worth adapting underscore.sortedIndex for comparators? Something like this should work for this case:

_.sortedIndex = function(array, obj, iterator, context) {
    if (array.length === 0) return 0;
    var comparator = _.isFunction(iterator) && iterator.length == 2;
    iterator = lookupIterator(iterator, context, 1);
    var value = comparator && iterator(obj);
    var low = 0, high = array.length;
    while (low < high) {
      var mid = (low + high) >>> 1;
      if (comparator ? comparator(obj, array[mid]) > 0 : iterator(array[mid]) < value) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return low;
};

[dts]

I'd say that updating sortedIndex in that way is important. Comparators are the native way that JS uses to describe sorting, so it makes sense to support them in libraries like underscore.

[joshuabambrick]

I considered developing the binary search approach that you suggested as part of my pull request on issue #3207. However, I decided against it as it is probably more common that a large number of items will be added at one time, especially at the initial load of the app, as opposed to separately.

In this case, adding u items to a finally n item list would take O(n lg n), but the binary insertion method would take O(u * n) - which I reckon would usually be higher or at least more noticable when it it higher. You could try to estimate which approach would be faster and change implementation on the fly but this would make the code more complicated and increase the file size.

[cmaher]

If you know when adding models stops, you can use { sort: false } and then manually sort when you're finished

[dts]

I am trying to maintain dependent collections (complete set A of models, subset B filtered by function X). They are kept synchronized by using add/remove/etc. events from A to B. Since there are only single-add events, I am limited to only adding one model at a time. I have currently hardcoded the sorting because the insertion sorting is so much faster than the previous method. This is fine for me, but I still haven't heard any convincing arguments for why single-insertion should be made slow in order to optimize for multi-insertions - can't we easily tell the difference between these two cases?

[jamiebuilds]

I figured I'd test to see what kind of performance boost one would get from using { sort: false } and calling collection.sort() when you are done, and it appears to actually slow things down: http://jsperf.com/backbone-collection-add (tested with the use case @dts outlined).

[jabberfest]

@thejameskyle awesome test! I tweaked it a bit. It's even slower if you don't sort both collections until the end.

http://jsperf.com/backbone-collection-add/6

[farias-r7]

I also don't know how that benchmark is computer opts per second. The results are suspect. Take a look at his. According to the test the Backbone Sort Implementation is way faster than the native Array sort. This makes no sense.

Backbone.Collection uses either the native javascript array "sort" or the underscore _.sortBy method behind the scenes. _.sortBy itself ends up using the Array.sort that is built into javascript.

http://jsperf.com/native-array-sort-performance

[megawac]

That's not suspect at all @jabberfest in your native tests you're doing the backbone sort on each addition to the collection + the extra native sort on the ever growing collectionA array. Whereas the other ones are just doing the backbone sort.

[jabberfest]

@megawac collectionA is just a plain javascript Array. collectionB is a Backbone Collection. I was confused because the results showed that sorting a Backbone Collection was significantly faster than sorting a javascript Array.

Sorry about the confusion. collectionA should have really been named more appropriately.

[megawac]

Ah nevermind, misread the tests. The differences is the backbone collection will only be length 20 whereas the native array will grow with the tests. AFAIK it only calls Benchmark.teardown between tests.

Fixed to show what you seem to want to see http://jsperf.com/native-array-sort-performance/2

[kidplug]

@dts - I had the same issue - maintaining a "filtered sub-collection" based off of the first collection.

Adding models one a time to the subcollection can be crushing to performance when the subcollection is a sorted collection.

I modified Backbone collection to send an "adds" event (after the "add" events) and pass the array of models that were added. That way your subcollection can receive all the new models in one event and do its own "bulk" add and have only ONE sort.

I did the same thing with "removes" - mostly for consistency.

[sayyedhanif]

Is there any utility/lib to improve performance(or optimize code) on backbone code while running on mobile

[jashkenas]

Yes. If you're adding items one at a time, keeping the list sorted is going to be fundamentally slower.

In my case, I cannot roll all of the additions into a single addition operation (which would trigger only one sort).

I'd suggest finding a way ;) That's the correct way to deal with this issue. (And one of the reasons why reset exists.)

[dts]

@jashkenas: It is possible, as @kidplug suggests, to add a new event by modifying or monkey-patching Backbone to support it, but this does not seem like a fantastic solution either, as it also involves modifying Backbone internals. I have not seen a way to do this without bungling up the innards of backbone, which is why I raised this issue. Further, there doesn't seem to be a compelling reason preventing the correct-location insertion of the item (mergesort, basically), except that the sortedIndex method doesn't accept comparators.

[sayyedhanif]

Thanks for ur suggestions...