464866 - TM: Use regexp string as key for the regexp fragment cache

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Comment 1

[Andreas Gal :gal]

Attachment: use regexp source+flags as key

Comment 2

[Andreas Gal :gal]

This is a whopping 50ms perf win on sunspider.

Comment 3

[David Anderson [:dvander] - inactive, e-mail if emergency]

Comment on attachment 348154 [details] [diff] [review]
use regexp source+flags as key

>+static Fragment* 

Angels! -- (C) Brendan

Comment 4

[Andreas Gal :gal]

Not a blocker, hold off on this one according to sayrer.

But we might want to redo our benchmark numbers for the paper with it since it affects a whole bunch of benchmarks. dmandelin?

Comment 5

[Robert Sayre]

(In reply to comment #2)
> This is a whopping 50ms perf win on sunspider.

Which tests does it change? I'm expecting tagcloud, for one.

Comment 6

[Brendan Eich [:brendan]]

Comment on attachment 348154 [details] [diff] [review]
use regexp source+flags as key

Drive-by nit-picking.

>+static void*
>+hashRegExp(uint16 flags, jschar* s, size_t n)

Nit: static functions are capitalized.

>+struct RESideExit : public SideExit
>+{
>+    uint16 flags;
>+    size_t re_length;
>+    jschar re_chars[1];
>+};

Flip flags and re_length for better packing. Might use re_flags for similar naming (flags is vague -- are these side-exit or regexp flags? if obviously the latter, same goes for chars) and aesthetics.

Opening brace of struct on same line, generally. jstracer.h is not consistent. If this makes it hard to see the superclass(es) we should go the other way, but at least be consistent.

>+static Fragment* 
>+lookupNativeRegExp(JSContext* cx, uint16 flags, jschar* re_chars, size_t re_length)

Capitalization nit.

>+{
>+    Fragmento* fragmento = JS_TRACE_MONITOR(cx).reFragmento;
>+    Fragment* fragment = fragmento->getLoop(hashRegExp(flags, re_chars, re_length));

Why not make the caller hash to avoid rehashing later in compile when calling getAnchor? If one of two callers needs the string chars and length, you could even re-parameterize lookupNativeRegExp to take a JSString* and use js_HashString instead of duplicating its guts.

r=me on a followup for tracemonkey landing.

/be

Comment 7

[Andreas Gal :gal]

http://hg.mozilla.org/tracemonkey/rev/2601301b793d

Comment 8

[Andreas Gal :gal]

Backed out. Sets the tinderboxes ablaze.

Comment 9

[David Mandelin [:dmandelin]]

Fixing this is proving more difficult than I had hoped. I think the main problem is that the generated native code refers to the RECharSet* stored in the JSRegExp, so we can get:

  re = js_NewRegExp(/[abc]/, ...)   /* creates new RECharSet for [abc] */
  MatchRegExp(re);
  js_DestroyRegExp(re)              /* frees RECharSet created above */
  re2 = js_NewRegExp(/[abc]/, ...)  /* native compiler finds previous version
                                       which refers to freed RECharSet */

The obvious solution is to store a copy of the RECharSet (or really, just its bit map) with the generated code (say, in a skip buffer). But that doesn't work by itself because the bitmap is not actually created until the first time the regexp is used by matching. And the code that creates the bitmap takes an REGlobalData and an REMatchState as args, so it doesn't like to be called outside the matcher.

One possibility is to do the compilation lazily inside MatchRegExp like we had originally planned. That way, ProcessClass could be used as is and the only thing to make sure of is the memory usage.

Another is to refactor ProcessClass so it can be called from elsewhere. This solution seems cleaner but I have to make sure all the deps on REGlobalData and REMatchState can be boiled down to a few things available during compilation.

Comment 10

[David Mandelin [:dmandelin]]

Attachment: Fixed patch

I took 348154 and fixed the bugs as explained in my previous comment. Then I  reorganized the initialization of character classes a bit to eliminate the ambiguity about when the RECharSet is initialized. 

I also figured out and fixed the perf regression that occurred before when we moved regexp compilation after bytecode compilation. The bytecode compilation process combines sequential flat characters into flat strings. The native compiler didn't handle these before, because it didn't have to when run before bytecode compilation. I added support to the native compiler and now it works.

Comment 11

[David Mandelin [:dmandelin]]

Small update mostly for bizarreness value. The current patch won't compile all the regexps that appear in crypto-aes because it handles only character classes whose bitmap representations fit in 1024 bytes (in turn because LirBuffers don't hold things larger than pages). But it turns out that none of those regexps ever run anyway--they're inside dead functions.

Comment 13

[David Mandelin [:dmandelin]]

Pushed to TM as 21808:9f5e7a04b4bc.

Comment 14

[Robert Sayre]

http://hg.mozilla.org/releases/mozilla-1.9.1/rev/2313fcbf6780