784563 - Investigate being lazier about removing things from the purple buffer

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[Andrew McCreight [:mccr8]]

We remove things from the purple buffer every time we AddRef.  But if we Release soon after, we just add it again.  This is probably not the fastest thing in the world.  We could experiment with various ways of being lazier about removing things from the purple buffer, which would eliminate insertions. The drawback is that the max size of the purple buffer may grow.

A conservative option suggested by Olli is to use the participant field in the purple buffer entry that will be added by bug 750570 to indicate that a purple buffer entry is dead. Instead of removing something from the purple buffer when you addref, you set the flag. When you later decref, you clear the flag.  When doing purple buffer cleanup, clear everything where the bit is set.

A more aggressive option is just to not do the removal, and hope that our optimizations are awesome enough that the addref removal isn't really that important.

Probably a first step is to see how often the insertion/removal really happens, and how much time it really takes.

Comment 1

[Olli Pettay [:smaug][[e-mail]]]

The "conservative" approach should be quite fast.
It would slow down decr() if the object is already in the purple buffer, since one bit would
have to be unset. incr() one the other hand would become hopefully significantly faster in case
the object is in the purple buffer since NS_CycleCollectorForget2 wouldn't have to be called.
But we might want to call some cycle collector's purple buffer counter method to tell that
the is one more not-really-purple-thing in the buffer.

Comment 2

[Olli Pettay [:smaug][[e-mail]]]

(yet it is possible that this all won't speed up anything. nsPurpleBuffer::Remove isn't that
complicated.)

Comment 3

[Olli Pettay [:smaug][[e-mail]]]

Attachment: WIP

Doesn't seem to crash opt build immediately. Need to test debug build.

Changes also NS_CycleCollectorForget2 so that it doesn't return anything.
(I'm hoping compiler could do some tiny optimizations because of the change, 
but should look at the generated code.)

Comment 4

[Andrew McCreight [:mccr8]]

Comment on attachment 655371 [details] [diff] [review]
WIP

Review of attachment 655371 [details] [diff] [review]:
-----------------------------------------------------------------

