[ruby-core:109517] [Ruby master Feature#18776] Object Shapes

["jemmai (Jemma Issroff)" <noreply@ruby-lang.org>]

Issue #18776 has been updated by jemmai (Jemma Issroff).

File object-shapes.patch added

# Object Shapes Update

We are writing with an update on the Object Shapes implementation, and to ask what needs to be done before we can merge our work. I have continued work on this alongisde Aaron and Eileen.

## Code changes

[These](https://github.com/jemmaissroff/ruby/tree/object-shapes-prototyping) are our proposed code changes to implement Object Shapes in CRuby.

This patch adds an object shape implementation. Each object has a shape, which represents attributes of the object, such as which slots ivars are stored in and whether objects are frozen or not. The inline caches are updated to use shape IDs as the key, rather than the class of the object. This means we don't have to read the class from the object to check IC validity. It also allows more cache hits in some cases, and will allow JITs to optimize instance variable reading and writing.

The patch currently limits the number of available shape IDs to 65,536 (using 16 bits). We created a new IMEMO type that represents the shape, so shapes can be garbage collected.  Collected shape IDs can be reused later.

## CPU performance:

We measured performance with microbenchmarks, [RailsBench](https://github.com/k0kubun/railsbench), and [YJIT bench](https://github.com/Shopify/yjit-bench). Here are the performance metrics we gathered.

These are all microbenchmarks which measure ivar performance:

```
$ make benchmark ITEM=vm_ivar
compare-ruby: ruby 3.2.0dev (2022-08-16T15:58:56Z master ac890ec062) [arm64-darwin21]
built-ruby: ruby 3.2.0dev (2022-08-16T20:12:55Z object-shapes-prot.. 872fa488c3) [arm64-darwin21]
# Iteration per second (i/s)

|                           |compare-ruby|built-ruby|
|:--------------------------|-----------:|---------:|
|vm_ivar                    |     98.231M|  102.161M|
|                           |           -|     1.04x|
|vm_ivar_embedded_obj_init  |     33.351M|   33.331M|
|                           |       1.00x|         -|
|vm_ivar_extended_obj_init  |     25.055M|   26.265M|
|                           |           -|     1.05x|
|vm_ivar_generic_get        |     18.374M|   17.215M|
|                           |       1.07x|         -|
|vm_ivar_generic_set        |     12.361M|   14.537M|
|                           |           -|     1.18x|
|vm_ivar_of_class           |      8.378M|    8.928M|
|                           |           -|     1.07x|
|vm_ivar_of_class_set       |      9.485M|   10.264M|
|                           |           -|     1.08x|
|vm_ivar_set                |     89.411M|   91.632M|
|                           |           -|     1.02x|
|vm_ivar_init_subclass      |      6.104M|   12.928M|
|                           |           -|     2.12x|
```

To address the outliers above:
* `vm_ivar_generic_set` is faster because this patch adds inline caches to generic ivars, which did not exist previously
* `vm_ivar_init_subclass` is significantly faster because, with shapes, subclasses can hit caches (as class is no longer part of the cache key)

Object Shapes and Ruby master perform roughly the same on [RailsBench](https://github.com/k0kubun/railsbench).

On the following measurement, Ruby master had 1852.1 requests per second, while Object Shapes had 1842.7 requests per second.

```
$ RAILS_ENV=production bin/bench 
ruby 3.2.0dev (2022-08-15T14:00:03Z master 0264424d58) [arm64-darwin21]
1852.1
```

```
$ RAILS_ENV=production bin/bench 
ruby 3.2.0dev (2022-08-15T15:20:22Z object-shapes-prot.. d3dbefd6cd) [arm64-darwin21]
1842.7

```

## Memory performance

Each Ruby object contains a shape ID.  The shape ID corresponds to an index in an array. We can easily look up the shape object given a shape ID. Currently, we have a fixed size array which stores pointers to all active shapes (or NULL in the case that the shape is yet to be used). That array is ~64k * sizeof(uintptr_t) (about 500kb) and is currently a fixed size overhead for the Ruby process.

Running an empty Ruby script, we can see this overhead. For instance:

On Ruby master:

```
$ /usr/bin/time -l ruby -v -e' ' 
ruby 3.2.0dev (2022-08-15T14:00:03Z master 0264424d58) [arm64-darwin21]
28639232  maximum resident set size
```

With the shapes branch:

```
$ /usr/bin/time -l ./ruby -v -e' '
ruby 3.2.0dev (2022-08-15T15:20:22Z object-shapes-prot.. d3dbefd6cd) [arm64-darwin21]
28917760  maximum resident set size
```

This is roughly a 0.97% memory increase on an empty Ruby script. Obviously, on bigger Ruby processes, it would represent an even smaller memory increase.

## YJIT Statistics

We also ran YJIT-bench and got the following results:

on Ruby master:

```
end_time="2022-08-17 09:31:36 PDT (-0700)"
yjit_opts=""
ruby_version="ruby 3.2.0dev (2022-08-16T15:58:56Z master ac890ec062) [x86_64-linux]"
git_branch="master"
git_commit="ac890ec062"

-------------  -----------  ----------  ---------  ----------  -----------  ------------
bench          interp (ms)  stddev (%)  yjit (ms)  stddev (%)  interp/yjit  yjit 1st itr
30k_ifelse     2083.0       0.1         203.6      0.0         10.23        0.80        
30k_methods    5140.1       0.0         476.7      0.1         10.78        3.95        
activerecord   188.1        0.1         99.5       0.2         1.89         1.23        
binarytrees    804.8        0.1         409.2      1.1         1.97         1.93        
cfunc_itself   232.5        2.4         43.3       1.5         5.36         5.34        
chunky_png     2316.9       0.2         757.3      0.3         3.06         2.86        
erubi          412.1        0.4         281.3      1.0         1.46         1.47        
erubi_rails    31.1         2.2         17.4       2.7         1.78         0.33        
fannkuchredux  11414.6      0.2         2773.5     1.3         4.12         1.00        
fib            591.8        1.1         41.7       4.5         14.20        13.93       
getivar        234.2        3.1         23.5       0.1         9.95         1.00        
hexapdf        4755.7       1.0         2517.3     3.0         1.89         1.51        
keyword_args   520.7        0.6         54.6       0.2         9.55         9.24        
lee            2274.1       0.2         1133.3     0.2         2.01         1.98        
liquid-render  296.7        0.3         139.3      2.8         2.13         1.46        
mail           212.9        0.1         127.9      0.1         1.66         0.72        
nbody          225.4        0.2         78.3       0.2         2.88         2.70        
optcarrot      14592.1      0.7         4072.8     0.3         3.58         3.43        
psych-load     3947.8       0.0         2075.5     0.1         1.90         1.88        
railsbench     2826.0       0.6         1774.4     1.9         1.59         1.26        
respond_to     424.3        0.2         154.5      3.1         2.75         2.76        
rubykon        22545.1      0.4         6993.5     1.3         3.22         3.24        
setivar        185.9        5.6         97.0       0.0         1.92         1.00        
str_concat     123.1        0.9         28.6       2.0         4.31         3.35        
-------------  -----------  ----------  ---------  ----------  -----------  ------------
Legend:
- interp/yjit: ratio of interp/yjit time. Higher is better. Above 1 represents a speedup.
- 1st itr: ratio of interp/yjit time for the first benchmarking iteration.
```

with the shapes branch:

```
end_time="2022-08-16 13:56:32 PDT (-0700)"
yjit_opts=""
ruby_version="ruby 3.2.0dev (2022-08-15T18:35:34Z object-shapes-prot.. 51a23756c3) [x86_64-linux]"
git_branch="object-shapes-prototyping"
git_commit="51a23756c3"

-------------  -----------  ----------  ---------  ----------  -----------  ------------
bench          interp (ms)  stddev (%)  yjit (ms)  stddev (%)  interp/yjit  yjit 1st itr
30k_ifelse     2135.2       0.0         340.1      0.1         6.28         0.95        
30k_methods    5180.7       0.0         906.2      0.1         5.72         3.56        
activerecord   189.2        0.1         174.5      0.1         1.08         0.83        
binarytrees    783.2        1.0         438.7      2.5         1.79         1.82        
cfunc_itself   225.2        1.6         44.0       0.6         5.11         5.01        
chunky_png     2394.9       0.2         1657.0     0.2         1.45         1.44        
erubi          418.1        0.5         284.3      1.1         1.47         1.45        
erubi_rails    31.6         1.5         26.2       2.1         1.21         0.34        
fannkuchredux  12208.5      0.1         2821.6     0.4         4.33         0.99        
fib            565.7        0.3         41.3       0.1         13.69        13.59       
getivar        247.6        0.1         244.9      2.0         1.01         1.02        
hexapdf        4961.0       1.6         4926.1     0.9         1.01         0.94        
keyword_args   499.7        0.8         57.0       0.4         8.77         8.65        
lee            2360.0       0.6         2138.6     0.6         1.10         1.11        
liquid-render  294.7        0.7         274.9      1.4         1.07         0.91        
mail           216.6        0.1         157.7      0.7         1.37         0.70        
nbody          232.7        0.2         237.2      0.5         0.98         0.99        
optcarrot      15095.8      0.7         18309.2    0.5         0.82         0.83        
psych-load     4174.5       0.1         3707.9     0.1         1.13         1.13        
railsbench     2923.7       0.8         2548.4     1.4         1.15         0.98        
respond_to     409.2        0.3         162.6      1.7         2.52         2.52        
rubykon        22554.1      0.7         20160.6    0.9         1.12         1.10        
setivar        249.6        0.1         169.5      0.1         1.47         0.99        
str_concat     137.8        0.8         29.0       2.4         4.75         3.50        
-------------  -----------  ----------  ---------  ----------  -----------  ------------
Legend:
- interp/yjit: ratio of interp/yjit time. Higher is better. Above 1 represents a speedup.
- 1st itr: ratio of interp/yjit time for the first benchmarking iteration.
```

We are seeing some variations in YJIT benchmark numbers, and are working on addressing them.

## 32 bit architectures

We're storing the shape ID for T_OBJECT types in the top 32 bits of the flags field (sharing space with the ractor ID).  Consequently 32 bit machines do not benefit from this patch. This patch makes 32 bit machines always miss on inline caches.

## Instance variables with ID == 0

This is minor, but we also do not support instance variables whose ID is 0 because the outgoing edge tables are `id_table`s which do not support `0` as a key. There is [one test for this feature](https://github.com/ruby/ruby/blob/ac890ec0624e3d8a44d85d67127bc94322caa34e/test/-ext-/marshal/test_internal_ivar.rb#L9-L21), and we have marked it as pending in this patch.

## Merging

We think this feature is ready to merge. Please give us feedback, and let us know if it is possible to merge now. If it's not possible, please let us know what needs to be improved so that we can merge.

## Future work

We plan to work next on speeding up the class instance variables. We will implement caching for this, and see the full benefits of object shapes in this case.

----------------------------------------
Feature #18776: Object Shapes
https://bugs.ruby-lang.org/issues/18776#change-98686

* Author: jemmai (Jemma Issroff)
* Status: Open
* Priority: Normal
----------------------------------------
# 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:

```ruby
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`.  

![](https://user-images.githubusercontent.com/1988560/167918360-0a6c91aa-2587-48cb-8ff2-7f3a9583288e.svg)

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:

```ruby
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`.

![](https://user-images.githubusercontent.com/1988560/167918899-f1a6f344-ae5e-4dc0-b17a-fb156d1d550f.svg)

### 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.

```ruby
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:

```ruby
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:

```ruby
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!
```

![](https://user-images.githubusercontent.com/1988560/167920001-c4e6326b-3a3c-483b-a797-9e02317647d7.svg)

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!

---Files--------------------------------
object-shapes.patch (180 KB)


-- 
https://bugs.ruby-lang.org/