ROM Colors

Copyright 2020 Moddable Tech, Inc.
Revised: August 12, 2020

Opportunity

In XS, instances are mostly linked list of properties with a key and a value. To get a value by key, the runtime iterates the linked list to find a property with a matching key.

Of course XS already implements several optimizations to access properties by index: in array instances, in closures, in global and local scopes.

The XS linker prepares most classes, objects, prototypes, functions to be accessed straightly from ROM. Such instances and their properties never change. That is an opportunity to access properties by index, especially since iterating a linked list in ROM is not optimal.

Intuitively indexes could be chosen for keys, then instances could be rearranged to have matching properties at that index. But if indexes are chosen too naively, instances and properties could take a lot of memory. So a technique is necessary to choose indexes while keeping instances and properties as dense as possible.

Graph Coloring

The technique is based on graph coloring. Similar techniques are applied to object programming languages for decades. See for instance:

• André and Royer, Optimizing method search with lookup caches and incremental coloring, OOPSLA '92 proceedings.

• Driesen, Selector table indexing & sparse arrays, OOPSLA '93 proceedings.

When intrinsics and all modules are preloaded, the XS linker traverses all instances and their properties to build a conflict graph. The nodes are the keys, the edges are the conflicts. Two keys conflict if there is an instance that has properties for both keys. Choosing indexes for keys is equivalent to coloring nodes in the graph.

Once the graph is colored, each key has a color that can be used to access a property by index.

property = instance[key.color]

Since non conflicting keys can reuse the same color, the runtime has to check if the property matches the key.

if (property.key == key)
	return property

Optimal graph coloring could be complex, but coloring from the most to the least conflicted key usually gives good enough results: the number of colors is significantly smaller than the number of keys.

Memory Layout

What remains to be done is to reorganize the ROM so properties are where the color of their key wants them to be.

Instances and properties are slots. Initially the XS linker allocates slots in the order instances and properties are created.

For instance, here are part of the Math object with a few properties, followed by the JSON object.

Firstly keys are colored. Since keys can conflict in several instances, their colors are never sequential.

Secondly the properties are moved to the color of their key:

That is enough to access properties by index but there are holes! Here above slots 2, 7, 8, and 9 are unused. Graph coloring minimizes the number of colors, but because of conflicts, some instances can be sparse.

Eventually instances are moved to fill the holes.

Now the two objects are intertwined to reduce the memory footprint. There are usually enough instances without properties or with a few properties to fill all holes.

Despite all movements, the order of the linked lists is maintained. That is required by several object traversal functions.

Results

Here is a simple test.

const math = Math;
const now = Date.now();
for (let i = 0; i < 100000; i++) {
	math.imul(i, 1)
	math.max(i, 0)
	math.min(i, 0)
	math.sign(i)
}
trace((Date.now() - now) + "\n");

The Math object is in ROM and its imul, max, min and sign properties are accessed 100000 times. The Math object is cached into a const to avoid the interference of global scope optimizations, the properties are selected to avoid floating point operations.

Here are results without and with the optimization:

That is interesting: less the device is performant, more the gain is significant.