Closed
Bug 424808
Opened 17 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)
|
(deleted),
patch
|
Fallen
:
review+
|
Details | Diff | Splinter Review |
|
(deleted),
image/png
|
Details | |
|
(deleted),
patch
|
mmecca
:
review+
|
Details | Diff | Splinter Review |
Screenshot of problem with sorting
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•17 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•17 years ago
|
Attachment #311434 -
Flags: review? → review?(philipp)
|
||
Comment 2•17 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•17 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•17 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•17 years ago
|
||
But i'm not planning to work on it, atm
Assignee: mvl → nobody
Status: ASSIGNED → NEW
|
|
Assignee | |
Comment 6•15 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•15 years ago
|
||
Work in Progress, Part 1. First apply bug 424808's patch, then this patch, ...
|
|
Assignee | |
Comment 8•15 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•14 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
•