bottle-neck of ListBox::AddItem

[beyondlwm]

Hi,

I'm using Listbox for my project, while I found the efficiency of "AddItem" getting slower and slower as the item count increase.
I did some analysis:
To Add 2000 items: (the cost time is progress * 600 s)
Origin：Finished at progress: 0.642449
then Remove Binary chop (my own logic)：Finished at progress: 0.636080
then Remove ensureItemIsVisible: Finished at progress: 0.422948
then Use native std::vector instead of AddItem method : Finished at progress: 0.000307

You can see "AddItem" spends 253 seconds more than native vector!

After some time I found the bottle-neck is here:
void Listbox::configureScrollbars(void) in CEGUI\CEGUIBase\src\elements\CEGUIListbox.cpp Line 572
I saw cegui call function
float totalHeight = getTotalItemsHeight();
float widestItem = getWidestItemWidth();
at line 577 578, in these two method, there is a for loop in it. it's O(N) operation. that's why we getting slower and slower.


what I'm going to do is, add two member-variable to monitor the total height and wide. so each time we want to get them ,just return the variable instead of calculating them by iterating visit each member. However, I hope there will be more optimization in function ensureItemIsVisible.

Is there any better solution that I may miss? Any replies will be welcome.

[beyondlwm]

Hi,

I think I've found a bug in void Listbox::ensureItemIsVisible(size_t item_index)

At the first 4 rows like :

Scrollbar* vertScrollbar = getVertScrollbar();
// handle simple "scroll to the bottom" case
if (item_index >= getItemCount())
{
vertScrollbar->setScrollPosition(vertScrollbar->getDocumentSize() - vertScrollbar->getPageSize());
}

Notice that: item_index will never >= getItemCount(), max value of item_index could be getItemCount() -1. so the simple case will never be triggered. that's why this function will costs some time.


By the way my version is 0.7.5.


After I cache the totalHeight and widest variable of box list , and fix the bug which is mentioned above, the result becomes much better like :

Origin：Finished at progress:0.009866

I think there should be more optimization we can do, because sometimes we can ignore the scrollbar operation (such as init some item in the box), that would be future work, however, current efficiency is good enough for me.

There is one thing confuse me : why each item has a different height? Any one can show me an example that a list has different height items?

[Kulik]

I've been developing for Worldforge/Ember and I have noticed it as well. I will look into it once I get the necessary time.

Could you perhaps clone v0-7 and make a pull request with the necessary change?