From: "jemmai (Jemma Issroff)" Date: 2022-09-15T19:23:18+00:00 Subject: [ruby-core:109904] [Ruby master Feature#18776] Object Shapes Issue #18776 has been updated by jemmai (Jemma Issroff). # Summary The implementation has been updated to solve some performance problems and simplify both source code and generated code. The performance of this branch against multiple benchmarks, including microbenchmarks, RailsBench and YJIT Bench show that the performance of Object Shapes is equivalent to, if not better than, the existing ivar implementation. We have also improved the memory overhead and made it half of what it was previously. Overall, code complexity has been decreased, memory overhead is small and performance is better or on par with `master`. We think this is a good state for this feature to be merged. We would like to get feedback from Ruby committers on [this PR](https://github.com/ruby/ruby/pull/6386) or in this issue for that reason. # Details Since our previous update, we have made the following changes: * The shape ID is now 32 bits on 64 bit machines when debugging is disabled. This gives us significantly more shapes in most cases. When debugging is enabled, Ractor check mode is also enabled. Ractor check mode [stores the Ractor ID in the flags bits](https://github.com/ruby/ruby/blob/abb1a273319e1cac8736253421a821d014f32ed7/ractor_core.h#L290-L304), and shapes needs to use that space too. Given this constraint, when debug mode is enabled Shapes only consumes 16 bits leaving the other 16 bits for Ractor IDs. * The shape ID is now stored in the upper 32 bits of the flags field. This ensures a consistent location for finding the shape id. All objects allocated from the heap will have their shape id stored in the top 32 bits. This simplifies looking up the shape id for a given object, which reduces code complexity. It also simplifies the machine code emitted from the JIT. * On platforms that support mmap, we now use mmap to allocate the shape list. Since mmap lazily maps to physical pages, this allows us to lazily allocate space for the shape list. # CPU performance These are our updated perfomance results: ## Microbenchmarks We ran microbenchmarks comparing master to object shapes and got the following results: ``` $ make benchmark ITEM=vm_ivar ... compare-ruby: ruby 3.2.0dev (2022-09-13T06:44:29Z master 316b44df09) [arm64-darwin21] built-ruby: ruby 3.2.0dev (2022-09-13T11:25:59Z object-shapes-prot.. ef42354c33) [arm64-darwin21] # Iteration per second (i/s) | |compare-ruby|built-ruby| |:--------------------------|-----------:|---------:| |vm_ivar | 100.020M| 108.705M| | | -| 1.09x| |vm_ivar_embedded_obj_init | 33.584M| 33.415M| | | 1.01x| -| |vm_ivar_extended_obj_init | 26.073M| 26.635M| | | -| 1.02x| |vm_ivar_generic_get | 16.599M| 18.103M| | | -| 1.09x| |vm_ivar_generic_set | 12.505M| 18.616M| | | -| 1.49x| |vm_ivar_get | 8.533| 8.566| | | -| 1.00x| |vm_ivar_get_uninitialized | 81.117M| 79.294M| | | 1.02x| -| |vm_ivar_lazy_set | 1.921| 1.949| | | -| 1.01x| |vm_ivar_of_class | 8.359M| 9.094M| | | -| 1.09x| |vm_ivar_of_class_set | 10.678M| 10.331M| | | 1.03x| -| |vm_ivar_set | 90.398M| 92.034M| | | -| 1.02x| |vm_ivar_set_on_instance | 14.269| 14.307| | | -| 1.00x| |vm_ivar_init_subclass | 6.048M| 13.029M| | | -| 2.15x| ``` Class instance variables have never benefited from inline caching, so always take the non-cached slow path. Object shapes made the slow path slower, so the `vm_ivar_of_class_set` benchmark slowdown is expected. As follow up to object shapes, @jhawthorn is planning to re-implement instance variables on classes to use arrays instead of `st_table`s. With his change, class instance variables will be able to realize the benefits of object shapes by taking the cached, fast path. ## Railsbench We ran Railsbench 10 times on master and shapes, and got the following results: RailsBench Box Plot Master: ``` ruby 3.2.0dev (2022-09-13T06:44:29Z master 316b44df09) [arm64-darwin21] Request per second: 1898.3 [#/s] (mean) Request per second: 1890.8 [#/s] (mean) Request per second: 1894.7 [#/s] (mean) Request per second: 1885.0 [#/s] (mean) Request per second: 1868.2 [#/s] (mean) Request per second: 1884.2 [#/s] (mean) Request per second: 1860.6 [#/s] (mean) Request per second: 1902.1 [#/s] (mean) Request per second: 1927.1 [#/s] (mean) Request per second: 1894.8 [#/s] (mean) ``` This averages to `1890.58` requests per second Shapes: ``` ruby 3.2.0dev (2022-09-13T11:25:59Z object-shapes-prot.. ef42354c33) [arm64-darwin21] Request per second: 1901.9 [#/s] (mean) Request per second: 1900.1 [#/s] (mean) Request per second: 1903.1 [#/s] (mean) Request per second: 1902.2 [#/s] (mean) Request per second: 1905.2 [#/s] (mean) Request per second: 1903.0 [#/s] (mean) Request per second: 1910.7 [#/s] (mean) Request per second: 1916.3 [#/s] (mean) Request per second: 1905.6 [#/s] (mean) Request per second: 1894.4 [#/s] (mean) ``` This averages to `1904.25` requests per second ## YJIT Bench: We ran YJIT Bench on master and shapes, excluding benchmarks which do not measure instance variables, and got the following results: Master: ``` ruby_version="ruby 3.2.0dev (2022-09-13T06:44:29Z master 316b44df09) [x86_64-linux]" git_branch="master" git_commit="316b44df09" ------------- ----------- ---------- --------- ---------- ----------- ------------ bench interp (ms) stddev (%) yjit (ms) stddev (%) interp/yjit yjit 1st itr activerecord 115.5 0.3 74.7 2.1 1.55 1.31 chunky_png 748.0 0.1 500.9 0.1 1.49 1.46 erubi 260.4 0.6 202.8 1.0 1.28 1.25 erubi_rails 18.4 2.0 13.2 3.5 1.39 0.50 getivar 91.9 1.4 23.1 0.2 3.98 0.98 hexapdf 2183.0 0.9 1479.4 3.0 1.48 1.31 liquid-render 144.3 0.4 87.6 1.5 1.65 1.32 mail 125.6 0.2 104.5 0.3 1.20 0.81 optcarrot 5013.9 0.7 2227.7 0.5 2.25 2.20 psych-load 1804.1 0.1 1333.0 0.0 1.35 1.35 railsbench 1933.3 1.1 1442.5 1.6 1.34 1.20 rubykon 9838.4 0.4 4915.1 0.2 2.00 2.11 setivar 64.9 1.4 27.9 3.1 2.32 1.01 ``` Shapes: ``` ruby_version="ruby 3.2.0dev (2022-09-13T11:25:59Z object-shapes-prot.. ef42354c33) [x86_64-linux]" git_branch="object-shapes-prototyping" git_commit="ef42354c33" ------------- ----------- ---------- --------- ---------- ----------- ------------ bench interp (ms) stddev (%) yjit (ms) stddev (%) interp/yjit yjit 1st itr activerecord 118.6 0.1 76.4 0.2 1.55 1.27 chunky_png 760.5 0.2 488.8 0.3 1.56 1.52 erubi 252.4 0.6 199.9 1.0 1.26 1.25 erubi_rails 18.5 2.5 13.7 3.3 1.35 0.53 getivar 89.8 1.2 23.3 0.0 3.85 1.00 hexapdf 2364.9 1.0 1649.2 2.8 1.43 1.30 liquid-render 147.3 0.6 90.3 1.7 1.63 1.30 mail 128.7 0.3 106.0 0.2 1.21 0.82 optcarrot 5170.7 0.8 2681.7 0.3 1.93 1.88 psych-load 1786.4 0.1 1480.2 0.0 1.21 1.20 railsbench 1988.9 0.8 1482.4 1.7 1.34 1.23 rubykon 9729.6 1.2 4841.3 1.7 2.01 2.17 setivar 61.6 0.3 32.2 0.1 1.91 1.00 ``` Here are comparison numbers between the two measurements. (> 1 means shapes is faster, < 1 means master is faster): ``` bench interp (shapes / master) yjit (shapes / master) activerecord 1.03 1.02 chunky_png 1.02 0.98 erubi 0.97 0.99 erubi_rails 1.01 1.04 getivar 0.98 1.01 hexapdf 1.08 1.11 liquid-render 1.02 1.03 mail 1.02 1.01 optcarrot 1.03 1.20 psych-load 0.99 1.11 railsbench 1.03 1.03 rubykon 0.99 0.98 setivar 0.95 1.15 ``` # Memory consumption Due to the mmap change, our memory consumption has decreased since our last update. Measuring execution of an empty script over 10 runs, we saw an average consumption of 29,107,814 bytes on master, and 29,273,293 bytes with object shapes. This means on an empty script, shapes has a 0.5% memory increase. Obviously, this difference would represent a significantly lower percentage memory increase on larger, production-scale applications. # Code complexity We have reduced overall code complexity by: * Removing the `iv_index` table on the class and replacing it with a shape tree which can be used independent of object types * Reducing the checks in the set instance variable and get instance variable cached code paths by removing the frozen check, class serial check and `vm_ic_entry_p` check in favor of a shape check. The code below is the fast code path (cache hit case) for setting instance variables. (Assertions and debug counters removed for clarity.) Master: ```c if (LIKELY(!RB_OBJ_FROZEN_RAW(obj))) { if (LIKELY( (vm_ic_entry_p(ic) && ic->entry->class_serial == RCLASS_SERIAL(RBASIC(obj)->klass)))) { if (UNLIKELY(index >= ROBJECT_NUMIV(obj))) { rb_init_iv_list(obj); } VALUE *ptr = ROBJECT_IVPTR(obj); RB_OBJ_WRITE(obj, &ptr[index], val); return val; } } ``` Shapes: ```c shape_id_t shape_id = ROBJECT_SHAPE_ID(obj); if (shape_id == source_shape_id) { if (dest_shape_id != shape_id) { if (UNLIKELY(index >= ROBJECT_NUMIV(obj))) { rb_init_iv_list(obj); } ROBJECT_SET_SHAPE_ID(obj, dest_shape_id); } VALUE *ptr = ROBJECT_IVPTR(obj); RB_OBJ_WRITE(obj, &ptr[index], val); return val; } ``` * Reducing the number of instructions for instance variable access in YJIT. Here are the x86_64 assembly code instructions generated by YJIT which represent guard comparisons for getting instance variables: Master: ``` # guard known class 0x55cfff14857a: movabs rcx, 0x7f3e1fceb0f8 0x55cfff148584: cmp qword ptr [rax + 8], rcx 0x55cfff148588: jne 0x55d007137491 0x55cfff14858e: mov rax, qword ptr [r13 + 0x18] # Is the IV in range? 0x55cfff148592: cmp qword ptr [rax + 0x10], 0 0x55cfff148597: jbe 0x55d007137446 # guard embedded getivar # Is object embedded? 0x55cfff14859d: test word ptr [rax], 0x2000 0x55cfff1485a2: je 0x55d0071374aa ``` Shapes: ``` # guard shape, embedded, and T_* 0x55a89f8c7cff: mov rcx, qword ptr [rax] 0x55a89f8c7d02: movabs r11, 0xffff00000000201f 0x55a89f8c7d0c: and rcx, r11 0x55a89f8c7d0f: movabs r11, 0x58000000002001 0x55a89f8c7d19: cmp rcx, r11 0x55a89f8c7d1c: jne 0x55a8a78b5d4e ``` The shapes code has one comparison and one memory read whereas the master code has three comparisons and four memory reads. # Conclusion As we said at the beginning of this update, based on the metrics and rationale described above, we think object shapes is ready to merge. Please give us feedback [on our PR](https://github.com/ruby/ruby/pull/6386) or this issue. Thank you! ---------------------------------------- Feature #18776: Object Shapes https://bugs.ruby-lang.org/issues/18776#change-99147 * 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/ Unsubscribe: