Performancetuning of Store by optimizing Ext.util.Collection

[crp_spaeth]

Hey Guys,

I am currently running some performance test on the Ext.data.Store and syncing back and forth with different Proxies like Ext.data.proxy.SQL.

I run into some bottlenecks which are kindly fatal with a big amount of records managed by The store.

While profiling I located two bottlenecks in the replace method of the internal used Ext.util.Collection class.

In 2.1 the Method looks like this:

   replace: function(oldKey, item) {
        var me = this,
            sorted = me.sorted,
            filtered = me.filtered,
            filterable = me.mixins.filterable,
            items = me.items,
            keys = me.keys,
            all = me.all,
            map = me.map,
            returnItem = null,
            oldItemsLn = items.length,
            oldItem, index, newKey;


        if (arguments.length == 1) {
            item = oldKey;
            oldKey = newKey = me.getKey(item);
        } else {
            newKey = me.getKey(item);
        }


        oldItem = map[oldKey];
        if (typeof oldKey == 'undefined' || oldKey === null || typeof oldItem == 'undefined') {
             return me.add(newKey, item);
        }


        me.map[newKey] = item;
        if (newKey !== oldKey) {
            delete me.map[oldKey];
        }


        if (sorted && me.getAutoSort()) {
            Ext.Array.remove(items, oldItem);
            Ext.Array.remove(keys, oldKey);
            Ext.Array.remove(all, oldItem);


            all.push(item);


            me.dirtyIndices = true;


            if (filtered && me.getAutoFilter()) {
                // If the item is now filtered we check if it was not filtered
                // before. If that is the case then we subtract from the length
                if (filterable.isFiltered.call(me, item)) {
                    if (oldItemsLn !== items.length) {
                        me.length--;
                    }
                    return null;
                }
                // If the item was filtered, but now it is not anymore then we
                // add to the length
                else if (oldItemsLn === items.length) {
                    me.length++;
                    returnItem = item;
                }
            }


            index = this.findInsertionIndex(items, item);


            Ext.Array.splice(keys, index, 0, newKey);
            Ext.Array.splice(items, index, 0, item);
        } else {
            if (filtered) {
                if (me.getAutoFilter() && filterable.isFiltered.call(me, item)) {
                    if (items.indexOf(oldItem) !== -1) {
                        Ext.Array.remove(items, oldItem);
                        Ext.Array.remove(keys, oldKey);
                        me.length--;
                        me.dirtyIndices = true;
                    }
                    return null;
                }
                else if (items.indexOf(oldItem) === -1) {
                    items.push(item);
                    keys.push(newKey);
                    me.indices[newKey] = me.length;
                    me.length++;
                    return item;
                }
            }


            index = me.items.indexOf(oldItem);


            keys[index] = newKey;
            items[index] = item;
            this.dirtyIndices = true;
        }


        return returnItem;
    },

In this Implementation the relativly slow (O(n)) indexOf method of the item-Array is used to get the index of the given item. By using the Collections-Class "indexOf"-Method

     indexOf: function(item) {
        if (this.dirtyIndices) {
            this.updateIndices();
        }

        var index = this.indices[this.getKey(item)];
        return (index === undefined) ? -1 : index;
    },

which uses the member indices to internal hashmap the keys to the index (~O(1)) tweaks this method a lot.

The other bottleneck is in the logic of setting the dirtyIndices flag to true. Setting this flag will intearnaly lead to rehashing all indices. As long as the keys didn't change this is not nessasery at all.
By adding the following condition before the flagging the boost is tremendous and shouldn't cause side effects.

if(oldKey == newKey)
    this.dirtyIndices = true;

I ended up with the following Implementation:

replace: function(oldKey, item) {
       var me = this,
           sorted = me.sorted,
           filtered = me.filtered,
           filterable = me.mixins.filterable,
           items = me.items,
           keys = me.keys,
           all = me.all,
           map = me.map,
           returnItem = null,
           oldItemsLn = items.length,
           oldItem, index, newKey;




       if (arguments.length == 1) {
           item = oldKey;
           oldKey = newKey = me.getKey(item);
       } else {
           newKey = me.getKey(item);
       }




       oldItem = map[oldKey];
       if (typeof oldKey == 'undefined' || oldKey === null || typeof oldItem == 'undefined') {
            return me.add(newKey, item);
       }




       me.map[newKey] = item;
       if (newKey !== oldKey) {
           delete me.map[oldKey];
       }




       if (sorted && me.getAutoSort()) {
           Ext.Array.remove(items, oldItem);
           Ext.Array.remove(keys, oldKey);
           Ext.Array.remove(all, oldItem);




           all.push(item);




           me.dirtyIndices = true;




           if (filtered && me.getAutoFilter()) {
// If the item is now filtered we check if it was not filtered
// before. If that is the case then we subtract from the length
               if (filterable.isFiltered.call(me, item)) {
                   if (oldItemsLn !== items.length) {
                       me.length--;
                   }
                   return null;
               }
// If the item was filtered, but now it is not anymore then we
// add to the length
               else if (oldItemsLn === items.length) {
                   me.length++;
                   returnItem = item;
               }
           }




           index = this.findInsertionIndex(items, item);




           Ext.Array.splice(keys, index, 0, newKey);
           Ext.Array.splice(items, index, 0, item);
       } else {
           if (filtered) {
               if (me.getAutoFilter() && filterable.isFiltered.call(me, item)) {
                   if (me.indexOf(oldItem) !== -1) {
                       Ext.Array.remove(items, oldItem);
                       Ext.Array.remove(keys, oldKey);
                       me.length--;
                       me.dirtyIndices = true;
                   }
                   return null;
               }
               else if (me.indexOf(oldItem) === -1) {
                   items.push(item);
                   keys.push(newKey);
                   me.indices[newKey] = me.length;
                   me.length++;
                   return item;
               }
           }




           index = me.indexOf(oldItem);




           keys[index] = newKey;
           items[index] = item;
           if (newKey !== oldKey) {
               this.dirtyIndices = true;
           }
       }




       return returnItem;
   },

For syncing a Store into a WebSql - Database with a big amount of phantom Records (> 10000) the impact is kind of big... When running the implementation of 2.1 it tooks Minutes on my developing maschine:

before.jpg

with the optimized version only seconds...

after.jpg

It would be nice to see some upcomming optimation in the new Release!

Regards Martin

[mitchellsimoens]

We will take a look at this, thanks for digging into this!

[TommyMaintz]

Hi Martin,

I have applied your optimizations to our codebase for the next release. Thanks for digging into this! I think there might be even more room for optimization in regards of just updating the indices instead of setting the flag in certain places, but that change is more drastic and one I dont want to make right now.

Best,
Tommy