Closed Bug 577950 Opened 10 years ago Closed 10 years ago

nsPrefBranch::RemoveObserver is inefficient

Categories

(Core :: Preferences: Backend, defect)

defect
Not set

Tracking

()

RESOLVED FIXED

People

(Reporter: sayrer, Assigned: justin.lebar+bug)

Details

(Keywords: perf)

Attachments

(5 files, 12 obsolete files)

95.23 KB, image/png
Details
7.21 KB, text/plain
Details
111 bytes, text/plain
Details
24.37 KB, patch
Details | Diff | Splinter Review
2.44 KB, patch
bzbarsky
: review+
Details | Diff | Splinter Review
nsPrefBranch::RemoveObserver calls strcmp in a loop over every entry each time an observer is removed. I've been browsing for about 10 minutes, and I have about 15 tabs in total open. This makes for about 1200 entries to iterate over.
Snow Leopard's spin control is much nicer. From browsing around for a while with it on, I can see that the cycle collector is really huffing and puffing here. At the time I took these samples, I couldn't tell how many observers were around, but there were probably quite a few. 

I filed bug 577953 on the fact that the number of observers seems to continually rise. However, since we create pref observers with reckless abandon, we should find a more efficient way to find them for removal. Maybe a hashtable instead of an array.
boy howdy, we sure are iterating over that array as we close windows
Comment on attachment 456770 [details]
sample of what happens during a cycle collection

there's also an entry in there where the observer count is 1. that looks like a bug to me, probably someone creating a new preference service rather than calling getService.
We will need to fix this data structure and keep the per-window preference observer calls we have now. That's a pretty dumb way to do things, but we probably can't change it compatibly for Firefox 4.

A sensibly multi-process browser would have the pref service in the supervisor process, and delete all registrations by client process ID once a window is closed.
> We will need to fix this data structure and keep the per-window preference
> observer calls we have now.

Actually, we have a patch for the latter too.  See bug 561076.  Worth applying the not-finalized patch there and remeasuring?
Assignee: nobody → justin.lebar+bug
I can remeasure with the patch from bug 561076.  Sayre, how exactly did you generate the output in comment 3?
(In reply to comment #6)
> I can remeasure with the patch from bug 561076.  Sayre, how exactly did you
> generate the output in comment 3?

Just stuck a printf in nsPrefBranch::RemoveObserver
Status: NEW → ASSIGNED
I didn't rigorously profile, but it looks like this function is still hot even with the patch from bug 561076.
OS: Mac OS X → All
Hardware: x86 → All
Version: unspecified → Trunk
looks like nsObserverService more or less does the right thing.
> looks like this function is still hot even with the patch from bug 561076.

Sure.  We should fix this anyway.  I'm just interested in what the numbers look like with that patch...
So as far as fixing this bug, I see at least the following options:

1)  Separate per-prefname lists (with a hashtable mapping prefnames to lists)?
2)  A single PRCList, with a hashtable mapping observer+prefname to the right
    entry in the list for fast removal.

Other ideas?
(In reply to comment #10)
> Sure.  We should fix this anyway.  I'm just interested in what the numbers look
> like with that patch...

I can run them if you're really curious.  Do you have a particular workload in mind?

(In reply to comment #11)
> So as far as fixing this bug, I see at least the following options:
> 
> 1)  Separate per-prefname lists (with a hashtable mapping prefnames to lists)?
> 2)  A single PRCList, with a hashtable mapping observer+prefname to the right
>     entry in the list for fast removal.
> 
> Other ideas?

I was doing #2 but without the PRCList.  Why is that necessary?
(In reply to comment #11)
> So as far as fixing this bug, I see at least the following options:
> 
> 1)  Separate per-prefname lists (with a hashtable mapping prefnames to lists)?
> 2)  A single PRCList, with a hashtable mapping observer+prefname to the right
>     entry in the list for fast removal.

