417947 - match_or_replace improvements

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Robert Sayre]

unpack-code spends more than 50% of its time in match_or_replace.

Comment 1

[jag (Peter Annema)]

Per Shark, for match_or_replace:

30.6% ComputeGlobalThis
24.5% js_Interpret (7.4% JS_GC, 7.2% InternNonIntElementId, 3.6% js_GetProperty)
20.9% js_ExecuteRegExp (10.4% MatchRegExp, 7.9% JS Arena maintenance)
 5.3% js_NewStringCopyN
 4.0% JS_realloc
 3.0% __memcpy

Comment 2

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

How old's that tree?  Surprised to see CGT that high.

Comment 3

[Robert Sayre]

Yes, that should be tried again today.

Comment 4

[jag (Peter Annema)]

That was with a build from after the recent CGT changes. I was equally surprised.

Comment 5

[jag (Peter Annema)]

So jQuery uses the packer from http://dean.edwards.name/packer/ and it looks like the others do too. For the simple |var foo = 1;| with Base62 encoding the following is generated (prettified by me):

eval(
  function(p,a,c,k,e,r) {
    e = String;
    if (!''.replace(/^/, String)) {
      while (c--)
        r[c] = k[c] || c;
      k = [function(e) { return r[e] }];
      e = function() {
        return '\\w+';
      }
      c = 1;
    }

    while (c--) {
      if (k[c])
        p = p.replace(new RegExp('\\b' + e(c) + '\\b', 'g'), k[c]);
    }
    return p;
  }
  ('0 2=1;', 3, 3, 'var||foo'.split('|'), 0, {})
);


So it has an array of words, and each word in the original code is replaced by a number or letter (0-9a-zA-Z). It then either uses a look-up function as the argument to replace() (needing only one call), or it iterates over the array of words manually and calls replace for each (index,word) pair.

Note that for more than 10 words the generated script uses (instead of |e = String|):

e = function(c) {
  return c.toString(a);
}

to convert from base 10 to base 62 (well, base N, really, with N passed in as the |a| argument).

Comment 6

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

Indeed, we're hitting CGT from the do_push_rval case with op == JSOP_CALLNAME.  (Tree from this morning plus PCT-fix and arrays.)

Digging some more.

Comment 7

[Robert Sayre]

<shaver>	ah. they eval
<shaver>	eval == heavyweight
<shaver>	heavyweight == call object
<shaver>	call == CGT

Comment 8

[jag (Peter Annema)]

Does that explain this tree?

str_replace
  match_or_replace
    replace_glob
      find_replen
        js_Invoke
          ComputeGlobalThis

Comment 9

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

I think so, since the scripted caller is heavyweight, but I'd need to trace it more to be sure.  Brendan probably knows off the top of his head.

Comment 10

[Blake Kaplan (:mrbkap) (inactive)]

Attachment: Untested patch

It seems to me that we can skip the the js_ComputeThis in js_Invoke if !native or (fun->flags & JSFUN_FAST_NATIVE): any scripted callee will go through JSOP_THIS or kin and any fast native has to use JS_THIS{,_OBJECT} anyway. I'm not set up to test this right now, though.

Comment 11

[Blake Kaplan (:mrbkap) (inactive)]

Attachment: Handle non-callable things

I haven't done any perf testing on the testcase here, but this should avoid the pain that jag was seeing (at least based on what I can glean out of that packed JS function!).

Comment 12

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

Comment on attachment 304101 [details] [diff] [review]
Handle non-callable things

>Index: jsinterp.c
>===================================================================
>RCS file: /cvsroot/mozilla/js/src/jsinterp.c,v
>retrieving revision 3.432
>diff -p -U8 -r3.432 jsinterp.c
>--- jsinterp.c	18 Feb 2008 21:01:47 -0000	3.432
>+++ jsinterp.c	18 Feb 2008 22:47:54 -0000
>@@ -1256,17 +1256,18 @@ have_fun:
>     if (flags & JSINVOKE_CONSTRUCT) {
>         JS_ASSERT(!JSVAL_IS_PRIMITIVE(vp[1]));
>     } else {
>         /*
>          * We must call js_ComputeThis in case we are not called from the
>          * interpreter, where a prior bytecode has computed an appropriate
>          * |this| already.
>          */
>-        if (!js_ComputeThis(cx, JS_FALSE, vp + 2)) {
>+        if (native && fun && !(fun->flags & JSFUN_FAST_NATIVE) &&
>+            !js_ComputeThis(cx, JS_FALSE, vp + 2)) {

Comment wants an update to describe the only-slow-native logic.  Perhaps merge slow-native
guard into else if, leaving js_ComputeThis call distinct to follow comment?

You'd think that after 12 years I'd have a better sense of what style should prevail.

Comment 13

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

string-unpack-code in the browser is very glad to make your patch's acquaintance.

Comment 14

[Blake Kaplan (:mrbkap) (inactive)]

Attachment: Updated comment

Comment 15

[Brendan Eich [:brendan]]

Comment on attachment 304138 [details] [diff] [review]
Updated comment

r/a=me with "But we need to compute |this| eagerly only for slow native functions."

/be

Comment 16

[Blake Kaplan (:mrbkap) (inactive)]

Attachment: With that

Comment 17

[Blake Kaplan (:mrbkap) (inactive)]

Fix checked into trunk.

Comment 18

[jag (Peter Annema)]

Nice! Went from 760ms to 510ms here.