[wx-dev] #9527: Patch to improve wxGrid::BlockToDeviceRect. dramatic speed improvement on large grids

[wxTrac]

Ticket URL: <http://trac.wxwidgets.org/ticket/9527>

#9527: Patch to improve wxGrid::BlockToDeviceRect.  dramatic speed improvement on
large grids
-------------------------------------------------------------------------------------------------------+
 Reporter:  kjones at cedrus.com                                                                          |       Owner:       
     Type:  optimization                                                                               |      Status:  new  
 Priority:  normal                                                                                     |   Milestone:       
Component:  GUI-generic                                                                                |     Version:  2.8.7
 Keywords:  speed optimization wxGrid wxGridCellAttrProvider wxGridSelection ClearSelection SelectCol  |   Blockedby:       
    Patch:  1                                                                                          |    Blocking:       
-------------------------------------------------------------------------------------------------------+
 I have created a patch to eliminate unnecessary looping during column-
 selection events.  This is a significant speed optimization (especially
 for large grids).

 I noticed that when I have a grid containing 10,000 rows or so, if I
 perform a single left click on a column heading (to select the column),
 there is a noticeable lag between the moment when I make the click and the
 moment when the grid paints the selected column with the selection color.
 This lag can be as long as 1 or 2 seconds.

 (Note: This slowness might not be so noticeable in a grid that does not
 use attributes.  I am using wxGrid::SetRowAttr, which causes the grid to
 construct and use a wxGridCellAttrProvider internally.)

 I discovered that the slowness is being caused by some unnecessary looping
 in wxGrid::BlockToDeviceRect.

 The inefficiency of wxGrid::BlockToDeviceRect can be described as follows:

         BlockToDeviceRect receives as input two pairs of (row,col)
 coordinates.  It receives the (row,col) pair for both the Top Left cell
 and the Bottom Right cell that define the targeted block of cells.

         For example, if I select all of "column 4" in a grid that has
 10,000 rows, then the Top Left cell parameter is set to ( 0, 4 ) and the
 Bottom Right parameter is set to ( 9999, 4 ).

         What BlockToDeviceRect then does is to loop through all 10,000
 cells to find what I will call the "total bounding rectangle" that will
 fully contain all of the selected cells.  You might think that knowing the
 rectangle of the Top Left cell and knowing the rectangle of the Bottom
 Right cell would be sufficient for you to extrapolate the "total"
 rectangle that would bound the entire column.  However, that is **NOT**
 sufficient.  Why not?  Answer: because somewhere in the middle of the
 column there could be a cell which has been merged into its neighbor cell.
 That merged cell will be twice as wide as the other cells.  I will need to
 expand my total bounding rectangle to accommodate that "extra-wide" cell
 in the middle of the column.

         After looping through 10,000 cells, BlockToDeviceRect then calls
 upon wxWindowBase::GetClientSize to determine how much of that "total
 bounding rectangle" is actually shown in the viewable displayed area of
 the grid's scroll window.

         The end result is that BlockToDeviceRect will return a rectangle
 that represents the overlap of the ClientSize (the actual "on screen"
 window) and the absolute selection rectangle (which is very large....
 10,000 rows tall).



 CONCLUSION:   It is wasteful for BlockToDeviceRect to loop through 10,000
 rows (or more) when we have readily-available methods of determining how
 many of those rows are actually viewable in the client window.

 I have submitted a patch which takes advantage of the binary search that
 has already been a part of wxGrid for as long as I have known wxGrid.

 The wxGrid class already makes available "internalXToCol(x)" and
 "internalYToRow(y)", which both make good use of a binary search to help
 quickly determine which column and which row are at any given pixel
 location of the viewable area.

 My patch simply makes new use of this already-implemented binary search by
 applying internalXToCol and internalYToRow inside of
 wxGrid::BlockToDeviceRect.

 This has sped up column selection events for me dramatically.  (Again, one
 reason why my grid objects might be more sensitive to this slowdown than
 someone else's grid objects is that I am using attributes, which means
 that every time the size of a cell is queried, wxGridTableBase::GetAttr
 will call m_attrProvider->GetAttr(row, col, kind) ).


--
Ticket URL: <http://trac.wxwidgets.org/ticket/9527>