I think other inefficiencies will dwarf what we see in nsPrefBranch with either of those choices. nsObserverService is pretty much #1, and I've not seen it in a profile.
What do you imagine the extra overhead from #2 as compared #1 would be?
(In reply to comment #14)
> What do you imagine the extra overhead from #2 as compared #1 would be?

Tough to say without doing both and measuring. #2 is probably slower to add items, which does happen in Txul, but #1 will do a linear search comparing pointers that scales with roughly the number of tabs open.

What we have now was doing strcmp() on a workload that approximated thousands of tabs with design #1, and then we get a pause.
iow, I don't think the choice matters.
> Do you have a particular workload in mind?

Whatever was used in comment 1 through comment 3?

> I was doing #2 but without the PRCList.  Why is that necessary?

It might not be if we don't need to enumerate all observers in some sort of defined order or anything like that.
Attached patch Patch v1 (obsolete) — Splinter Review
Patch for review.

I'm playing with a bit of fire (where exactly is commented in the patch) to deal with the fact that RemoveObserver is reentrant (i.e. RemoveObserver triggers calls to RemoveObserver).  I think it's right, and memcheck doesn't complain, but a careful review is probably in order.

I'll try and get some timing numbers now.
Attachment #457380 - Flags: review?(bzbarsky)
Hm.  This is segfaulting when I open lots and lots of tabs.  I guess something is broken.  :)
Attachment #457380 - Flags: review?(bzbarsky)
Attached patch Patch v2 (obsolete) — Splinter Review
Less crashy now.
Attachment #457380 - Attachment is obsolete: true
Attachment #457416 - Flags: review?(bzbarsky)
Attachment #457416 - Attachment is patch: true
Attachment #457416 - Attachment mime type: application/octet-stream → text/plain
Benchmark methodology:

* Make a release build
* Set dom.popup_maximum to 200
* $ perf record -ig dist/bin/firefox
* Visit attached file, which opens 200 popups.
* Once all the popups have loaded, close the browser.
* $ perf report -g graph

No patches
  5.39% - strcmp_sse42
  0.28% - nsContentUtils::UnregisterPrefCallback()
  0.54% - nsPrefBranch::RemoveObserver()

Patch from bug 561076 (attachment 447074 [details] [diff] [review]) only
  0.26% - strcmp_sse42
  0.00% - nsContentUtils::UnregisterPrefCallback()
  0.06% - nsPrefBranch::RemoveObserver()

Patch from this bug (attachment 457416 [details] [diff] [review]) only
  5.02% - strcmp_sse42
  0.51% - nsContentUtils::UnregisterPrefCallback()
  0.02% - nsPrefBranch::RemoveObserver()

Both patches
  0.27% - strcmp_sse42
  0.00% - nsContentUtils::UnregisterPrefCallback()
  0.01% - nsPrefBranch::RemoveObserver()

So it looks like bug 561076's patch gives us a large speedup (from avoiding
strcmps) and this patch gives us a small speedup.

