1101337 - Hang opening reftest analyzer

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[Benoit Girard (:BenWa)]

Works fine with TBPL but not treehearder:
https://tbpl.mozilla.org/?tree=Try&rev=ebe810b66428
vs.
https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=ebe810b66428

Comment 1

[Benoit Girard (:BenWa)]

Attachment: Samples

Comment 2

[Ryan VanderMeulen [:RyanVM]]

I've seen this too.

Comment 3

[Benoit Girard (:BenWa)]

Total guess: TBPL only feeds the shortlog to reftest analyzer while TreeHerder puts everything. Maybe the platform needs to handle large text in a textbox faster, maybe TreeHerder needs to feed the shortlog.

Comment 4

[Ed Morley [:emorley]]

Agree this is most likely due to downloading the whole log, which is covered by bug 1063640.

We can either dupe this to there, or else morph this to be about platform improvements (to happen in parallel). Can I leave it up to you to decide if the latter is useful? :-)

Comment 5

[Cameron Dawson [:camd]]

Hey Ed: do you think this should become a P1?

Comment 6

[Cameron Dawson [:camd]]

From Philor in IRC:  
philor> camd: if 1101337 isn't P1, then just removing the UI until it isn't fatal should be
philor> it's just too tempting, having it right there

Comment 7

[Ed Morley [:emorley]]

Duping per comment 4.

I don't think this is a P1, I only hang for a second or two. Unless I've just not found a suitable example? (The links in comment 0 don't work any more)

Comment 8

[Ryan VanderMeulen [:RyanVM]]

I hit one today that made me force kill my browser. That wasn't nice.

Comment 9

[Ed Morley [:emorley]]

In which case happy for you to make bug 1063640 a P1 :-)

Comment 10

[Benoit Girard (:BenWa)]

Nope, the platform shouldn't hang for a text workload in the 100mb (I believe logs are smaller). This is a platform bug.

You guys are welcome to work around it in bug 1063640 until we fix it in the platform.

Comment 11

[Benoit Girard (:BenWa)]

Attachment: testeditor.html

Comment 12

[(no longer active)]

This is caused by nsContentUtils::PlatformToDOMLineBreaks being O(n^2).  I have a test fix on the try server that makes that function O(n).

Comment 13

[(no longer active)]

Benoit, please note that other things elsewhere in Gecko may still be slow in such circumstances.  If you hit this in TreeHerder again after my patches land, please file follow-ups with profiles.  Thanks!

Comment 14

[(no longer active)]

Attachment: Part 1: Add a linear substring replace API to XPCOM strings for the special case where the replacement is a shrinking one; r=froydnj

ReplaceSubstring() is an O(n^2) algorithm because we have to move the
remainder of the string, search it again and potentially memmove most of
it again as we find more matches.  It's easy however to implement a
linear algorithm that can only handle shrinking replacements (where the
length of the pattern to look for is not smaller than the length of the
replacement string.)  This patch adds such an API to XPCOM string
classes.  We will use this API in various parts of the platform later.

Note that we currently don't build TestStrings.cpp, so the test case in
this patch is not run automatically, but the test case has been verified
to pass separately by moving the test function into Gecko and calling it
during startup and stepping through it in the debugger.

Comment 15

[(no longer active)]

Attachment: Part 2: Optimize the conversion of platform specific line breaks into DOM line breaks; r=jst

This will help with test cases such as assigning a value containing
a lot of line breaks to a textarea, as done in TreeHerder, for
example.

Comment 16

[(no longer active)]

Comment on attachment 8534786 [details] [diff] [review]
Part 1: Add a linear substring replace API to XPCOM strings for the special case where the replacement is a shrinking one; r=froydnj

Nathan, please review this mercilessly.  :-)

Specifically, please let me know if you can think of other cases to test.  I'd like to have as many different tests here as possible, even though we can't run them on the infra yet.

Comment 17

[Ed Morley [:emorley]]

Thank you for digging into this :-)

Comment 18

[(no longer active)]

(In reply to Ed Morley (moved to Treeherder) [:edmorley] from comment #17)
> Thank you for digging into this :-)

