683839 - Optimize access to Array instances

Status: RESOLVED WONTFIX

(Tamarin Graveyard :: Library, defect, P3)

Description

[Lars T Hansen]

Array operations can in many ways be optimized like Vector operations (see bug #681888 for example).  Type information should be used - typed code that uses Arrays would benefit.  Helper methods should be streamlined and would benefit all code that uses Arrays.

Looking at helper methods first: The Array internals have a lot of contortions to deal with the possibility that Array may be subclassed (and the subclasses may be non-dynamic, as well, see bug #654807).  For example, in the fast-inlined _getUintProperty we see this:

    Atom ArrayObject::_getUintProperty(uint32_t index) const
    {
        // this is a hot function, but we still must
        // call the virtual function in case it's been overridden
        return getUintProperty(index);
    }

For the sake of an experiment, just replacing the call to getUintProperty by a call to the inlined getUintPropertyImpl gives us a speedup of 1.38 to 1.44 on the array-read microbenchmarks working on dense arrays.

If we take dense arrays as our focus a single bit in the ArrayObject, "this is a dense true-Array", set at creation time for true Array instances and then reset if the Array turns sparse, would allow more fast paths to be taken quickly, and might allow some operations to be in-lined.

A variant on that is a flag that says that the array is a dense true-Array without any holes in its index range.  In this case the flag would be a uint32_t that is the length of the array, or zero.  Now we make use of type information: An inlined getter to an object of known type Array would load the field, check the index against it, and if the index is strictly less than the length would just load the value from the array.  If the index check fails we trap.  This would also work for fast computation of Array.length.

Arrays store atoms but that does not mean we have to throw away available type information.  We could call different setter helpers depending on whether the value to be set is known to be a general atom, an RCObject, or a non-pointer; the different helpers would optimize the write barrier in different ways.  (Write barriers should be inlined into the helpers whenever possible.)

Comment 1

[Lars T Hansen]

The point about a true-Array can be refined a little: it's an easy approximation to "does not override the 'length' getter or setter".

Comment 2

[Lars T Hansen]

The brightspot data in bug #599357 should motivate work on this bug: Arrays are heavily used in actual content.

Comment 3

[Lars T Hansen]

Further notes from discussions with Edwin, and from general thinking around the problem.  (Convenient to gather this information here at this time.)

1) The Atom representation in Array does not have to be the same as "normal" atoms, instead we can use 64-bit values with NaN tagging (for example) so that we do not, as a rule, have to box when storing into an Array.  Typed code that knows its storing a double (or for that matter int or uint) would not box, but would call type-specialized helpers.  Typed code that reads values destined for particular typed variables would call type-specialized helpers to avoid boxing during the load.

2) Arrays will frequently be monotyped so we should support dense monotyped Arrays (the JS engines have this).  For example, an Array containing doubles would not have to be scanned by the GC at all.  A NaN could represent a hole; reading a NaN values would then take a slow path.  The simple trick for making this work in the absence of type information would be for Array to have a number of cached-length values, one per type specializer.  A cached-length would be nonzero if it is a true type-specialized array of that type.  For example, storing a double we would load the cached-length for double arrays; this is either zero if the object is not a true Array, not specialized to double, or not dense; otherwise it's the length so there's just a range check and store, no write barrier or anything.  Reading would be pretty much the same.  Not clear how many length fields we'd want but double, int/uint, RC pointer, and atom are likely.

Vector.<*> and Vector.<Object> would benefit significantly from the "better atom representation" optimization, but probably not from the inference of content type since the content type is fixed.

Generally speaking, dense Arrays should do about as well as Vector, modulo the read barrier that checks for the hole.  Also, the "trap" case can yield values of any type so the most we can say about a value read is pretty much that it's an Atom.

Comment 4

[Lars T Hansen]

It may be tricky to represent holes in monotyped int/uint arrays if we stick to 32-bit representation, because there are no bit patterns available.  (With the NaN trick in Number arrays we would use a different-looking NaN for holes than for "normal" use.)  Representing the values using 64 bits might be the easiest; the high word would be nonzero for a hole.  It's an expensive representation but not overly so.

Comment 5

[Sylvestre Ledru [:Sylvestre]]

Tamarin isn't maintained anymore. WONTFIX remaining bugs.