Closed Bug 1441876 Opened 4 years ago Closed 3 years ago

Asking for memory report can cause a virtual iloop comparing strings in JS CollectReports()

Categories

(Core :: JavaScript Engine, defect, P3)

58 Branch
defect

Tracking

()

RESOLVED FIXED
mozilla62
Tracking Status
firefox62 --- fixed

People

(Reporter: jesup, Assigned: jesup)

References

(Blocks 1 open bug)

Details

Attachments

(2 files, 3 obsolete files)

If you do Measure in about:memory, sometimes a Content process will virtually iloop - taking minutes or even hours in the MemoryReporter.  I've seen this and captured a profile on it at least twice.  The first time, after many, manyminutes it appeared to finish IIRC, and I took a GC log and ran it through stringy.py.  I found there were *many* several-k-long strings with a 6 or 8-char difference deep in the string (some node id it appeared).  

A profile shows it's spending 100% of it's time in StatsCellCallback(), and within that 67% in js::HashStringChars<> and 33% in js::EqualStringsPure()

https://perfht.ml/2F0jpKE
FYI this was on Beta 59, windows 10 x64
Although you said most of the time is in Vector::growStorage, if we're talking minutes/hours-long, I think we must be hitting O(n^2) behavior.  Without being able to look at the workload, if we're doing non-flatting hashing and string comparison, there's an obvious way to hit O(n^2) behavior: if a rope is created for a large string with N intermediate rope nodes (each logically containing a subset of the one large string), then about:memory will do an O(n) operation on each rope node.

