JM: Optimize 'typeof' comparisons.

RESOLVED FIXED

Status

()

defect
RESOLVED FIXED
9 years ago
9 years ago

People

(Reporter: sstangl, Assigned: evilpie)

Tracking

(Blocks 1 bug)

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(1 attachment, 7 obsolete attachments)

Reporter

Description

9 years ago
JSNES source frequently produces bytecode such as:

[jaeger] JSOps         1 00064:  34  typeof
[jaeger] JSOps         1 00065:  34  string "undefined"
[jaeger] JSOps         2 00068:  34  ne

Instead of doing a string comparison, we should detect whether the string is one of the known types, and output a comparison on the Value's type. We can optimize this entire complicated procedure to just a branchPtr().
Good idea. See similar bug 574233. This approach would cover a bunch of cases in date-format-tofte as well.
Could go even further, since typeof does not convert, and peephole optimize that sequence into a "isDefined" test -- have to be careful to allow for unqualified names not found in the scope chain to be used, of course.

Similar idea for isString, isNumber, etc.

/be
Blocks: 460050
Assignee

Comment 4

9 years ago
So a few things:
 * I cant test x64 myself, somebody needs to check this please :)
 * I am not entirely sure what behavior i trigger if a variable is _not_ defined, but it seems to work. Please could somebody explain how this works?
 * I would do the other cases to, but you can't seem to distinguish function and object

Performance: 

for (var i = 0; i < 1e6; i++) {
   typeof y === "number";
}

From ~31 to ~3, other are similar, only typeof for _not_ defined variables, is still dog slow ~220 to ~180.
Comment on attachment 487053 [details] [diff] [review]
Optimize typeof x === 'number'|'string'|'boolean'|'undefined'

># HG changeset patch
># User Tom Schuster <evilpies@gmail.com>
># Date 1288389391 -7200
># Node ID 08c8ca7d2e185b59bca2c44cfa210ed3119bca0d
># Parent  66f4a212edebd33473bdf56408bd3af6de1c6719
>specialize sequence typeof x === 'number' etc.
>
>diff -r 66f4a212edeb -r 08c8ca7d2e18 js/src/methodjit/FastOps.cpp
>--- a/js/src/methodjit/FastOps.cpp	Thu Oct 28 12:23:00 2010 -0700
>+++ b/js/src/methodjit/FastOps.cpp	Fri Oct 29 23:56:31 2010 +0200
>@@ -914,7 +914,61 @@
>             return;
>         }
>     }
>+    
>+    
>+    

One blank line is enough, and no trailing whitespace please.

