Bug 45749 – Extend YARR JIT with beginning character look-up optimization

• Status: RESOLVED
• Resolution: WONTFIX
• Component: JavaScriptCore

[Peter Varga]

Search the start index of the first potential match before the pattern
matching process. Use the vector of possible beginning characters which are collected
by YARR's parser.

[Peter Varga]

Created attachment 67548 [details]
proposed patch

Performance results:

                                      ref               mod
regexp-dna:   1.060x as fast   21.1ms +/- 1.1%   19.9ms +/- 1.1%
v8-regexp:    1.011x as slow  350.9ms +/- 0.2%  354.7ms +/- 0.1%

[Early Warning System Bot]

Attachment 67548 [details] did not build on qt:
Build output: http://queues.webkit.org/results/3998008

[WebKit Review Bot]

Attachment 67548 [details] did not build on gtk:
Build output: http://queues.webkit.org/results/4019006

[Csaba Osztrogonác]

(In reply to comment #2)
> Attachment 67548 [details] did not build on qt:
> Build output: http://queues.webkit.org/results/3998008

It will build on Qt after https://bugs.webkit.org/show_bug.cgi?id=45748 fixed.

[WebKit Review Bot]

Attachment 67548 [details] did not build on win:
Build output: http://queues.webkit.org/results/4017011

[Geoffrey Garen]

Do you know why v8-regexp got slower?

[Peter Varga]

(In reply to comment #6)
> Do you know why v8-regexp got slower?

I made some other measurements:
- I increased the number of iterations in the v8-regexp benchmark. The ratio of the difference between the two results 
didn't increase.
- I just measured with the parser's patch (https://bugs.webkit.org/show_bug.cgi?id=45748). I noticed that the slow-down still remains.
- On another machine the v8 benchmark's results were different. v8-regexp was faster than the reference but 
other tests' (which don't contain regular expressions) performance results were different. I think it is caused by deviation.

It looks like the slow-down with v8-regexp is caused by the beginning character collecting in the parser.
I'm working on this problem.

[Geoffrey Garen]

Any idea why this would slow down the JIT but not the interpreter? Your interpreter results show a solid improvement on v8-regexp. It's surprising that the JIT wouldn't improve as well.

[Peter Varga]

(In reply to comment #8)
> Any idea why this would slow down the JIT but not the interpreter? Your interpreter results show a solid improvement on v8-regexp. It's surprising that the JIT wouldn't improve as well.

I think this optimization haven't enough possibilities to make faster the pattern matching in case of v8-regexp test. Therefore the overhead of the character collecting is greater than the profit of the optimization in case of JIT.

However this optimization is more efficient in case of interpreter and the overhead of character collecting is same in both case, therefore the overhead should be negligible when the interpreter does the pattern matching.

[Gavin Barraclough]

Hi Peter,

I think Michael is going to take a look over your patch, since he's been working in this area at the minute.  He has a patch on bugs.webkit.org/show_bug.cgi?id=45787 that I imagine could conflict with this, which is at commit-queue+ at the minute.  You may need to update your patches once this has landed to resolve any merge issues.

cheers,
G.

[Peter Varga]

Created attachment 68070 [details]
proposed patch v2

updated patch for top of trunk.

[Early Warning System Bot]

Attachment 68070 [details] did not build on qt:
Build output: http://queues.webkit.org/results/4035090

[WebKit Review Bot]

Attachment 68070 [details] did not build on gtk:
Build output: http://queues.webkit.org/results/4084022

[WebKit Review Bot]

Attachment 68070 [details] did not build on win:
Build output: http://queues.webkit.org/results/4031067

[Peter Varga]

The new performance results without the collecting of character classes:

                                       ref                mod
regexp-dna:  1.055x as fast     21.1ms +/- 1.1%    20.0ms +/- 0.0%
v8-regexp:   ??                316.6ms +/- 0.6%   317.6ms +/- 0.2%

[Peter Varga]

Created attachment 71439 [details]
proposed patch v3

update patch.

[Early Warning System Bot]

Attachment 71439 [details] did not build on qt:
Build output: http://queues.webkit.org/results/6117003

[Build Bot]

Attachment 71439 [details] did not build on win:
Build output: http://queues.webkit.org/results/5992105

[Eric Seidel (no email)]

Comment on attachment 71439 [details]
proposed patch v3

r- for qt and win failures.

[Peter Varga]

Created attachment 75659 [details]
proposed patch v3

I upload the previous patch again. It has failed on the last ews check because a depedency wasn't landed but now it seems ok.

[Eric Seidel (no email)]

Oliver, Gavin:  This patch has been up for review for 6 months.  it's tiny.  Please r- it or r+ it.  I will r- this next week if it still remains undecided.

[Gavin Barraclough]

Comment on attachment 75659 [details]
proposed patch v3

Clearing review flag pending 61306

[Gavin Barraclough]

Marking this won't fix based on resolution to r61306.