"paste" in Bookmark Manager is very slow (O(n^2))

RESOLVED WONTFIX

Status

SeaMonkey
Bookmarks & History
RESOLVED WONTFIX
13 years ago
5 years ago

People

(Reporter: Jan Darmochwal, Assigned: Jan Darmochwal)

Tracking

({fixed-seamonkey1.1a, perf})

Trunk
fixed-seamonkey1.1a, perf

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [2012 Fall Equinox])

Attachments

(3 attachments, 3 obsolete attachments)

(Assignee)

Description

13 years ago
User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8b) Gecko/20050217
Build Identifier: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8b) Gecko/20050217

I've timed some bookmark operations (import, select, delete, undo delete and
paste) and found out that "undo delete" and "paste" are O(n^2) (see attached
images).
The problem seems to be with selecting the bookmarks *after* the actual
operation has been performed. The function "onSelectionChanged" in
xpfe/components/bookmarks/resources/bookmarksTree.xml is called n times (when
pasting n bookmarks). The bookmarks seem to be selected one-by-one. This is very
slow as the time to select one additional bookmark is about proportional to the
total number of bookmarks selected. 


Reproducible: Always

Steps to Reproduce:
1. select a large number of bookmarks
2. copy the bookmarks
3. paste the bookmarks
Actual Results:  
pasting the bookmarks takes very long (almost 2 hours for 2000 bookmarks on my
machine)

Expected Results:  
pasting bookmarks should be much faster
(Assignee)

Comment 1

13 years ago
Created attachment 178371 [details]
graph for duration of bookmark operations (import, select, delete)
(Assignee)

Comment 2

13 years ago
Created attachment 178372 [details]
graph for duration of bookmark operations (undo delete, paste)
(Assignee)

Comment 3

13 years ago
Created attachment 178373 [details]
another graph for duration of bookmark operations (undo delete, paste)

Updated

13 years ago
Keywords: perf
Version: unspecified → Trunk
(Assignee)

Comment 4

13 years ago
Sorry, I've messed some things up with the number of bookmarks. It's 4000
instead of 2000 and 5000 instead of 2500. This also explains the "jumps" in the
graph between 1500 and 2000 bookmarks. 

BTW, this is a seamonkey-only bug, works ok with Firefox.
(Assignee)

Comment 5

13 years ago
Created attachment 185965 [details] [diff] [review]
suppress select events while selecting pasted bookmarks
Attachment #185965 - Flags: review?(neil.parkwaycc.co.uk)
(Assignee)

Updated

13 years ago
Status: UNCONFIRMED → NEW
Ever confirmed: true
(Assignee)

Comment 6

13 years ago
Created attachment 186816 [details]
duration of paste operation with/without patch
Attachment #178371 - Attachment is obsolete: true
Attachment #178372 - Attachment is obsolete: true
Attachment #178373 - Attachment is obsolete: true
(Assignee)

Comment 7

13 years ago
Created attachment 186819 [details]
paste is still O(n^2) with patch

In attachment 185965 [details] [diff] [review] you can see that paste is much faster after applying the
patch (~15x as fast for 100 bookmarks, ~30x as fast for 500 bookmarks). But as
you can see in this attachment, it's still slow and it's still in O(n^2).
Pasting 5000 bookmarks now takes "only" ~4 minutes instead of over 2 hours
without the patch.

Another thing that becomes visible with the patch applied is that pasting
becomes slower with the undo history growing. I measured all the times by
cutting and pasting the bookmarks with an empty undo history.
(Assignee)

Updated

13 years ago
OS: Linux → All
Hardware: PC → All

Updated

13 years ago
Attachment #185965 - Flags: superreview+
Attachment #185965 - Flags: review?(neil.parkwaycc.co.uk)
Attachment #185965 - Flags: review+
(Assignee)

Comment 8

13 years ago
Much of the time required for pasting bookmarks is spent in
RDFContainerImpl::Renumber() in rdf/base/src/nsRDFContainer.cpp. Renumber()
makes space for new bookmarks to be inserted. It gets called for every single
bookmark. Things could be significantly sped up, if we could create the space
for all the new bookmarks before inserting them. Would be nice if

a) there was an InsertElementsAt() method that allowed to insert multiple
   bookmarks at once
b) Renumber() could be called from bookmarks.js
 or
c) there was no need to renumber the items in the RDF container

Calling Renumber() in BookmarkInsertTransaction::doTransaction() in bookmarks.js
before inserting the bookmarks would save quite some time:

time required for pasting 1000 bookmarks
renumber while inserting (current): 9.8s
renumber before inserting: 1.5s (1.05s of which are spent selecting the
   bookmarks after they have been inserted)

Firefox could probably profit even more from such a patch as it does not select
bookmarks after pasting them.

Comment 9

13 years ago
This problem is known in the RDF code, and it will depend on more than one bug.

Please discuss changes to RDF code in RDF bugs, and make this one depend on it.
I haven't found a precise bug on this so far.
(Assignee)

Updated

13 years ago
Depends on: 298613
(Assignee)

Comment 10

13 years ago
(In reply to comment #9)
> This problem is known in the RDF code, and it will depend on more than one bug.
> 
> Please discuss changes to RDF code in RDF bugs, and make this one depend on it.
> I haven't found a precise bug on this so far.

I have looked at all the RDF bugs and I haven't found a bug on this. I have
created bug 298613 for it.

Comment 11

12 years ago
Reassigning as per Bug #32644
Assignee: p_ch → nobody
(Assignee)

Comment 12

12 years ago
Could someone with CVS access please submit the patch? Thanks in advance.
Whiteboard: [checkin needed]
Assignee: nobody → jdarmochwal
Checked in attachment 185965 [details] [diff] [review] on the trunk.
mozilla/xpfe/components/bookmarks/resources/bookmarksTree.xml 	1.21

Should this be marked FIXED?
Whiteboard: [checkin needed]
(Assignee)

Comment 14

12 years ago
(In reply to comment #13)
> Checked in attachment 185965 [details] [diff] [review] [edit] on the trunk.

Thanks for checkin.

> Should this be marked FIXED?

No, it's not completely fixed yet.

Updated

12 years ago
Attachment #185965 - Flags: approval-seamonkey1.1a?
Attachment #185965 - Flags: approval-seamonkey1.1a? → approval-seamonkey1.1a+

Updated

12 years ago
Keywords: fixed-seamonkey1.1a

Comment 15

5 years ago
With moving from RDF to Places, is this bug still actual?
Whiteboard: [2012 Fall Equinox]

Comment 16

5 years ago
Carrying Wontfix from Bug 298613 and close this one too
Status: NEW → RESOLVED
Last Resolved: 5 years ago
Resolution: --- → WONTFIX
You need to log in before you can comment on or make changes to this bug.