Shapes

[egranata]

Shapes are basically what Python's adaptive LOAD_ATTR (in Python's bytecode) and modern JavaScript VMs do to optimize attribute lookup

When an object is first built, it starts at "empty shape". Each time an attribute X is written, it transitions to the shape of "I had this list of attributes written to me", e.g.

val foo = Box(); # empty shape
foo.x = 1; # shape [x]
foo.y = 2; # shape [x,y]
foo.z = 3; # shape [x,y,z]
foo.x = 2; # shape [x,y,z]

Hashtables of attributes by name are replaced by symbols (which are globally uniqued int mappings of attribute names); symbols are then stored in integer-indexed slots and looked up by shape, so in our example

shape [x] -> {slot(x) = 0}
shape [x,y] -> {slot(x) = 0 slot(y) = 1}
shape [x,y,z] -> {slot(x) = 0 slot(y) = 1 slot(z) = 2}

With all that plumbing, you can then go to each READ_ATTRIBUTE (in Aria's bytecode) and discover that, for example, you're always reading the attribute at slot 2, so you can replace READ_ATTRIBUTE Symbol(z) with LOAD_SLOT 2 and make attribute read O(1) in the happy case

[egranata]

Shape support is pretty basic at this point. Main things missing:

• sidecar allocation may be too expensive, since a Cell is brought up for every opcode but is empty for most of them;
• policy on disabling shape optimization on ReadAttributeSymbol needs to be improved (see comments on Enable sidecar to optimize reading of attributes #494 (comment) for details);
• operator lookup does not follow optimized path (goes through read_attribute instead of resolving via shapes);
• can enum cases also be optimized with shapes?;
• can bound methods be cached somehow?