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

NEW
Unassigned

Status

()

defect
P3
major
7 years ago
2 months ago

People

(Reporter: tux, Unassigned)

Tracking

(Depends on 2 bugs, Blocks 1 bug, {perf, reproducible})

11 Branch
x86
Linux
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [fxsearch][qf:p3])

Attachments

(2 attachments)

Reporter

Description

7 years ago
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: 7 years ago
Resolution: --- → DUPLICATE
Duplicate of bug: 681420
Reporter

Comment 3

7 years ago
(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?
Reporter

Comment 5

7 years ago
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?

Comment 6

7 years ago
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

Comment 7

7 years ago
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.

Updated

7 years ago
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.

Comment 12

6 years ago
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.

Comment 13

6 years ago
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.

Comment 14

5 years ago
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.

Updated

5 years ago
Duplicate of this bug: 975864

Comment 16

5 years ago
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.

Comment 17

5 years ago
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.

Comment 19

5 years ago
i have same problem

when i want delete ~ 13000 entries (or more), i can go to sleep 1hour -_-

Comment 20

4 years ago
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.

Comment 21

4 years ago
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!

Comment 22

4 years ago
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.

Comment 23

4 years ago
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

Comment 24

4 years ago
(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. )

Comment 25

4 years ago
85.000 entries i want delete, boom crash... :-(

Please Mozilla, fix it or rewrite it :(
Priority: -- → P2
Posted file wip
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)
Duplicate of this bug: 1194471
(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

Updated

4 years ago
Duplicate of this bug: 1117546

Updated

4 years ago
Blocks: 1206393
Whiteboard: [fxsearch]
Priority: P2 → P3

Updated

3 years ago
Duplicate of this bug: 1247943

Comment 39

3 years ago
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

Updated

3 years ago
Duplicate of this bug: 1282311

Comment 41

3 years ago
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

Comment 48

2 years ago
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.

Updated

2 years ago
Duplicate of this bug: 1402919
Duplicate of this bug: 1149935
Duplicate of this bug: 871908

Updated

2 years ago
Duplicate of this bug: 1418992
Duplicate of this bug: 1427437
Duplicate of this bug: 1431392

Updated

Last year
Duplicate of this bug: 1442365

Comment 58

Last year
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.
Comment hidden (metoo)
Comment hidden (metoo)
Comment hidden (advocacy, metoo)

Comment 63

9 months ago
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?

Comment 64

8 months ago
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
Comment hidden (metoo)
Duplicate of this bug: 1521588

Comment 68

5 months ago

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

Comment hidden (metoo)
Depends on: 1523743

Updated

4 months ago
Duplicate of this bug: 1524800

Comment 71

4 months ago

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.

Updated

4 months ago
Duplicate of this bug: 1530697

Updated

3 months ago
Duplicate of this bug: 1534096

Comment 74

2 months ago

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.

You need to log in before you can comment on or make changes to this bug.