513379 - JS_ISSPACE should check for space character at least

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Robert Sayre]

we do expensive table lookups every time

Comment 1

[Andreas Gal :gal]

Attachment: patch

Comment 2

[Robert Sayre]

Comment on attachment 397383 [details] [diff] [review]
patch

actually, we can do better

Comment 3

[Robert Sayre]

this comparison from WebKit catches more control characters and it should rule out most non-space in the first check:

http://svn.webkit.org/repository/webkit/trunk/JavaScriptCore/wtf/ASCIICType.h

 return c <= ' ' && (c == ' ' || (c <= 0xD && c >= 0x9));

Comment 4

[Brendan Eich [:brendan]]

(In reply to comment #3)
> this comparison from WebKit catches more control characters and it should rule
> out most non-space in the first check:
> 
> http://svn.webkit.org/repository/webkit/trunk/JavaScriptCore/wtf/ASCIICType.h
> 
>  return c <= ' ' && (c == ' ' || (c <= 0xD && c >= 0x9));

Please use number line order for that range test: (9 <= c && c <= 0xD).

/be

Comment 5

[Brendan Eich [:brendan]]

(In reply to comment #4)
> Please use number line order for that range test: (9 <= c && c <= 0xD).

It would be good to confirm the optimizer does the right thing (gcc mac at least) too (I'd appreciate it).

/be

Comment 6

[Andreas Gal :gal]

Confirmed to resolve the hot spot in shark. Lets leave bit fiddling to gcc. All I care for is that its fast =)

Comment 7

[Andreas Gal :gal]

Attachment: patch

Comment 8

[Robert Sayre]

Comment on attachment 397435 [details] [diff] [review]
patch

r=me with bracket-on-new-line formatting fixed and explanation of why it's hard to otool the assembly here.

Comment 9

[Andreas Gal :gal]

http://hg.mozilla.org/tracemonkey/rev/972e53ee1a5f

Comment 10

[Andreas Gal :gal]

00000da6        cmpl    $0x000000ff,%edx
00000dac        jal     0x00000e80
00000db2        cmpl    $0x20,%edx
00000db5        jbel    0x00000f00
00000f00        sete    %al
00000f03        subl    $0x09,%edx
00000f06        cmpl    $0x04,%edx
00000f09        setbe   %dl

And this ladies and gentlemen is the definitive proof that we should stop strength reducing comparisons by hand and leave that to gcc.

Comment 11

[Mike Shaver (:shaver emeritus)]

Comment on attachment 397435 [details] [diff] [review]
patch

>+static inline bool
>+JS_ISSPACE(jschar c) {
>+    uint32 w = uint32(c);
>+    if (w < 256) {
>+        return w <= ' ' && (w == ' ' || (9 <= w && w <= 0xD));
>+    } else {
>+        return (JS_CCODE(w) & 0x00070000) == 0x00040000;
>+    }
>+}

else-after-return, and extra bracing to boot.

static inline bool
JS_ISSPACE(jschar c)
{
    uint32 w = uint32(c);
    if (w < 256)
        return w <= ' ' && (w == ' ' || (9 <= w && w <= 0xD));
    return (JS_CCODE(w) & 0x00070000) == 0x00040000;
}

Comment 12

[Robert Sayre]

> 
> else-after-return, and extra bracing to boot.

I believe nit follow-ups have left this fixed in the repo

Comment 13

[Brendan Eich [:brendan]]

Comment on attachment 397435 [details] [diff] [review]
patch

>+static inline bool
>+JS_ISSPACE(jschar c) {

Brace on next line.

>+    uint32 w = uint32(c);

No need for cast from narrower unsigned type, and why uint32? That's suboptimal on some 64-bit targets. Just unsigned would be better, but do we need w at all? The compiler can load uint16 c into a register and use the right ALU and branch ops on it, and JS_CCODE doesn't need other than jschar (uint16) for its macro-parameter.

>+    if (w < 256) {
>+        return w <= ' ' && (w == ' ' || (9 <= w && w <= 0xD));
>+    } else {
>+        return (JS_CCODE(w) & 0x00070000) == 0x00040000;

No else after return; also overbraced.

/be

Comment 14

[Brendan Eich [:brendan]]

Sorry for repeated nit nags -- I was reading hgweb not bugmail.

The uint32 cast and w temp still seem bogus.

/be

Comment 15

[Robert Sayre]

(In reply to comment #14)
>
> The uint32 cast and w temp still seem bogus.

iirc this was because Shark complained about comparing 16-bit to 32-bit. bad for core duo perf.

Comment 16

[Andreas Gal :gal]

16-bit comparisons are expensive on core2. This forces gcc to not do that.

Comment 17

[Robert Sayre]

Attachment: shark message

you can actually select text in these shark messages, so here's a screenshot. these are all over js/src, fwiw. most not in hot paths.

Comment 18

[Brendan Eich [:brendan]]

The cast is unnecessary in any event on w's initializer.

Use unsigned for better 64-bit future-proofing. uint32 is unnecessarily precise and it could cost to narrow in-CPU down the road.

/be

Comment 19

[Andreas Gal :gal]

http://hg.mozilla.org/tracemonkey/rev/f49b9ccc0f2a

Comment 20

[Nicholas Nethercote [inactive]]

(In reply to comment #11)
> (From update of attachment 397435 [details] [diff] [review])
> >+static inline bool
> >+JS_ISSPACE(jschar c) {
> >+    uint32 w = uint32(c);
> >+    if (w < 256) {
> >+        return w <= ' ' && (w == ' ' || (9 <= w && w <= 0xD));
> >+    } else {
> >+        return (JS_CCODE(w) & 0x00070000) == 0x00040000;
> >+    }
> >+}
> 
> else-after-return, and extra bracing to boot.
> 
> static inline bool
> JS_ISSPACE(jschar c)
> {
>     uint32 w = uint32(c);
>     if (w < 256)
>         return w <= ' ' && (w == ' ' || (9 <= w && w <= 0xD));
>     return (JS_CCODE(w) & 0x00070000) == 0x00040000;
> }

I find this a really unfortunate style guideline.  While I can appreciate the no-else-after-return in this case:

int f() 
{
  if (errorcase())
    return;
  lots of code here;
  lots of code here;
  lots of code here;
}

In cases like the quoted one above I find the else-after-retur style *much* easier to read, it's much more functional, in the sense of "functional programming".  In fact I'd argue this is optimal:

  return ( w < 256
         ? w <= ' ' && (w == ' ' || (9 <= w && w <= 0xD))
         : (JS_CCODE(w) & 0x00070000) == 0x00040000 
         );

because it's a pure expression.  (It's unfortunate that C's if-then-else expressions have the ugly ?: syntax, but we have to live with that.)  I bet it gives the compiler more leeway to micro-optimize as well.  

(I've been thinking about writing a blog post about this, I think I'll go do that now.)

Comment 21

[Brendan Eich [:brendan]]

Nick: statements suck, no argument. The primal sin of B and C was losing BCPL's expression language nature. If you want to write an expression, or as if using an expression language, then return A ? B : C is the way to go as you say, and it'd work here. But if B and/or C require statements, then the mighty "if" statement is mandatory and the old style rule stands.

/be

Comment 22

[Andreas Gal :gal]

I do see more value in consistency than endless arguments. I am even willing to give up my favorite type* style. I just want some simple rules to follow, and "Brendan's rules" are somewhat consistent and sometimes I even get it right the first time. The rest I get nitted to death and then get it right. Either way. Its just formatting.

Comment 23

[Brendan Eich [:brendan]]

Did this bug's patch regress js/tests/ecma_3/Unicode/uc-002.js?

Please run the testsuite, it's easy.

/be

Comment 24

[Andreas Gal :gal]

Testing

Comment 25

[Andreas Gal :gal]

This patch fixes it. SFX doesn't do this. Are we sure we are right and they are wrong?

     if (w < 256)
-        return w <= ' ' && (w == ' ' || (9 <= w && w <= 0xD));
+        return (w <= ' ' && (w == ' ' || (9 <= w && w <= 0xD))) || (w == 0xA0);
 
     return (JS_CCODE(w) & 0x00070000) == 0x00040000;

Comment 26

[Mike Shaver (:shaver emeritus)]

There is a reference in one of the SS crypto tests to only FF doing something with 0xA0:

http://mxr.mozilla.org/mozilla-central/source/js/src/t/crypto-aes.js#278

Would be good to know if we are indeed doing the right thing here, by ES5's lights.

Comment 27

[Brendan Eich [:brendan]]

You guys can read 7.2 as well as I can :-P. The latest draft is linked from

http://wiki.ecmascript.org/doku.php?id=es3.1:es3.1_proposal_working_draft

7.2 White Space
White space characters are used to improve source text readability and to separate tokens (indivisible lexical units) from each other, but are otherwise insignificant. White space characters may occur between any two tokens, and may occur within a StringLiteral or a RegularExpressionLiteral (where they are considered significant characters forming part of the literal value) or within a Comment, but cannot appear within any other kind of token.

The ECMAScript white space characters are listed in Table 2.

Table 2 — Whitespace Characters Code Unit Value Name Formal Name
\u0009 Tab            <TAB>
\u000B Vertical Tab   <VT>
\u000C Form Feed      <FF>
\u0020 Space          <SP>
\u00A0 No-break space <NBSP>

Please file a new bug on this, blocking this bug, and patch there.

/be

Comment 28

[Jeff Walden [:Waldo]]

(In reply to comment #18)
> Use unsigned for better 64-bit future-proofing. uint32 is unnecessarily precise
> and it could cost to narrow in-CPU down the road.

unsigned is just unsigned int, which has no intrinsic size or specified meaning of the size the compiler assigns it -- why is unsigned more future-proof?  Either size_t or uintptr_t seem to make the most sense to me, on this point.

That said, shouldn't we be basing optimizations on actual demonstrated performance issues, not on what we think compilers might possibly do?  Anything other than uint32_t seems like premature optimization to me.

Comment 29

[Brendan Eich [:brendan]]

(In reply to comment #28)
> (In reply to comment #18)
> > Use unsigned for better 64-bit future-proofing. uint32 is unnecessarily precise
> > and it could cost to narrow in-CPU down the road.
> 
> unsigned is just unsigned int, which has no intrinsic size or specified meaning
> of the size the compiler assigns it -- why is unsigned more future-proof?

Because the compiler generally does best in optimizing the "natural" int types (int and unsigned) for the target architecture, and some 64-bit targets penalize 32-bit unsigned types because of the need to mask off the high 32 bits.

> Either size_t or uintptr_t seem to make the most sense to me, on this point.

No sizeof or pointer-differencing here, so these do not make any sense.

> That said, shouldn't we be basing optimizations on actual demonstrated
> performance issues, not on what we think compilers might possibly do?  Anything
> other than uint32_t seems like premature optimization to me.

You assumed your conclusion. Outrageous! :-P The issue is not hypothetical and it's not only about optimization.

We should not assume uint32_t is best, particularly in this case. C99 lawyers might recommend uint_fast32_t but I contend unsigned is best. What we know:

1. This bug's result, that LCP stalls hurt (thanks to Shark, boo to GCC for not selecting better instructions.

It's true that uint32 is a sufficient workaround per the Intel docs (http://developer.intel.com/products/processor/manuals/index.htm -- see "Intel® 64 and IA-32 Architectures Optimization Reference Manual" Assembly/Compiler Coding Rule 21 at least -- anyone know a GCC hacker who should read this?). But uint32 is not a necessary workaround (see next point).

2. The particular case in point here does not require exactly 32 bits, or 32-bit unsigned modular arithmetic, or any such thing. This fact does not depend on the target micro-architecture.

3. Using int or unsigned has not always proven future-proof (Windows 3.1; AMD64 LLP64 model) but in my long-term experience it has worked better than over-specifying all local variable types.

4. This is not all about optimization, since optimization requires knowing the target microarchitecture. Given (2) above, we should prefer the least ugly and over-specified type, which is unsigned.

See also

http://www.nabble.com/Proposal-about-integer-types-used-in-WebKit-td24650794.html

I do not agree with Darin Adler's original post (always use int instead of int32_t if no library-interfacing requirement dictates the bit-sized type) but he's right for many cases of local variables and formal parameters, which do not need to specify bit size, and which can hurt 64-bit performance by over-specifying.

/be

Comment 30

[Jeff Walden [:Waldo]]

(In reply to comment #29)
> > Either size_t or uintptr_t seem to make the most sense to me, on this point.
> 
> No sizeof or pointer-differencing here, so these do not make any sense.

Agreed enough, but they're the closest standards explicitly specify as the "natural" architecture word size, at least if you assume addresses will always be such.

Are there any compilers that, when compiling, treat local-only uses of the natural types de novo for purposes of instruction selection?  (Actually: there really can't be, else reimplementation of stdint.h, assigning to pointers, etc. would be unreliable.)  Without that the natural types are no better than "arbitrarily use one of these types while making no effort to optimize for local uses", as far as I can tell.


> > That said, shouldn't we be basing optimizations on actual demonstrated
> > performance issues, not on what we think compilers might possibly do?
> > Anything other than uint32_t seems like premature optimization to me.
> 
> You assumed your conclusion. Outrageous! :-P

Did not.  You assumed it would make a difference 64-bit using unsigned versus using uint32_t; I submit that you have not demonstrated that potential performance win.


> 2. The particular case in point here does not require exactly 32 bits, or
> 32-bit unsigned modular arithmetic, or any such thing. This fact does not
> depend on the target micro-architecture.

Quite.  My potential replacement for a uint32_t cast didn't have this requirement.


> 4. This is not all about optimization, since optimization requires knowing the
> target microarchitecture.

An apparently-irrelevant widening cast, motivated only by subpar compilers, using perf measurements on a single microarchitecture, is surely the epitome of micro-optimization, no?

Comment 31

[Brendan Eich [:brendan]]

(In reply to comment #30)
> > You assumed your conclusion. Outrageous! :-P
> 
> Did not.

Apologies, I didn't see where you showed that uint32 is not de-optimizing on IA64 under all type models. I claim it is de-optimizing under IP64 at least.

See "9.2.4 Sign Extension to Full 64-Bits" in "Intel® 64 and IA-32 Architectures Optimization Reference Manual" at

http://developer.intel.com/products/processor/manuals/index.htm

Long ago I worked on a 64-bit architecture where int and long were 64 bits, short was 32 bits, and we added short short for 16 bits (long long was 128 bits).

I don't know why you're arguing so strenuously in favor of uint32 (_t to boot). None of uint32_t, uint_fast32_t, size_t, or uintptr_t is needed for w in the patch here. Rehashing an argument about micro-optimization justifying too narrow a type doesn't help.

/be

Comment 32

[Jason Orendorff [:jorendorff]]

This regressed ecma_3/Unicode/uc-002.js. Character 160 (U+00A0, NO-BREAK SPACE) is no longer considered whitespace.

Spec says it's whitespace. http://bclary.com/2004/11/07/#a-7.2

Comment 33

[Andreas Gal :gal]

Yeah patch in one of the comments. Will fix today.

Comment 34

[Blake Kaplan (:mrbkap) (inactive)]

http://hg.mozilla.org/mozilla-central/rev/972e53ee1a5f -- gal, what happened to comment 33?

Comment 35

[Andreas Gal :gal]

#34: We filed a separate bug and fixed it.

Comment 36

[Bob Clary [:bc] (inactive)]

uc-002 is fixed fwiw.

Comment 37

[Robert Sayre]

http://hg.mozilla.org/releases/mozilla-1.9.2/rev/984a9cef9903