1.40 KB, patch
Chris Thomas (CTho) [formerly firstname.lastname@example.org email@example.com]: approval-seamonkey1.1a+
|Details | Diff | Splinter Review|
5.32 KB, image/png
5.02 KB, image/png
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
Created attachment 178371 [details] graph for duration of bookmark operations (import, select, delete)
Created attachment 178373 [details] another graph for duration of bookmark operations (undo delete, paste)
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.
Created attachment 185965 [details] [diff] [review] suppress select events while selecting pasted bookmarks
Created attachment 186816 [details] duration of paste operation with/without patch
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.
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.
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.
(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.
Reassigning as per Bug #32644
Assignee: p_ch → nobody
Could someone with CVS access please submit the patch? Thanks in advance.
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]
(In reply to comment #13) > Checked in attachment 185965 [details] [diff] [review]  on the trunk. Thanks for checkin. > Should this be marked FIXED? No, it's not completely fixed yet.
Attachment #185965 - Flags: approval-seamonkey1.1a? → approval-seamonkey1.1a+
With moving from RDF to Places, is this bug still actual?
Whiteboard: [2012 Fall Equinox]
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.