Closed Bug 734643 Opened 12 years ago Closed 1 year ago

Extremely slow deleting from history (seems some O(n^2) algorithm is there)

Categories

(Firefox :: Bookmarks & History, defect, P3)

Product:
Firefox
Component:
Bookmarks & History
Version:
11 Branch
Type:
defect

Tracking

()

Status:
RESOLVED FIXED
Project Flags:
Performance Impact low

People

(Reporter: tux, Unassigned)

References

(Depends on 1 open bug, Blocks 3 open bugs)

Details

(Keywords: perf, reproducible, Whiteboard: [fxsearch])

Attachments

(1 file, 4 obsolete files)

about:telemetry values
9.45 KB, text/plain
Details 
User Agent: Mozilla/5.0 (X11; Linux i686; rv:2.0) Gecko/20100101 Firefox/4.0
Build ID: 20111220165912

Steps to reproduce:

1. Open your browsing history with approx 5000 entries.
2. Filter them by some string to see about 4000 entries.
3. Select them all and press delete.

(File like this can be used to artificially create large browsing history quite quickly for testing)
<html><script>
setTimeout("window.location='this_file.html?'+Math.random();",20);
</script></html>



Actual results:

After about 10 seconds, I heard some harddrive noise and first 300 entries were removed. After another 10 seconds another burst of harddrive activity and next 300 entries were deleted. The interval between deletion batches approached to zero as number of entries that are to be deleted approached to zero.

This suggests some O(n^2) algorithm is there ....

Deleting about 4000 entries took several minutes. Deleting about 50000 entries (some of my profiles have even more items in history) needs several HOURS.



Expected results:

Deleting from history should be much faster.
Component: Untriaged → Bookmarks & History
QA Contact: untriaged → bookmarks
You are on an outdated versione, improvements made recent versions that would largely help this case.
Status: UNCONFIRMED → RESOLVED
Closed: 12 years ago
Resolution: --- → DUPLICATE
(In reply to Marco Bonardo [:mak] from comment #1)
> You are on an outdated versione, improvements made recent versions that
> would largely help this case.

I am using Firefox 11, as I have specified in the Version field (ok, I should set up User Agent switcher to fake something newer :). I think, Firefox 11 is quite fresh. You should not rely on User Agent string, as the browser used to report the bug may not be the same as browser where the bug occurred.

As that bug was marked fixed about 6 months ago and the Firefox 11 release is not that old, I suspect that it is not fixed, though in the past the slowness was even worse.

Therefore this bug is not duplicate. Firefox 11 is still slow.
Status: RESOLVED → UNCONFIRMED
Resolution: DUPLICATE → ---
ah well, yes, deleting 50 thousands entries may be slow, as you said it's done in batches (300 at a time, but there is no delay between removals), it's not done in one step cause otherwise your UI would be blocked for minutes, that was the original much worse bug.
So the question is, are you complaining the UI is completely unresponsive when deleting, or just that deleting many entries is not instant?
Did you try if disabling all add-ons (safe mode) improves that time?
When you say browsing history, you mean the sidebar or the library?
Actually, both.
The deletion of only one batch is fast (you select 300 items, press Delete and in about 0.5 sec the items are deleted)

But if you select more, then only the last batch needs 0.5 seconds to be deleted. The second to last needs about 1 second, third to last about 1.5 seconds ... and it gets worse.
If you delete 5000 items the delay between deletions is about 10 seconds, for 50000 items it is more than minute (so firefox seems to be stuck) - this is on desktop core i7, so on some netbooks that could be much worse.

 Seems that in every iteration of 300 to delete there is some operation done on entire list that is yet to be deleted, so that is probably why is it so slow. And during that delay the UI is completely unresponsive.

I have not tried to disable the addons, I'll try it, though I don't have many of them (basically just Firebug and Adblock).

Is there some debug tool/profiler known to work well with Firefox so I can measure in which function is the execution stuck?
Attached file about:telemetry values — 
I have just deleted ~13,000 history entries (older than 6 months) and it lasted over 10 minutes. (It is not a slow computer)
Firefox was unresponsive in this time.

Attached you will find my about:telemetry values.
I think this bug should be marked as a Snappy topic.
Thanks

Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/17.0 Firefox/17.0
buildID = 20121119183901
I was using a hotspot with a login page for about 2 years which I had to login again after 10 minutes of inactivity, and had about 15,000 entries for this page including redirections.

I went into history and chose "Forget this site" yesterday and it locked up my Firefox and maxed out my disk drive, but only did this for about a minute or so.

The hard-drive my profile is on is an old and slow 160gb drive so perhaps you are experiencing a different issue? 10 minutes seems a little long.
Status: UNCONFIRMED → NEW
Ever confirmed: true
We must notify for each removal, add-ons may be using these notifications and slow us down quite a bit.
Forget about this site is slightly different story, since it has not just do delete history, but also any other info (cookies, plug-ins info, ...)
I don't delete history as a rule (don't recall last time I did it), so I don't know if this horrible performance is normal.

Tried deleting 600 some entries by doing library, pick history(all) folder on left, filter on 'crash-stats-php', select all, delete key. It kills the CPU and I get unresponsive script**. Can't break out of unresponsive with "stop script" or "continue", while it deletes roughly 20 entries at a time (per updates of History's selection list).

The deletes might be slower than "normal" in my case because many tabs are open and iGC and CC can spike under these conditions - but I'm not currently seeing a spike.

