Closed
Bug 424808
Opened 16 years ago
Closed 13 years ago
addItem in calendar-month-day-box scales badly
Categories
(Calendar :: Calendar Frontend, defect)
Calendar
Calendar Frontend
Tracking
(Not tracked)
RESOLVED
FIXED
1.0b7
People
(Reporter: mvl, Assigned: Fallen)
Details
(Whiteboard: [not needed beta][no l10n impact])
Attachments
(3 files, 4 obsolete files)
5.03 KB,
patch
|
Fallen
:
review+
|
Details | Diff | Splinter Review |
16.02 KB,
image/png
|
Details | |
12.63 KB,
patch
|
mmecca
:
review+
|
Details | Diff | Splinter Review |
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)
Reporter | ||
Comment 1•16 years ago
|
||
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)
Reporter | ||
Updated•16 years ago
|
Attachment #311434 -
Flags: review? → review?(philipp)
Comment 2•16 years ago
|
||
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.
Assignee | ||
Comment 3•16 years ago
|
||
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+
Reporter | ||
Comment 4•16 years ago
|
||
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
Reporter | ||
Comment 5•16 years ago
|
||
But i'm not planning to work on it, atm
Assignee: mvl → nobody
Status: ASSIGNED → NEW
Assignee | ||
Comment 6•14 years ago
|
||
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
Assignee | ||
Comment 7•14 years ago
|
||
Work in Progress, Part 1. First apply bug 424808's patch, then this patch, ...
Assignee | ||
Comment 8•14 years ago
|
||
... , and then this patch
Assignee | ||
Updated•14 years ago
|
Flags: blocking-calendar1.0+
Whiteboard: [not needed beta][no l10n impact]
Assignee | ||
Updated•14 years ago
|
Whiteboard: [not needed beta][no l10n impact] → [needed beta][no l10n impact]
Assignee | ||
Comment 9•13 years ago
|
||
This is too risky for the next beta, lets postpone this one.
Whiteboard: [needed beta][no l10n impact] → [not needed beta][no l10n impact]
Assignee | ||
Comment 10•13 years ago
|
||
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)
Assignee | ||
Updated•13 years ago
|
Whiteboard: [not needed beta][no l10n impact] → [not needed beta][no l10n impact][needs review]
Comment 11•13 years ago
|
||
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-
Comment 12•13 years ago
|
||
Comment 13•13 years ago
|
||
When dayboxItemComparator is called from binaryInsertNode the node is passed as the second parameter, but it is still expecting the item.
Assignee | ||
Comment 14•13 years ago
|
||
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)
Assignee | ||
Comment 15•13 years ago
|
||
Found another issue
Attachment #549095 -
Attachment is obsolete: true
Attachment #549107 -
Flags: review?(matthew.mecca)
Attachment #549095 -
Flags: review?(matthew.mecca)
Comment 16•13 years ago
|
||
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+
Assignee | ||
Comment 17•13 years ago
|
||
Thanks, seems I missed that! Tested and fixed
Whiteboard: [not needed beta][no l10n impact][needs review] → [not needed beta][no l10n impact]
Assignee | ||
Comment 18•13 years ago
|
||
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
Assignee | ||
Comment 19•13 years ago
|
||
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.
Description
•