Last Comment Bug 780473 - optimize list rebuilding and filter update/movement operations in the filter list dialog
: optimize list rebuilding and filter update/movement operations in the filter ...
Status: RESOLVED FIXED
[gs]
: perf
Product: MailNews Core
Classification: Components
Component: Filters (show other bugs)
: Trunk
: All All
: -- normal with 1 vote (vote)
: Thunderbird 18.0
Assigned To: :aceman
:
:
Mentors:
https://getsatisfaction.com/mozilla_m...
Depends on: 450302
Blocks: 243241 TB2SM 783214 543419 775450 783110 783491
  Show dependency treegraph
 
Reported: 2012-08-05 08:06 PDT by :aceman
Modified: 2012-10-08 02:14 PDT (History)
13 users (show)
ryanvm: in‑testsuite-
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
fixed


Attachments
WIP patch (17.30 KB, patch)
2012-08-05 13:19 PDT, :aceman
rkent: feedback+
Details | Diff | Splinter Review
patch v2 (19.84 KB, patch)
2012-08-15 15:08 PDT, :aceman
no flags Details | Diff | Splinter Review
patch v3 (19.41 KB, patch)
2012-08-16 13:33 PDT, :aceman
mkmelin+mozilla: review+
Details | Diff | Splinter Review
patch v4 (19.48 KB, patch)
2012-08-25 07:45 PDT, :aceman
acelists: review+
acelists: feedback+
standard8: approval‑comm‑aurora+
Details | Diff | Splinter Review

Description :aceman 2012-08-05 08:06:06 PDT
After bug 450302 has landed, the rebuildFilterList function is called more times as the list toggles between filtered and unfiltered view.
Even in the unfiltered view this has performance impact if the list is very long.

I benchmarked on a 3Ghz machine with 10000 filters.
In this scenario, Move to Top takes 8 seconds even in unfiltered view.
In filtered view, Move Up takes 20 seconds.
Also setting the search string to a value that matches few filters takes on the order of 50 seconds.

I'll attach a patch shortly.
Comment 1 :aceman 2012-08-05 13:19:41 PDT
Created attachment 649128 [details] [diff] [review]
WIP patch

So after applying this patch I get these times:
- 1 second
- 2 seconds
- 2-5 seconds (it depends a bit on how many elements were shown in the list before the new search term is written)

But I see some caching effects in that first time I do an operation it takes longer but all subsequent runs are very fast (the times written above).

The meat of the patch is this:
- optimize rebuildFilterList() to reuse existing listitems (instead of tearing all down and creating new ones) and then add/remove the tail as needed.
- remove many places where rebuildFilterList() is called and then the search is applied to it by removing non-matching rows. This was merged into rebuildFilterList() to only pass through the XUL rows once and only render those that match.

There are also some small optimizations, like removal of updateSearchBox() in some places (as it is called in rebuildFilteList already). And fixes to selection in moveFilter.

Axel please see if I didn't break any of your search logic anywhere.

I think there must be a way to also remove one rebuild when msgMoveMotion.Up and msgMoveMotion.Down. But I must think about that.
Also I want to shuffle the arguments to rebuildFilterList and document them, but I attach this to start discussion.
Comment 2 Kent James (:rkent) 2012-08-15 09:42:01 PDT
Comment on attachment 649128 [details] [diff] [review]
WIP patch

So I looked over the patch, but did not try to apply it.

It has been several years since I worked in this code, so it would reasonably take me an hour or two to really review this carefully, which I am not going to to. Just looking at it briefly there were no obvious problems though, and it is worthwhile to fix some of these performance issues.

One note though: Code churn can break extensions. I found several extensions that use rebuildFilterList (though 2 involve Axel, the other active one is Filter of Filters by xzer) I'm not sure how your changes would affect those extensions, or whether the patch breaks them anyway. But if you could avoid changing the calling sequence to rebuildFilterList, it would be nice.
Comment 3 :aceman 2012-08-15 10:54:50 PDT
Thanks a lot. rebuildFilterList after the patch still has the same functionality but I change the meaning of the argument. And the argument the extensions probably pass (gCurrentFilterList) will actually break the function after the patch.
I think Axel can remove the usage of rebuildFilterList (maybe all overlaying of TB filterlist dialog) in his QuickFolders extension (because the functionality is now merged in bug 450302). I can't say for the other extensions.