Is it ok to flatten ropes during about:memory?
(In reply to Luke Wagner [:luke] from comment #2)
> Is it ok to flatten ropes during about:memory?

It is a bit unfortunate, IMO, but maybe it's okay. We could only do it for ropes that have other ropes as child nodes...
Actually, thinking about this a bit more, flattening might not be the answer.  Already, about:memory probably is being smart about dependent strings (to avoid double-counting memory), so maybe the fix is to make about:memory smart about ropes instead of doing this pure flattening operation.  Actually, if about:memory is just walking the GC heap, does it even need to do anything for ropes since it'll eventually see all the flat-string leaves?
So this allStrings HashMap is used to find notable strings: https://searchfox.org/mozilla-central/rev/14d933246211b02f5be21d2e730a57cf087c6606/js/src/vm/MemoryMetrics.cpp#660

If that's the only use of this HashMap, it's probably okay to not add ropes (and dependent strings) to it because ropes don't use much memory anyway...
Hm nevermind comment 5, the map is keyed on the string *chars*, so ropes could still have many copies and end up being notable.
Could we give up the case where a long notable string is a rope composed only of short (non-notable) flat leaf strings and thus assume notable strings ultimately involved notable flat strings (which we'll find directly in our GC traversal)?  If so, then I would think comment 5 was right and we could ignore rope and dependent strings.
(In reply to Luke Wagner [:luke] from comment #4)
> Actually, thinking about this a bit more, flattening might not be the
> answer.  Already, about:memory probably is being smart about dependent
> strings (to avoid double-counting memory)

Yeah, we ignore ropes when calculating the malloc heap size [1,2].

> so maybe the fix is to make
> about:memory smart about ropes instead of doing this pure flattening
> operation.  Actually, if about:memory is just walking the GC heap, does it
> even need to do anything for ropes since it'll eventually see all the
> flat-string leaves?

That's how it works for calculating the size, but not for notable strings.

(In reply to Jan de Mooij [:jandem] from comment #5)
> So this allStrings HashMap is used to find notable strings:
> https://searchfox.org/mozilla-central/rev/
> 14d933246211b02f5be21d2e730a57cf087c6606/js/src/vm/MemoryMetrics.cpp#660
> 
> If that's the only use of this HashMap, it's probably okay to not add ropes
> (and dependent strings) to it because ropes don't use much memory anyway...

Yeah AFAICT we only use `allStrings` for finding notable strings. We're going to ignore ropes anyhow since it won't be notable (it has basically no size if I understand correctly). We could probably rename `allStrings` to `notableStrings` and only add strings to it [3] if `IsNotable() == true`.

[1] https://searchfox.org/mozilla-central/rev/14d933246211b02f5be21d2e730a57cf087c6606/js/src/vm/String.cpp#39-41
[2] https://searchfox.org/mozilla-central/rev/14d933246211b02f5be21d2e730a57cf087c6606/js/src/vm/MemoryMetrics.cpp#528,531
[3] https://searchfox.org/mozilla-central/rev/14d933246211b02f5be21d2e730a57cf087c6606/js/src/vm/MemoryMetrics.cpp#540
(In reply to Luke Wagner [:luke] from comment #7)
> Could we give up the case where a long notable string is a rope composed
> only of short (non-notable) flat leaf strings and thus assume notable
> strings ultimately involved notable flat strings (which we'll find directly
> in our GC traversal)?  If so, then I would think comment 5 was right and we
> could ignore rope and dependent strings.

I'm pretty sure they way we count things a notable string will *never* be a rope, so this is probably okay. Nick you wrote all of this, does that sound about right?
Flags: needinfo?(n.nethercote)
Okay so technically a rope *can* be notable, for example:

> 31,440 B (00.01%) ── string(length=97, copies=1310, ",wc:65.532.1280.966,ac:923.1268.300.250,am:i,cc:923.1268.300.250,piv:92,obst:0,th:1,reas:f,cmps:1")/gc-heap/latin1
> 33,048 B (00.01%) ── string(length=45, copies=1377, "/n    in ErrorBoundary (created by Base__Base")/gc-heap/latin1

In both cases the rope string has a size of 24 bytes but there are a ton of copies of it. I'm still inclined to ignore them.
AFAICT ropes can be notable. Note that the hashing of ropes is really inefficient, using the descriptively-named `InefficientNonFlatteningStringHashPolicy`, which uses this hash function:
https://searchfox.org/mozilla-central/rev/efce4ceddfbe5fe4e2d74f1aed93894bada9b273/js/src/vm/MemoryMetrics.cpp#57-60

I agree with erahm that the notable string detector should act like JSString::sizeOfExcludingThis() -- ignore ropes, dependent strings, and external strings.
Flags: needinfo?(n.nethercote)
Priority: -- → P3
Obviously we wouldn't leave hard-coded 50's in there, and might make it longer for 'verbose'.  Also, I duplicated instead of overloading length=0 or some such, to avoid overhead in hot-path code (StringType.cpp/JSRope), which might be overkill.
Attachment #8976749 - Flags: feedback?(sphink)
Assignee: nobody → rjesup
Status: NEW → ASSIGNED
This replaces the existing logic that does a full copy of the rope and then
hashes and instead iteratively hashes each portion of the rope. While it
avoids allocating a new string it still does some allocations in order to
iteratively process the rope rather than risk stack exhaustion.
Attachment #8976750 - Flags: review?(sphink)
Sorry for the churn, slight update.
Attachment #8976751 - Flags: review?(sphink)
Attachment #8976750 - Attachment is obsolete: true
Attachment #8976750 - Flags: review?(sphink)
Comment on attachment 8976749 [details] [diff] [review]
Limit the length for string compares when hashing/de-duping for memory reporting

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

::: js/src/vm/MemoryMetrics.cpp
@@ +81,2 @@
>          return false;
> +    if (s1_length > length) {

Should this be s1_length < length?
> > +    if (s1_length > length) {
> 
> Should this be s1_length < length?

Yes, thanks!
cleaned up some, fixed a bug.  Tested by using 5 as the max matching length
Attachment #8977029 - Flags: review?(sphink)
Attachment #8976749 - Attachment is obsolete: true
Attachment #8976749 - Flags: feedback?(sphink)
Comment on attachment 8977029 [details] [diff] [review]
Limit the length for string compares when hashing/de-duping for memory reporting

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

::: js/src/vm/MemoryMetrics.cpp
@@ +38,5 @@
>  using JS::CompartmentStats;
>  
>  namespace js {
>  
> +#define MAX_STRING_HASH_LENGTH 100

I think recently static const size_t has been winning the battle against #define for these.

Any particular reason for 100 vs 50 or 64 or something else? Just asking; I don't have an opinion.

@@ +75,5 @@
>  }
>  
>  template <typename Char1, typename Char2>
>  static bool
> +EqualStringsPure(JSString* s1, JSString* s2, size_t length)

s/length/limit/ or charLimit or maxCharsToCompare or something.

@@ +83,4 @@
>          return false;
> +    if (s1_length < length) {
> +        length = s1_length;
> +    }

You're in JS-land; get rid of the curly brackets for single-line consequents.

::: js/src/vm/StringType.cpp
@@ +402,5 @@
> +    if (nullTerminate)
> +        out[n] = 0;
> +
> +    return true;
> +}

So... this looks good to me, but this code prefers right-leaning ropes and I'm hoping my patch in bug 1462486 does better by preferring left-leaning ropes. I'd imagine that it doesn't matter nearly as much when you have a length limit, but then again the conversion here should be similarly mechanical (well, mostly; I guess you'd need to skip out of range right children entirely and instead iterate onto the left child). I haven't successfully done a talos build, and it's possible that the CPU will prefer filling memory left to right. I guess I should do a microbenchmark to test.

Anyway, it's up to you, and I'm fine with landing this as-is, or landing it like this now and then changing it, or changing it over completely.

::: js/src/vm/StringType.h
@@ +1439,5 @@
> +void
> +CopyChars(CharT* dest, const JSLinearString& str)
> +{
> +    CopyChars(dest, str, str.length());
> +}

Not a big deal, but I'd probably vote for defining these inline, just because every time you add another copy of the word "template" to the code base, an angel cries.
Attachment #8977029 - Flags: review?(sphink) → review+
Comment on attachment 8976751 [details] [diff] [review]
Implement a more efficient JSRope hasher

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

Both of these patches seem worth landing to me.

::: js/src/vm/MemoryMetrics.cpp
@@ +57,2 @@
>      } else {
> +        // Use rope's optimized hash function.

I wondering if "optimized" should be "in place" or "noncopying"?

::: js/src/vm/StringType.cpp
@@ +388,5 @@
> +            if (nodeStack.empty())
> +                break;
> +            str = nodeStack.popCopy();
> +        }
> +    }

Sadly, this once again prefers right-leaning ropes, but in this case I don't think there's anything we can do about it. Oh well, it's a totally minor concern here.

::: js/src/vm/StringType.h
@@ +704,5 @@
> +    // Hash function specific for ropes that avoids allocating a temporary
> +    // string. There are still allocations internally so it's technically
> +    // fallible.
> +    //
> +    // The hash itself is implemented so as to return the same value as if

s/The hash itself is implemented so as to return/Returns/
Attachment #8976751 - Flags: review?(sphink) → review+
Comment on attachment 8976751 [details] [diff] [review]
Implement a more efficient JSRope hasher

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

Oh! One more request -- can you update the comment in js/public/MemoryMetrics.h? Right now it is:

/**
 * This hash policy avoids flattening ropes (which perturbs the site being
 * measured and requires a JSContext) at the expense of doing a FULL ROPE COPY
 * on every hash and match! Beware.
 */
struct InefficientNonFlatteningStringHashPolicy
{
    typedef JSString* Lookup;
    static HashNumber hash(const Lookup& l);
    static bool match(const JSString* const& k, const Lookup& l);
};
https://hg.mozilla.org/mozilla-central/rev/ba708fde30b8
Status: ASSIGNED → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla62
Attachment #8977029 - Attachment is obsolete: true
Blocks: 1504926
You need to log in before you can comment on or make changes to this bug.