Closed Bug 604045 Opened 9 years ago Closed 9 years ago

TypeInference: identify packed arrays


(Core :: JavaScript Engine, defect)

Not set





(Reporter: bhackett, Assigned: bhackett)


(Blocks 1 open bug)



(1 file, 1 obsolete file)

If an array is known to be monomorphic (e.g. all integers, or all strings) and to have no holes up to its length (to be packed, which implies dense), it can be accessed with similar speed to a java JIT.

x[i]  // x known packed array, i known int

load x into r1
load i into r2
load r1->length into r3
branch r2 >= r3 to slow path
load r1->slots into r3
load/push r3[r2]  // no load of type needed if monomorphic

Identifying packed arrays needs a mix of static and dynamic analysis.  Some cases, in increasing complexity.


x = Array(1,2,3);

Must be packed.


x = [1,2,3,4,5];

Scan initializer for holes.


x = Array();
for (i = 0; i < ...; i++)
  x[i] = ...;

The OOL SETELEM fast path that bumps the length can check it doesn't bump more than one.


x = Array(n);
for (i = 0; i < n; i++)
  x[i] = ...;

Trickier, as the array doesn't become packed until the loop finishes.  Static analysis is needed to ensure that every slot up to the length is filled in.


var global = Array(100);


function foo() {
  for (var i = 0; i < 100; i++)
    global[i] = 0;

This pattern is used for the MEM array in the shell testcase in bug 514765, and could be handled in the same manner as case D) given that the global is a singleton object (per bug 604035).

This sort of analysis is opportunistic --- not terribly robust, just captures some reasonably common patterns of array initialization.  Looking through array usage in SS:

3d-cube: fine, except Q is slow
3d-morph: fine
3d-raytrace: fine
access-fannkuch: maybe perm1, others hard
access-nbody: fine
access-nsieve: array not packed
bitops-nsieve-bits: hard
crypto-aes: fine
crypto-md5: fine
crypto-sha1: fine
date-format-tofte: fine
math-spectral-norm: fine
string-base64: fine
Thinking on this more, this can be done purely dynamically by adding an initializedLength() member to dense arrays, which is <= length and <= capacity (but may be less than both, i.e. not a resurrected MINLENCAP), and all contents up to capacity are uninitialized (conceptually holes, up to the length).  GETELEM and SETELEM check against the initialized length, and if SETELEM never bumps it by more than one then the array is packed.

This would still only be beneficial for type inference, where TypeObjects give enough granularity to distinguish sites accessing packed vs. unpacked arrays.  For perf, SETELEM on holes needs to write both the length and initialized length, but that is offset by not needing to fill new/resized arrays with holes).  The initialized length could be stored in the object's emptyShapes field (slowifying any dense arrays which are prototypes of other objects).
No longer blocks: 557407
Attached patch patch (obsolete) — Splinter Review
This adds an initializedLength for dense arrays to use, keeps track of packed state, updates the JITs and inference and integrates inference information about dense and packed arrays into JM.  Running tests individually, saves me 7ms on SS in JM over bug 608750 (~10ms on AWFY) and about 10% on the shell test in bug 514765.  For this microbenchmark:

function foo(x, y) {
  var a = Array(y);
  for (var i = 0; i < y; i++)
    a[i] = 0;
  for (var i = 0; i < x; i++) {
    for (var j = 0; j < y; j++)
      var k = a[j];
foo(10000, 10000);

V8:  468
JSC: 432
TM:  372
JM (old): 582
JM (new): 313

When making the inner loop body into 'a[j] = 0':

V8:  431
JSC: 476
TM:  696 (weird)
JM (old): 525
JM (new): 302

Most of the improvement seems to be in the arrays, rather than better handling of compares and ++ from bug 608750 (that will improve with better regalloc).  Two more things for packed arrays which will be in separate patches:

- The type is still always written when setting an array element.  This is 
unnecessary for monomorphic packed arrays (all values have same JSValueType).

- Guess at likely unpacked arrays.  Currently, all dense arrays are treated as packed until they become unpacked from a set above the initialized length.  Should do better here to avoid unnecessary recompilation, by pattern matching on initialization patterns.  Packed arrays are generally initialized with 'for (i = 0; i < ...; i++) a[i] = ...' or similar loops.
Assignee: general → bhackett1024
Attached patch updated patchSplinter Review
Landed this on JM.
Attachment #488332 - Attachment is obsolete: true
Blocks: 619423
No longer blocks: TypeInference
Closed: 9 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.