IonMonkey: Octane, pdfjs.js:16934: Optimize string comparisons of switch-case

NEW
Unassigned

Status

()

Core
JavaScript Engine: JIT
P5
normal
5 years ago
a year ago

People

(Reporter: nbp, Unassigned)

Tracking

(Blocks: 1 bug)

Firefox Tracking Flags

(Not tracked)

Details

(URL)

Attachments

(1 attachment)

(Reporter)

Description

5 years ago
PdfJS Type1Parser_extractFontProgram is taking a lot of time in the switch statement which looks for known keywords.  Most of the strings flowing into the switch statements are not matching any of the cases.

Instrumenting the switch to check the overall cost of cases comparisons show that we spend ~300 ms at doing the strict equality comparisons where the switch cost ~355ms.

Doing a simple check on the first character reduces the switch time to ~140ms.
(Reporter)

Comment 1

5 years ago
The code from PdfJS looks like that:

        token += c;
        if (!glyphsSection) {
          switch (token) {
            case '/CharString':

Ion checks for pointer equality & atoms.  I think that we can infer from "token += c" that token would not alias any existing string and that it would not be an atom either.

v8 is checking for length equality first by getting the length field which is not packed, which makes their non-equality test fast (load 0xXX(reg1), reg3; cmp 0xXX(reg2), reg3; je …).

1/ If we can get hints that one string is constant, then we should do the following:

load 0xXX(reg1), reg3
or Imm32(JSString::LENGTH_SHIFT - 1), reg3
sub 0xXX(reg2), reg3
test JSString::LENGTH_MASK, reg3
jnz …
oolCall

which is still less efficient than v8.  This approach improve the micro benchmark by 10%, but it does not seems to bring anything to the v8 benchmark.

2/ Another approach would be to detect that one of the operands has just been computed, (concatenation), and deduce that it is unnecessary to check for pointers & atoms equality as the operand just came out-of a concatenation and is likely to be a rope.  Then we can replace the comparison by a simple one which check the length of a string and fallback on the C++ call if the length are equal.

I am currently testing this second approach, hopping to get some results soon.
If we shortcut faster with the length check first (including the necessary unmasking), does that help our score?
(Reporter)

Comment 3

5 years ago
(In reply to Nicolas B. Pierron [:pierron] [:nbp] from comment #1)
> 2/ Another approach would be to detect that one of the operands has just
> been computed, (concatenation), and deduce that it is unnecessary to check
> for pointers & atoms equality as the operand just came out-of a
> concatenation and is likely to be a rope.  Then we can replace the
> comparison by a simple one which check the length of a string and fallback
> on the C++ call if the length are equal.

This approach improve the micro benchmark by 25%.  Which corresponds to a 1% improvement on PdfJS.

(In reply to David Anderson [:dvander] from comment #2)
> If we shortcut faster with the length check first (including the necessary
> unmasking), does that help our score?

I don't think this will help in all cases, for example in atoms comparisons, which is frequent, I guess you would want to compare only the pointers at best, and all one-character comparisons are likely to be atom comparisons.

I also noticed that v8 is not doing any VM calls for string comparisons.
(Reporter)

Comment 4

5 years ago
Created attachment 712055 [details] [diff] [review]
Implement approach 1 & 2.

This patch only improve PdfJS by ~1%.

It add a new MIR which is generated if at least one of the operands flowing in an MCompare is guaranteed to be the result of a concatenation, in which case the the MCompare is replaced by an MCompareRopes in which we add MStringLEngth inputs before the GVN phase.

Also, the case of a constant right-hand-side (frequent when comparing immediate values, or switch case one) is optimized on both visitCompareS and visitCompareRS. (RS = Rope String)
Attachment #712055 - Flags: review?(dvander)
Attachment #712055 - Flags: review?(dvander)
(We decided not to take this at the moment since it didn't seem to impact pdfjs.)
(Reporter)

Updated

a year ago
Assignee: nicolas.b.pierron → nobody
Status: ASSIGNED → NEW
Component: JavaScript Engine → JavaScript Engine: JIT
Priority: -- → P5
You need to log in before you can comment on or make changes to this bug.