>+    JSOp fused = JSOp(PC[JSOP_TYPEOF_LENGTH]);
>+    if (fused == JSOP_STRING) {
>+        JSOp op = JSOp(PC[JSOP_TYPEOF_LENGTH + JSOP_STRING_LENGTH]);        
> 
>+        if (op == JSOP_STRICTEQ || op == JSOP_EQ || JSOP_STRICTNE || op == JSOP_NE) {
>+            JSAtom *atom = script->getAtom(fullAtomIndex(PC + JSOP_TYPEOF_LENGTH));

Note that fullAtomIndex handles only the 16-bit immediate case implied by matching JSOP_STRING, anyway, so you don't need it.

A nit on fullAtomIndex: it should use GET_UINT16, not GET_SLOTNO.

>+            JSRuntime *rt = cx->runtime;          
>+            JSValueType type;

Note uninitialized variable here -- should be initialized to JSTYPE_LIMIT.

>+            Assembler::Condition cond = (op == JSOP_STRICTEQ || op == JSOP_EQ) ? Assembler::Equal 
>+                                    : Assembler::NotEqual;              

Nit: wrap before ? and : and make them underhang the (.

>+            
>+            if (atom == rt->atomState.typeAtoms[JSTYPE_VOID]) {
>+                type = JSVAL_TYPE_UNDEFINED;
>+            } else if (atom == rt->atomState.typeAtoms[JSTYPE_STRING]) {
>+                type = JSVAL_TYPE_STRING;
>+            } else if (atom == rt->atomState.typeAtoms[JSTYPE_BOOLEAN]) {
>+                type = JSVAL_TYPE_BOOLEAN;
>+            } else if (atom == rt->atomState.typeAtoms[JSTYPE_NUMBER]) {
>+                type = JSVAL_TYPE_INT32;
>+                                
>+                /* JSVAL_TYPE_DOUBLE is 0x0 and JSVAL_TYPE_INT32 is 0x1, use <= or > to match both */
>+                cond = (cond == Assembler::Equal) ? Assembler::BelowOrEqual : Assembler::Above;
>+            }
>+            
>+            if (type) { 

Trailing space nit again, and probably elsewhere -- don't do it!

Non-nit: this should test type != JSTYPE_LIMIT.

>+                PC += JSOP_TYPEOF_LENGTH;
>+                PC += JSOP_STRING_LENGTH;
>+                
>+                RegisterID result = frame.allocReg(Registers::SingleByteRegs);
>+                
>+                #if defined JS_CPU_X86 

Nit (trailing space aside): don't we prefer # in column 1? We do in most of SpiderMonkey. Not in nanojit, but that is downstream of the nanojit-central repo and under separate style rules.

>+                if (frame.shouldAvoidTypeRemat(fe))
>+                    masm.set32(cond, masm.tagOf(frame.addressOf(fe)), ImmType(type), result);
>+                else
>+                    masm.set32(cond, frame.tempRegForType(fe), ImmType(type), result);                    
>+                #elif defined JS_CPU_X64
>+                RegisterID maskReg = frame.allocReg();
>+                masm.move(ImmType(type), maskReg);
>+
>+                RegisterID r = frame.tempRegForType(fe);
>+                masm.setPtr(cond, r, maskReg, result);
>+
>+                frame.freeReg(maskReg);
>+                #endif
>+
>+                frame.pop();
>+                frame.pushTypedPayload(JSVAL_TYPE_BOOLEAN, result);               
>+                return;                

So how does an unbound variable get evaluated here into fe, without throwing a ReferenceError prematurely (which typeof nosuchvar avoids)?

/be
Assignee

Comment 6

9 years ago
>Note that fullAtomIndex handles only the 16-bit immediate case implied by
>matching JSOP_STRING, anyway, so you don't need it.
Don't know what this means

>So how does an unbound variable get evaluated here into fe, without throwing a
>ReferenceError prematurely (which typeof nosuchvar avoids)?
Yes this was kind of my question, too.
Assignee

Comment 7

9 years ago
Attachment #487053 - Attachment is obsolete: true
Assignee

Comment 8

9 years ago
Ops sorry!
(In reply to comment #6)
> >Note that fullAtomIndex handles only the 16-bit immediate case implied by
> >matching JSOP_STRING, anyway, so you don't need it.
> Don't know what this means

Not to worry, dvander knows. It's just that fullAtomIndex does only the non-full case (which is fine for now), and there's a nit about its implementation (have a look and re-read my nit about using GET_UINT16).

/be
Assignee

Comment 10

9 years ago
All nits fixed.
I do understand the |typeof nosuchvar| case now. For not defined variables we end up calling stubs::GetGlobalName, which itself calls NameOp, and if this function cant find a global variable, it throws. But beforehand it checks if the next op is typeof, and then just pushes undefined.
Attachment #487071 - Attachment is obsolete: true
Assignee

Comment 11

9 years ago
Posted patch v4 (obsolete) — Splinter Review
Uses JSVAL_TYPE_UNINITIALIZED instead of JSTYPE_LIMIT.

One number v8-earley-boyer:
js -m before: ~312ms
js -m after: ~299ms
Attachment #487226 - Attachment is obsolete: true
Assignee

Updated

9 years ago
Attachment #487227 - Flags: review?(brendan)
(In reply to comment #11)
> Created attachment 487227 [details] [diff] [review]
> v4
> 
> Uses JSVAL_TYPE_UNINITIALIZED instead of JSTYPE_LIMIT.

Those are not from the same category (enum, ad-hoc int subrange type)! Just use JSTYPE_LIMIT, you are computing a JSType value here, not a jsval or js::Value.

/be
Assignee

Comment 13

9 years ago
This isn't JSType, but JSValueType.
(In reply to comment #13)
> This isn't JSType, but JSValueType.

Apologies -- I'm blind. Will get eye transplants and review in a second.

/be
Attachment #487227 - Attachment is patch: true
Attachment #487227 - Attachment mime type: application/octet-stream → text/plain
Comment on attachment 487227 [details] [diff] [review]
v4

Looks good to me, thanks for doing this.

David mentioned that he would have a look this weekend, and I'm a JM rookie, so r?'ing him too.

/be
Attachment #487227 - Flags: review?(dvander)
Attachment #487227 - Flags: review?(brendan)
Attachment #487227 - Flags: review+
Comment on attachment 487227 [details] [diff] [review]
v4

>+            if (type != JSVAL_TYPE_UNINITIALIZED) {
>+                PC += JSOP_TYPEOF_LENGTH;
>+                PC += JSOP_STRING_LENGTH;

This would be clearer as,
    PC += JSOP_STRING_LENGTH;
    PC += JSOP_EQ_LENGTH;

Since the compiler will add JSOP_TYPEOF_LENGTH itself when this function returns.

>+
>+                RegisterID result = frame.allocReg(Registers::SingleByteRegs);
>+
>+#if defined JS_CPU_X86
>+                if (frame.shouldAvoidTypeRemat(fe))
>+                    masm.set32(cond, masm.tagOf(frame.addressOf(fe)), ImmType(type), result);
>+                else
>+                    masm.set32(cond, frame.tempRegForType(fe), ImmType(type), result);
>+#elif defined JS_CPU_X64

This etc will assert if fe->isTypeKnown(), which can be true if the earlier detection fell through. For example,
  var x = { };
  if (typeof x == "bleh")

But in this case you know the comparison will be false anyway, so you can just push a constant.
Attachment #487227 - Flags: review?(dvander)
Assignee

Comment 17

9 years ago
Okay will fix #1.
But i am not quite sure about the second one, for example if someone does typeof {} == "object", we should emit true, but can because it might be an function object. So i think the easiest thing would be to do. Or did it misunderstand something?

>(fused == JSOP_STRING && !fe->isTypeKnwon())

Thanks for review.
In your case, "object" isn't detected, so if you know |fe| is typed as an object, then it's not any of the types you handle.

But you can just skip this case too :)
Assignee

Comment 19

9 years ago
Posted patch v5 (obsolete) — Splinter Review
Attachment #487227 - Attachment is obsolete: true
Assignee

Updated

9 years ago
Attachment #487397 - Flags: review?(dvander)
Attachment #487397 - Attachment is patch: true
Attachment #487397 - Attachment mime type: application/octet-stream → text/plain
Attachment #487397 - Flags: review?(dvander) → review+
Nice, thanks!
Assignee: general → evilpies
Status: NEW → UNCONFIRMED
Ever confirmed: false
Keywords: checkin-needed
Reporter

Comment 21

9 years ago
(In reply to comment #19)

x64 does not need to clobber a register. Instead, we should use JSC's scratchRegister by implementing a setPtr() that takes an immPtr argument for x64.
Status: UNCONFIRMED → ASSIGNED
Ever confirmed: true
Comment on attachment 487397 [details] [diff] [review]
v5

>+#if defined JS_CPU_X86
>+                if (frame.shouldAvoidTypeRemat(fe))
>+                    masm.set32(cond, masm.tagOf(frame.addressOf(fe)), ImmType(type), result);
>+                else
>+                    masm.set32(cond, frame.tempRegForType(fe), ImmType(type), result);
>+#elif defined JS_CPU_X64
>+                RegisterID maskReg = frame.allocReg();
>+                masm.move(ImmType(type), maskReg);
>+
>+                RegisterID r = frame.tempRegForType(fe);
>+                masm.setPtr(cond, r, maskReg, result);
>+
>+                frame.freeReg(maskReg);
>+#endif

Is there a missing #else/#error here, or does ARM work without any extra code?

/be
Reporter

Comment 23

9 years ago
(In reply to comment #22)
> Is there a missing #else/#error here, or does ARM work without any extra code?
Yes, we want JS_NUNBOX32 and JS_PUNBOX64.
Comment on attachment 487397 [details] [diff] [review]
v5

Do what sstangl said and r? for a fast r+, I hope.

/be
Attachment #487397 - Flags: review+ → review-
Assignee

Comment 25

9 years ago
Posted patch v6 (obsolete) — Splinter Review
Hope i got this right, i just replaced the two compiler directives.
Attachment #487397 - Attachment is obsolete: true
Assignee

Updated

9 years ago
Attachment #487593 - Flags: review?(dvander)
Reporter

Comment 26

9 years ago
Assignee

Comment 27

9 years ago
Attachment #487593 - Attachment is obsolete: true
Attachment #487693 - Attachment is obsolete: true
Attachment #487593 - Flags: review?(dvander)
Assignee

Updated

9 years ago
Attachment #487703 - Flags: review?(dvander)
Do we need a TM version of this bug?
Attachment #487703 - Flags: review?(dvander) → review+
Assignee

Comment 29

9 years ago
>Do we need a TM version of this bug?
Don't known, for me it looks like, TM bakes in the types at record time.

Anyway, can somebody commit this patch or do you only accept fixes at the moment?
Comment on attachment 487703 [details] [diff] [review]
v6 with x64 setPtr(), no clobber [thanks sstangl]

This looks good to me for Fx4/Moz2.

/be
Attachment #487703 - Flags: approval2.0?
> TM bakes in the types at record time.

TM bakes in the LHS at record time.  It still does the string compare, as far as I can tell.

Please file a followup bug on making a similar change to TM?
Assignee

Comment 32

9 years ago
Okay filled bug 613967. Don't want to suck, but how is the approval going?
sayrer's your approval-man.

Updated

9 years ago
Attachment #487703 - Flags: approval2.0? → approval2.0+
Assignee

Comment 34

9 years ago
Okay made some really stupid mistake.

Could somebody just change 
> if (op == JSOP_STRICTEQ || op == JSOP_EQ || JSOP_STRICTNE || op == JSOP_NE) {
to
> if (op == JSOP_STRICTEQ || op == JSOP_EQ || op == JSOP_STRICTNE || op == JSOP_NE) {

and commit it?
http://hg.mozilla.org/tracemonkey/rev/8c5f62e68881

includes fix in comment 34.
Keywords: checkin-needed
Whiteboard: fixed-in-tracemonkey

Comment 36

9 years ago
http://hg.mozilla.org/mozilla-central/rev/8c5f62e68881
Status: ASSIGNED → RESOLVED
Last Resolved: 9 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.