Poor performance inserting into sorted tables

[gbeaty]

I've been evaluating a number of different table/grid systems for their performance upserting data in real-time, especially on mobile devices.

I made this benchmark for Backgrid. 9 columns, 100 rows:
https://gist.github.com/gbeaty/981f91592eec8cf6f222

Obviously it does a bit more than just manipulate the table, but in backgrid's case there isn't a lot of other boilerplate to affect things. Just a JSON.parse() call.

On my i7, I get unsorted upsert times of about 3.5 ms, and sorted times of 280 ms.
On my Samsung Note 2 phone, those numbers are 24 ms and 1900 ms.

For comparison's sake, on i7 / Note 2:
DataTables sorted: 11.5 ms / 122 ms (sorting had no effect)
SlickGrid unsorted: 0.06 ms / 0.5 ms
SlickGrid sorted: 0.5 ms / 3.6 ms

I'm using Chrome for all benchmarks.

SlickGrid uses array.sort(), and supports batch inserts, edits, whatever, so many things can be changed before a re-sort.

Did I mis-use the Backgrid or Backbone APIs to achieve these #s?

[wyuenho]

Backgrid by itself doesn't do anything particularly stupid to slow things down, but Backgrid does use jQuery and it ain't the speediest animal on the planet. Google SpeedTracer is showing something like 630ms spent in jQuery's limbo of performance hell during a 700ms interval.

Can you give Zepto and jQuery Mobile a try tho?

[wyuenho]

BTW, there's support for batch insertion and removal. It's not obvious but you can just do it the Backbone way - pass options.silent: true to your collection and then call grid.render or grid.body.render(), which will be a little bit faster.

I'm very interested in seeing the code for your benchmark for all these other grids.

[wyuenho]

I've narrowed down the cause of slowness to the frequent construction of the jQuery object in Backbone.View's constructor. Without hacking up Backgrid's own View subclass object, I've avoided view (and hence jQuery) construction where possible and simply reuse existing nested views.

Time for refreshing the grid has been cut down by roughly half. Row insertion is still roughly the same as the individual row views still need to be constructed one by one, again, blame jQuery and Backbone.View. Removing rows should be as fast as it can be without. Since Backbone 1.0, Collection.fetch now defaults to use Collection.set, so there will be a separate reflow for each element inserted, you can pass {option.reset: true}, to force a reset and thru only repaint once.

It is possible to half rendering time (or more) again by completely ripping jQuery out by using a custom View subclass. But that's going a little too far.

I've tested sorting the first example from the document using this new approach. That big chunk of time time spent in jQuery went down from 600ms+ to ~300ms.

There are a couple of things broken at the moment, namely a body test, the empty row and compatibility with backbone-pageable. Fixes will go in the perf branch shortly.

Checkout the perf branch for details.

[gbeaty]

Thanks for the quick response. Unfortunately this still leaves Backgrid far too slow in mobile updates for our uses (we're going to have to go with SlickGrid), but I hope the benchmarks have been of some use to you.

I've tried Zepto mobile, without significant improvement. For some reason I'm unable to replicate my previous #s even with normal jQuery. I'm not sure what changed, but I'm not all that familiar with javascript so should probably just leave this sort of thing to people who are.

Zepto unsorted: 5.6ms on PC, 28ms on Note2.
Zepto sorted: 387ms PC, 1964ms Note2.
jQuery unsorted: 7.5ms on PC, 35ms on Note.
jQuery sorted: 581ms on PC, 3619ms on Note 2.
(this is with normal jQuery and the same version of BackGrid I used before)

We aren't doing anything special with DataTables or SlickGrid. SlickGrid uses DataView, which slows things down a tad (but its so fast, who cares). We are using bScrollInfinite with DataTables, which speeds things up a bit. There's a lot of our own code in those benchmarks but I post gists of them if it'll help you.

[wyuenho]

Thanks for this ticket. I've done some benchmarks of my own and I think I know where the hotspots are and what I should do to make Backgrid really fast. The thing is, Backgrid is less then 3 months since its initial release. It hasn't even reached 0.3. Performance improvement will be a continuous process and involve lots of experiments, but I assure you, I realize that this may potentially become a big problem on tablets and I have total confidence that I can drastically improve the performance of Backgrid by ripping out jQuery when I release 0.3.

[gbeaty]

Ah whoops, I'd identically missed a source change that added an extra row being upserted per call in my last #s, which is why they were higher than before.

I was very happy with the unsorted performance. With Zepto (jQ mobile oddly did not help) its only 12ms on my phone, much faster than DT and probably not anything the user would notice. Is there any way to get the sorted figures down in the short-term? All of our tables are always sorted. I suppose its nothing as simple as moving towards your own sorting routine.

[gbeaty]

Also, I'm seeing about 90ms spent in body.render() and 110ms in render(), per call. So using them is not nearly as quick as non-silent row inserts . Most of the time seems to be spent on backbone and jQuery event handlers?

[wyuenho]

Sorting in Backbone is actually pretty damn fast, it's creating the jQuery context in every View construction that's slow, and I bet it's the same whether it's jQuery, Zepto, Enders, Mootools or what have you. The way Backgrid works is to create a bunch of nested View objects that act as a sort of reversed-DOM on the JS side. Rerendering the naive way essentially involves destroying the View objects and the DOM nodes that the View objects are managing and creating new View objects. In the experimental perf branch, Chrome's profiler shows that 90+% of the JS time spent is in creating the O(n^2) that many jQuery contexts for all the table cells. The bad news is that there's no way to tell Backbone.View to not automatically create all those jQuery contexts for me, the good news is, when I get down to improve Backgrid's performance, I can make a custom Backgrid.View class that doesn't use jQuery at all. I'm confident that it'll match Slickgrid's performance. There's no short term fix however. This will have to wait til 0.3.0, which hopefully I'll be able to release in about a month.

[elyk]

I was testing the new perf branch and wrapped the sort listeners callback refresh call (on line 2036) in Underscore.js's defer function and it drastically improved performance. In fact, it was about the same as unsorted performance.

Do you see any reason not to do this?

[elyk]

Never mind. Issue still remains.

[oosterholt]

+1

[excentris]

+1

[WRidder]

+1