Totally selfish!  I have spent around 6 months of my life making exactly this much faster a few years ago.  Just finishing the job.  :-)

Comment 19

[Nathan Froyd [:froydnj]]

Comment on attachment 8534786 [details] [diff] [review]
Part 1: Add a linear substring replace API to XPCOM strings for the special case where the replacement is a shrinking one; r=froydnj

Why not modify ReplaceSubstring to use the linear time algorithm in cases where we can?  And/or why not modify ReplaceSubstring to be linear in all cases, not just shrinking ones?

Comment 20

[(no longer active)]

(In reply to Nathan Froyd (:froydnj) from comment #19)
> Why not modify ReplaceSubstring to use the linear time algorithm in cases
> where we can? 

I hate it when functions change their performance characteristics depending on their arguments/etc.  I think a change between a linear and quadratic algorithm should be made explicitly by the caller.  Note that in a lot of cases the string being searched in is small and the quadratic algorithm doesn't hurt us that much, as evidenced by how long this has lived in the code base without anyone complaining.

> And/or why not modify ReplaceSubstring to be linear in all
> cases, not just shrinking ones?

Doing the linear algorithm in all cases is more involved since it will deal with the doubling growth strategy and I would also need to deal with how to handle the various storage mechanisms, whereas here I can just call MutatePrep() once with the maximum needed capacity.  Also the general case linear algorithm wouldn't help me with the issue at hand, so I decided to stick with the simpler case and leave the rest to someone else.  :-)

Comment 21

[Nathan Froyd [:froydnj]]

(In reply to :Ehsan Akhgari (not reading bugmail, needinfo? me!) from comment #20)
> > And/or why not modify ReplaceSubstring to be linear in all
> > cases, not just shrinking ones?
> 
> Doing the linear algorithm in all cases is more involved since it will deal
> with the doubling growth strategy and I would also need to deal with how to
> handle the various storage mechanisms, whereas here I can just call
> MutatePrep() once with the maximum needed capacity.

What's wrong with something like:

  // Determine all locations of the target string.
  nsAutoTArray<uint32_t, 16> positions;
  uint32_t i = 0;
  while (i < mLength) {
    int32_t offset = FindSubstring(mData + i, mLength - i, ...);
    if (offset == kNotFound) {
      break;
    }

    positions.AppendElement(offset);
    i = offset + aTarget.Length();
  }

  // Anything to do?
  if (positions.IsEmpty()) {
    return;
  }

  // Compute the length of the resulting string.

  // Single call to MutatePrep, to give us a new buffer.

  // Copy non-matching portions of the string + replacements into new buffer,
  // as the current patch does.

?

> Also the general case
> linear algorithm wouldn't help me with the issue at hand, so I decided to
> stick with the simpler case and leave the rest to someone else.  :-)

The first part of this statement doesn't sound right to me: you want a linear algorithm, why does it matter whether the algorithm is general or handles only the shrinking case?

Comment 22

[Nathan Froyd [:froydnj]]

(In reply to Nathan Froyd (:froydnj) from comment #21)
>   // Determine all locations of the target string.

Actually might be better to record all the pieces that *don't* match; I think that makes the later parts of the algorithm be somewhat simpler.

Comment 23

[Benoit Girard (:BenWa)]

If we want to have a special case for shrinking that is faster than that's fine.

But I thinking having a O(n^2) string replace is a big bug and we should focus on fixing that first.

Comment 24

[(no longer active)]

(In reply to Nathan Froyd (:froydnj) from comment #21)
> (In reply to :Ehsan Akhgari (not reading bugmail, needinfo? me!) from
> comment #20)
> > > And/or why not modify ReplaceSubstring to be linear in all
> > > cases, not just shrinking ones?
> > 
> > Doing the linear algorithm in all cases is more involved since it will deal
> > with the doubling growth strategy and I would also need to deal with how to
> > handle the various storage mechanisms, whereas here I can just call
> > MutatePrep() once with the maximum needed capacity.
> 
> What's wrong with something like:
> 
>   // Determine all locations of the target string.
>   nsAutoTArray<uint32_t, 16> positions;
>   uint32_t i = 0;
>   while (i < mLength) {
>     int32_t offset = FindSubstring(mData + i, mLength - i, ...);
>     if (offset == kNotFound) {
>       break;
>     }
> 
>     positions.AppendElement(offset);
>     i = offset + aTarget.Length();
>   }
> 
>   // Anything to do?
>   if (positions.IsEmpty()) {
>     return;
>   }
> 
>   // Compute the length of the resulting string.
> 
>   // Single call to MutatePrep, to give us a new buffer.
> 
>   // Copy non-matching portions of the string + replacements into new buffer,
>   // as the current patch does.
> 
> ?

There is nothing wrong with it, it's just not necessarily better than what we have now.  ReplaceSubstring can very well be used for very small strings so doing this can slow things down for such consumers.  One can of course measure all of the cases that happen in real life and then choose what to do for the general case, but given that I haven't seen any profile to suggest that such an improvement can make a difference in practice, I'd rather not scope creep this bug.

> > Also the general case
> > linear algorithm wouldn't help me with the issue at hand, so I decided to
> > stick with the simpler case and leave the rest to someone else.  :-)
> 
> The first part of this statement doesn't sound right to me: you want a
> linear algorithm, why does it matter whether the algorithm is general or
> handles only the shrinking case?

Please look at the second part of the patch.  The performance problem that I am trying to solve is for the shrinking only case.  Doing a linear algorithm for the general case is strictly slower because you either need to realloc or you need to do two passes on the string.  I just can't think of something that doesn't have those downsides.

Comment 25

[(no longer active)]

(In reply to Benoit Girard (:BenWa) from comment #23)
> But I thinking having a O(n^2) string replace is a big bug and we should
> focus on fixing that first.

Fixing that won't fix anything as well as my current patch does for this bug.  Can we please move the discussion about the general algorithm in a follow-up bug?

Comment 26

[(no longer active)]

OK, so I had a lengthy discussion about this with BenWa on IRC today.  He was arguing that we should just make the general case linear and not worry about doing multiple passes on the string, and while I didn't agree with him initially, he got me curious to implement the two approaches, so I went ahead and did that.  It turns out that with the test case on this bug, with either of the two approaches, nsContentUtils::PlatformToDOMLineBreaks won't show up in the profile!

So, BenWa was right, and we should fix this issue in XPCOM for all ReplaceSubstring() calls.

Comment 27

[(no longer active)]

Attachment: Make the ReplaceSubstring() XPCOM string API linear; r=froydnj

ReplaceSubstring() is an O(n*m) algorithm (n being the length of the
string and m being the number of occurrences of aTarget) because we have
to move the remainder of the string, search it again and potentially
memmove most of it again as we find more matches.  This patch rewrites
that function to make it O(n+m).

Note that we currently don't build TestStrings.cpp, so the test case in
this patch is not run automatically, but the test case has been verified
to pass separately by moving the test function into Gecko and calling it
during startup and stepping through it in the debugger.

Comment 28

[Benoit Girard (:BenWa)]

(In reply to :Ehsan Akhgari (not reading bugmail, needinfo? me!) from comment #27)
> Note that we currently don't build TestStrings.cpp, so the test case in
> this patch is not run automatically, but the test case has been verified
> to pass separately by moving the test function into Gecko and calling it
> during startup and stepping through it in the debugger.

Might be a good candidate to port to GTest, looks like a bunch of simple but a bit tedious work. Might be a decent first bug.

Comment 29

[Nathan Froyd [:froydnj]]

Comment on attachment 8535388 [details] [diff] [review]
Make the ReplaceSubstring() XPCOM string API linear; r=froydnj

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

BenWa for XPCOM string maintainer! :D  I'm glad he had that conversation with you so I didn't have to.  (And credit to NeilAway on IRC for prompting me to ask why we were adding a second function in the first place.)

::: xpcom/string/nsTStringObsolete.cpp
@@ +466,5 @@
>    if (aTarget.Length() == 0)
>      return;
>  
> +  // Remember all of the non-matching parts.
> +  nsAutoTArray<std::pair<uint32_t, uint32_t>, 16> nonMatching;

I dislike std::pair for its lack of readability when using members.  Could you please just write out the five lines of struct definition for the element type here?

@@ +482,5 @@
>  
> +    newLength += aNewValue.Length();
> +    i += r + aTarget.Length();
> +    if (i >= mLength) {
> +      // Add an auxilary entry at the end of the list to help as an edge case

Nit: "auxiliary"

@@ +488,5 @@
> +      nonMatching.AppendElement(std::make_pair(mLength, mLength));
> +      break;
> +    }
> +  }
> +

I think it'd be good to insert a check here for:

  // If there's only one non-matching segment, then the target string was not
  // found, and there's nothing to do.
  if (nonMatching.Length() == 1) {
    // Maybe MOZ_ASSERT the dimensions of the non-match are what we expect.
    return;
  }

as that behavior matches the original.  No sense heap-churning things in the non-matching case.

@@ +504,5 @@
> +  if (aTarget.Length() >= aNewValue.Length()) {
> +    // In the shrinking case, start filling the buffer from the beginning.
> +    const uint32_t delta = (aTarget.Length() - aNewValue.Length());
> +    for (i = 1; i < nonMatching.Length(); ++i) {
> +      memmove(mData + nonMatching[i].first - i * delta,

There ought to be a way to name the reused-below subexpressions here to make the code clearer.  Something like:

  char_type* segmentPtr = mData + nonMatching[i].first;

would be a good start (bikeshedding on the name(s) welcome).

Can you also add a comment, something like:

  // When we move the i'th non-matching segment into position, we need to account for the
  // characters deleted by the previous |i| replacements by subtracting |i * delta|.

@@ +506,5 @@
> +    const uint32_t delta = (aTarget.Length() - aNewValue.Length());
> +    for (i = 1; i < nonMatching.Length(); ++i) {
> +      memmove(mData + nonMatching[i].first - i * delta,
> +              mData + nonMatching[i].first,
> +              sizeof(char_type) * (nonMatching[i].second - nonMatching[i].first));

This is the only computation you perform with .second (duplicated below); it seems like you might as well just make .second be the length of the non-matching substring, rather than the end of the non-matching substring, and avoid this computation.

@@ +516,5 @@
> +    const uint32_t delta = (aNewValue.Length() - aTarget.Length());
> +    const uint32_t numNonMatching = nonMatching.Length();
> +    if (numNonMatching > 1) {
> +      for (i = numNonMatching - 1; i > 0; --i) {
> +        memmove(mData + nonMatching[i].first + i * delta,

Same comments from the above case apply, but in the reverse sense ("adding" instead of "deleting") for |i * delta|.

Comment 30

[(no longer active)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/2954a37bc2df

Comment 31

[(no longer active)]

And backed out since ASAN discovered a buffer overflow. :(

Comment 32

[[e-mail]]

Comment on attachment 8535388 [details] [diff] [review]
Make the ReplaceSubstring() XPCOM string API linear; r=froydnj

>+      // Add an auxilary entry at the end of the list to help as an edge case
>+      // for the algorithms below.
Would including the null terminator as part of the string data save you an edge case?

>+  if (!MutatePrep(newLength, &oldData, &oldFlags))
>+    return;
>+  if (oldData) {
>+    // Copy all of the old data to the new buffer.
(I'm sure there's a way to avoid copying all the old data to the wrong place and then fixing it up afterwards, but I can't quite think of it offhand.)

>+      memmove(mData + nonMatching[i].first - i * delta,
>+              mData + nonMatching[i].first,
>+              sizeof(char_type) * (nonMatching[i].second - nonMatching[i].first));
>+      char_traits::copy(mData + nonMatching[i].first - i * delta - aNewValue.Length(),
>+                        aNewValue.Data(), aNewValue.Length());
Sticking to char_traits::copy would be slightly more readable and consistent.
(The second copy actually precedes the first copy in memory; I think the processor's cache might prefer you to write to the destination in strictly ascending order.)

>+    if (numNonMatching > 1) {
If the substring was not actually found in the original string, wouldn't it be better to return much earlier than this?

Comment 33

[(no longer active)]

(In reply to :Ehsan Akhgari (not reading bugmail, needinfo? me!) from comment #31)
> And backed out since ASAN discovered a buffer overflow. :(

OK, the problem was that in the shrinking case we could allocate a smaller buffer, which means losing access to part of the source data.  So instead of allocating a mLength sized buffer I need to allocate an XPCOM_MAX(mLength, newLength) sized buffer.

(In reply to [e-mail] from comment #32)
> Comment on attachment 8535388 [details] [diff] [review]
> Make the ReplaceSubstring() XPCOM string API linear; r=froydnj
> 
> >+      // Add an auxilary entry at the end of the list to help as an edge case
> >+      // for the algorithms below.
> Would including the null terminator as part of the string data save you an
> edge case?

No, the edge case is handling the last (in case of shrinking and first in case of growing) segment being empty.  We still need to run the last iteration of the for loop in order to copy the replacement bytes into place.

> >+  if (!MutatePrep(newLength, &oldData, &oldFlags))
> >+    return;
> >+  if (oldData) {
> >+    // Copy all of the old data to the new buffer.
> (I'm sure there's a way to avoid copying all the old data to the wrong place
> and then fixing it up afterwards, but I can't quite think of it offhand.)

Yes.  But I think having only two code paths helps the readability of this code.

> >+      memmove(mData + nonMatching[i].first - i * delta,
> >+              mData + nonMatching[i].first,
> >+              sizeof(char_type) * (nonMatching[i].second - nonMatching[i].first));
> >+      char_traits::copy(mData + nonMatching[i].first - i * delta - aNewValue.Length(),
> >+                        aNewValue.Data(), aNewValue.Length());
> Sticking to char_traits::copy would be slightly more readable and consistent.

That is not an option since char_traits::copy uses memcpy and on the first copy the ranges are overlapping in memory, so you really do need memmove!

> (The second copy actually precedes the first copy in memory; I think the
> processor's cache might prefer you to write to the destination in strictly
> ascending order.)

Good point.  Fixed.

> >+    if (numNonMatching > 1) {
> If the substring was not actually found in the original string, wouldn't it
> be better to return much earlier than this?

Nathan already suggested this, but I forgot to remove this now stale branch.

https://hg.mozilla.org/integration/mozilla-inbound/rev/95377313608b

Comment 34

[[e-mail]]

(In reply to Ehsan Akhgari from comment #33)
> (In reply to comment #32)
> No, the edge case is handling the last (in case of shrinking and first in
> case of growing) segment being empty.
Meaning you deliberately trigger the code that handles that case?

> That is not an option since char_traits::copy uses memcpy and on the first
> copy the ranges are overlapping in memory, so you really do need memmove!
I've just discovered char_traits::move

Comment 35

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

Backed out in https://hg.mozilla.org/integration/mozilla-inbound/rev/afd27046e00c for linux build bustage:

https://treeherder.mozilla.org/ui/logviewer.html#?job_id=4611334&repo=mozilla-inbound

Comment 36

[(no longer active)]

(In reply to [e-mail] from comment #34)
> (In reply to Ehsan Akhgari from comment #33)
> > (In reply to comment #32)
> > No, the edge case is handling the last (in case of shrinking and first in
> > case of growing) segment being empty.
> Meaning you deliberately trigger the code that handles that case?

Yes, that's how I don't need to special case the other end!

> > That is not an option since char_traits::copy uses memcpy and on the first
> > copy the ranges are overlapping in memory, so you really do need memmove!
> I've just discovered char_traits::move

Awesome!  This makes the code less ugly.

This was innocent, will reland.

Comment 37

[[e-mail]]

Attachment: For posterity this is what my version looks like

As well as avoiding the extra copy when a new buffer is created, I save the lengths of the gaps instead of their positions and use them to advance along the string as I make the replacements. (I used short variable names to save typing.)

Comment 38

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/b5478506f7c6

Comment 39

[(no longer active)]

(In reply to [e-mail] from comment #37)
> Created attachment 8536004 [details] [diff] [review]
> For posterity this is what my version looks like
> 
> As well as avoiding the extra copy when a new buffer is created, I save the
> lengths of the gaps instead of their positions and use them to advance along
> the string as I make the replacements. (I used short variable names to save
> typing.)

This looks good based on a quick look.  Please put it up on a bug for review!