Array Element Kinds and Representation Transitions

An array is the one place in a dynamic language where the compiler has a static fact: the elements are contiguous, and index i is at a computable address. Everything else about the elements is unknown. The type of each element, the presence of holes, whether the array is dense at all, and whether the values are stored unboxed or as pointers are all decided at run time, and they can all change as the array is written.

Element kinds are the runtime’s answer. An array carries a kind in its header, and the kind determines the width of each element and the meaning of the bytes at each position. A read compiles to a check of the kind followed by a load at a scale factor chosen by the kind. The check is one comparison, and the scale factor is a constant per case, so the read is a compare and a load with no multiplication by a variable width.

The kinds and what they encode

The set varies by engine, but the structure is common. There is a packed kind for each element representation: small integers, doubles, and tagged values. There is a holey variant of each, for arrays with missing elements, where the missing element is represented by a distinguished sentinel rather than by a value. There is a kind for arrays backed by external memory, such as typed arrays. And there is a kind for arrays that have been converted to a dictionary because they are sparse.

Packed small integers have no separate storage at all when the array is the only reference to its elements: the values occupy the backing store the array always has, and the array’s kind records that each element there is an integer rather than a pointer. Packed doubles are the case where the kind changes what the store contains, because a double does not fit in a tagged word: each element becomes an eight-byte IEEE 754 value, so a thousand-element array occupies eight kilobytes of elements and no allocation per element. Packed tagged values store each element as a pointer, so the array occupies eight kilobytes of elements plus the storage of every element that is a heap object.

The distinction between small integers and doubles matters because the operations differ. Adding two small integers is an integer add; adding two doubles is a floating-point add; adding a small integer to a double requires converting one of them. An array whose kind is known to be small integers lets the compiler generate an integer loop with no conversions, and that is the fast case for counting and indexing.

Holes matter because a holey array cannot be read with a plain load that assumes a value is present. The sentinel has to be checked, and the check is a compare against a constant that no legitimate value can equal. Holey kinds exist separately from packed kinds so that the common case, an array with no holes, does not pay that compare.

How a kind changes

The transitions are driven by writes, and each transition is triggered by a write that the current kind cannot represent.

Writing a double into an array of small integers forces a transition to the double kind. The alternative, boxing the double and transitioning to the tagged kind, would be a larger change and would lose the ability to store the other elements unboxed. The runtime converts in place: it allocates a new backing store of doubles, converts each existing element, and updates the array’s kind and backing pointer.

Writing an arbitrary object into an array of doubles forces a transition to the tagged kind, because an object reference cannot be stored in eight bytes of IEEE 754. This transition converts every existing double into a boxed heap number, which is the expensive direction: each element becomes an allocation, and the array’s memory use grows by the size of the box plus the pointer.

Writing past the end of a packed array creates a hole if the index skips ahead, transitioning the kind from packed to holey. Writing at the exact end extends the array without creating a hole and does not change the kind. This distinction is why a[a.length] = v is cheap and a[i] = v with i far beyond the length is not: the second leaves a run of holes, and if the run is large enough the engine may convert the array to a dictionary.

const a = [1, 2, 3];       // packed small integers
a.push(4.5);               // -> packed doubles, existing elements converted
a.push({});                // -> packed tagged, doubles boxed
delete a[1];               // -> holey tagged

The sequence shows the ratchet. Each step is triggered by one write, and each step is more expensive than the last. The final step, delete, is a change of density rather than of element representation: the element is removed, the array becomes holey, and the kind keeps the tagged element type it already had.

Why the transitions are one-way

Converting an array of tagged values back to doubles would require proving that every element is a double, which is a scan of the whole array, and it would require that no compiled code holds a reference to the old backing store. The scan is O(n) and the reference problem is worse: compiled code may have cached the array’s backing pointer and its kind, and a change invalidates both.

Engines therefore do not promote, with narrow exceptions. An array created empty and then filled with doubles may be created directly with the double kind by the allocation-site feedback, because the site has seen doubles before and can allocate the right kind from the start. That is not a transition; it is a better initial guess, and it is the main reason the kind of an array literal is decided by the literal’s contents rather than by the first write.

The asymmetry has a consequence for how arrays should be built. An array that will hold doubles should be built with doubles from the first element, so that no conversion ever happens. An array whose elements are added one at a time in a loop is at the mercy of the loop’s first iteration; if that iteration writes an integer and later iterations write doubles, every later write checks for a transition that has already happened, and the array ends up as doubles after one conversion.

The check on the read path

A compiled read of a[i] with a known kind is a bounds check, a load, and, for the tagged kind, a check that distinguishes a pointer from an immediate before the value is used as a number. The bounds check compares i against the array’s length, which is held in the array header and is usually kept in a register across a loop. The load uses the kind’s scale factor.

The kind itself is checked by the inline cache guard, which is the same mechanism as a property access, and which is described in Monomorphic Inline Caches and the Guard That Makes Them Work. A site that has only ever seen the double kind holds that kind and a scale factor of eight; a site that has seen both the small-integer kind and the double kind holds two cases, and the second case converts the integer to a double before the arithmetic.

The interesting case is a loop over an array whose kind is stable. The kind check is hoisted out of the loop if the array is not modified inside it, because the guard is on the array’s header and the header cannot change without a write. If the loop writes to the array, the check has to stay, because a write can transition the kind and the array’s backing pointer can change under the loop.

That last point is the source of a common and non-obvious cost. A loop that both reads and writes an array cannot hoist the backing store pointer, so every iteration reloads it. A loop that only reads can. The difference is not the kind check itself but the loss of the invariant that the backing store does not move.

Sparse arrays and the dictionary fallback

An array with a small number of elements at large indices is not worth storing densely. Storing index 1,000,000 densely would allocate eight megabytes for one element, so engines convert to a dictionary keyed by index once the density falls below a threshold.

The threshold is a ratio, not an absolute count, and it is a tuning constant. The conversion is triggered by a write at an index far beyond the current length, or by enough deletes that the array is mostly holes. Once converted, the array is a hash table and every access is a lookup, with the cost described in The Dictionary Object Model and the Cost of a Name Lookup.

The conversion is one-way in the same sense as the others. An array that became a dictionary stays one, because the pattern that caused the conversion, large sparse indices, is not a pattern that reverses.

The behaviour that surprises is the interaction with length. A write at index 1,000,000 sets the length to 1,000,001 regardless of representation, so an array can be sparse and long at the same time. Iterating it with an index loop touches a million positions and finds one element; iterating with the language’s own iteration protocol visits only the present ones. The representation does not change that contract, but it does determine which iteration is cheap.

What the kinds are worth

The reason to have element kinds at all is that the alternative, an array of boxed values, makes every numeric loop pay for an allocation and a tag check per element. A loop summing a thousand doubles in a tagged array allocates nothing but dereferences a thousand pointers to heap numbers, each of which may be in a different cache line. The same loop over a packed double array reads eight kilobytes sequentially, which the prefetcher handles well.

The design constraint is that the representation must be inferable from the values the program actually writes, without any annotation from the programmer. That is what the kinds do: they are the runtime’s summary of what has been written, and the transitions are the runtime’s response to a write that the summary does not cover.

The limitation is that the summary is historical and can be wrong about the future. An array that has held only small integers for its whole life can receive a double at any point, and the code compiled around the integer kind must be prepared to deoptimize. The guard makes that safe, and the one-way transition makes it permanent, which is why a single unusual write to a hot array costs more than the write itself.