Closed Bug 412047 Opened 12 years ago Closed 12 years ago

jsregexp.c upcase() is slow

Categories

(Core :: JavaScript Engine, defect, P2)

x86
macOS
defect

Tracking

()

RESOLVED FIXED

People

(Reporter: sayrer, Assigned: igor)

References

Details

Attachments

(2 files, 2 obsolete files)

On the SunSpider regexp-dna test, 55-65% of time is spent inside SimpleMatch, and 27-30% of SimpleMatch's time is spent in upcase().
Attached image shark screenshot
Flags: blocking1.9?
Version: unspecified → Trunk
The exclamation point is Shark chiding the generated assembly. In this case,

"This instruction has a length-changing prefix which overrides the default operand size setting. This causes a slow decode stall on the target CPU. Using 16-bit (short) immediates or variables is the most common reason for this codegen. Try replacing those values with 32-bit (int) values."
Version: Trunk → unspecified
One thing that might help here (separately from improving the speed of our toupper/tolower routines) might be to keep an extra upper-cased copy of the expression-string, so that it doesn't have to be upcased ever.  The copy would only need to exist for regexp with the "FOLD" flag (/i) for case-insensitive matching.
(In reply to comment #0)
> and 27-30% of SimpleMatch's time is spent in upcase().

Given the complexity of JS_TOUPPER macro it should be worth to try to avoid going through Unicode tables when u <= 127:

static jschar
upcase(jschar ch)
{
    jschar cu = JS_TOUPPER(ch);
    if (ch >= 128 && cu < 128)
        return ch;
    return cu;
}

#define JS_TOUPPER(c)   ((jschar) ((JS_CCODE(c) & 0x00100000)                 \
                                   ? (c) - ((int32)JS_CCODE(c) >> 22)         \
                                   : (c)))

#define JS_CCODE(c)     (js_A[js_Y[(js_X[(uint16)(c)>>6]<<6)|((c)&0x3F)]])
Attached patch v1 (obsolete) — Splinter Review
The patch adds explicit optimization for ASCII cases and changes upcase/downcase to use uintN as argument/return type.

Note that downcase currently contains:

    jschar cl = JS_TOLOWER(ch);
    if (cl >= 128 && ch < 128)
         return ch;
    return cl;

But that check  if (cl >= 128 && ch < 128) is never true since upcasing of ASCII letters in Unicode always stays below 128. So downcase is equivalent to:
  
    return JS_TOLOWER(ch);
Assignee: general → igor
Status: NEW → ASSIGNED
Attachment #296694 - Flags: review?(crowder)
Comment on attachment 296694 [details] [diff] [review]
v1

Looks good, though it does seem a lot of the casts might be unnecessary:

if (ch < (uintN)128)

for example could just be

if (ch < 128) or if you -are- getting a warning

if (ch < 128U) ?

I don't have a 64-bit platform to try this out on, though.