I changed the argument because it seemed basically unused (the passed in gCurrentFilterList was always the same current list, never something else).
I can keep the argument and just ignore it and add another one for my needs.
What are the proposals here?
Comment 4 neil@parkwaycc.co.uk 2012-08-15 12:27:22 PDT
Well, I find the relationship between onFindFilter and rebuildFilterList to be quite confusing so I think you should split rebuildFilterList into two methods so that onFindFilter doesn't have to call it.
Comment 5 Axel Grude [:realRaven] 2012-08-15 13:02:37 PDT
(In reply to :aceman from comment #3)
> Thanks a lot. rebuildFilterList after the patch still has the same
> functionality but I change the meaning of the argument. And the argument the
> extensions probably pass (gCurrentFilterList) will actually break the
> function after the patch.

I think Filter of Filters will be obsolete after the landing patch for bug 450302 - otherwise there will be multiple search boxes. Both quickFilters and QuickPasswords guard against that patch and omit the overlay in a patched Thunderbird, so there is no problem here either. They will only overload onTop, onBottom, onUp, onDown and onFindFilter  (and use rebuildFilterList(gCurrentFilterList)) when there is no searchBox element in the dialog.

> I changed the argument because it seemed basically unused (the passed in
> gCurrentFilterList was always the same current list, never something else).
> I can keep the argument and just ignore it and add another one for my needs.
> What are the proposals here?

I am not sure that it is safe to overwrite the global gCurrentFilterList  during setFolders(), need to apply your patch to see.
Comment 6 :aceman 2012-08-15 15:08:20 PDT
Created attachment 652253 [details] [diff] [review]
patch v2

Good idea Neil. But I could actually leave it at one function and just not call onFindFilter directly anymore. I moved the focusing stuff to rebuildFilterList and that allowed to strip onFindFilter a lot. Axel?
Comment 7 :aceman 2012-08-15 15:12:28 PDT
(In reply to Axel Grude [:realRaven] from comment #5)
> I think Filter of Filters will be obsolete after the landing patch for bug
> 450302 - otherwise there will be multiple search boxes. Both quickFilters
> and QuickPasswords guard against that patch and omit the overlay in a
> patched Thunderbird, so there is no problem here either. They will only
> overload onTop, onBottom, onUp, onDown and onFindFilter  (and use
> rebuildFilterList(gCurrentFilterList)) when there is no searchBox element in
> the dialog.
That would be cool. I CCed a user xzer, I hope it is the author of the Filter of Filters extension.

(I have CCed Seamonkey guys by mistake, I always forget this one FilterListDialog.js file is TB-only. Sorry about that.)

> I am not sure that it is safe to overwrite the global gCurrentFilterList 
> during setFolders(), need to apply your patch to see.
I think previously seFolders was calling rebuildFilterList that also overwrote gCurrentFilterList so I moved this to setFolders directly, thinking it is equivalent. Please check it.
Comment 8 xzer 2012-08-15 16:30:24 PDT
> That would be cool. I CCed a user xzer, I hope it is the author of the
> Filter of Filters extension.
> 

Thank you for cc me, aceman. I will be glad to see it becomes a built-in
function of TB. Since my extention will become obsolete after the bug 450302,
I do not think there is anything that should worry about.

Only one thing that I want to know which release version will include the
patch on bug 450302? I think I can add some version check to avoid misuse.
Comment 9 xzer 2012-08-15 16:42:20 PDT
One more thing, I think the WIP patch here would be released with the patch of bug 450302 together, is there any misunderstanding?

If WIP patch will be released before bug 450302, I think it actually causes a problem to me.
Comment 10 :aceman 2012-08-15 21:35:12 PDT
Bug 450302 is already fixed and marked as being released in Thunderbird 17.

The bug here is only an optional speed improvement for the filter list dialog, on top of bug 450302. I doubt it will still make it into TB17. It is true that only this bug here will break your extension, but you should actually disable your functionality when fix for bug 450302 is present so starting at TB17.
Comment 11 xzer 2012-08-15 22:52:32 PDT
(In reply to :aceman from comment #10)
> Bug 450302 is already fixed and marked as being released in Thunderbird 17.
> 
> The bug here is only an optional speed improvement for the filter list
> dialog, on top of bug 450302. I doubt it will still make it into TB17. It is
> true that only this bug here will break your extension, but you should
> actually disable your functionality when fix for bug 450302 is present so
> starting at TB17.

It's good. I will kill my extension when TB17 being released.
Comment 12 :aceman 2012-08-16 01:52:46 PDT
OK, I think I can still optimize moveFilter() to not rebuild the list twice (once generating full list and then the new filtered list). Then I can drop the new second argument to rebuildFilterList.
Comment 13 :aceman 2012-08-16 03:07:29 PDT
CCing John David Galt as he is interested in the performance of the dialog with 1000s of filters (bug 450302 comment 49).

For testers, there is a filter generator at https://bugzilla.mozilla.org/attachment.cgi?id=514339 that you can use to create any number of filters.
Comment 14 :aceman 2012-08-16 13:33:45 PDT
Created attachment 652547 [details] [diff] [review]
patch v3

Optimization from comment 12. I could even remove both arguments to rebuildFilterList.
With this version, Move Up/Down takes 0.5s in filtered view (with 10000 out of 10003 filters shown as in comment 0).
Comment 15 Axel Grude [:realRaven] 2012-08-16 18:34:34 PDT
Sorry I am still fighting with my c-c build, which appears to be broken after the latest tree checkout. Once I can build again, I will be able to give feedback.
Comment 16 Magnus Melin 2012-08-18 12:21:57 PDT
Comment on attachment 652547 [details] [diff] [review]
patch v3

Review of attachment 652547 [details] [diff] [review]:
-----------------------------------------------------------------

Thx for the patch, just a few nits. r=mkmelin

::: mail/base/content/FilterListDialog.js
@@ +240,4 @@
>    if (selectedFilter) {
>      // Get the position in the unfiltered list.
>      // - this is where the new filter should be inserted!
> +    for (let i = 0; i < gCurrentFilterList.filterCount; i++) {

should cache gCurrentFilterList.filterCount

@@ +259,5 @@
>  
>      // Select the new filter, it is at the position of previous selection.
>      list.clearSelection();
> +    list.addItemToSelection(list.getItemAtIndex(position));
> +    updateViewPosition(position + 1);

you could add a comment that +1 is for the list header

@@ +519,5 @@
> +  while (activeElement != null) {
> +    if (activeElement == searchBox) {
> +      searchBoxFocus = true;
> +      break;
> +    } else if (activeElement.id) {

I'd prefer else if on a new line

@@ +557,5 @@
> +    if (aTempFilterList && aTempFilterList[listitemIndex] != i)
> +      continue;
> +
> +    if (listitemCount > listitemIndex) {
> +      // If there is free existing listitems, reuse it.

are .. them

@@ +562,5 @@
> +      // Use .children[] instead of .getItemAtIndex() as it is much faster.
> +      listitem = list.children[listitemIndex + 1];
> +      nameCell = listitem.childNodes[0];
> +      enabledCell = listitem.childNodes[1];
> +    } else {

else on new line

@@ +572,5 @@
> +      listitem.appendChild(nameCell);
> +      listitem.appendChild(enabledCell);
> +      list.appendChild(listitem);
> +      // We have to attach this listener to the listitem, even though we only care
> +      // about clicks on the enabledCell.  However, attaching to that item doesn't

multiple spaces before However

@@ +591,4 @@
>    }
> +  // Remove any superfluos listitems, if the number of filters shrunk.
> +  for (let i = listitemCount - 1; i >= listitemIndex; i--)
> +    list.removeChild(list.lastChild);

i think for clauses should always have braces
Comment 17 :aceman 2012-08-25 07:37:36 PDT
(In reply to Magnus Melin from comment #16)
> @@ +259,5 @@
> >  
> >      // Select the new filter, it is at the position of previous selection.
> >      list.clearSelection();
> > +    list.addItemToSelection(list.getItemAtIndex(position));
> > +    updateViewPosition(position + 1);
> 
> you could add a comment that +1 is for the list header
updateViewPosition should operate on real listitems, that do not contain the headers. So I do not know what the +1 is for (I added that code in the past when I understood this list code a lot less). I just remove that line now as it is not needed (the currently selected line should not change after the new filter is inserted, so no need to update the view.
Comment 18 :aceman 2012-08-25 07:45:06 PDT
Created attachment 655317 [details] [diff] [review]
patch v4

While this is ready for checkin, I'd still like to hear the opinion from RealRaven, as it quite reworks his onFindFilter function he only recently added and completely reworks the way the list is redrawn.

Let's hope he can check it before TB17 is branched (I think Monday 27th)...
Comment 19 Axel Grude [:realRaven] 2012-08-30 14:59:49 PDT
Comment on attachment 655317 [details] [diff] [review]
patch v4

feedback+ from me! Works as expected, nice patch. I only did smoke testing
Comment 20 :aceman 2012-08-30 15:07:45 PDT
Comment on attachment 655317 [details] [diff] [review]
patch v4

Thanks.
Comment 21 Ryan VanderMeulen [:RyanVM] 2012-08-31 03:31:09 PDT
https://hg.mozilla.org/comm-central/rev/83616ca185bb
Comment 22 :aceman 2012-09-10 03:17:35 PDT
Comment on attachment 655317 [details] [diff] [review]
patch v4

This has baked on trunk for 10 days now. I haven't seen any bad reports about it.
Let's try to move it into the same release as bug 450302.

[Approval Request Comment]
Regression caused by (bug #): 450302
User impact if declined: unnecessary performance penalty when using the new features from bug 450302.
Comment 23 Mark Banner (:standard8, limited time in Dec) 2012-10-08 02:14:51 PDT
https://hg.mozilla.org/releases/comm-aurora/rev/526e2bab1310

Note You need to log in before you can comment on or make changes to this bug.