# Object Shapes implementation

Aaron Patterson, Eileen Uchitelle and I have been working on an implementation of Object Shapes for Ruby. We are filing a ticket to share what we've been doing, as well as get feedback on the project in its current state.

We hope to eventually submit the finalized project upstream after verifying efficacy.

## What are Object Shapes?

Object shapes are a technique for representing properties of an object. Other language implementations, including [TruffleRuby](https://github.com/oracle/truffleruby) and [V8](https://v8.dev/), use this technique. Chris Seaton, the creator of TruffleRuby, discussed object shapes in his [RubyKaigi 2021 Keynote](https://rubykaigi.org/2021-takeout/presentations/chrisgseaton.html) and Maxime Chevalier-Boisvert discussed the implications for YJIT in the latter part of [her talk at RubyKaigi 2021](https://www.youtube.com/watch?v=PBVLf3yfMs8&t=1100s). The original idea of object shapes [originates from the Self language](https://bibliography.selflanguage.org/_static/implementation.pdf), which is considered a direct descendant of Smalltalk.

Each shape represents a specific set of attributes (instance variables and other properties) and their values. In our implementation, all objects have a shape. The shapes are nodes in a tree data structure. Every edge in the tree represents an attribute transition.

More specifically, setting an instance variable on an instance of an object creates an outgoing edge from the instance's current shape. This is a transition from one shape to another. The edge represents the instance variable that is set.

For example:

class Foo
  def initialize
    # Currently this instance is the root shape (ID 0)
    @a = 1 # Transitions to a new shape via edge @a (ID 1)
    @b = 2 # Transitions to a new shape via edge @b (ID 2)
  end
end

foo = Foo.new

When `Foo` is intialized, its shape is the root shape with ID 0. The root shape represents an empty object with no instance variables. Each time an instance variable is set on `foo`, the shape of the instance changes. It first transitions with `@a` to a shape with ID 1, and then transitions with `@b` to a shape with ID 2. If `@a` is then set to a different value, its shape will remain the shape with ID 2, since this shape already includes the instance variable `@a`.


There is one global shape tree and objects which undergo the same shape transitions in the same order will end up with the same final shape.

For instance, if we have a class `Bar` defined as follows, the first transition on `Bar.new` through the instance variable `@a` will be the same as `Foo.new`'s first transition:

class Foo
  def initialize
    # Currently this instance is the root shape (ID 0)
    @a = 1 # Transitions to a new shape via edge @a (ID 1)
    @b = 2 # Transitions to a new shape via edge @b (ID 2)
  end
end

class Bar
  def initialize
    # Currently this instance is the root shape (ID 0)
    @a = 1 # Transitions to shape defined earlier via edge @a (ID 1)
    @c = 1 # Transitions to a new shape via edge @c (ID 3)
    @b = 1 # Transitions to a new shape via edge @b (ID 4)
  end
end

foo = Foo.new # blue in the diagram
bar = Bar.new # red in the diagram

In the diagram below, purple represents shared transitions, blue represents transitions for only `foo`, and red represents transitions for only `bar`.


### Cache structure

For instance variable writers, the current shape ID, the shape ID that ivar write would transition to and instance variable index are all stored in the inline cache. The shape ID is the key to the cache.

For instance variable readers, the shape ID and instance variable index are stored in the inline cache. Again, the shape ID is the cache key.

class Foo
  def initialize
    @a = 1 # IC shape_id: 0, next shape: 1, iv index 0
    @b = 1 # IC shape_id: 1, next shape: 2, iv index 1
  end
    
  def a
    @a # IC shape_id: 2, iv index 1
  end
end

## Rationale

We think that an object shape implementation will simplify cache checks, increase inline cache hits, decrease runtime checks, and enable other potential future optimizations. These are all explained below.

### Simplify caching

The current cache implementation depends on the class of the receiver. Since the address of the class can be reused, the current cache implementation also depends on an incrementing serial number set on the class (the class serial). The shape implementation has no such dependency. It only requires checking the shape ID to determine if the cache is valid.

### Cache hits

Objects that set properties in the same order can share shapes. For example:

class Hoge
  def initialize
    # Currently this instance is the root shape (ID 0)
    @a = 1 # Transitions to the next shape via edge named @a
    @b = 2 # Transitions to next shape via edge named @b
  end
end

class Fuga < Hoge; end

hoge = Hoge.new
fuga = Fuga.new

In the above example, the instances `hoge` and `fuga` will share the same shape ID. This means inline caches in `initialize` will hit in both cases. This contrasts with the current implementation that uses the class as the cache key. In other words, with object shapes the above code will hit inline caches where the current implementation will miss.

If performance testing reveals that cache hits are *not* substantially improved, then we can use shapes to reclaim memory from `RBasic`. We can accomplish this by encoding the class within the shape tree. This will have an equivalent cache hit rate to the current implementation. Once the class is encoded within the shape tree, we can remove the class pointer from `RBasic` and either reclaim that memory or free it for another use.

### Decreases runtime checking

We can encode attributes that aren't instance variables into an object's shape. Currently, we also include frozen within the shape. This means we can limit frozen checks to only cache misses.

For example, the following code:

class Toto
  def set_a
    @a = 1 # cache: shape: 0, next shape: 1, IV idx: 0
  end
end

toto = Toto.new # shape 0
toto.set_a     # shape 1

toto = Toto.new # shape 0
toto.freeze    # shape 2
toto.set_a     # Cache miss, Exception!


Without shapes, all instance variable sets require checking the frozen status of the object. With shapes, we only need to check the frozen status on cache misses.

We can also eliminate embedded and extended checks with the introduction of object shapes. Any particular shape represents an object that is _either_ extended or embedded. JITs can possibly take advantage of this fact by generating specialized machine code based on the shapes.

### Class instance variables can be stored in an array

Currently, `T_CLASS` and `T_MODULE` instances cannot use the same IV index table optimization that `T_OBJECT` instances use. We think that the object shapes technique can be leveraged by class instances to use arrays for class instance variable storage and may possibly lead to a reduction in memory usage (though we have yet to test this).

## Implementation Details

[Here](https://github.com/jemmaissroff/ruby/commit/4e95d01654f24ceff6c8330cf4e5c7dac504739e) is a link to our code so far.

As mentioned earlier, shape objects form a tree data structure. In order to look up the shape quickly, we also store the shapes in a weak array that is stored on the VM. The ID of the shape is the index in to the array, and the ID is stored on the object.

For `T_OBJECT` objects, we store the shape ID in the object's header. On 64 bit systems, the upper 32 bits are used by Ractors. We want object shapes to be enabled on 32 bit systems and 64 bit systems so that limits us to the bottom 32 bits of the Object header. The top 20 bits for `T_OBJECT` objects was unused, so we used the top 16 bits for the shape id. We chose the top 16 bits because this allows us to use `uint16_t` and masking the header bits is easier.

This implementation detail limits us to ~65k shapes. We measured the number of shapes used on a simple [Discourse](https://github.com/discourse/discourse) application (~3.5k), [RailsBench](https://github.com/k0kubun/railsbench) (~4k), and Shopify's monolith's test suite (~40k). Accordingly, we decided to implement garbage collection on object shapes so we can recycle shape IDs which are no longer in use. We are currently working on shape GC.

Even though it's unlikely, it's still possible for an application to run out of shapes. Once all shape IDs are in use, any objects that need new shape IDs will never hit on inline caches.

## Evaluation

We have so far tested this branch with [Discourse](https://github.com/discourse/discourse), [RailsBench](https://github.com/k0kubun/railsbench) and Shopify's monolith. We plan to test this branch more broadly against several open source Ruby and Rails applications.

Before we consider this branch to be ready for formal review, we want the runtime performance and memory usage of these benchmarks to be equivalent or better than it is currently. In our opinion, even with equivalent runtime performance and memory usage, the future benefits of this approach make the change seem worthwhile.

## Feedback

If you have any feedback, comments, or questions, please let us know and we'll do our best to address it. Thank you!