(That said, I'm new to using perf, so I might be misinterpreting this.  In
particular, it looks like the strcmp cost wasn't attached to
UnregisterPrefCallback in the profile, so perhaps changing how we do
RemoveObserver improved something else which I'm not listing here.)
Attached file Benchmark file
Warning: This tries to open 200 popups!
Comment on attachment 457416 [details] [diff] [review]
Patch v2

The method pointer thing doesn't seem necessary.  Just make FreeObserverFunc a friend of the class?

For the XPCOM change, make the function return nsAutoPtr<T> so you can't leak?  And have bsmedberg review that?
Attachment #457416 - Flags: review?(bzbarsky)
Attachment #457416 - Flags: review?(benjamin)
Attachment #457416 - Flags: review+
(In reply to comment #21)
> 
> No patches
>   5.39% - strcmp_sse42
>   0.28% - nsContentUtils::UnregisterPrefCallback()
>   0.54% - nsPrefBranch::RemoveObserver()

Judging by the function name, I'm guessing your strcmp implementation is pretty damn fast. Users with a more traditional one will get bitten worse.
Attached patch Patch v3 (obsolete) — Splinter Review
Addressing bz's review comments.  (Man, I feel silly about that method pointer.)
Attachment #457416 - Attachment is obsolete: true
Attachment #457970 - Flags: review?(benjamin)
Attachment #457416 - Flags: review?(benjamin)
Oh, one more thing.  In KeyEquals, you want to be returning PR_FALSE.
Attached patch Patch v4 (obsolete) — Splinter Review
Fixed previous patch's bustage on mac, and updated around changes from bug 578392.  mrbkap, could you check that I'm not messing what you fixed?
Attachment #457970 - Attachment is obsolete: true
Attachment #458441 - Flags: review?(benjamin)
Attachment #457970 - Flags: review?(benjamin)
Attachment #458441 - Flags: review?(mrbkap)
Attachment #458441 - Flags: review?(benjamin) → review+
I'm reworking this patch due to mrbkap's changes in bug 578392.  bsmedberg's r+ should carry over (I shouldn't have to change nsClassHashtable again), but I'll probably need another review from bz.
Attached patch Patch v5 (obsolete) — Splinter Review
This version avoids relying on the uniqueness of a stale pointer.  Blake, does it look like it also avoids the problem you fixed in bug 577950?
Attachment #458441 - Attachment is obsolete: true
Attachment #459600 - Flags: review?(mrbkap)
blocking2.0: --- → ?
I can trigger

WARNING: Failed attempt to remove a pref observer, probably leaking: 'alreadyRemoved', file ../../../../src/modules/libpref/src/nsPrefBranch.cpp, line 918

by opening and closing lots of tabs (without this patch applied).  I think we want to take this for FF 4 because it doesn't rely on the uniqueness of stale pointers like the code from bug 578392 does, so hopefully it's less likely to leak.
bz, blake says he's happy just to have you look at this patch, since you looked at the original patch and would have to look at this one after him anyway.
Attachment #459600 - Flags: review?(mrbkap) → review?(bzbarsky)
Is there any sane way to create an interdiff from what I already reviewed?  Or is it all different all over again?  :(
Blake's patch kind of nuked the last one.  I'll try to interdiff, but I'm not hopeful.

Looking over the patch text, it looks like I somehow managed to upload an old version of the patch.  I'll re-upload in the morning.
Attached patch Patch v6 (obsolete) — Splinter Review
Correct version of the previous patch.

I'll try and get an interdiff or somesuch.  Stay tuned...
Attachment #459600 - Attachment is obsolete: true
Attachment #462800 - Flags: review?(bzbarsky)
Attachment #459600 - Flags: review?(bzbarsky)
Sorry, bz; I can't get a useful interdiff.  Basically all the context and code changed between the patch you reviewed and the patch I just uploaded.

AFAICT the only code which didn't change is in nsClassHashtable.h.
Diffing patches (plain old diff) and grepping out context changes:

diff old new | grep '^[<>] [-+]'

can be helpful when interdiff fails.

/be
Comment on attachment 462800 [details] [diff] [review]
Patch v6

OK.  So general comments:

>+    NS_WARNING("Trying to add an observer that already exists?");

Looks wrong to me.  In fact, such an attempt will just silently leak; it wouldn't return false from put.  Add tests?

You're right that we should probably detect this situation, though, and at least not leak...

Can we make NotifyObserver just a class static instead of creating a new global symbol?

Why do you need an nsresult in RemoveExpiredCallback?

The weak ref constructor gets |canonical| from the wrong object.  Shouldn't that be a do_QueryReferent?  Again, test?

KeyEquals is wrong.  In particular, a given object might have multiple nsISupportsWeakReference tearoffs, no?   So the weakref compare testing false doesn't mean it's not the same observer...

On the other hand, you only need this to support the remove from NotifyObserver, right?  Would just testing |this == aKey| do the right thing, given your GetKey()?

You don't need the explicit .get() calls in GetObserver().

Document that precisely one of mWeakRef and mStrongRef is non-null?
Attachment #462800 - Flags: review?(bzbarsky) → review-
How would you suggest testing this?
Well, for the leak you could add the same observer to the same branch twice, right?  And perhaps add ctor/dtor logging to your key/data class?  And then as long as tests fail on leak, we would fail.

For the wrong canonical thing, I'm not sure.  I'm not sure there's a good way to implement an nsISupportsWeakReference that does that interface via tearoffs in JS....  Probably ok to skip testing that.
(In reply to comment #37)
> The weak ref constructor gets |canonical| from the wrong object.  Shouldn't
> that be a do_QueryReferent?

If it were

  canonical = do_QueryReferent(mWeakRef)

I'd agree that it's wrong.  But what's wrong with

  canonical = do_QueryReferent(aObserver)

?  aObserver comes from QI'ing an nsIObserver to nsISupportsWeakReference.

I'm probably misunderstanding something...
erm, do_QueryReferent should be do_QueryInterface in both cases above.
Oh, aObserver is the nsISupportsWeakReference, not the nsIWeakReference.  I got confused about that.  Ok, that works.
> Looks wrong to me.  In fact, such an attempt will just silently leak; it
> wouldn't return false from put.

Actually, I don't think it will leak the PrefCallback object.  The Put() call causes the PrefCallback that was in the hashtable to be destructed.

That said, we'd still end up calling PREF_RegisterCallback twice and PREF_UnregisterCallback only once in this case, causing us to leak a CallbackNode (created in PREF_RegisterCallback).

It's easy enough to check for this case.  But I'm not sure we can easily test for it without changing code in prefapi.cpp, since the things being leaked are malloc'ed.
Attached patch Patch v7 (obsolete) — Splinter Review
Attachment #462800 - Attachment is obsolete: true
Attachment #463612 - Flags: review?(bzbarsky)
Attached file Interdiff v6 -> v7 (obsolete) —
Attachment #463613 - Attachment mime type: application/octet-stream → text/plain
Comment on attachment 463612 [details] [diff] [review]
Patch v7

r=me.  Thanks for doing this, and especially for the interdiff!
Attachment #463612 - Flags: review?(bzbarsky) → review+
And thanks for the review at 3am the morning of your vacation!
Attachment #463612 - Flags: approval2.0?
Attachment #463612 - Flags: approval2.0? → approval2.0+
blocking2.0: ? → ---
This patch was causing the code in bug 533290 to crash with a use-after-free.

This can be fixed by giving PrefCallback either a strong reference or a proper WeakRef back to the prefbranch.

Any ideas as to whether a strong or a weak reference is preferable here?
I think the prefbranch itself should be an ephemeral object. We should hold a strong reference to the observer, and the branch name it was registered under "root.foo.bar.". If that branch is gone, we should create a new one.
Keywords: perf
Attached patch Patch v8 (obsolete) — Splinter Review
Aha.  There was a bug in FreeObserverFunc.  One-character change is all that's necessary to fix the use-after-free, AFAICT.
Attachment #463612 - Attachment is obsolete: true
Attachment #463613 - Attachment is obsolete: true
http://hg.mozilla.org/mozilla-central/rev/63bb61d1416e
Status: ASSIGNED → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
FWIW, I think this crash is triggered by the failure of an intermittently-failing test, so perhaps that's why I didn't see this on try.
Attached patch Patch v9 (obsolete) — Splinter Review
This appears to fix the crash we saw when I pushed yesterday.  I talked to Jonas about it, and it makes sense.
Attachment #466425 - Attachment is obsolete: true
I should say: The bug was a crappy implementation of PrefCallback::GetObserver().
Attached patch Interdiff v8 -> v9 (obsolete) — Splinter Review
Jonas, can you check this interdiff before I check in again?
Attachment #467454 - Flags: review?(jonas)
Comment on attachment 467454 [details] [diff] [review]
Interdiff v8 -> v9

Hells bells, I can't believe we did that!
Attachment #467454 - Flags: review?(jonas) → review+
Comment on attachment 467454 [details] [diff] [review]
Interdiff v8 -> v9

>   if (pCallback->IsExpired())
>   {
>     // Remove the expired weak reference from the pref branch's observers list.
>     pCallback->GetPrefBranch()->RemoveExpiredCallback(pCallback);
>     return NS_OK;
>   }
> 
>-  nsCOMPtr<nsIObserver> observer(pCallback->GetObserver());
>+  nsCOMPtr<nsIObserver> observer;
>+  pCallback->GetObserver(getter_AddRefs(observer));
>+  NS_ENSURE_TRUE(observer, NS_ERROR_FAILURE);

Do I need to worry about the following race condition:

 * IsExpired() returns false, then
 * the weakly-referenced object is freed, then
 * we call GetObserver(), which returns false,

or am I guaranteed that weakly-referenced objects won't disappear out from under me?
Is there a reason for the new GetObserver signature to not be returning already_AddRefed<nsIObserver>?

As far as comment 58 goes, the prefservice is main-thread-only, last I checked.  Furthermore, the standard weak-reference implementation is not threadsafe (e.g. nsQueryReferent::operator() will totally fail if mWeakPtr can go null after it's checked there).  So I'm not sure you need to worry about threading issues here.
Attached patch Patch v10Splinter Review
All right; this one returns already_AddRefed<nsIObserver>.

I also got rid of the questionable code from comment 58, if only for hygiene's sake.
Attachment #467447 - Attachment is obsolete: true
Attached patch Interdiff v9 -> v10 (obsolete) — Splinter Review
Attachment #467454 - Attachment is obsolete: true
Attachment #468376 - Flags: review?(bzbarsky)
That interdiff doesn't match the attached v10 patch.
Perhaps this is the right interdiff.
Attachment #468376 - Attachment is obsolete: true
Attachment #468376 - Flags: review?(bzbarsky)
Attachment #468382 - Flags: review?(bzbarsky)
Comment on attachment 468382 [details] [diff] [review]
Interdiff v9 -> v10 (second try)

You shouldn't need the explicit .get().  r=me with that, or a comment about why it's there.
Attachment #468382 - Flags: review?(bzbarsky) → review+
http://hg.mozilla.org/mozilla-central/rev/473b38f32d59
Status: REOPENED → RESOLVED
Closed: 10 years ago10 years ago
Resolution: --- → FIXED
Attachment #457443 - Attachment is patch: false
Comment on attachment 468375 [details] [diff] [review]
Patch v10

>+  if (mObservers.Get(pCallback)) {
>+    NS_WARNING("Ignoring duplicate observer.");
Filed bug 595799 on nsXPLookAndFeel's duplicate observer.
You need to log in before you can comment on or make changes to this bug.