::: xpcom/glue/nsISupportsImpl.h
@@ +156,4 @@
>        nsPurpleBufferEntry *e = NS_CCAR_TAGGED_TO_PURPLE_ENTRY(mTagged);
>        NS_ASSERTION(e->mObject == owner, "wrong entry");
> +      if (NS_UNLIKELY(--(e->mRefCnt) == 0)) {
> +        NS_CycleCollectorForget2(e);

You could probably avoid Forget entirely by nulling out mObject and setting mNotPurple, but maybe that's not worth doing, as we're freeing an object anyways.

Comment 5

[Olli Pettay [:smaug][[e-mail]]]

Ah, interesting idea.

Comment 6

[Olli Pettay [:smaug][[e-mail]]]

Attachment: doesn't crash immediately

Comment 7

[Olli Pettay [:smaug][[e-mail]]]

Attachment: try to force some more inlining

Comment 8

[Olli Pettay [:smaug][[e-mail]]]

Attachment: MOZ_ALWAYS_INLINE

Comment 9

[Olli Pettay [:smaug][[e-mail]]]

Attachment: v3

Gives about 20-25% perf boost in the range addref/release test and
in an event dispatching test when compiled locally -O2 with and without the patch.

(I made a tiny last minute change to the patch, so hopefully tryserver does still look ok.)

Comment 10

[Andrew McCreight [:mccr8]]

Comment on attachment 658967 [details] [diff] [review]
v3

Review of attachment 658967 [details] [diff] [review]:
-----------------------------------------------------------------

Nice patch!

I want to think some more about the four states a purple buffer entry can have (null vs nonnull mObject, mNotPurple true vs false) and what that means, and where we can check them, but here are my comments so far.

No need to do it here if you don't want to, but please at least file a followup bug to remove Suspect2, including all the surrounding XPCOM goop, so one of us can remember to do that at some point.

::: xpcom/base/nsCycleCollector.cpp
@@ +877,2 @@
>          if (!e) {
>              return nullptr;

You should update the comment near the declaration of RemoveSkippable that says that it removes entries if "nsPurpleBufferEntry::mObject is null", as that condition is now that the entry isn't live.

@@ +951,5 @@
>              e != eEnd; ++e) {
>              if (!(uintptr_t(e->mObject) & uintptr_t(1))) {
>                  // This is a real entry (rather than something on the
>                  // free list).
> +                if (e->mObject && e->mNotPurple) {

The DEBUG_CC chunk in SelectPointers(), UnmarkRemainingPurple(), RemoveSkippable() also have similar checks for mObject. Do any of them need to change?

@@ +2000,5 @@
>                  // free list).
>                  if (e->mObject) {
>                      void *o = e->mObject;
> +                    // Check mNotPurple before canonicalizing, since that
> +                    // may affect to purpleness, at least in theory.

How can that happen? Can't you just change the e->mObject check a few lines above to some kind of LiveEntry() predicate (eg e->mObject && !e->mNotPurple)?

::: xpcom/glue/nsISupportsImpl.h
@@ +89,5 @@
>    // When an object is in the purple buffer, it replaces its reference
>    // count with a (tagged) pointer to this entry, so we store the
>    // reference count for it.
> +  nsrefcnt mRefCnt : 31;
> +  nsrefcnt mNotPurple : 1;

Seems weird for mNotPurple to be nsrefcnt. Can you make it bool, or just an explicit int type?

Could you also change mNotPurple to mIsPurple or something? Double negations are confusing.

Also, please add a comment on what the mNotPurple/mIsPurple field is for. Something like, "when this flag is true/false, the purple buffer entry is in a state where there's an object out there that holds onto it, but we aren't counting that object as purple. This is done to reduce the cost of removing something from the purple buffer."

Now that I think of it, it might be a good idea to talk about the case where mObject can be null, and how that does or does not relate to the purple flag.

@@ +124,5 @@
>        nsPurpleBufferEntry *e = NS_CCAR_TAGGED_TO_PURPLE_ENTRY(mTagged);
>        NS_ASSERTION(e->mObject == owner, "wrong entry");
> +      NS_ASSERTION(e->mRefCnt, "purple ISupports pointer with zero refcnt");
> +      refcount = ++(e->mRefCnt);
> +      e->mNotPurple = true;

You should add a call to nsCycleCollector_logPurpleRemoval() here, like in RemovePurple.

@@ +182,2 @@
>    {
> +    NS_ASSERTION(HasPurpleBufferEntry(), "must have purple buffer entry");

Could you rename unmarkPurple() to something like releasePurpleBufferEntry()?  Unmark isn't a very clear name.

Comment 11

[Olli Pettay [:smaug][[e-mail]]]

(In reply to Andrew McCreight [:mccr8] from comment #10)
> No need to do it here if you don't want to, but please at least file a
> followup bug to remove Suspect2, including all the surrounding XPCOM goop,
> so one of us can remember to do that at some point.
Er, we still need suspect. In the earlier patch I was just changing its return value.
I also want to keep forget, in case some addon uses it.


> 
> ::: xpcom/base/nsCycleCollector.cpp
> @@ +877,2 @@
> >          if (!e) {
> >              return nullptr;
> 
> You should update the comment near the declaration of RemoveSkippable that
> says that it removes entries if "nsPurpleBufferEntry::mObject is null", as
> that condition is now that the entry isn't live.
You mean I should add also "or is entry's mNotPurple is true."



> 
> @@ +951,5 @@
> >              e != eEnd; ++e) {
> >              if (!(uintptr_t(e->mObject) & uintptr_t(1))) {
> >                  // This is a real entry (rather than something on the
> >                  // free list).
> > +                if (e->mObject && e->mNotPurple) {
> 
> The DEBUG_CC chunk in SelectPointers(), UnmarkRemainingPurple(),
> RemoveSkippable() also have similar checks for mObject. Do any of them need
> to change?
RemoveSkippable doesn't have DEBUG_CC, nor UnmarkRemainingPurple, and
SelectPointers does the right thing.

> 
> @@ +2000,5 @@
> >                  // free list).
> >                  if (e->mObject) {
> >                      void *o = e->mObject;
> > +                    // Check mNotPurple before canonicalizing, since that
> > +                    // may affect to purpleness, at least in theory.
> 
> How can that happen?
Some unusual addref/release implementation (not using the macro). But ok, perhaps
I don't need this.

> Can't you just change the e->mObject check a few lines
> above to some kind of LiveEntry() predicate (eg e->mObject &&
> !e->mNotPurple)?
I need to still unmark, so that we remove the purple entry.
Or am I missing which case you're thinking.


> @@ +89,5 @@
> >    // When an object is in the purple buffer, it replaces its reference
> >    // count with a (tagged) pointer to this entry, so we store the
> >    // reference count for it.
> > +  nsrefcnt mRefCnt : 31;
> > +  nsrefcnt mNotPurple : 1;
> 
> Seems weird for mNotPurple to be nsrefcnt. Can you make it bool, or just an
> explicit int type?
I wanted to be 100% even Windows packs there correctly, but I think you're right
that bool mNotPurple : 1; should work.




> 
> Could you also change mNotPurple to mIsPurple or something? Double negations
> are confusing.
I knew you were going to complain about that :)
In this case I'd prefer to have flag for the non-default case, which is mNotPurple

 
> Also, please add a comment on what the mNotPurple/mIsPurple field is for.
> Something like, "when this flag is true/false, the purple buffer entry is in
> a state where there's an object out there that holds onto it, but we aren't
> counting that object as purple. This is done to reduce the cost of removing
> something from the purple buffer."
k
 
> Now that I think of it, it might be a good idea to talk about the case where
> mObject can be null, and how that does or does not relate to the purple flag.
ok, I'll add a comment, something like.
mObject is set to null when nsCycleCollectingAutoRefCnt loses its reference to the PurpleBufferEntry so that
the entry can be put to the free list. When mObject is null, mNotPurple has no meaning.


> 
> @@ +124,5 @@
> >        nsPurpleBufferEntry *e = NS_CCAR_TAGGED_TO_PURPLE_ENTRY(mTagged);
> >        NS_ASSERTION(e->mObject == owner, "wrong entry");
> > +      NS_ASSERTION(e->mRefCnt, "purple ISupports pointer with zero refcnt");
> > +      refcount = ++(e->mRefCnt);
> > +      e->mNotPurple = true;
> 
> You should add a call to nsCycleCollector_logPurpleRemoval() here, like in
> RemovePurple.
Well, that is not clear. The object does still have purple buffer...
But ok, for backward compatibility I could do that.
#ifdef DEBUG_CC
  if (!e->mNotPurple) {
    nsCycleCollector_logPurpleRemoval(
      NS_CCAR_TAGGED_TO_PURPLE_ENTRY(mTagged)->mObject);
  }
#endif
  e->mNotPurple = true;



> 
> @@ +182,2 @@
> >    {
> > +    NS_ASSERTION(HasPurpleBufferEntry(), "must have purple buffer entry");
> 
> Could you rename unmarkPurple() to something like
> releasePurpleBufferEntry()?  Unmark isn't a very clear name.
k

Comment 12

[Olli Pettay [:smaug][[e-mail]]]

Attachment: v4

Had to update logging to get it work the same way it works now.

https://tbpl.mozilla.org/?tree=Try&rev=de0210601dfd

Comment 13

[Andrew McCreight [:mccr8]]

(In reply to Olli Pettay [:smaug] from comment #11)
> Er, we still need suspect. In the earlier patch I was just changing its
> return value.
Oops, I meant forget not suspect!

> I also want to keep forget, in case some addon uses it.

Okay, that sounds fine to me, though hopefully we won't accidentally break it now that we're not actually testing it.

> RemoveSkippable doesn't have DEBUG_CC, nor UnmarkRemainingPurple, and
> SelectPointers does the right thing.
Sorry, the DEBUG_CC was only supposed to refer to SelectPointers(). But anyways, I looked over them again in your most recent patch and they all look fine to me.

> > How can that happen?
> Some unusual addref/release implementation (not using the macro). But ok,
> perhaps I don't need this.
Yeah, I think we don't really want to support weird addref/release for the CC

> I need to still unmark, so that we remove the purple entry.
> Or am I missing which case you're thinking.
I think I was just confused.

> > >    // When an object is in the purple buffer, it replaces its reference
> > >    // count with a (tagged) pointer to this entry, so we store the
> > >    // reference count for it.
> > > +  nsrefcnt mRefCnt : 31;
> > > +  nsrefcnt mNotPurple : 1;
> > 
> > Seems weird for mNotPurple to be nsrefcnt. Can you make it bool, or just an
> > explicit int type?
> I wanted to be 100% even Windows packs there correctly, but I think you're
> right that bool mNotPurple : 1; should work.
Is Visual Studio actually better about packing things with different sizes now? It doesn't need to be a bool, necessarily, but if it isn't maybe just a comment about how it is only storing a bool is enough. Though maybe the fact that it is a single bit is a good enough indicator. Also, if you are going to check the packing anyways, I wonder if it would be better to have mParticipant before mRefCnt...

> I knew you were going to complain about that :)
> In this case I'd prefer to have flag for the non-default case, which is
> mNotPurple
Okay, with some of the comments you added, I'm a bit more clear about what each of these things are, so I guess it is okay.

> k
Thanks, the two new comments in nsPurpleBufferEntry are really great! I feel confident that I actually understand fully what is happening now. :)

> > You should add a call to nsCycleCollector_logPurpleRemoval() here, like in
> > RemovePurple.
> Well, that is not clear. The object does still have purple buffer...
True, it still uses space, but I think the more important thing is that it isn't considered purple any more.

> > Could you rename unmarkPurple() to something like
> > releasePurpleBufferEntry()?  Unmark isn't a very clear name.
> k
Thanks!

Comment 14

[Andrew McCreight [:mccr8]]

Comment on attachment 659210 [details] [diff] [review]
v4

Review of attachment 659210 [details] [diff] [review]:
-----------------------------------------------------------------

Looks good!

::: xpcom/base/nsCycleCollector.cpp
@@ +954,5 @@
> +                    nsCycleCollectionParticipant* cp = e->mParticipant;
> +                    CanonicalizeParticipant(&o, &cp);
> +                    cp->UnmarkIfPurple(o);
> +                    Remove(e);
> +                    continue;

Maybe use an |else if| instead of a |continue|? I think it is good to avoid weird control constructs if possible.

@@ +2494,5 @@
> +    mStats.mSuspectNode++;
> +
> +    if (!cp &&
> +        nsCycleCollector_shouldSuppress(static_cast<nsISupports *>(aObject)))
> +        return;

This changes the behavior: in the original code, when shouldSuppress is true, we don't add it to the purple buffer. Maybe return a bool from this function or something and return early in Suspect2 if it returned false. You can just ignore the return for nsCycleCollector_logPurpleAddition.

::: xpcom/glue/nsISupportsImpl.h
@@ +82,5 @@
>  // Support for ISupports classes which interact with cycle collector.
>  
>  struct nsPurpleBufferEntry {
> +  // mObject is set to null when nsCycleCollectingAutoRefCnt loses its
> +  // reference to the PurpleBufferEntry so that the entry can be put to the

"added to" or "put on" instead of "put to" maybe?

@@ +96,5 @@
> +  // When this flag is true, the purple buffer entry is in
> +  // a state where there's an object out there that holds onto it, but we aren't
> +  // counting that object as purple. This is done to reduce the cost of removing
> +  // objects from the purple buffer.
> +  nsrefcnt mNotPurple : 1; // nsrefcnt to ensure right packing.

Oh you already added the comment about packing. Great.

Comment 15

[Olli Pettay [:smaug][[e-mail]]]

Attachment: v5

Comment 16

[Olli Pettay [:smaug][[e-mail]]]

https://hg.mozilla.org/mozilla-central/rev/2abc79eb9283