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

Status: RESOLVED WONTFIX

(SeaMonkey :: Bookmarks & History, defect)

Description

[Jan Darmochwal]

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

Comment 1

[Jan Darmochwal]

Attachment: graph for duration of bookmark operations (import, select, delete)

Comment 2

[Jan Darmochwal]

Attachment: graph for duration of bookmark operations (undo delete, paste)

Comment 3

[Jan Darmochwal]

Attachment: another graph for duration of bookmark operations (undo delete, paste)

Comment 4

[Jan Darmochwal]

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.

Comment 5

[Jan Darmochwal]

Attachment: suppress select events while selecting pasted bookmarks

Comment 6

[Jan Darmochwal]

Attachment: duration of paste operation with/without patch

Comment 7

[Jan Darmochwal]

Attachment: 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.

Comment 8

[Jan Darmochwal]

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

[Axel Hecht]

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.

Comment 10

[Jan Darmochwal]

(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

[Ray Booysen]

Reassigning as per Bug #32644

Comment 12

[Jan Darmochwal]

Could someone with CVS access please submit the patch? Thanks in advance.

Comment 13

[:Gavin Sharp [email: [e-mail]]]

Checked in attachment 185965 [details] [diff] [review] on the trunk.
mozilla/xpfe/components/bookmarks/resources/bookmarksTree.xml 	1.21

Should this be marked FIXED?

Comment 14

[Jan Darmochwal]

(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.

Comment 15

[Phoenix]

With moving from RDF to Places, is this bug still actual?

Comment 16

[Phoenix]

Carrying Wontfix from Bug 298613 and close this one too