my places.sqlite is 14.5MB.

** unresponsive script on treeView.js, tree.xml,
Severity: normal → major
Keywords: perf, reproducible
(In reply to Wayne Mery (:wsmwk) from comment #10)
> ** unresponsive script on treeView.js, tree.xml,

controller.js, etc.  not surprisingly the file can be random.

> deletes roughly 20 entries at a time 
this varied. perhaps deleting more entries at a time as the number of selections got lower. In the final response of unresponsive script I as at 120 selected, clicked in the dialog, and pretty quickly the library display refreshed with no selections, i.e. 120 deletions happened within a second or two.
I tried to delete some very old history, but Firefox hanged. Selecting "stop script" in the slow script dialog didn't solve the problem, nor stopped trying to delete the history I think. As said by Wayne, sometimes it was treeviews.js, sometimes it was controller.js... and so I decided to kill the process. Then when I opened Firefox again, it was a new window, without my app tabs.
I can confirm that.
Firefox 24, started the browser in safe mode and wanted to delete 10,000 entries from a database with approx 170,000 entries. This took more than 25 minutes and completely locked up the browser as a whole.

This is a pic of the performance graph during the deletion: http://i.imgur.com/yA1KR3H.png

Each blue block lasted for about 40 seconds and stands for only 300 deleted entries. The intervals between the blocks became shorter the more entries have been deleted up to that point. And I/O went up to over 1.4GB.
Still present in Firefox 28: deleting some 21,000 history entries took 40 minutes, with the browser almost completely unresponsive during this time. Script alerts about chrome://browser/content/places/tree.xml:317 became less frequent after the first 15 minutes or so (at which time I closed the History window), but he browser was still unusable until the deletion was complete.
new info
the same bug on last FF version. I noticed it for ~1 year (each time was latest version).
it's not just slow, but browser really hangs when deleting thousands of items from history!!

also set flag to cross-platform. For me is Windows 7 x86, not Linux as is specified in header.


A similar thing o noticed to in download manager - then deleting more than 60 items it is slow and also appear small hangs.
For the time being there is a workaround.  One can download SQLite3 and then (after exiting Firefox such that the history file is no longer locked) opening a command prompt in one's profile directory and executing a command like 

    path/to/sqlite3 places.sqlite "delete from moz_places where url like '%SEARCH_TERM%';"

It is of course recommended that one carefully checks that the search term won't include things that one doesn't want deleted and taking a backup of places.sqlite is obviously a good idea as well. 

Many thanks to http://kb.mozillazine.org/Places.sqlite for the relevant documentation.
(In reply to Kasper Henriksen from comment #17)
> For the time being there is a workaround.  One can download SQLite3 and then
> (after exiting Firefox such that the history file is no longer locked)
> opening a command prompt in one's profile directory and executing a command
> like

don't do this for any reason, you are breaking your database coherency, and will surely have issues.
i have same problem

when i want delete ~ 13000 entries (or more), i can go to sleep 1hour -_-
So yeah, Windows 7,8,8.1, 10.... open Firefox 39.0 (or any Firefox for at least few years back):

- open history window (ctrl+shift+h)
- search something that will have lot of hits ("google" for instance - in my case 5800+hits)
- press ctrl+a to select all and firefox starts having performance issues (only for selecting it)
- press delete and go for lunch, as it will delete 300 records per instance and deleting is extremely slow (but gets faster with each deletion).

What is the issue from coder standpoint? Most likely, you don't take list of selected ids and do something like "DELETE FROM history WHERE id IN(1,2,13,43,123,...)". Instead it feels like you are doing something like "DELETE FROM history WHERE id=1; DELETE FROM history WHERE id=2;" and most likely, you don't even disable indexing before that operation and re-enable it afterwards (as it gets faster and faster with less and less records).

I need my history, I use it heavily, but I don't like to have everything in it... which makes me endure this pretty often.

Yet I've seen this bug multiple times throughout the history and it is still alive and kicking. Please, please pretty please, fix it already.
Mac user here, also confirming this bug in Firefox 40. In 2015 this kind of database performance is just incredibly embarrassing. The search box can search the entire database in under 1 second, finding 1000s of matches, yet deleting the results of that search can take several minutes! There is a "Forget about this site" entry in the context menu, so obviously batch-deletion was envisioned as a use-case. I refuse to believe this can't be drastically improved!
Same here Ian,
  I am on Windows with FF40.0.3 and I have 97,000 or so entries for a one single website I would like to delete. Forget this site crashes Firefox , deleting 4000 selected entries takes about a minute per 300! That's about 5 and a half hours for the entire site. I would expect a minute or two to do this at the max.
Follow up details from Windows FF40.0.3 ...
Attempt to delete 50,000 selected entries for the one site ... crashed
Attempt to delete 40,000 selected entries for the one site ... crashed
Attempt to delete 35,000 selected entries for the one site ... Possible hung with the first 600 appearing to have been deleted
Attempt to delete 25,000 selected entries for the one site ... Success after an hour or so
(I've not checked the code)
From the comments it looks like, that sqlite is used as backend.
It could be related with the:
https://www.sqlite.org/lang_transaction.html
Transactions probably should be added: 
BEGIN TRANSACTION; 
delete something
COMMIT;

(https://www.sqlite.org/faq.html:
Transaction speed is limited by the rotational speed of your disk drive. 
A transaction normally requires two complete rotations of the disk platter, which on a 7200RPM disk drive limits you to about 60 transactions per second. )
85.000 entries i want delete, boom crash... :-(

Please Mozilla, fix it or rewrite it :(
Priority: -- → P2
Attached file wip (obsolete) — 
The callback when start/finish one removePages chunk takes a lot of time, which can be avoided. With this WIP, removing 4000 histories takes <10s on my PC.

A busy indicator will make it even better.
Attachment #8665896 - Flags: feedback?(mak77)
there is a better way to notify Begin/End, through the .getObservers() API. But this way the UI is completely unusable until the whole removal is done, that is why currently it's removePages doing the batching.
The other problem is that these APIs are about to be deprecated, and then any fix here may be elided by the new APIs.
I'm not saying the current situation is fine, it is horrible, but putting some workarounds here and there won't make a future proof fix.

We also need to check what makes the end callback so slow. from the profile it looks like it's invalidateContainer trying to restore selection (particularly getNewRowForRemovedNode), and then the select event fires and causes oncommandupdate, that updates the commands on the selection. It's likely we can act at these points to largely improve the situation.

Fwiw, if you want to try the begin/endBatch way properly (using getObservers) then I may evaluate it as a temporary improvement while we consider all the architectural problems. If you want to investigate what I said above to figure which parts of the selection code are slow, feel free to.

In addition to this, there is also an IO problem due to bug 871908, that should also be fixed apart. As you can see the problem is due to a bunch of different causes summing up.
Attachment #8665896 - Flags: feedback?(mak77)
(In reply to Marco Bonardo [::mak] from comment #28)
> We also need to check what makes the end callback so slow. from the profile
> it looks like it's invalidateContainer trying to restore selection
> (particularly getNewRowForRemovedNode), and then the select event fires and
> causes oncommandupdate, that updates the commands on the selection. It's
> likely we can act at these points to largely improve the situation.

Are these all necessary? For instance, restoring selection searches for equivalent node which is just removed, but it doesn't seem needed when remove histories.
Flags: needinfo?(mak77)
(In reply to Ting-Yu Chou [:ting] from comment #30)
> Are these all necessary? For instance, restoring selection searches for
> equivalent node which is just removed, but it doesn't seem needed when
> remove histories.

What we want for history is just to select the next entry (like you remove entries 5 and 6, we should select 7, if it exists). So it's likely there are shortcuts to avoid invoking getNewRowForRemovedNode. I'm not sure if this invalidation happens before or after we set a new selection, but it's likely it would be useful if the view could tell the treeview to skip restoring or give hints to restrict searching the node to a subset of the tree, this should be feasible. The current solution is a catch-all that in some cases is a perf hit with low (or nonexistent) benefit. Yes, there is space for improvement here.
Flags: needinfo?(mak77)
so there are various things we can do here:
1. preparatory work: bug 1107364 (move findNodeByDetails to js)
2. modify findNodeByDetails to use a Map (or a WeakMap). We can build a Map when we build the tree, and use it to find nodes. We could build a custom hash out of url+time+itemId.
3. figure a way to short circuit _getNewRowForRemovedNode when we know the node has gone
Depends on: 1107364
(In reply to Marco Bonardo [::mak] from comment #28)
> there is a better way to notify Begin/End, through the .getObservers() API.

I'm not sure how does this work. The wip is trying to avoid the callbacks in nsNavHistory::BeginUpdateBatch() and nsNavHistory::EndUpdateBatch() from each removePages() invocation. How could getObservers() help here?
instead of exposing begin/end in the idl, you would getObservers and then directly invoke onBeginUpdateBatch/onEndUpdateBatch on each observer.

Btw, the suggested solution in command 32 is still the best path forward, we should clearly be using an hash to find stuff in large lists.
(In reply to Marco Bonardo [::mak] from comment #34)
> instead of exposing begin/end in the idl, you would getObservers and then
> directly invoke onBeginUpdateBatch/onEndUpdateBatch on each observer.

No, it's not about how to invoke onBeginUpdateBatch/onEndUpdateBatch.

I exposed begin/end in the idl so I can call it to increase |mBatchLevel| in nsNavHistory::BeginUpdateBatch() before removing any histories, which later calling nsNavHistory::RemovePages() for a chunk will *not* trigger onBeginUpdateBatch/onEndUpdateBatch for any observers.

The sequence now is:

  _removeRowsFromHistory()
  nsNavHistory::RemovePages()
  observers.onBeginUpdateBatch()
  remove a chunk of histories
  observers.onEndUpdateBatch()
  nsNavHistory::RemovePages()
  observers.onBeginUpdateBatch()
  remove a chunk of histories
  observers.onEndUpdateBatch()
  nsNavHistory::RemovePages()
  observers.onBeginUpdateBatch()
  remove a chunk of histories
  observers.onEndUpdateBatch()
  ...
  ...

And the WIP will make it:

  _removeRowsFromHistory()
  observers.onBeginUpdateBatch()
  nsNavHistory::RemovePages()
  remove a chunk of histories
  nsNavHistory::RemovePages()
  remove a chunk of histories
  nsNavHistory::RemovePages()
  remove a chunk of histories
  ...
  ...
  observers.onEndUpdateBatch()
Yes, the problem is removePages is issuing a batch, but the new History.remove API won't, then we can manually notify batches.
The problem is this code uses old APIs and the batch APIs are likely to disappear as well, so relying on them is not a future proof change.
There's a lot to do here...
Depends on: 871908
Blocks: 1206393
Whiteboard: [fxsearch]
Priority: P2 → P3
Copying comment 1 from #1247943, since nobody here did a benchmark and it demonstrates the nonlinearity:
"
Tested with Firefox 45 b5 x64

history items - time to delete
1000  - 56 sec
3000  - 2:40 min
9900  - 22:40 min
10000 - 27 min
19800 - 61min
"
No longer blocks: 1206393
For future searchers, I also found that deleting a large amount of history resulted in extremely high memory use.  Here is the oom killer doing its work after swapping 16 GB:

kernel: [4324826.849850] Out of memory: Kill process 25567 (firefox) score 945 or sacrifice child
kernel: [4324826.849854] Killed process 25567 (firefox) total-vm:57294148kB, anon-rss:31445172kB, file-rss:0kB

I deleted all history older than 6 months.  Probably a few years' worth.
I still having problems. 
It's impossible to delete because I need delete on all my devices already synced.

I have more than 40.000 bookmarks :-(

Problems: (Time to delete is infinity)
Script: chrome://browser/content/browser-places.js:1883
Script: chrome://browser/content/places/treeView.js:669
Script: chrome://browser/content/places/treeView.js:850
Script: chrome://browser/content/places/treeView.js:1123
Script: chrome://browser/content/places/editBookmarkOverlay.js:1128
Script: chrome://browser/content/browser-places.js:1864

The problem is: where is located the bookmarks database?
I need delete and sync to server to delete synced from mozilla servers.

Ideas?

Thanks...
Flags: needinfo?(twm)
Flags: needinfo?(mak77)
Flags: needinfo?(janus926)
I guess this question is for :mak as he mentioned the new History API in comment 36, which I know nothing about.
Flags: needinfo?(janus926)
Hello, I'm sorry you are having this problem, unfortunately at this time we don't have resources to spend on history views performance. The primary bug to fix here is bug 1107364, but it's not trivial and not very handy for newcomers.
So far I can only suggest to manually do the operations in chunks, like 1000 at a time.
I'd also suggest to keep bookmarks into separate folders, and not all of them in the same container. Long term this should help.

I know it's not a great answer. We're definitely aware of the issue.
Flags: needinfo?(mak77)
(In reply to Marco Bonardo [::mak] from comment #44)
> Hello, I'm sorry you are having this problem, unfortunately at this time we
> don't have resources to spend on history views performance. The primary bug
> to fix here is bug 1107364, but it's not trivial and not very handy for
> newcomers.
> So far I can only suggest to manually do the operations in chunks, like 1000
> at a time.
> I'd also suggest to keep bookmarks into separate folders, and not all of
> them in the same container. Long term this should help.
> 
> I know it's not a great answer. We're definitely aware of the issue.

OK. Thanks anyway.
(In reply to Marco Bonardo [::mak] from comment #44)
> Hello, I'm sorry you are having this problem, unfortunately at this time we
> don't have resources to spend on history views performance. The primary bug
> to fix here is bug 1107364, but it's not trivial and not very handy for
> newcomers.

If so, why don't we take attachment 8665896 [details]? Maybe it's not perfect, but at least it will make deletion doable.
Flags: needinfo?(mak77)
(In reply to Ting-Yu Chou [:ting] from comment #46)
> If so, why don't we take attachment 8665896 [details]? Maybe it's not
> perfect, but at least it will make deletion doable.

the problem in comment 42 is about bookmarks, that is not going to help. And I think I already commented about that patch, it's not an acceptable solution, technically.
Flags: needinfo?(mak77)
Whiteboard: [fxsearch] → [fxsearch][qf]
Whiteboard: [fxsearch][qf] → [fxsearch][qf:p3]
Depends on: 933374
Depends on: 843357
Who else has noticed that deletion is even slower recently (Firefox 55.0.2 on Linux)? More linear, but not in a good way: even a single block of 300 takes 44 seconds, i.e. it's as if a significant per-entry time has been added. This is not a slow computer, either. Previously I was deleting in batches of 3000, now that's unbearable. Here are some timings:

entries | seconds
--------+--------
     75 |      10
    150 |      21
    300 |      44
    600 |      94
   1200 |     219
   2400 |     572
(In reply to Paul from comment #48)
> Who else has noticed that deletion is even slower recently (Firefox 55.0.2
> on Linux)? More linear, but not in a good way: even a single block of 300
> takes 44 seconds, i.e. it's as if a significant per-entry time has been
> added. This is not a slow computer, either. Previously I was deleting in
> batches of 3000, now that's unbearable. Here are some timings:

This is likely bug 1376149 which we're hoping to address soon.
Flags: needinfo?(twm)
we should also reintroduce result batching notifications on history removals.
An addition:

Playing around with the history I recognized tha the favicon is displayed on each line. This has to be looked up if it isn't in Cache.

If the server does not exist any more (#1442365), the favicon lookup times out. And it seems to lookup every line, since a none existing favicon is looked up for every line?

Deleting of Items where the favicons are resolvable goes much faster...

Ervin
I can reproduce this on Windows 10 with Firefox 60 beta. 
Select thousands of History entries from the Library window and delete them. The Library window freezes. After each 100 deleted items, this message about Unresponsive Script comes up https://i.imgur.com/wWpTgfX.png (repeats after each 100-200 deleted items)

Closing the Library window seems to make the wiping process much faster.
I just ran into this issue - I tried to remove all "google.com" entries (which were lots of) and Fx basically froze, and after a while it showed notification that the script execution was slow and taking a lot of time and I was presented with option to continue/stop.

This is quite annoying that I can't remove history for particular website. I know that it's doable from "Information view", but this also removes cookies *AND* it removes cookies from containers (but this is somewhat separate issue).

Any pointers where to start looking to optimise it?
I discovered followed:

When i select a large amount of history entries and press delete, firefox hangs for a while, but when i select the same amount of history entries and press delete and directly deselect by select only one history entries, deleting is extreme fast.

Test case 1:
selected 6000 history entries and pressed delete, it took 22 min to delete them and Firefox was frozen in that time.

Test case 2:
selected 6000 history entries pressed delete and deselected by select only one history entries, it took only 1 min to delete.
yes, restoring selection is one of the expensive operations we do that can be largely improved, what you noticed is likely related to that.
Blocks: 1511852

The 'Forget this site' functionality still demonstrates the problems described above on the 66.0a1 (which is why I filed the duplicated mentioned above).

Depends on: 1523743

The deletion of the history older than 6 months happens rapidly itself.

But after that Firefox eats 11Gb RAM and 200%CPU for several hours.

It's possible to use firefox during cleanup process. (But it become very slowly.) It's event possible to close it. But the last time it crashed during close. I've send crash report.

For about 2 weeks now firefox nightly has had this problem. Any modification to the bookmarks is painfully slow. about:support doesn't count the number of bookmarks, so I don't know how many I have but 6 months ago it was 5k, I think.

Adding a bookmark takes ages and then the window does popup, it's empty for a while. I could record a video if requested, but there'd be nothing special to see. Should you require more information, I'd be happy to provide it

(In reply to Librem Grief from comment #74)

For about 2 weeks now firefox nightly has had this problem. Any modification to the bookmarks is painfully slow. about:support doesn't count the number of bookmarks, so I don't know how many I have but 6 months ago it was 5k, I think.

Hi, this is unlikely to be related directly to this bug. Please can you file a new bug and attach the about:support output from the places verification.

I knew about this bug (or just inefficiency) for a long time and today i found a workaround how to not sit with frozen browser for huge amount of time.

I was deleting 3.5k items.

As usual, everything froze and after some time the usual popup came on - Abort, continue, debug script.
I clicked debug and as it turns out, items were deleted from the list.

It looks like its not deleting taking time, but something else. Maybe some callbacks that should have been delegated from main thread to background jobs to not block the whole browser.

I must say this is one of those things that stops people from switching over, because this should not be the case. Especially not in 2019 after 8 years from the original bug report.

(In reply to pavelloz from comment #78)

It looks like [it’s] not deleting taking time, but something else. Maybe some callbacks that should have been delegated from main thread to background jobs to not block the whole browser.

See comment 28:

We also need to check what makes the end callback so slow. from the profile it looks like it's invalidateContainer trying to restore selection (particularly getNewRowForRemovedNode), and then the select event fires and causes oncommandupdate, that updates the commands on the selection. It's likely we can act at these points to largely improve the situation.

And see comments 64, 65.

When I select a large amount of history entries and press delete, Firefox hangs for a while, but when I select the same amount of history entries and press delete and directly deselect by selecting only one history entry, deleting is extremely fast.

(Emphasis and grammar edits mine.)

It’s restoring selection that seems to be slow.

Given the hint above, I have found that if after selecting all, hit delete, then esc a couple of times (which means that the highlighted list is apparently cleared, I can use the browser more or less normally (perhaps just a little slower) while the history continues to be deleted in batches - as I am typing this, in fact. What that means above the coding I cannot begin guess, but it is certainly not a locked browser now. The task was to delete some 36,000 entries - it has been going for about 9 minutes already.

Does that help?

= sorry, "about the coding"

At the moment we don't have the resources to spend on the investigation side.
I agree that one of the improvements involves the restoreSelection code path: https://searchfox.org/mozilla-central/search?q=restoreSelection&path=places
But is invalidateContainer being invoked too often, or is restoreSelection just slow? And if it's the former, what's the invalidateContainer stack, if it's an operation that is not expected to restore selection, can we temporarily disable that around that specific operation? and so on...
The code is mostly javascript, if you are proficient with that, it should be possible to follow the code and find improvements. The huge costs here are into verifying that those improvements don't cause unexpected bugs in other operations.

Is history being rewritten?

I think this is one of the oldest parts (if not the oldest) in Fx. I remember the same UI on version 3 or 4, which looks like its been forgotten, but its still an important feature to a lot of people.

Im asking, because i dont know if i should invest time to learn how to profile/mock data in Firefox to fix it, as im fairly proficient in javascript and i care about performance a lot.

Also, maybe thats a stupid question, but, which selection exactly it is restoring?

Simple scenario:

  1. User selects 10 rows to delete.
  2. User clicks delete

The end.

What restore selection is exactly trying to reselect if everything that user had selected, wanted to just delete and it shouldnt exist after the operation?

(In reply to pavelloz from comment #83)

Is history being rewritten?

We'd like to, finding resources is a problem, but there's the will. The question is "when", and likely it's still months far away.

(In reply to pavelloz from comment #84)

What restore selection is exactly trying to reselect if everything that user had selected, wanted to just delete and it shouldnt exist after the operation?

It depends, for example if the removal happens node by node, and we're not skipping reselection, after each removal the tree gets rebuilt and selection restored on the other items that have not been removed yet (and I suspect that's what happens). And at the end, we're likely to select something (probably the entry before the ones that were selected) but that's a single thing so it should be cheap. The bug is there, so explaining what happens is probably as expensive as fixing the bug.

Interesting way to trigger this bug: upgraded ubuntu from 19.04 to 19.10 (ff 72.0.1) with some few thousand entries in history.

After the first boot on 19.10, open firefox, open history. It will ask if you want to delete all history entries. No matter what you select, the Unresponsive Script popup (treeview.js:198 in this case) will show up and not response to anything (can barely move the mouse, no attempt to press spacebar/enter on the popup worked). I had to wait 17min just for the machine (core i3) to be able to switch to another physical TTY and i could not ever get a password prompt before the login attempt timedout. Eventually I got a OOM event that killed firefox for me.

I was very close to just unplug the computer during all this.

I will probably not be impacted by this bug anytime soon and it will slip my mind soon as I do not have much time for open source as I used to... But if someone can point me to the general direction of where the problem is I can spend some time to suggest a patch in the next week.

Although I cannot tell why it seems O(n^2), I have a workaround, maybe a potential fix.

When I open the history in the "Library", search for a domain, press "Ctrl+A" to select all, then press "delete" to delete the records.
It takes very long time as people mentioned above. Slow for 4000 items, and seems endless for 14000 items.

Then I open ~/.mozilla/firefox/xxx.default-xxx/places.sqlite, execute below sql statements. It finished the deletion in less than 1 second.

delete from moz_places where url like "http://example.net/%";
delete from moz_historyvisits where moz_historyvisits.place_id not in (
  SELECT id from moz_places
);

It seems the deletion doesn't cascade to other tables with foreign key reference so I'm not sure if I have missed some tables.

I guess the Firefox delete large among of history items very slowly is because it has to delete the items one by one (using statement like where id=?) because the user may not be selecting all matched result.
How about add a specific button "Delete all matched items" so this trick can be applied from the Firefox GUI?

(In reply to aabbcc1241 from comment #90)

How about add a specific button "Delete all matched items" so this trick can be applied from the Firefox GUI?

That would not be suitable as it doesn't address the UI side. The issue here, as has already been discussed, is getting the UI updated. As Marco has said in comment 82 and comment 85, the UI parts are the bits that really need the investigation here. My suspicion is that to fix this, we might also need to migrate our remove observers over to a new observer system so that we can batch notifications, but that's only a suspicion at this stage.

We should just throw away the history view and make a new one that is both useful to the users (the current one is not) AND fast.

I agree the suggest by Macro. As least for me, I don't care if the view is not updated in the middle of deletion.
Say it is deleting 1000 items, I won't mind if the UI display as if the 1000 items are still there until all of them are deleted.

8 years obnoxious bug
Why is it so hard to deal with this? (I haven't dared to look the code)

Why not just add another option do the UI: "Remove history older than:" and call directly the corresponding sqlite command without updating any UI componente.

Some discussion of this problem and bug on Hacker News:

https://news.ycombinator.com/item?id=24061787

(In reply to timbugzilla from comment #95)

Some discussion of this problem and bug on Hacker News:

https://news.ycombinator.com/item?id=24061787

This link shows a discussion about privacy and deleting cookies. It an entirely different subject.

The current issue is about slow updating the history database and UI component.

(In reply to sparcbr from comment #96)

This link shows a discussion about privacy and deleting cookies. It an entirely different subject.

They also discuss slow deleting from history and even link this bug.
https://news.ycombinator.com/item?id=24062006

A few quick checks: deleting from 50 (in 50s) to 300, it takes about 2 .5 s / 50 (in this machine) for the list to be shown as losing those items. But, immediately after that deletion the main FF process takes most of the cycles of one core for about 10 s / 50 (there is some but not a lot of disk activity). During this time switching tabs takes at least 1 s, maybe slower on occasions. From about 350 deletions, the second phase - busy main process - starts before the deletion from the list is shown. It would thus appear that even though the deletions have formally been completed, FF will become sluggish. Deleting a 1000 items it takes about 2 minutes for the history to lose those items (progressively) - that is longer than would have been expected, the main process CPU usage gets ragged in the overlap - mutual interference, competition? - and the switching delay increases to ~2 s. (This effect is certainly there at 500.) Repeated deletes of 50, for which you have to wait for the highlighted list to disappear, get slower and slower as the main process is involved.

Does this suggest anything? The question is what process occurs after the (apparent) deletion - sorting? Whatever that is, it appears not to be the actual deletion, but that thread competes with the deletion itself after a certain size. It seems to form a queue, and just goes on and on with (large enough) deletions occurring closely enough.

Initial list was about 13,000, still problematic by the time I reached 7,500 - these are nol really very big data sets. But, there is extra use of RAM during the second phase: 500 deletions required up to 2.3 GB more - that is 4.6 MB per item!, in at least 4 stages, with gradual recovery.

Blocks: 1663262

BTW: why are (101) and (102) tagged 'advocacy'?

They are all comments which are essentially "metoo" or comments designed to make us fix it sooner (e.g. "It is incredible that this problem still exists"). These types of comment are not helpful (as they spam everyone on the bug) and are against the etiquette: https://bugzilla.mozilla.org/page.cgi?id=etiquette.html. If they keep on happening, then we will likely mark this bug as restricted commenting.

We understand this is still an issue, and we recognise that it is a pain point for people who do hit it. However, it likely involves a significant amount of non-trivial work to fix. At the moment our focus is on improving other areas of Firefox, and we don't have the time available to dedicate to this.

Apologies. I had checked etiquette beforehand and could find no indication of what the obscure tag meant - it seems like the wrong word is being used (clarify that page with your elaboration?). Point taken, though, although I would have thought data such as (102) would be helpful, where only the last line seems offensive under the rules. Work-load and priorities understood; I assume then that no activity does not mean ignored or forgotten.
Thanks for the explanation. (Ironically, this reply is also technically empty ... )

Blocks: 1675998
Blocks: 1685140
No longer blocks: 1685140
See Also: → 1685140
See Also: → 1695129
OS: Linux → All
Hardware: x86 → All

In version 88 history deletes very fast. 288 rows deletes in 2-3 sec. Thanks.
In previous versions it could take time over 20 sec.

(In reply to kolio from comment #115)

In version 88 history deletes very fast. 288 rows deletes in 2-3 sec. Thanks.
In previous versions it could take time over 20 sec.

That's probably the effect of Daisuke's work with new history notifications, and in particular bug 1694818. That is part of the architecture work necessary to fix this, but it's just the beginning of the work.

500 in 20 s, 1000 in 65 s, 2000 in 3 min 25s, but no apparent extra RAM use or core saturation, and switching now OK (except window refresh in FF). Seems to be an improvement, indeed. Very glad to see work being done on this.

I found a work-around, and pin-pointed what causes the hanging.

If you have all the history entries highlighted during the deletion, then for example 3000 entries:

Delete will take this long for the first 300 and every after...
300 -> 15 seconds
300 -> 10 seconds
300 -> 5 seconds

There is this kind of pattern.

Work-around:

Click anywhere in the list of items to de-select all right after starting the delete request.

What happens: Firefox doesn't hang and starts deleting entries immediately.

Image explanation with work around steps:

https://i.imgur.com/nBafaYB.png

Note: I scrolled up a bit and saw another user has provided the same work-around 3 years ago: https://bugzilla.mozilla.org/show_bug.cgi?id=734643#c64

Coding Quick Fix?

- Add a "deselect all history items" UI command when deletion has begun

That does indeed appear to work - 1000 items in 15 s here, against 50 s with the highlight on.
Thank you.

Just tried with ww.google.com, 6078 entries. Highlighted all, clicked delete and then immediately clicked a couple times on the list. The screen initially was frozen for nearly a minute but then came back to life and went very quickly. Total time was about 85 seconds. Good work around until a builtin fix. Thanks

(In reply to bugbasher from comment #120)

I found a work-around, and pin-pointed what causes the hanging.

Smart, we are aware that the issue is due to re-selecting entries in the very long list, so this makes total sense, because you clear the selection there's nothing to re-select.

Why can't you just deselect the to-be-deleted entries automatically? Seems like that would be a very easy way to make this issue go away. They aren't going to exist after deletion anyway, so there is no reason to keep them selected.

Yes, it's possible that pre-calculating the final node to be selected before the removal starts, accumulating the removals in memory, and changing the selection before proceeding with removals, would improve things. It should be measured. If anyone is willing to modify the code and check the effect of that, you're welcome to. The code is more or less around this area https://searchfox.org/mozilla-central/source/browser/components/places/content/controller.js#930-947,990-1004

I've run up against this issue, found this thread, and wanted to point out that deletion can still take a long time even with the deselect workaround mentioned above (thanks for that by the way, it helps immensely). It took a few dozen seconds on my machine (macbook + firefox 91.0) to delete about 8000 items that were not selected, as opposed to a few dozen minutes for a similar number of selected items. Dozens of seconds is a lot better than dozens of minutes, especially when it means firefox is relatively more responsive in the meantime, but it's still much slower than it should be.

See Also: → 1656521
Performance Impact: --- → P3
Whiteboard: [fxsearch][qf:p3] → [fxsearch]

The biggest hang (the one users are circumventing by deselecting the nodes) seems to be caused by the eventListener at line 25 of browser/components/places/content/places-tree.js. In my case, this "while (true) {...}" hangs the entire browser. Problem is, I have no idea why this code exists in the first place and it's probably there for a reason.

But even without it, the functions PTV_nodeRemoved (this one is especially important) and PTV_invalidateContainer in browser/components/places/content/treeView.js probably also run for every single node that has been deleted. They're responsible for visually removing a node, rebuilding the view, selecting the next node, that kind of thing.

If these where called only at the end of the deletion, I think deleting a thousand entries could take mere milliseconds. The request is actually blazing fast, but these few eventListeners responsible for the visual side wake up hundreds of times for nothing.

Now I don't want to get your hopes high, I'm just reporting what I found, I'm not a FF dev and I don't know this code, but maybe I'll keep poking at it and see what I can find.

I got a 20k history row places.sqlite, and when I try to delete some history, the search is fast, but the delete operation speed is intolerably slow. Firefox hangs and every 3 minute delete 300. I terminate Firefox after 15minute delete only 900 rows, and there are 18000+ to delete.

By contrast, if I do the same operation by a tool name DB Browser for SQLite (open source on Github), it took a second for searching and deleting, then about another second to commit the change to the actual file.

I think either firefox commit to the sqlite after every row delete, or keep updating the "history window" by a query the database block the commit(so we can see the results drop 300 for a moment), or worst, it does both.

Why my comment140 mark as advocacy?
I post a comparison between Firefox and another SQLite software to Firefox places.sqlite by a real-world operation. it is more than a hours VS a few seconds.(Firefox is VERY slow and apperantly improvable)
I make conjectures of Why the speed is so slow.
I didn't push anyone to fix it soon, just don't understand the standard.

In the process of migrating remaining bugs to the new severity system, the severity for this bug cannot be automatically determined. Please retriage this bug using the new severity system.

Severity: major → --

Currently, deleting 2,000 history items causes 2,000 PlacesVisitRemoved events
to be fired. Each such event results in a call to invalidateContainer() in
treeView.js. This is an expensive function.

On a Macbook Pro 2015, it took 73 seconds to delete 2,000 history items.

This patch introduces a new event: PlacesBatching. A PlacesBatching(true) event
is fired before the PlacesVisitRemoved events, and then a PlacesBatching(false)
event is fired afterwards. treeView.js receives these batching
notifications and defers the call to invalidateContainer() until all
PlacesVisitRemoved events have finished. The end result is that
invalidateContainer() is executed only once instead of 2,000 times.

On a Macbook Pro 2015, thanks to this patch it took < 1 second to delete
2,000 history items, representing a performance increase of over 7,000%.

Assignee: nobody → 3ecdbelo
Status: NEW → ASSIGNED

Depends on D158932

The following patch is waiting for review from a reviewer who resigned from the review:

ID Title Author Reviewer Status
D158939 Bug 734643 - Fix clang-format warning. r=mak 3ecdbelo mak: Resigned from review

:3ecdbelo, could you please find another reviewer?

For more information, please visit auto_nag documentation.

Flags: needinfo?(3ecdbelo)

Changes to the patches are required, not a new reviewer.

Flags: needinfo?(3ecdbelo)

Resigning in Phabricator means something like "I'm not able to review this patch (because it's out of my area of expertise or because I don't have time)", that's why the bot suggested finding a new reviewer.

Attachment #9297790 - Attachment is obsolete: true
Attachment #9297800 - Attachment is obsolete: true

Further investigation has revealed that repeatedly invoking
treeView.js invalidateContainer() is not the primary cause of the
poor performance when a user deletes a large number of
items from a history query.

Yes, one of the nsNavHistoryQueryResultNode observers is being
refreshed for every Page_removed event, resulting in
repeated calls to treeView.js invalidateContainer(). This
definitely has a performance impact.

However, even worse is that another of the nsNavHistoryQueryResultNode
observers is being incrementally updated for every Page_removed
event. This is causing the majority of the slowdown.

This patch provides a simple solution: when handling a PlacesEvent
containing 50 or more Page_removed events and no other events,
just refresh all the history observers once and return.

With this change, we are able to achieve the 7,000% speedup
when a user deletes 2,000 items from a history query.

Attachment #9298420 - Attachment is obsolete: true

Please file a bug blocking this one, and post the patch there, as I suggested.

Depends on: 1795070

Resetting assignee, since Francis worked on bug 1795070 that should have helped quite a bit with this issue, thank you a lot.
For now we'll keep this open to keep collecting feedback.

Assignee: 3ecdbelo → nobody
Status: ASSIGNED → NEW
Attachment #8665896 - Attachment is obsolete: true

At present, deleting 2000 (without esc) took 30 s / 300 (when there was a list refresh) for the first 900, then accelerated a little; total 2.5 min. FF locked in the meantime still.
There has been a lot of discussion of event calls etc, but no mention of the oddly large memory usage. Is that not a factor?

Tried a few seconds ago on a not-so-recent mac book pro. Deleting ~2600 history entries took around 2 seconds. Pretty good :)

Please note the fix for bug 1795070 won't be released until around 13th December in Firefox 108. Please make sure you have that version before testing again/commenting.

108.0a1 (2022-11-10)/macOS 12.6.1 - deleted ~1000 records in ~3 seconds. TY Francis.

Marco, based on recent discussion, can this item be marked as closed?

Flags: needinfo?(mak)

I have just tested (109.0, 32-b, laptop) and 1000 went in about 2 s, and 2000 more in about 5 s, then 3 s - very hard to time!
109.0, 64-b (PC) took 30 s, 25 s and 25 s for 2000. Both Win 7 Pro, much improved for sure.
The problem is indeed substantially fixed, but the difference is a bit odd.

(In reply to Dr B W Darvell from comment #159)

I have just tested (109.0, 32-b, laptop) and 1000 went in about 2 s, and 2000 more in about 5 s, then 3 s - very hard to time!

This is likely the effect of a cache, it's normal.

(In reply to Daniel Nguyen from comment #158)

Marco, based on recent discussion, can this item be marked as closed?

Yes, bringing this on forever is not useful, it's better to move to new bugs in case someone wants to report specific cases.
Let's call this fixed by bug 1795070.

I'm happy that the situation improved a lot, when we started working on the new notifications system in Places, years ago, we knew it could be used to improve performance, this was a nice confirmation the direction was correct, Francis patch could leverage the system advantages.
There's a lot that can be done yet.

Status: NEW → RESOLVED
Closed: 12 years ago → 1 year ago
Flags: needinfo?(mak)
Resolution: --- → FIXED
Duplicate of this bug: 933374
Duplicate of this bug: 1427607
Duplicate of this bug: 1397267
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: