Closed Bug 833913 Opened 7 years ago Closed 7 years ago

Make NS_{Unr,R}egisterMemoryReporter O(1) instead of O(n)

Categories

(Toolkit :: about:memory, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla21

People

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

References

Details

Attachments

(3 files, 2 obsolete files)

khuey and I want to make one memory reporter per large blob for bug 832609.  But to do that, we need to make adding/removing memory reporters faster, to avoid poor performance in the case when you have many memory blobs.

Right now it's an O(n) operation to insert or remove a memory reporter.  We can easily do better than this.
Semi-relatedly, I've been thinking about adding a memory reporter that counts how many memory reporters there are...
Trivial change (and not really related to this bug).
Attachment #706445 - Flags: review?(benjamin)
I think there was a copy/paste error in the original implementation:
There was no copy constructor on nsCOMPtrHashKey, but in its place there
was a one-arg constructor taking nsPtrHashKey<T>.  I changed this to be
a copy constructor (i.e., taking nsCOMPtrHashKey<T>).
Attachment #706447 - Flags: review?(benjamin)
The tests insert a number of memory reporters all with the same amounts.
Currently, they're sorted in about:memory by the order in which they were
registered.  But of course we can't do that if we're using a hashtable.

It's possible that there is non-determinism in the tests remaining and the
hashtable just happens to be giving the right results.  If so, I expect we'll
get some random oranges in the about:memory tests.  But I tried to catch all
the non-determinism by running the tests multiple times and by tweaking the
hash function, so hopefully it's OK.
Attachment #706449 - Flags: review?(n.nethercote)
This is the main event.

In the past njn has said he's not entirely comfortable with this XPCOM-y stuff,
so I imagine he'd appreciate if khuey looked at this patch.  But if Nick is
comfortable reviewing by himself, that's also fine with me.
Attachment #706451 - Flags: review?(n.nethercote)
Attachment #706451 - Flags: review?(khuey)
Attachment #706445 - Flags: review?(benjamin) → review+
Comment on attachment 706447 [details] [diff] [review]
Part 2, v1: Move nsCOMPtrHashKey to nsHashKeys.h.

This class is different from nsISupportsHashKey in a subtle and probably undesirable way: this class only compares the raw interface pointer for equality, instead of querying it back to nsISupports and comparing the canonical nsISupports. In the case of tearoffs (which can sometimes happen in xpconnect), this means that you could basically end up with multiple instances of the same object in the hash.

Now... perhaps this doesn't matter; especially when you know what kind of objects you're storing and that they won't have tearoffs, it really doesn't matter.

This class is also different from nsRefPtrHashKey in a way that probably doesn't matter. I suspect that clients who don't care should just use nsRefPtrHashKey, and clients that do care should use nsISupportsHashKey, and this class does not need to exist.
Attachment #706447 - Flags: review?(benjamin) → review-
Comment on attachment 706447 [details] [diff] [review]
Part 2, v1: Move nsCOMPtrHashKey to nsHashKeys.h.

I suspect you're right about nsCOMPtrHashKey.  I'll have a try.  Thanks!
Comment on attachment 706451 [details] [diff] [review]
Part 4: Switch nsMemoryReporterManager to using nsTHashtable.

I'm going to redo this one.
Attachment #706451 - Attachment is obsolete: true
Attachment #706451 - Flags: review?(n.nethercote)
Attachment #706451 - Flags: review?(khuey)
Comment on attachment 706449 [details] [diff] [review]
Part 3: Make about:memory sort reporters with equal amounts by name, and update the tests to match this.

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

It turns out that I'm picky about how sorting comparison functions are written :)

::: toolkit/components/aboutmemory/content/aboutMemory.js
@@ +578,5 @@
>  
>      if (nodeA && nodeB) {
> +      let cmp = TreeNode.compareAmounts(nodeA, nodeB);
> +      if (cmp != 0) {
> +        return cmp;

I found the comment and code of this function hard to follow.  Here's a (untested!) rewritten version.

  // Sort our list of processes.
  let processes = Object.keys(treesByProcess);
  processes.sort(function(aProcessA, aProcessB) {
    assert(aProcessA != aProcessB, 
           "Elements of Object.keys() should be unique, but saw duplicate " + 
           aProcessA + " elem.");

    // Always put the main process first.
    if (aProcessA == gUnnamedProcessStr) {
      return -1;
    }
    if (aProcessB == gUnnamedProcessStr) {
      return 1;
    }

    // Then sort by resident size.  Treat a missing size as zero.
    let nodeA = degeneratesByProcess[a]['resident'];
    let nodeB = degeneratesByProcess[b]['resident'];
    let residentA = nodeA ? nodeA._amount : 0;
    let residentB = nodeB ? nodeB._amount : 0;

    if (residentA < residentB) {
      return -1;
    }
    if (residentA > residentB) {
      return 1;
    }

    // Then sort by process name.
    if (aProcessA < aProcessB) {
      return -1;
    }
    if (aProcessA > aProcessB) {
      return 1;
    }
    return 0;
  });


Changes:
- rename |a| and |b| as |aProcessA|, |aProcessB|, which makes it clearer in the presence of multiple values being compared.

- Doesn't use TreeNode.compare, because that just obfuscated things in this case.  This allowed the "default resident value is zero" approach.

- Comments are inline.

- Control flow is simpler.

- |aProcessA| is always on the LHS of comparisons.

What do you think?

@@ +590,5 @@
>      if (nodeB) {
>        return 1;
>      }
>  
> +    // Comparre process names, if all else fails.  This guarantees a stable

Typo: "Comparre".

@@ +880,5 @@
>    }
>  };
>  
> +// To get a stable sort (which is particularly important for the tests of
> +// about:memory), we sort by name if the amounts are the same.

"stable" isn't the right word here -- you're changing the meaning of "equal", not the ordering of equal elements.

Maybe "deterministic sort" is the right phrase?

Also, I like describing the primary and secondary sorts clearly.  E.g. "We sort by size, then by name."

@@ +885,3 @@
>  TreeNode.compareAmounts = function(a, b) {
> +  if (a._amount != b._amount)
> +    return b._amount - a._amount;

Standard style is to always brace if bodies in JS code.

@@ +885,4 @@
>  TreeNode.compareAmounts = function(a, b) {
> +  if (a._amount != b._amount)
> +    return b._amount - a._amount;
> +  return TreeNode.compareUnsafeNames(a, b);

How about this?

  let diff = b._amount - a._amount;
  return (diff !== 0) ? diff : TreeNode.compareUnsafeNames(a, b);

Alternatively (this is more like the other cases in this file):

  if (a._amount < b._amount) {
    return -1;
  }
  if (a._amount > b._amount) {
    return 1;
  }
  return TreeNode.compareUnsafeNames(a, b);
Attachment #706449 - Flags: review?(n.nethercote) → review+
Now with less nsCOMPtrHashKey; this is much better.
Attachment #706447 - Attachment is obsolete: true
Attachment #706556 - Flags: review?(n.nethercote)
Attachment #706556 - Flags: review?(khuey)
Comment on attachment 706556 [details] [diff] [review]
Part 3, v2: Switch nsMemoryReporterManager to using nsTHashtable.

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

::: xpcom/base/nsMemoryReporterManager.cpp
@@ +708,5 @@
> +    {
> +        aHashtable.EnumerateEntries(EnumeratorFunc, this);
> +    }
> +
> +    virtual ~HashtableEnumerator() {}

No need for a virtual dtor.

@@ +732,5 @@
> +}
> +
> +NS_IMETHODIMP HashtableEnumerator::HasMoreElements(bool* aResult)
> +{
> +    *aResult = (mIndex < mArray.Count());

Unnecessary parens.

@@ +739,5 @@
> +
> +NS_IMETHODIMP HashtableEnumerator::GetNext(nsISupports** aNext)
> +{
> +    if (mIndex < mArray.Count()) {
> +        nsCOMPtr<nsISupports> next = mArray.SafeObjectAt(mIndex);

Why do you need SafeObjectAt here?

@@ +741,5 @@
> +{
> +    if (mIndex < mArray.Count()) {
> +        nsCOMPtr<nsISupports> next = mArray.SafeObjectAt(mIndex);
> +        next.forget(aNext);
> +        mIndex++;

I would just stick the ++ in the ObjectAt call, but this is really nitpicky.

@@ +767,5 @@
>  nsMemoryReporterManager::EnumerateReporters(nsISimpleEnumerator **result)
>  {
> +    // Memory reporters are not necessarily threadsafe, so EnumerateReporters()
> +    // must be called from the main thread.
> +    MOZ_ASSERT(NS_IsMainThread());

I would prefer this aborted in release builds too.

@@ +782,5 @@
>  nsMemoryReporterManager::EnumerateMultiReporters(nsISimpleEnumerator **result)
>  {
> +    // Memory multi-reporters are not necessarily threadsafe, so
> +    // EnumerateMultiReporters() must be called from the main thread.
> +    MOZ_ASSERT(NS_IsMainThread());

Ditto.

@@ +861,4 @@
>  
> +    if (!mReporters.Contains(reporter)) {
> +        return NS_ERROR_FAILURE;
> +    }

Super nit: newline after }

@@ +874,4 @@
>  
> +    if (!mMultiReporters.Contains(reporter)) {
> +        return NS_ERROR_FAILURE;
> +    }

Ditto.
Attachment #706556 - Flags: review?(khuey) → review+
Comment on attachment 706556 [details] [diff] [review]
Part 3, v2: Switch nsMemoryReporterManager to using nsTHashtable.

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

::: xpcom/base/nsMemoryReporterManager.cpp
@@ +823,5 @@
> +    // reporter.
> +    uint32_t refcnt = NS_ADDREF(reporter);
> +    MOZ_ASSERT(refcnt >= 2);
> +    NS_RELEASE(reporter);
> +#endif

Factor this out into a separate method, e.g. RefCountIsNonZero().
Attachment #706556 - Flags: review?(n.nethercote) → review+
> "stable" isn't the right word here -- you're changing the meaning of "equal",
> not the ordering of equal elements.

That's absolutely right; I've fixed this and incorporated your other comments.
I think this is fine, but mochitest-chrome was not shutting down cleanly for me, so I pushed to try to make sure this is normal.

https://tbpl.mozilla.org/?tree=Try&rev=25997d097c76
Assignee: nobody → justin.lebar+bug
https://hg.mozilla.org/mozilla-central/rev/346157c3cd44
https://hg.mozilla.org/mozilla-central/rev/da129718ccb1
https://hg.mozilla.org/mozilla-central/rev/5527dd4bfcbf
Status: NEW → RESOLVED
Closed: 7 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla21
No longer blocks: 832609
You need to log in before you can comment on or make changes to this bug.