Project

General

Profile

Actions

Feature #18776

open

Object Shapes

Added by jemmai (Jemma Issroff) about 2 months ago. Updated about 2 months ago.

Status:
Open
Priority:
Normal
Assignee:
-
Target version:
-
[ruby-core:108522]

Description

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 and V8, use this technique. Chris Seaton, the creator of TruffleRuby, discussed object shapes in his RubyKaigi 2021 Keynote and Maxime Chevalier-Boisvert discussed the implications for YJIT in the latter part of her talk at RubyKaigi 2021. The original idea of object shapes originates from the Self language, 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 0
  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 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 application (~3.5k), 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, 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!

Actions #1

Updated by tenderlovemaking (Aaron Patterson) about 2 months ago

  • Description updated (diff)
Actions #2

Updated by tenderlovemaking (Aaron Patterson) about 2 months ago

  • Description updated (diff)

Updated by ko1 (Koichi Sasada) about 2 months ago

Great patch.
I'm looking forward to seeing evaluation results.

Questions:

  • how to use parent id?
  • how to find next id with additional ivar?

Updated by byroot (Jean Boussier) about 2 months ago

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.

Might be a silly question, but how popular are 32bits systems these days? Would it be acceptable to make objects a bit bigger on 32 bits systems so that both 32bits and 64bits Ruby have a 32bit shape IDs?

Updated by jemmai (Jemma Issroff) about 2 months ago

Thanks for the feedback, Koichi.

ko1 (Koichi Sasada) wrote in #note-3:

  • how to use parent id?

The rb_shape type is as follows:

struct rb_shape {
    VALUE flags;
    struct rb_shape * parent;
    struct rb_id_table * edges;
    struct rb_id_table * iv_table;
    ID edge_name;
};

parent is a pointer on the shape itself, and we use it primarily for GC

  • how to find next id with additional ivar?

When we add a new ivar, if there is no transition we have to find a new ID. Right now we're doing a linear scan of available IDs. Once we're confident in shape ID GC, we'll switch the algorithm to something more efficient like using a bitmap

Updated by tenderlovemaking (Aaron Patterson) about 2 months ago

byroot (Jean Boussier) wrote in #note-4:

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.

Might be a silly question, but how popular are 32bits systems these days? Would it be acceptable to make objects a bit bigger on 32 bits systems so that both 32bits and 64bits Ruby have a 32bit shape IDs?

I'm not sure how popular 32 bit systems are, especially where high performance is a requirement. But I do think the broader question of "how much work should we do to support 32 bit systems?" is something we should think about. For now I think we can make shapes work well on 32 bit machines so I'm not too worried about it at this point (though it definitely would be easier if we had more than 16 bits 😆)

Updated by byroot (Jean Boussier) about 2 months ago

it definitely would be easier if we had more than 16 bits

Yeah, my worry is that while the Shopify monolith is probably among the bigger codebases, ~40k out of ~65k is really not that much leeway.

Updated by tenderlovemaking (Aaron Patterson) about 2 months ago

byroot (Jean Boussier) wrote in #note-7:

it definitely would be easier if we had more than 16 bits

Yeah, my worry is that while the Shopify monolith is probably among the bigger codebases, ~40k out of ~65k is really not that much leeway.

When we measured on Shopify core it was before we had started implementing shape GC. There were ~40k shapes, but that was the total number of shapes ever seen. Hopefully with shape GC we'll see a lower number of live shapes.

Updated by masterleep (Bill Lipa) about 2 months ago

If you call memoized methods in a different order, would that cause instances of the same class to have multiple shapes?

Updated by byroot (Jean Boussier) about 2 months ago

If you call memoized methods in a different order, would that cause instances of the same class to have multiple shapes?

Yes.

Updated by ko1 (Koichi Sasada) about 2 months ago

jemmai (Jemma Issroff) wrote in #note-5:

When we add a new ivar, if there is no transition we have to find a new ID. Right now we're doing a linear scan of available IDs. Once we're confident in shape ID GC, we'll switch the algorithm to something more efficient like using a bitmap

Ah, my question was how to find an existing transition.

Updated by ko1 (Koichi Sasada) about 2 months ago

struct rb_id_table * edges;

and I understand edges manages the next transitions. Thanks.

Actions

Also available in: Atom PDF