Add items to the unifinder list more efficiently
Categories
(Calendar :: Calendar Frontend, enhancement)
Tracking
(Not tracked)
People
(Reporter: darktrojan, Assigned: darktrojan)
References
(Blocks 1 open bug)
Details
(Keywords: perf)
Attachments
(1 file, 1 obsolete file)
|
5.16 KB,
patch
|
darktrojan
:
review+
|
Details | Diff | Splinter Review |
When we add items to the unifinder list (unifinderTreeView.addItems) the whole tree is re-sorted at the end of the operation. If there's many existing items or few new items, this is a big waste of time. With this bug I propose to splice new items into the right point of the existing list where it is advantageous to do so.
|
Assignee | |
Comment 1•6 years ago
|
||
I don't know how much improvement this will make in practice. If there is a good improvement, I'll look into a further optimisation where the new items are sorted before the for-loop begins and looking for the insertion index doesn't begin at 0 for every item.
|
||
Comment 2•6 years ago
|
||
Maybe patches in bug 1502923 could give you some ideas. It was supposed to be big performance win according to reporter but it was backed out for causing regressions.
|
|
Assignee | |
Comment 3•6 years ago
|
||
I'm aware, I reviewed that patch and checked it in. I figure that since I'm taking a new approach I'd start a new bug and avoid the clutter.
|
||
Comment 4•6 years ago
|
||
If this bug is not closed and mark as duplicate of bug 1502923 could it be at least marked as blocking it? This way when this bug is resolved, the other one could be looked at again to check that it sort the performance issue reported. I am very glad to see that someone has come to look into the issue.
|
|
Assignee | |
Updated•6 years ago
|
|
|
||
Comment 5•6 years ago
|
||
Geoff,
First, I would like to thank you for your efforts to look into the issue. It is not an easy one...
Second, as I was looking at your patch (not tested), having worked on bug 1502923 and its patch, I have few feedback/question that I hope you may find of interest...
From my understanding, the introduction of the bulkSort condition would reduce the number of sorting as items are added but it seems your intention persists to sort multiple times the unifinder list of items (that keeps growing) while items are added to the tree. Current bug is that the all list is sorted after each item added, now with your patch you would do it only after a batch of items are added (more items added than number of items in the list), which would improve the situation but not resolve the fact that you sort multiple time while adding items which remain a waist of time/resources used, especially when the calendar is first loaded at startup. Am I right in my understanding? What is the reason for this?
If that is the case, why not add ALL items instead and then sort them ALL only ONCE after the LAST item is added? It would be much more efficient. Equivalent to a click on one of the header column to sort items by end-users, but only after the last items is added.
In the "else" part of code, you seems to calculate the position of the item while adding it to the tree... so your repeat this process for each item added... but isn't already the role of the function "this.calculateIndexMap(true);" which is called later in the code to do so on the overall tree re-indexing at ONCE?
How would your change "saves a lot of function calls and calculation." as you indicate in comment? Can you explain?
About code line 449 "if (bulkSort || !this.selectedColumn) {" why did you added "|| !this.selectedColumn"? What is it for?
This means in case end-user never selected a column to sort unifinder data ever (false is the default value of selectedColumn when setting up Thunderbird new profile), you would end-up sorting all added items after each item is added... which is the current situation that is supposed to be resolved :-)
Hope that help to clarify about your patch proposal...
Regards,
Richard
|
||
Comment 6•6 years ago
|
||
|
|
Assignee | |
Comment 7•6 years ago
|
||
Good catch, fixed.
|
|
Assignee | |
Comment 8•6 years ago
|
||
(In reply to Richard Leger from comment #5)
From my understanding, the introduction of the bulkSort condition would reduce the number of sorting as items are added but it seems your intention persists to sort multiple times the unifinder list of items (that keeps growing) while items are added to the tree. Current bug is that the all list is sorted after each item added, now with your patch you would do it only after a batch of items are added (more items added than number of items in the list), which would improve the situation but not resolve the fact that you sort multiple time while adding items which remain a waist of time/resources used, especially when the calendar is first loaded at startup. Am I right in my understanding? What is the reason for this?
If that is the case, why not add ALL items instead and then sort them ALL only ONCE after the LAST item is added? It would be much more efficient. Equivalent to a click on one of the header column to sort items by end-users, but only after the last items is added.
By far the most common size of aItemArray (for reasons not dealt with here) is 1. It's much, much faster to find the right place in the list and splice it in there, than it is to add it to the end of the list and sort the whole lot again. This holds true up to some size of aItemArray relative to the size of eventArray where it becomes faster to sort afterwards. I'm not actually sure what that point is but I've estimated it's around the point where aItemArray is larger than eventArray.
In at least the case of importing calendar items, addItems is called once for each item (which seems stupid but again, I'm not looking at that here) and doing a full sort each time is very wasteful.
When the calendar is first loaded, setItems is called instead, which sorts once for all items.
In the "else" part of code, you seems to calculate the position of the item while adding it to the tree... so your repeat this process for each item added... but isn't already the role of the function "this.calculateIndexMap(true);" which is called later in the code to do so on the overall tree re-indexing at ONCE?
That's not what calculateIndexMap does. The index map is used to find the position of a given item in the list. In my code we're finding the item (actually just the item's property for the selected column) for a given position in the list.
How would your change "saves a lot of function calls and calculation." as you indicate in comment? Can you explain?
Looking at the sortItems function, you'll see that getItemSortKey is called twice for every comparison needed to sort the list. (The number of comparisons could be as bad as the length of the list squared.) In my code we call getItemSortKey once for every item.
About code line 449 "if (bulkSort || !this.selectedColumn) {" why did you added "|| !this.selectedColumn"? What is it for?
This means in case end-user never selected a column to sort unifinder data ever (false is the default value of selectedColumn when setting up Thunderbird new profile), you would end-up sorting all added items after each item is added... which is the current situation that is supposed to be resolved :-)
If there's no selected column, no sorting happens. Especially now I've fixed the mistake Paul caught.
|
|
Assignee | |
Comment 9•6 years ago
|
||
|
|
Assignee | |
Updated•6 years ago
|
|
||
Updated•6 years ago
|
|
||
Comment 10•6 years ago
|
||
Pushed by mozilla@jorgk.com:
https://hg.mozilla.org/comm-central/rev/3a098643e080
Add items to the unifinder list more efficiently. r=pmorris
|
|
||
Comment 11•6 years ago
|
||
Hi Geoff,
Few more comments/questions...
(In reply to Geoff Lankow (:darktrojan) from comment #8)
(In reply to Richard Leger from comment #5)
From my understanding, the introduction of the bulkSort condition would reduce the number of sorting as items are added but it seems your intention persists to sort multiple times the unifinder list of items (that keeps growing) while items are added to the tree. Current bug is that the all list is sorted after each item added, now with your patch you would do it only after a batch of items are added (more items added than number of items in the list), which would improve the situation but not resolve the fact that you sort multiple time while adding items which remain a waist of time/resources used, especially when the calendar is first loaded at startup. Am I right in my understanding? What is the reason for this?
If that is the case, why not add ALL items instead and then sort them ALL only ONCE after the LAST item is added? It would be much more efficient. Equivalent to a click on one of the header column to sort items by end-users, but only after the last items is added.
By far the most common size of
aItemArray(for reasons not dealt with here) is 1.
Correct because currently by design event items are added one by one to the unifinder tree via the additem function your patch modifies.
So aItemArray contains only one event item.
That also means that if calendar contains 4000 events, the additem function will be called 4000 times (to keep in mind), so it is essential to keep its definition and actions as small as possible from a performance point of view as every actions in that function would be repeated a number of times. It should only be doing one and single thing: add the item to the tree, nothing else... I am not sure this goal is currently achieved within your patch...
Apart from the essential, any others processing such as indexing, sorting, should be done outside this function when all items of the calendar would have been added to the tree otherwise you repeat those action each time one item is added to the unfinder tree which is where you loose all the performance!
That is why when I see you still trying to sort within the additem function or use "for" statement, I can already predict that performance will be lost to some extant as those action may be repeated as much as they are number of items in calendar if All Events are to be viewed... if not for every added item for every batch of them... this may still not be right as it may mean performance would decrease faster as number of items grow...
Have you measure how much performance improvement you patch bring compared to current situation?
How much improvement should we expect?
How does it compare with improvement obtained with patch from Bug 1502923?
It's much, much faster to find the right place in the list and splice it in there, than it is to add it to the end of the list and sort the whole lot again.
Sorry to doubt with this statement because it requires two actions (unless I am mistaking what you mean by "splice it in there"), find the right place (time/resource consuming as many actions required) and add the item to tree, each time an item is added (at each additem call). While adding it at the end of tree would be much faster because this would be the only one action done within additem function.
Again any indexing and sorting shall not happen within the additem function or only once if you can be sure within that function that the added items is the last to be added (which I don't think you can now at the moment). Those shall only be processed ones when the last item would have been added to the tree (load completed). When I say last item I mean last item from the total list of items from the overall lot not just from the batch or bulk items you may be processing from the lot...
This holds true up to some size of
aItemArrayrelative to the size ofeventArraywhere it becomes faster to sort afterwards.
Not sure I agree with this...
I'm not actually sure what that point is but I've estimated it's around the point where
aItemArrayis larger thaneventArray.
This would never happens because aItemArray is always size of one (at the moment)... as you indicated yourself :-)
Also as a separate additional note, sortItems() [via unifinderTreeView.sortItems(); or this.sortItems();] will trigger calculateIndexMap() so if it is run in line via 455 this.sortItems(); why to run it again at line 484 this.calculateIndexMap(true); because that will effectively run twice the same function (but not necessarily with the same param agreed but it that really required?).
I am not sure to understand how often the line 455 will be called but I can already tell that line 484 will be called each time an item is added, which may cause a great loss of performance... if run 4000 times in a calendar with 4000 items... while I believe it could be run only once after all items would have been added to the unifinder tree... just a thought...
Hope that make sense.
Thank you anyway for your patch, looking forwards to check performance results it may bring...
|
|
||
Comment 12•6 years ago
|
||
Just to give a view in term of Lightning network calendar CalDAV performance improvements... via reproducible tests and measurements already available...
As I suspected, TB Nightly 70.0a1 (2019-07-26 08-35-20) which include patch for this bug, provide some improvements (~8m58s) over current TB ESR 60.8.0 (~100mn+) but nothing near the ~68s obtained with TB 66.0b3 patched with patch.v3 issued in Bug 1502923.
Here are more details on tests & results for your information...
Context
- Thunderbird running on Windows 10 Pro 64 bits computer (i7/12GB RAM/SSD drive)
- ADSL connection (~7.77 Mbps Download | 0.66 Mbps Upload | 60ms Ping Time as measured via https://www.broadband.co.uk/broadband-speed-test/)
- No patch applied (vanilla Thunderbird freshly installed) unless stipulated...
Reproducible Test Environment (Setup & Process)
- Install TB version to test
- Open TB
- Create new profile (dedicated to that version)
- No email setup
- Add one CalDAV Calendar(with about ~4000 items)
-- no read-only
-- no reminder
-- no offline support
-- add permanent exception for SSL certificate - Delete Home Calendar (local default calendar)
- Find Event View (unifinder) -> select All Events
- Restart TB
- Cancel all prompts
- Start DevTools (CTRL+SHIFT+I) > Networking
- Start Windows Task Manager > Performance > Wifi
- Go to Calendar Tab
- Enable Calendar
- Enter credentials and start stop watch as soon as pressing OK button to authenticate and start loading of calendar items
Test results
(Tables below may be easier to read online on Bugzilla than via email as data would be formatted into a nice table)
Without sorting - Find Event View (unifinder) -> keep selectedColumn=false (default - no particular sorting)
| # | TB Version | LoadingTime*(Disappearance**) | DevTools > Networking |
|---|---|---|---|
| 01 | 60.8.0 (32-bit) ESR | ~6m23s (50s) | 48 requests - 7.98MB transferred - Finish: 7m65s |
| 05 | 66.0b3 (32-bit) Beta with patch.v3*** | Not available | Not available |
| 02 | 68.0b5 (32-bit) Beta | ~3m34s (14s) | 45 requests - 7.97MB transferred - 3m71s |
| 07 | 70.0a1 (2019-07-26 08-35-20) (32-bit)**** | ~4m59s (15s) | 45 requests - 7.97MB transferred - 4m86s |
With sorting - Find Event View (unifinder) -> keep selectedColumn=true (Title column selected by end-user for sorting)
| # | TB Version | LoadingTime*(Disappearance**) | DevTools > Networking |
|---|---|---|---|
| 03 | 60.8.0 (32-bit) ESR | more than 100m (unknown) | more than 61 requests - more than 12.33MB transferred - Finish more than: 101m76s |
| 06 | 66.0b3 (32-bit) Beta with patch.v3*** | ~68s (unknown) | (unknown) |
| 04 | 68.0b5 (32-bit) Beta | ~47m48s (15s) | 56 requests - 10.33MB transferred - 47m02s |
| 08 | 70.0a1 (2019-07-26 08-35-20) (32-bit)**** | ~8m58s (1m03s) | 45 requests - 7.97MB transferred - 7m79s |
Legend
m=minutes
s=seconds
Footnotes
*: LoadingTime is the time measure from login to Calendar which trigger loading of items, till all items are fully loaded (when that happens items briefly all disappear from the week view, before re-appearing after a while, so till they re-appear)
**: Disappearance is the period of time during which calendar items already loaded disappear temporarily from the week view (upon the end of loading - after last item added to unifinder tree)
***: As per test result observed in Bug 1502923 Comment 49 after patch.v3 applied to TB 66.0b3 but causing regression starting 68.x branch
****: Thunderbird version including patch https://bugzilla.mozilla.org/attachment.cgi?id=9080765&action=diff from this Bug 1567055
|
|
Assignee | |
Comment 13•6 years ago
|
||
Richard, in this bug I'm not interested in solving all the problems with adding items to the unifinder list. Just this particular problem with this particular function, which as you have seen, makes a difference.
|
|
||
Comment 14•6 years ago
|
||
(In reply to Geoff Lankow (:darktrojan) from comment #13)
Richard, in this bug I'm not interested in solving all the problems with adding items to the unifinder list.
It is great to see little progress but shall it be considered as enough?
As you are at it, why not to fix ALL problems related to the additem function?
You clearly have the power and ability to do so... so why not?
When I see all the changes you have done in this function in 70 branch, I am wondering if it would have not been better to take time and resources to fix the performance issue in 68 ESR first, then work on the new approach in 70 branch?
Unless you intend to backport those changes in 68 ESR branch somehow...
Bug 1502923 comment 49 (from 5 months ago) clearly identify some of the root causes of performance issues.
patch.v3 issued and applied to 66 branch showed tremendous results in terms of performance.
Have you taken those findings into account?
Currently it seems we will end-up with a 68 ESR version that still take 47mn to load one calDav calendar (with ~4000 items), this is incomprehensible and still unbearable for end-users especially considering that a solution is at hand...
Can we at least expect to get a 68.1 version that actually fix the performance issue not just a little (~8m58s) but to much more extent (near ~68s or better)?
Yes little progress have been made, but much more progress could have been achieved in the same laps of time, don't you think?
I am still not sure to understand why it has not... what is your plan?
Sorry to insist on this matter but Lightning performance is a critical issue for end-users than need fixing "yesterday"...
Looking forward to further improvements.
|
|
Assignee | |
Comment 15•6 years ago
|
||
I know that you have major performance issues with Lightning. What you don't seem to understand is that as well as Lightning I'm also responsible for copious amounts of other things which also require large amounts of my time. I can only do one thing at once. In this bug, I fix this problem. If there are other problems, and I acknowledge that there are, I will fix them in bugs of their own, as and when I have time available.
|
|
||
Comment 16•6 years ago
|
||
(In reply to Geoff Lankow (:darktrojan) from comment #15)
I know that you have major performance issues with Lightning.
It is not only me, but all your end-users that are encountering the same issues and they are fed-up with it :-)
I am just raising their voice... at least those I know using CalDav calendars and especially those using multiple of them... and in light of the new ESR version coming up...
What you don't seem to understand is that as well as Lightning I'm also responsible for copious amounts of other things which also require large amounts of my time. I can only do one thing at once.
Don't get me wrong, I understand your position but...
- Is it really a matter of time &resources or priority? It is hard to believe that 47mn to load one calendar is not an issue that shall take priority to fix over any other issues within Lightning (apart from Thuderbird crashes :-)) and be considered as critical to fix... also especially considering that you are already working on the additem function here... which is the culprit...
- Are you the only one that can fix this performance issue related to this additem function?
- Can't you get help? If not for the performance issue raised, for other issues so you can use your time and resources to look at perf issues? Most of the work has been done in Bug 1502923 it may just be a matter of fixing the related regression in 68 branch...
- Either by delegating to someone or get more resources (even just temporarily) from the engineer dev team to help fixing the issue?
- Can't you help those like me trying to help fixing the issue? Do you realise the amount of time and energy I am spending (and spent) in trying to analyse and identify the issue in the first place and help fixing it? It is probably nothing compared to what you do, but with my limited knowledge of the code I have managed to reach great results... but I am limited in the power I have over fixing it... I may not be the only one in such situation... with a bit of your help (knowledge of the code, experience, time and resources) it may be fixable quite quickly... that is why I am a bit insistent on the matter... in regards of great benefit it may bring... to all end-users... not just me...
In this bug, I fix this problem. If there are other problems, and I acknowledge that there are, I will fix them in bugs of their own, as and when I have time available.
The performance bug has been on going for YEARS... It is frustrating to see issues will remain in 68 ESR version despite best effort!
A dedicated Bug 1502923 was registered in Oct 2018 (9 months ago, among a long list of other bugs raising same or similar issues), in an attempt to have the performance issue looked at and sorted... so far it has been partially "acknowledge" and partially "sorted" patch.v3 published till regression in 68 branch...
How many more years would we have to wait so time and resources are available before this "fixable" issue is being fixed? I did raise awareness on the tb-planning mailing list as well hoping it may help you get resources you need...
Just a thought.
Maybe I am just trying too hard...
|
|
||
Comment 17•6 years ago
|
||
(In reply to Pulsebot from comment #10)
Pushed by mozilla@jorgk.com:
https://hg.mozilla.org/comm-central/rev/3a098643e080
Add items to the unifinder list more efficiently. r=pmorris
Find attached here https://bugzilla.mozilla.org/attachment.cgi?id=9083573 the TB 70.0a1(2019-07-30) > DevTools > Performance > Call Tree while loading CalDAV calendar with ~4000 items (about 25 network requests through out of 45) following publication of patch from this bug.
This highlight huge performance impact due to unifinder addItems function calls to:
- calculateIndexMap
- findIndex & map (required for splicing)
Also published in Bug 1502923 Comment 94 for the record...
Additional performance tests to evaluate impact of this patch also available in Bug 1502923 Comment 95...
Description
•