Closed Bug 682592 Opened 13 years ago Closed 13 years ago

do bidi scan when nsTextFragment content is changed

Categories

(Core :: DOM: Core & HTML, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla9

People

(Reporter: arno, Assigned: arno)

References

Details

Attachments

(2 files, 2 obsolete files)

Hi,
This bug comes from bug 582858, comment 34.
Actually, it should be possible to scan a string for bidi while it's copied to m2b. This scan could be started at the point where 8bit scan ended.
nsTextFragment SetTo and Append methods would take an optional argument. So callers could to specify if that scan should be done, instead of calling UpdateBidiStatus afterwards.
Summary: do → do bidi scan while copying string to m2b in nsTextFragment
Attached file testcase
testcase:
file I use to test createTextNode speed.
First test calls createTextNode with a long (10000000 chars) string containing with non-8bit character at start of the string.
Second test is the same except non-8bit character are at the middle of the string.
Third test is the same except non-8bit character are at the end of the string.

Fourth test createTextNode 100000 times with a 20 character string, with non-8bit character at start of the string.
Fifth test is the same except non-8bit character are at the middle of the string
And Sixth test is the same except non-8bit character are at the end of the string
Attached patch patch proposal (obsolete) — Splinter Review
Here is a patch proposal. I'm unsure if it's correct yet, or it needs more work.

It does what sicking proposed: execute bidi scan from the point where 8bit scan stopped. Also, this scan is performed inside the SetTo and Append methods. They take an optional parameter (default to false) to define if that scan must occur.

Before anything else, I have a question:
I did not understood Is8Bit neither Is8BitUnvectorized. Then I based my patch on the assumption that those functions stop processing the string at the exact offset where a non-8bit character is found. Is this the case, or could that be different ?

Assuming this is the case:

Here are the results I obtain on testcase without this patch (average on 10tries):

140ms, 143ms, 152ms, 184ms, 184ms, 190ms

and here are the results with this patch:
143ms, 117ms, 96ms, 173ms, 166ms, 163ms
So we can see, unsurprisingly, that performances improve a lot for a long string with a lot of 8bits characters at start, and some non-8bit characters near the end.
But they also improve for the generic case.

Performance seem to decrease slightly for the first case. So, I made more than 10 tries, and it seems that, on average, performances decrease by a few percents for this test. I also noticed that, if executing the call to UpdateBidiFlag before nsMemory::Clone, performances seemed to slightly improve by a few percent. Could that be caused by some platform specific optimization ? otherwise, may be it is statistically insignificant.

Also, I tried to execute the scan at the same at as the copy to m2b (take each character, check if it's a bidi, then append it to m2b). I noticed this was slightly slower. I suppose this is because memcpy is well optimized.
Summary: do bidi scan while copying string to m2b in nsTextFragment → do bidi scan when nsTextFragment content is changed
So, Is8Bit/Is8BitUnvectorized stop when they find the first non-8bit character in the string.  With that in mind, is this patch correct?  Wouldn't we potentially miss the bidi characters after them?
Comment on attachment 556402 [details] [diff] [review]
patch proposal

Arno, you might want to ask for a feedback.
Attachment #556402 - Attachment is patch: true
Attachment #556402 - Flags: feedback?(justin.lebar+bug)
Comment on attachment 556402 [details] [diff] [review]
patch proposal

> I based my patch on the assumption that those functions stop processing the
> string at the exact offset where a non-8bit character is found. Is this the
> case, or could that be different ?

This is not the case for the vectorized version of Is8Bit.  The vectorized
version checks multiple characters at once.

>   // Check one XMM register (16 bytes) at a time.
>   const PRInt32 vectWalkEnd = ((len - i) / numUnicharsPerVector) * numUnicharsPerVector;
>   __m128i vectmask = _mm_set1_epi16(0xff00);
>   for(; i < vectWalkEnd; i += numUnicharsPerVector) {
>     const __m128i vect = *reinterpret_cast<const __m128i*>(str + i);
>     if (!is_zero(_mm_and_si128(vect, vectmask)))
>-      return PR_FALSE;
>+      return i;
>   }
> 
>   // Check one word at a time.
>   const PRInt32 wordWalkEnd = ((len - i) / numUnicharsPerWord) * numUnicharsPerWord;
>   for(; i < wordWalkEnd; i += numUnicharsPerWord) {
>     const size_t word = *reinterpret_cast<const size_t*>(str + i);
>     if (word & mask)
>-      return PR_FALSE;
>+      return i;
>   }

Notice in these loops that we do i += numUnicharsPerVector (8) and i +=
numUnicharsPerWord (2 or 4).  So as your patch written, if you have a string
where there's a non-ASCII character immediately followed by a bidi character,
we might miss the bidi char.

I know the SSE code (the first loop) is kind of messy, but you should be able
to understand the second loop.  Say we're on a 64-bit system, so
numUnicharsPerWord is 4.  Then we read 4 unichars into |word|, and then do

  word & 0xff00ff00ff00ff00

The mask 0xff00... keeps the bits from the high-order byte of each character.
So the result of masking word is zero only if all the chars are ASCII.

The SSE version does the exact same thing, just 16 bytes at a time.

It seems to me that it's acceptable if instead of returning the index of the
first 8-bit character, the method returns something a little before that.
You'll have to scan just a few more chars for bidi-ness, but no big deal,
right?  So maybe you can return |i - numUnicharsPerVector| and |i -
numUnicharsPerWord|, respectively (and add a check so they don't go negative).

Would that work?
Attachment #556402 - Flags: feedback?(justin.lebar+bug) → feedback-
Thanks for your explanation of Is8bit.

(In reply to Justin Lebar [:jlebar] from comment #5)
> 
> It seems to me that it's acceptable if instead of returning the index of the
> first 8-bit character, the method returns something a little before that.
> You'll have to scan just a few more chars for bidi-ness, but no big deal,
> right?  So maybe you can return |i - numUnicharsPerVector| and |i -
> numUnicharsPerWord|, respectively (and add a check so they don't go
> negative).

If I understand correctly, that what the patch is actually doing (mainly by chance)

  for(; i < wordWalkEnd; i += numUnicharsPerWord) {
    const size_t word = *reinterpret_cast<const size_t*>(str + i);
    if (word & mask)
      return i;
  }

If i is, say, 64, and numUnicharsPerWord is 4,
characters 64,65,66 and 67 will be loaded into word. Then, if one of them is > 255, 64 will be returned.
I think the same reasoning applies to first loop.
Attached patch patch proposal (obsolete) — Splinter Review
It's the same patch, with a comment to explain what FirstNon8Bit returns, and with tests.
Assignee: nobody → arno
Attachment #556402 - Attachment is obsolete: true
Attachment #557773 - Flags: review?(jonas)
try server log for this patch:
https://tbpl.mozilla.org/?tree=Try&usebuildbot=1&rev=13abbd596d4d
Comment on attachment 557773 [details] [diff] [review]
patch proposal

I won't have time to look at this, Justin, could you do the honors?
Attachment #557773 - Flags: review?(jonas) → review?(justin.lebar+bug)
> If I understand correctly, that what the patch is actually doing (mainly by chance)

Ah, I think you're right!  I'll have a closer look at this in the morning.
Comment on attachment 557773 [details] [diff] [review]
patch proposal

This patch looks good to me.  I'd like you to add a few more comments, mainly because this code is so old and poorly-documented.

>   if (aOffset == 0 && endOffset == textLength) {
>     // Replacing whole text or old text was empty
>-    mText.SetTo(aBuffer, aLength);
>+    mText.SetTo(aBuffer, aLength, !document || !document->GetBidiEnabled());
>   }

It would be good to comment somewhere why you don't scan for bidi if the
document already has bidi enabled.

>+  if (document && mText.IsBidi()) {
>+    document->SetBidiEnabled();
>+  }

Please add a comment to the effect of "If we found bidi characters in
mText.SetTo() above, indicate that the document contains bidi characters."

>+/*
>+ * XXX: This function returns -1 if all characters in str are 8 bit characters.
>+ * Otherwise, it returns a position of first non-8bit character or lesser. For
>+ * example, if first non-8bit character is at position 25, it may return 25, or
>+ * for example 24, or 16. But it guarantees there is no non-8bit character
>+ * before returned value.
>+ */
>+static inline PRInt32
>+FirstNon8Bit(const PRUnichar *str, const PRUnichar *end)

Nice comment!  But please don't start with "XXX", which we use for reminders
that code needs to be fixed.  Also, the second sentence is a bit awkward.  How
about "Otherwise, it returns a value less than or equal to the index of the
first non-8bit character in str."?

>-  if (need2) {
>+  if (first16bit != -1) {
>     // Use ucs2 storage because we have to

Please add a comment here indicating what first16bit != -1 indicates.

>diff -r ca5a3569462d content/base/src/nsTextFragment.h
>--- a/content/base/src/nsTextFragment.h	Sun Aug 28 21:20:46 2011 +0100
>+++ b/content/base/src/nsTextFragment.h	Thu Sep 01 18:00:52 2011 +0200
>   /**
>    * Return PR_TRUE if this fragment contains Bidi text
>-   * For performance reasons this flag is not set automatically, but
>-   * requires an explicit call to UpdateBidiFlag()
>+   * For performance reasons this flag is only set if explicitely required (see
>+   * SetTo and Append aUpdateBidi argument)
>    */
>   PRBool IsBidi() const
>   {
>     return mState.mIsBidi;
>   }

s/required/requested, and to make it clear that aUpdateBidi is an argument on both SetTo and Append, maybe make the parenthetical "by setting the aUpdateBidi argument on SetTo or Append to true".  Also, please end the sentence with a period.

>-  void SetTo(const PRUnichar* aBuffer, PRInt32 aLength);
>+  void SetTo(const PRUnichar* aBuffer, PRInt32 aLength, PRBool aUpdateBidi = PR_FALSE);

Is this default param used anywhere?

>-  void Append(const PRUnichar* aBuffer, PRUint32 aLength);
>+  void Append(const PRUnichar* aBuffer, PRUint32 aLength, PRBool aUpdateBidi = PR_FALSE);

Similarly for this default param.  If they're not used anywhere (I can't find
somewhere that they are), let's just not provide a default.

>+   We want to check that bidi is detected correctly. So, we have a reference
>+   document where ltr is set explicitely with <bdo> element. Then, we compare
>+   it with test document.
>+
>+   In mozilla, once bidi has been detected in a document, document always
>+   consider it's in bidi mode. So, if one fragment enables bidi correctly, and
>+   we create or update a fragment in the same document, that operation may not
>+   enable bidi by itself, but it will not be detected. So, we need to have new
>+   document for each test.
>+
>+   So, instead of many diferent reftests, this mochitest implements a
>+   reftest-like. It creates reference text fragments in reference iframe, test
>+   text fragments in test iframe, and compare the documents. Then, it reloads
>+   test iframe. Reference iframe does not need to be reloaded between tests.
>+   It's ok (and may be, desired) to keep bidi always enabled in that document. 
>+*/

Thanks for this comment.  I would have had no idea what was going on,
otherwise.  :)  s/may be/maybe.

>+
>+SimpleTest.waitForExplicitFinish();
>+var refFrame = document.getElementById("iframe-ref")
>+var testFrame = document.getElementById("iframe-test");
>+
>+refFrame.addEventListener("load", function() {
>+  testFrame.addEventListener("load", function() {
>+    try {
>+      tests.next();
>+      ok(compareSnapshots(snapshotWindow(testFrame.contentWindow), 
>+                        snapshotWindow(refFrame.contentWindow), true)[0], 

Please fix indentation.

r=me with those changes!
Attachment #557773 - Flags: review?(justin.lebar+bug) → review+
Attached patch updated patchSplinter Review
patch addressing all review comments.
Attachment #557773 - Attachment is obsolete: true
Keywords: checkin-needed
Aw, oops.  I didn't notice that the checkin comment didn't include "r=jlebar".  But it still has the bug number, so we're ok.

Thanks for the patch!
(In reply to Justin Lebar [:jlebar] from comment #13)
> inbound: http://hg.mozilla.org/integration/mozilla-inbound/rev/61c6b2646ccd

now on m-c
Status: NEW → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
Whiteboard: [inbound]
Target Milestone: --- → mozilla9
Depends on: 703773
Depends on: 918215
You need to log in before you can comment on or make changes to this bug.