Drastically improve performance in the diff viewer

Review Request #792 — Created March 28, 2009 and submitted — Latest diff uploaded


Review Board SVN (deprecated)


This change introduces a number of major speed improvements to the diff viewer.

1) We're moving to jQuery 1.3.2, which gives us a lot of under-the-hood performance improvements. I've seen 500ms and more shaved off of some of my test diffs.

2) Finding the row representing a line number in a table is now much faster. We were blindly binary searching before, but now we use the power of "maths" to see if we can find the appropriate row relative to where we are on each iteration. While sometimes an "Expand" row will be in the way, often times within a couple iterations we'll be able to directly grab the row we want. In one of my test cases, this took the number of iterations down from 10 to 2.

3) We no longer attempt to grab the row for the line number ending a comment range if we know it's the same row as the beginning of that range. We just reuse the existing value, saving us a binary search.

4) We limit our search area for the binary search based on the known starting line number in a range and the known number of lines. This has sped up some searches quite a bit, in terms of the number of iterations needed, especially combined with the other optimizations in here.

5) We further limit the search based on the last found line number. To do this, we pre-sort the list of line numbers passed to the script, so that earlier line numbers always come first. Then, when we find a beginning row for a comment flag, we set that as the beginning of the range to search next.

6) We no longer grab all anchors across all diff tables every time a diff loads. This was about 30ms a call before. Now we simply take the newly loaded table (since we already have it) and just scan for anchors inside of that, and add to the previous list of anchors. This takes us from 30ms per diff file to ~0.5-1ms per diff file.

7) We add most heavy elements with lots of children to the DOM as late as possible. We attempt to build the tree first and then append to an element at the very end. This saves the browser a lot of work and gives us some pretty good speed boosts (somewhere in the neighborhood of 25ms in a couple places, per diff).
I built up a huge change of whole file deletions and added 5 comments to one diff and 15 comments to another.

Before all these changes, the first diff took ~80ms to load and populate comments, and another ~30ms to update anchors. The second diff took ~1100ms for comments, ~30ms to update anchors.

After these changes, the first diff took about 30ms for comments, 0.5ms for anchors. The second took ~155ms for comments, ~0.5ms for anchors.