Closed Bug 424808 Opened 16 years ago Closed 13 years ago

addItem in calendar-month-day-box scales badly

Categories

(Calendar :: Calendar Frontend, defect)

defect
Not set
normal

Tracking

(Not tracked)

RESOLVED FIXED

People

(Reporter: mvl, Assigned: Fallen)

Details

(Whiteboard: [not needed beta][no l10n impact])

Attachments

(3 files, 4 obsolete files)

addItem in calendar-month-day-box [1] first compares the hashID of the newly added item to the hashIDs of all existing items (O(N), [1]). Then it goes off to do a linear search for the insertion point (O(N), [2]).
Adding M items into an empty box therefore scales as O(M^2). That's bad.

Measured in time, the worst offender is the second issue, because the comparator function is slowish. A straight-forward solution is to binary-search for the insertion point.
I'm not sure about the solution for the first. Maybe a secondary hash-table with the hashIDs?

[1] http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/calendar/base/content/calendar-month-view.xml#380
[2] http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/calendar/base/content/calendar-month-view.xml#438

(datapoint: adding 100 items to one day takes about a minute on my box. Way too slow)
patch makes adding lots of items much faster: going from (about) 4500msec to 1700msec for 100 items. (artificial testcase)
(Note: adding just a few items won't see a similar speed increase, since a significant part of the time is spend in other places. For example, I don't see any differences with or without the patch for just 5 items)
Assignee: nobody → mvl
Status: NEW → ASSIGNED
Attachment #311434 - Flags: review?
Attachment #311434 - Flags: review? → review?(philipp)
Comment on attachment 311434 [details] [diff] [review]
[checked in] binary search v1

>-          function comptor(a, b) {
>+          function dayboxItemComperator(a, b) {

Please use the correct spelling "dayboxItemComparator" (note the two 'a' in Comparator) here and in other places of your patch.
Comment on attachment 311434 [details] [diff] [review]
[checked in] binary search v1

>       <method name="addItem">
>         <parameter name="aItem"/>
>         <body><![CDATA[
>+          // XXX This scales badly for adding lots of items: O(N^2)
>           for each (ed in this.mItemData) {
>             if (aItem.hashId == ed.item.hashId)
>             {
>               this.deleteItem(aItem);
>               break;
>             }
>           }
> 
I'd probably go with a hash map to get rid of the for each() loop here, but I'm fine with that happening in a different bug.



>+          function binarySearch(array, low, high, newItem, comptor) {
Might there be other places where a binary search is more useful? If so, we might want to make this function part of calUtils or such. Fine for a different bug though.

Also, I'd prefer renaming the "array" argument. Its probably case sensitive, but since "Array" is a reserved identifier, its probably not a good idea to use "array".


>+            if (q > 0)
>+              return binarySearch(array, mid + 1, high, newItem, comptor);
>+            else if (q < 0)
>+              return binarySearch(array, low, mid, newItem, comptor);
Use {}

>+          if (this.mItemData.length == 0)
>+            newIndex = 0;
>+          else
>+            newIndex = binarySearch(this.mItemData, 0, this.mItemData.length - 1, newItem, dayboxItemComperator);
Use {}, also split binarySearch() arguments into multiple lines if you like.


Functionality looks fine to me, comments are only minor.
r=philipp
Attachment #311434 - Flags: review?(philipp) → review+
Comment on attachment 311434 [details] [diff] [review]
[checked in] binary search v1

patch checked in. Leaving open for the other issue (I think it fits perfectly in this bug. no need for a new one)
Attachment #311434 - Attachment description: binary search v1 → [checked in] binary search v1
But i'm not planning to work on it, atm
Assignee: mvl → nobody
Status: ASSIGNED → NEW
Work in progress. I've reduced the propagation time for events in the month view by 15%, but I need to add some code back in, so it might not be that great just yet.
Assignee: nobody → philipp
Status: NEW → ASSIGNED
Attached patch WiP Patch - Part 1 - v1 (obsolete) β€” β€” Splinter Review
Work in Progress, Part 1. First apply bug 424808's patch, then this patch, ...
Attached patch WiP Patch - Part 2 - v1 (obsolete) β€” β€” Splinter Review
... , and then this patch
Flags: blocking-calendar1.0+
Whiteboard: [not needed beta][no l10n impact]
Whiteboard: [not needed beta][no l10n impact] → [needed beta][no l10n impact]
This is too risky for the next beta, lets postpone this one.
Whiteboard: [needed beta][no l10n impact] → [not needed beta][no l10n impact]
Attached patch Fix - v2 (obsolete) β€” β€” Splinter Review
Why so complicated when it can be so easy! Until now we have been using an array that contains an object with { item: <calIItemBase>, box: <DOMNode> } and doing lots of sorting and iterating.

This patch makes use of the fact that a DOM NodeList is already an array and uses a hash map to improve access speed. This patch gave me a speed increase of 20% while drawing month view boxes.
Attachment #434239 - Attachment is obsolete: true
Attachment #434241 - Attachment is obsolete: true
Attachment #548793 - Flags: review?(matthew.mecca)
Whiteboard: [not needed beta][no l10n impact] → [not needed beta][no l10n impact][needs review]
Comment on attachment 548793 [details] [diff] [review]
Fix - v2

Codewise looks good, but this seems to break sorting by start time, r- based on that.
Attachment #548793 - Flags: review?(matthew.mecca) → review-
When dayboxItemComparator is called from binaryInsertNode the node is passed as the second parameter, but it is still expecting the item.
Attached patch Fix - v3 (obsolete) β€” β€” Splinter Review
Good catch, although I should have seen that, pretty obvious. At least it uncovered that the comptor wasn't always comparing the right thing. I've fixed the binaryInsertNode function now, this should do it.
Attachment #548793 - Attachment is obsolete: true
Attachment #549095 - Flags: review?(matthew.mecca)
Attached patch Fix - v4 β€” β€” Splinter Review
Found another issue
Attachment #549095 - Attachment is obsolete: true
Attachment #549107 - Flags: review?(matthew.mecca)
Attachment #549095 - Flags: review?(matthew.mecca)
Comment on attachment 549107 [details] [diff] [review]
Fix - v4

This breaks the sort in the alarm dialog - the widgetAlarmComptor function in calendar-alarm-dialog.js needs to be updated to take the items as parameters.

Otherwise looks good, r=mmecca with above fixed.
Attachment #549107 - Flags: review?(matthew.mecca) → review+
Thanks, seems I missed that! Tested and fixed
Whiteboard: [not needed beta][no l10n impact][needs review] → [not needed beta][no l10n impact]
Pushed to comm-central <http://hg.mozilla.org/comm-central/rev/bdd326df804a>

-> FIXED
Status: ASSIGNED → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
Target Milestone: --- → Trunk
This bug was also pushed to comm-beta and comm-aurora, likely during the last merge.
Target Milestone: Trunk → 1.0b6
You need to log in before you can comment on or make changes to this bug.