Closed
Bug 604045
Opened 14 years ago
Closed 14 years ago
TypeInference: identify packed arrays
Categories
(Core :: JavaScript Engine, defect)
Tracking
()
RESOLVED
FIXED
People
(Reporter: bhackett1024, Assigned: bhackett1024)
References
(Blocks 1 open bug)
Details
Attachments
(1 file, 1 obsolete file)
(deleted),
patch
|
Details | Diff | Splinter Review |
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.
A)
x = Array(1,2,3);
Must be packed.
B)
x = [1,2,3,4,5];
Scan initializer for holes.
C)
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.
D)
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.
E)
var global = Array(100);
...
function foo() {
for (var i = 0; i < 100; i++)
global[i] = 0;
}
foo();
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
Assignee | ||
Comment 1•14 years ago
|
||
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).
Assignee | ||
Updated•14 years ago
|
Blocks: TypeInference
Assignee | ||
Comment 2•14 years ago
|
||
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
Assignee | ||
Comment 3•14 years ago
|
||
Landed this on JM.
http://hg.mozilla.org/projects/jaegermonkey/rev/022de3c39539
Attachment #488332 -
Attachment is obsolete: true
Assignee | ||
Comment 4•14 years ago
|
||
Updated•14 years ago
|
Status: NEW → RESOLVED
Closed: 14 years ago
Resolution: --- → FIXED
You need to log in
before you can comment on or make changes to this bug.
Description
•