532873 - >>>= operator bad performances

Status: RESOLVED WORKSFORME

(Core :: JavaScript Engine, enhancement)

Description

[David Bruant]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; fr; rv:1.9.1.5) Gecko/20091109 Ubuntu/9.10 (karmic) Firefox/3.5.5
Build Identifier: Mozilla/5.0 (X11; U; Linux i686; fr; rv:1.9.1.5) Gecko/20091109 Ubuntu/9.10 (karmic) Firefox/3.5.5

The >>>= operator is very slow by comparison of other bit-wise operator.
This code : 
var N = 100000000;
var X = 1;
for(var i=1 ; i<N ; i++){
    X >>= (i&0x1F);
}
takes about 0.5 s while the same code with >>>= takes about 4seconds. 

Reproducible: Always

Steps to Reproduce:
1) insert the following code in any webpage :

<script>
      var t = (new Date()).getTime();
      var N = 100000000;
      var X = 1;
      for(var i=1 ; i<N ; i++){
		X >>= (i&0x1F);
				 }
      document.write("bla : " + ((new Date()).getTime()-t)/1000 + " secondes | "+ X);
    </script>
2) Replace >>= by >>>= to see the difference
Actual Results:  
>>>= takes 4s
>>= takes 0.5s

Expected Results:  
they should take the same time

Comment 1

[Brendan Eich [:brendan]]

Sure enough (printed number is milliseconds, I simplified the HTML script):

$ TMFLAGS=stats ./Darwin_DBG.OBJ/js -j /tmp/ursh.js
3252
recorder: started(2), aborted(0), completed(2), different header(0), trees trashed(2), slot promoted(0), unstable loop variable(1), breaks(0), returns(0), merged loop exits(0), unstableInnerCalls(0), blacklisted(0)
monitor: exits(2), timeouts(0), type mismatch(0), triggered(2), global mismatch(0), flushed(0)

$ TMFLAGS=stats ./Darwin_DBG.OBJ/js -j /tmp/rsh.js
399
recorder: started(1), aborted(0), completed(1), different header(0), trees trashed(1), slot promoted(0), unstable loop variable(0), breaks(0), returns(0), merged loop exits(0), unstableInnerCalls(0), blacklisted(0)
monitor: exits(1), timeouts(0), type mismatch(0), triggered(1), global mismatch(0), flushed(0)

$ cat /tmp/rsh.js
var t = Date.now();
var N = 100000000;
var X = 1;
for (var i=1 ; i<N ; i++) {
  X >>= (i&0x1F);
}
print(Date.now() - t);

Confirming. Andreas, David: >>> is rare enough this is not high priority but it might be work a diagnosis to see what lurks below.

/be

Comment 2

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

The >>>= version becomes type unstable and builds a double version.


With >>=

leaving trace at x.js:4@74, op=lt, lr=0x83f8e4, exitType=LOOP, sp=2, calldepth=0, cycles=0
stack0=int<100000000> stack1=int<100000000> 
global0=int<0> global1=int<100000000> global2=int<100000000> 

With >>>=

leaving trace at x.js:4@74, op=lt, lr=0x83fabc, exitType=LOOP, sp=2, calldepth=0, cycles=0
stack0=int<100000000> stack1=int<100000000> 
global0=double<0> global1=int<100000000> global2=int<100000000>

Comment 3

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

>>>= matches isPromoteUint but not isPromoteInt, so writeBack():

3730	    if (demote && isPromoteInt(i))
3731	        i = ::demote(lir, i);
3732	    return lir->insStorei(i, base, offset);
3733	}

Will always cause this to store back as a double.

Comment 4

[Andreas Gal :gal]

We have to remain faithful to the semantics of the language, which requires us to represent unsigned 32-bit results for >>>. That requires 33 bits, which doesn't fit into an integer register. The JIT already optimizes the code if we can tell that the sign bit is dropped:

var t = Date.now();
var N = 100000000;
var X = 1;
for (var i=1 ; i<N ; i++) {
    X = (X >>> (i&0x1F)) | 0;
}
print(Date.now() - t);

This should be as fast as >>.

Comment 5

[David Bruant]

(In reply to comment #4)
> var t = Date.now();
> var N = 100000000;
> var X = 1;
> for (var i=1 ; i<N ; i++) {
>     X = (X >>> (i&0x1F)) | 0;
> }
> print(Date.now() - t);
> 
> This should be as fast as >>.

It is in my configuration.

Comment 6

[David Bruant]

After retesting on FF4b11, this bug seems to have been fixed.
Is it a side-effect of the new value representation (http://blog.mozilla.com/rob-sayre/2010/08/02/mozillas-new-javascript-value-representation/) ?

Anyway. Changing status.