[Change] Performance problem: MCL::setItem() is O(n^2)

[mmixLinus]

G'day All,

I'm occasionally building large multicolumn lists and have noticed a problem, that there could be a workaround for: The setItem() operation seems to be quadratic in time. See graph below. The data points are from real life usage, with n being the number of lines added (each line contains 12 items in my case), and the interpolation graph is ~ n^2. The time is in seconds. Without having done any further tests or code changes, my guess is that the culprit is the call to onListContentsChanged() which signals the list has changed, for every item added. If the signal receiver does something for all previously added items, the method ends up being quadratic in time.


I was just thinking that maybe the ContentsChanged signalling should be optional, by adding a default enabled flag (so the API doesn't "break"), and that there should be provided a way for me to explicitly signal the change when my setItems are done. Would it work? Would it help?

Code: Select all

void MultiColumnList::setItem(ListboxItem* item, const MCLGridRef& position, bool bSignalChange /* = true */)
{
...
   if (bSignalChange) {
      // signal a change to the list contents
      WindowEventArgs args(this);
      onListContentsChanged(args);
   }
}


Ideas? I could be completely wrong, of course, and it is the actual array assignment d_grid[position.row][position.column] = item; that is the problem. Anyway, I might try this soon.
/mmixLinus

[mmixLinus]

Hi team,

Well, if you define soon as being "within one month" then it seems I made it! (Not forgetting the obligatory multiplication with pi squared).

So, what I'm trying to say, is that I got around to experimenting with deferring MultiColumnList updates, useful when you're building large tables, for example. So you might be interested in adding this feature ; ) My system is (still ) CEGUI 0.7.4. I'm unaware of any unwanted side-effects, but you (the team) could probably point them out. Also, these results are surely applicable to all the areas in the code that build list and table widgets, and fire UpdateEvents for each added item. But I've only tested for MCL, and only addRow() and setItem(). Of course not everyone is building 800x12 tables, but note that for the "Before" scenario, even at less than 100 rows, we are talking about 1 second build time (quite a lot in a "real-time" 3d graphics environment).

Without much ado, here are the results (Before = Immediate Update, the way 0.7.4 does it (as reported above), After = experimental deferred updating):

I'm doing 9 setItems for each row (not 12 as the image says).
As you can see, the experiment runs about 10 times faster for 100 rows, and 100 times faster for 800 rows!
These are the changes to MultiColumnList.h:

Code: Select all

   //changes in MultiColumnList.h
   uint   addRow(ListboxItem* item, uint col_id, uint row_id = 0, bool deferred_update = false);
   uint   addRow(uint row_id = 0, bool deferred_update = false);
   void   setItem(ListboxItem* item, const MCLGridRef& position, bool deferred_update = false);
   void   setItem(ListboxItem* item, uint col_id, uint row_idx, bool deferred_update = false);
   void   notifyListContentsChanged();


and in those methods I made the event firing optional:

Code: Select all

uint MultiColumnList::addRow(ListboxItem* item, uint col_id, uint row_id, bool deferred_update)
{
   .
   .
   .
  if (!deferred_update)
  {
    // signal a change to the list contents
    WindowEventArgs args(this);
    onListContentsChanged(args);
  }
}


To finalize tables I added this:

Code: Select all

/*************************************************************************
   Signal that the list contents have changed
   Useful for deferred updating
*************************************************************************/
void MultiColumnList::notifyListContentsChanged()
{
   // signal a change to the list contents
   WindowEventArgs args(this);
   onListContentsChanged(args);
}


My own use-case looks something like this:

Code: Select all

void bla::buildTracksList()
{
  for (int j = 0; j < numtracks; ++j) {
    mcl->addRow(true);     // true to defer updating of list
  }
  // Then, for each row
  for (int j = 0; j < numtracks; ++j) {
    item = new CEGUI::ListboxTextItem(trackno, 10*j + 0);
    item->setTextColours(fixcolour);
    item->setTextParsingEnabled(false);
    item->setSelectionBrushImage(sel_im);
    mcl->setItem(item, 0, j, true);        // true is for deferred updating

    // ... repeated eight more times (total, 9 setItem:s)
  }
  mcl->notifyListContentsChanged();
}


Cheers
/Linus

[jherico]

I'm encountering this issue as well. I'm trying to load a ~6 column list with about 200-300 rows and it takes quite a long time.

[Ident]

I sense strong necromancing skills being performed in this thread, lol

Either way for the next version timotei is currently reworking the MCL (next to other classes) so this issue might be gone by then.

Until then, a pull-request would be great so we can take a closer look at the suggested changes.

Deferred updating would btw be a good thing to have at other parts of CEGUI as well. It's a lot of code that would need to be inspected and changed though, so not easy to do.

[Ident]

Code: Select all

[21:57:40]   mpreisler      Timotei's View stuff is inherently lazy updated
[21:57:50]   mpreisler      this O(n^2) problem should not appear in the new code

Just a confirmation this will definitely be fixed in the next major release ( 1.0 )