How do you feel about keeping an upcased copy of either the regexp string or the input string, or both, to avoid upcasing entirely, for case-insensitve expressions?
Attachment #296694 - Flags: review?(crowder) → review+
(In reply to comment #6)
> How do you feel about keeping an upcased copy of either the regexp string or
> the input string, or both, to avoid upcasing entirely, for case-insensitve
> expressions?

My interpreting of the attachment 296663 [details] from comment 1 is that just optimizing the function itself may bring its contribution from 30% to, say, 5-7%. As such a cached upcased copy may not bring much benefits given the extra complexity of code.
Attached patch v2 (obsolete) — Splinter Review
The new version uses just 128, not (uintN) 128 in the patch.
Attachment #296694 - Attachment is obsolete: true
Attachment #296942 - Flags: review?(crowder)
Attached patch v2 (CVS diff)Splinter Review
The previous patch was not a cvs diff.
Attachment #296942 - Attachment is obsolete: true
Attachment #296943 - Flags: review?(crowder)
Attachment #296942 - Flags: review?(crowder)
Comment on attachment 296943 [details] [diff] [review]
v2 (CVS diff)

Looks great, I still think more casts could be shaved off, but again I don't have a good way to test.
Attachment #296943 - Flags: review?(crowder) → review+
Comment on attachment 296943 [details] [diff] [review]
v2 (CVS diff)

This should speedup regexp benchmarks for the price of little code bloat.
Attachment #296943 - Flags: approval1.9?
Attachment #296943 - Flags: approval1.9? → approval1.9+
Flags: blocking1.9? → blocking1.9+
Priority: -- → P2
I checked in the patch from comment 9 to the trunk:

http://bonsai.mozilla.org/cvsquery.cgi?module=PhoenixTinderbox&branch=HEAD&cvsroot=%2Fcvsroot&date=explicit&mindate=1200472057&maxdate=1200472275&who=igor%mir2.org
Status: ASSIGNED → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
It is interesting that the patch shrinked the size of compiled binaries on fx-linux-tbox despite new source lines being added.
                                         FROM                TO
 regexp-dna:          1.23x as fast      468.9ms +/- 3.0%    380.5ms +/- 0.4%
Flags: in-testsuite-
Flags: in-litmus-
Two questions:-

Q. 1:-
Will compiler optimize JS_MAX in  js/src/jsregexp.c at

   1057  if (state->flags & JSREG_FOLD) {
   1058      c = (jschar) JS_MAX(upcase(localMax), downcase(localMax));
   1059      if (c > localMax)
   1060          localMax = c;
   1061  }

to make as

   if (state->flags & JSREG_FOLD) {
       uintN upcase_localMax = upcase(localMax);
       uintN downcase_localMax = downcase(localMax);

       c = (jschar) JS_MAX(upcase_localMax, downcase_localMax);
       if (c > localMax) localMax = c;
   }

otherwise we are calling upcase, downcase two times in JS_MAX macro
which intern call JS_TOUPPER(ch) and JS_TOLOWER(ch) two times,
which will be too expensive for localMax > 128



Q. 2:-

whether upcase can handle characters [\]^_`{|}~
or is it not in path logic when doing

js> [/`/i.test('@'), /@/i.test('`')];




Biju:  I think that's a good point; the compiler cannot optimize additional function calls away without potentially changing the semantics of a program with functional side-effects, so it must not be optimizing in that way here.  I think your rewording is better.  New bug/patch?  If you don't get to it, I will do tomorrow.
To your second question, I'm confident upcase does the right thing for those characters.
(In reply to comment #17)
> To your second question, I'm confident upcase does the right thing for those
> characters.

OK, now I understood why it is working, because its uint 

    if (ch < 128) {
        if (ch - (uintN) 'a' <= (uintN) ('z' - 'a'))
            ch -= (uintN) ('a' - 'A');
         return ch;
    }

so in future if somebody change uint => int it will screw up
also logic looks complicated

I feel following is more readable
and also 1 mathematical operation faster if ch < 'a' 


    if (ch > 127) {
       // next statement using JS_TOUPPER
    } else if(ch < 'a' || ch > 'z'){  
       return ch;
    } else {  
       ch -= (uintN) ('a' - 'A');
       return ch;
    } 

(In reply to comment #16)
> New bug/patch?  If you don't get to it, I will do tomorrow.

I am really sorry I dont have a dev env 
(In reply to comment #18)
> (In reply to comment #17)
> so in future if somebody change uint => int it will screw up

Sorry, that's not a reason to bloat and slow down the code, even a little bit. It can be addressed by a comment, although anyone who would mindlessly change uint to int should not have commit access here. C is not Java; unsigned integer types have their uses.

> also logic looks complicated

A comment can address this, but really, once you learn the idiom, it looks like something you know. SpiderMonkey C code is not tuned for everyone's readability.

> I feel following is more readable
> and also 1 mathematical operation faster if ch < 'a' 

That's not a common case, and the subtract-immediate is one cycle on modern architectures. The branch-test is the thing to avoid duplicating, but in the case where c is outside a-z you impose two not-taken branches (short target displacements, so probably only a minor branch penalty -- the targets should be in the pipeline).

Separately, you've written an else after return non-sequitur. Don't do that.

/be
(In reply to comment #16)
> Biju:  I think that's a good point; the compiler cannot optimize additional
> function calls away without potentially changing the semantics of a program
> with functional side-effects, so it must not be optimizing in that way here.  I
> think your rewording is better.  New bug/patch?  If you don't get to it, I will
> do tomorrow.

Brian~
Just a follow up, did you got chance to fix this.
TIA

(In reply to comment #20)
> Just a follow up, did you got chance to fix this.

Please file a separated bug about JS_MAX(upcase(), downcase()).
(In reply to comment #21)
> Please file a separated bug about JS_MAX(upcase(), downcase()).

created Bug 416615
Depends on: 416615
You need to log in before you can comment on or make changes to this bug.