585978 - Add SSE implementation of is-ascii check in nsTextFragment

Status: RESOLVED FIXED

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

Description

[Justin Lebar (not reading bugmail)]

Attachment: Patch v1

Split off from bug 582858.

Vectorize the following loop in nsTextFragment.cpp:

PRBool need2 = PR_FALSE;
while (ucp < uend) {
  PRUnichar ch = *ucp++;
  if (ch >= 256) {
    need2 = PR_TRUE;
    break;
  }
}

Comment 1

[Justin Lebar (not reading bugmail)]

Benchmark results for the attached patch, testcase v1.1, and based atop b7836c3a63db:

Trunk: 220ms (first run), 155ms (later runs)
Patched: 180ms (first run), 122ms (later runs)

This is surprisingly only 30% faster, but the assembly it's generating looks OK
to me.

Comment 2

[Justin Lebar (not reading bugmail)]

Attachment: Benchmark v1.1

Comment 3

[Justin Lebar (not reading bugmail)]

We should also probably vectorize LossyConvertEncoding<PRUnichar, char> (in nsUTF8Utils.h).  There's a comment in nsTextFragment that says it's "likely to be carefully tuned", but in fact it seems pretty naive.

Comment 4

[Justin Lebar (not reading bugmail)]

Attachment: Patch v1.1

There are apparently two copies of this loop in the code.  This one replaces them both.

Comment 5

[Justin Lebar (not reading bugmail)]

Attachment: Patch v1.2

Build changes: Now based on patch v2 in bug 585818 (and patch v1 in bug 585708).  Sorry for the churn.

Comment 6

[Justin Lebar (not reading bugmail)]

Attachment: Patch v1.3

One more time...

Comment 7

[Justin Lebar (not reading bugmail)]

Wow, this is actually very much not right.  Fix soon.

Comment 8

[Justin Lebar (not reading bugmail)]

Attachment: Patch v1.4

This one should be much more right.

Comment 9

[Justin Lebar (not reading bugmail)]

Comment on attachment 465398 [details] [diff] [review]
Patch v1.4

Vlad says he doesn't think he's the right person to review here; untagging him.

Comment 10

[Benoit Jacob [:bjacob] (mostly away)]

I have no experience with the integer part of SSE, so I am very hesitant to call myself reviewer. I can just comment on this for now:

+static inline int
+is_zero (__m128i x)
+{
+  return
+    _mm_movemask_epi8(_mm_cmpeq_epi8 (x, _mm_setzero_si128 ())) == 0xffff;
+}

This function should return a bool, it seems :-)

Comment 11

[Justin Lebar (not reading bugmail)]

Attachment: Patch v1.5

Updating Makefile logic so it works properly on Linux 32.

Comment 12

[Justin Lebar (not reading bugmail)]

Attachment: Patch v1.6

(In reply to comment 10)
> This function should return a bool, it seems :-)

Fixed, thanks.

Comment 13

[Justin Lebar (not reading bugmail)]

Attachment: Patch v1.7 (rebased v1.6 to tip)

Comment 14

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Hi Justin, I'm pretty swamped with fennec b1 work and won't be able to do this review until probably the end of next week; it's going to need a very careful read.  If you need the review sooner than that, please request from someone else.  Sorry!

Comment 15

[Justin Lebar (not reading bugmail)]

That's all right -- I'm still waiting on a review on bug 585708 anyway.  :)

Comment 16

[Timothy B. Terriberry (:derf)]

Comment on attachment 469542 [details] [diff] [review]
Patch v1.7 (rebased v1.6 to tip)

> +ifneq (,$(filter x86 x86_64,$(CPU_ARCH)))

This test is yet again different from the one in bug 586698. Is there a reason why?

>  #include "nsTraceRefcnt.h"
> +
>  class nsString;

Whitespace-only change. Arguably a good one, but since it's the only modification in this file, perhaps inadvertent.

> +  while (str < end && (NS_PTR_TO_UINT32(str) & alignMask)) {
> ...
> +  while (end > str && (NS_PTR_TO_UINT32(str) & 0xf)) {

Same comment as in bug 586698 about pre-computing these lengths to avoid the per-character double-test.

> +    __m128i in = _mm_load_si128((__m128i *) str);

This uses a C-style cast, but everywhere else you convert pointers you use a reinterpret_cast<>. These should be consistent (especially since you're discarding the const qualifier, for no real reason that I can see).

Comment 17

[Justin Lebar (not reading bugmail)]

(In reply to comment #16)
> Comment on attachment 469542 [details] [diff] [review]
> Patch v1.7 (rebased v1.6 to tip)
> 
> > +ifneq (,$(filter x86 x86_64,$(CPU_ARCH)))
> 
> This test is yet again different from the one in bug 586698. Is there a reason
> why?

It should test on INTEL_ARCHITECTURE; I just hadn't modified the patch to reflect bug 585818.

> >  #include "nsTraceRefcnt.h"
> > +
> >  class nsString;
> 
> Whitespace-only change. Arguably a good one, but since it's the only
> modification in this file, perhaps inadvertent.

Indeed it's inadvertent.  Thanks.

Comment 18

[Justin Lebar (not reading bugmail)]

Attachment: Patch v2

After rewriting all the code to use array offsets (and incorporating Tim's suggestion about precomputing the loop bounds), the unvectorized code runs the benchmark in this bug just as fast as the vectorized code!

I suspect this might not be the case on a 32-bit machine, where in the unvectorized case, we have to do twice as many operations as I get to do on my 64-bit machine.

I also added a simple testcase.

Comment 19

[Justin Lebar (not reading bugmail)]

Attachment: Patch v2.1

Forgot a whitespace fix.

Comment 20

[Timothy B. Terriberry (:derf)]

Comment on attachment 492893 [details] [diff] [review]
Patch v2.1

r+=me

Comment 21

[Justin Lebar (not reading bugmail)]

Comment on attachment 492893 [details] [diff] [review]
Patch v2.1

I think this needs a review from someone in content, too.  jst?

Comment 22

[Justin Lebar (not reading bugmail)]

Comment on attachment 492893 [details] [diff] [review]
Patch v2.1

Requesting a2.0.

This plus bug 586698 yields a significant perf improvement when creating text nodes.  It's a self-contained change which shouldn't have strange interactions with other code, although of course it's string processing, so mistakes would be fatal.

Comment 23

[Daniel C]

What's the status here? It doesn't look like this landed and the approval is nearly 4 weeks old.

Comment 24

[Justin Lebar (not reading bugmail)]

It's blocked on bug 585708, which depends on bug 619178 and needs to land together with bug 616778 and bug 616782.  The latter three bugs still need review, and two of them are blockers.

Comment 25

[Justin Lebar (not reading bugmail)]

Although this is now (finally) unblocked, I think it's too late to check this
in for 4.0, so I'm clearing the a2.0 flag.  Feel free to renom if you disagree!

Comment 26

[(no longer active)]

I tried to land this on cedar, but the patch doesn't apply cleanly any more.  Please submit a new version of the patch, or land it on cedar yourself.

Comment 27

[Justin Lebar (not reading bugmail)]

What's the timeline for landing on cedar?

Comment 28

[(no longer active)]

(In reply to comment #27)
> What's the timeline for landing on cedar?

Land when it's ready.  :)

Comment 29

[Justin Lebar (not reading bugmail)]

Fixed in Cedar: http://hg.mozilla.org/projects/cedar/rev/712063da5959

Comment 30

[(no longer active)]

http://hg.mozilla.org/mozilla-central/rev/712063da5959