Implement Object Shapes #6386

jemmaissroff · 2022-09-15T19:15:38Z

This commit implements the Object Shapes technique in CRuby. Object Shapes is used for accessing instance variables and representing the "frozenness" of objects. Object instances have a "shape" and the shape represents some attributes of the object (currently which instance variables are set and the "frozenness"). Shapes form a tree data structure, and when a new instance variable is set on an object, that object "transitions" to a new shape in the shape tree. Each shape has an ID that is used for caching. The shape structure is independent of class, so objects of different types can have the same shape.

For example:

class Foo
  def initialize
    # Starts with shape id 0
    @a = 1 # transitions to shape id 1
    @b = 1 # transitions to shape id 2
  end
end

class Bar
  def initialize
    # Starts with shape id 0
    @a = 1 # transitions to shape id 1
    @b = 1 # transitions to shape id 2
  end
end

foo = Foo.new # `foo` has shape id 2
bar = Bar.new # `bar` has shape id 2

Both foo and bar instances have the same shape because they both set instance variables of the same name in the same order.

This technique can help to improve inline cache hits as well as generate more efficient machine code in JIT compilers.

This commit also adds some methods for debugging shapes on objects. See RubyVM::Shape for more details.

For more context on Object Shapes, see [Feature: #18776]

Co-Authored-By: Aaron Patterson tenderlove@ruby-lang.org
Co-Authored-By: Eileen M. Uchitelle eileencodes@gmail.com

ko1 · 2022-09-22T07:08:01Z

include/ruby/internal/fl_type.h

-    }
-}
+RUBY_SYMBOL_EXPORT_BEGIN
+void rb_obj_freeze_inline(VALUE obj);


inline function is used for performance but is it hard to keep inline?

It seems like the idea is to avoid exporting rb_shape_transition_shape_frozen as C API.

I think it's okay to make it a non-inline function for C API users even while the _inline name becomes a lie, but as Koichi said, it's worth checking if it impacts the interpreter's performance. If it does, you could define it as an inline function in an internal header, and use it as the implementation of (non-inline) rb_obj_freeze_inline.

Thanks for flagging this. Yes, we removed the inline because we didn't want to export the shape transition function.

I added a new benchmark for measuring freezing objects.

Running this benchmark, it looks like there's no performance change on freezing objects:

compare-ruby: ruby 3.2.0dev (2022-09-20T13:25:05Z master b3d8dddee7) [arm64-darwin21] built-ruby: ruby 3.2.0dev (2022-09-21T21:33:46Z object-shapes-prot.. d3003b71e3) [arm64-darwin21] # Iteration per second (i/s) | |compare-ruby|built-ruby| |:--------------|-----------:|---------:| |vm_freeze_obj | 364.956| 364.985| | | -| 1.00x|

👍 Thank you for confirming it.

k0kubun · 2022-09-22T14:42:40Z

configure.ac

@@ -3724,6 +3724,25 @@ AS_IF([test x"$MJIT_SUPPORT" = "xyes"],

 AC_SUBST(MJIT_SUPPORT)

+AC_ARG_ENABLE(compile-commands,


It'd be nice to remove the diff of #6352 from this PR.

k0kubun · 2022-09-22T14:49:16Z

lib/mjit/compiler.rb

@@ -73,23 +73,6 @@ def compile_body(f, iseq, status)
      src << "#undef GET_SELF\n"
      src << "#define GET_SELF() cfp_self\n"

-      # Generate merged ivar guards first if needed


I think you shouldn't have deleted the merge_ivar_guards_p optimization because checking RB_TYPE_P(obj, T_OBJECT) for self multiple times remains to be redundant. Now this place should check only RB_TYPE_P(GET_SELF(), T_OBJECT) and then the check should be removed from the following places when merge_ivar_guards_p.

Sorry, didn't mean to remove this. Should be fixed now!

k0kubun · 2022-09-22T15:18:50Z

Great job. My comment about MJIT #6386 (comment) is not a blocker because I can easily fix it as long as I'm aware that it was removed. However, I do want you to check #6386 (comment) because it's performance-related. #6386 (comment) is fairly trivial, but it's obvious that it should be removed.

I have zero experience of using imemo even today, so I'll leave it for other committers to review how it's used for shapes.

P.S. I misclicked the close button while cleaning up dust on my trackpad. I'm sorry 🙇

k0kubun · 2022-09-22T22:12:40Z

FYI, #6418 caused a conflict and I fixed it myself at 50d113e (I just re-executed the new bindgen.rb). I wanted to avoid force-pushing your branch, so I just pushed a merge commit. We could use "Squash and merge" if you don't want to rebase it and fix the same conflict again.

k0kubun

👍

@A

Object Shapes is used for accessing instance variables and representing the "frozenness" of objects. Object instances have a "shape" and the shape represents some attributes of the object (currently which instance variables are set and the "frozenness"). Shapes form a tree data structure, and when a new instance variable is set on an object, that object "transitions" to a new shape in the shape tree. Each shape has an ID that is used for caching. The shape structure is independent of class, so objects of different types can have the same shape. For example: ```ruby class Foo def initialize # Starts with shape id 0 @A = 1 # transitions to shape id 1 @b = 1 # transitions to shape id 2 end end class Bar def initialize # Starts with shape id 0 @A = 1 # transitions to shape id 1 @b = 1 # transitions to shape id 2 end end foo = Foo.new # `foo` has shape id 2 bar = Bar.new # `bar` has shape id 2 ``` Both `foo` and `bar` instances have the same shape because they both set instance variables of the same name in the same order. This technique can help to improve inline cache hits as well as generate more efficient machine code in JIT compilers. This commit also adds some methods for debugging shapes on objects. See `RubyVM::Shape` for more details. For more context on Object Shapes, see [Feature: #18776] Co-Authored-By: Aaron Patterson <tenderlove@ruby-lang.org> Co-Authored-By: Eileen M. Uchitelle <eileencodes@gmail.com> Co-Authored-By: John Hawthorn <john@hawthorn.email>

ivoanjo · 2022-09-27T20:26:56Z

This is amazing, congrats for getting this merged in! :)

YurySolovyov · 2022-09-27T20:30:21Z

I think it got reverted at 06abfa5

jaynetics · 2022-12-24T22:03:37Z

The revert was reverted in ad63b66

matzbot requested a review from a team September 15, 2022 19:16

jemmaissroff force-pushed the object-shapes branch from 985c6d8 to 6422f8d Compare September 21, 2022 22:05

ko1 reviewed Sep 22, 2022

View reviewed changes

maximecb requested review from k0kubun and XrXr September 22, 2022 14:01

k0kubun reviewed Sep 22, 2022

View reviewed changes

k0kubun closed this Sep 22, 2022

k0kubun reopened this Sep 22, 2022

matzbot requested a review from a team September 22, 2022 15:14

jemmaissroff force-pushed the object-shapes branch from 6422f8d to fe77e03 Compare September 22, 2022 17:30

k0kubun approved these changes Sep 22, 2022

View reviewed changes

maximecb approved these changes Sep 23, 2022

View reviewed changes

jemmaissroff force-pushed the object-shapes branch 2 times, most recently from 8e2fa28 to ecd2b50 Compare September 23, 2022 18:02

jemmaissroff force-pushed the object-shapes branch from ecd2b50 to 3fae3b1 Compare September 24, 2022 14:02

tenderlove merged commit 9ddfd2c into ruby:master Sep 26, 2022

jhawthorn mentioned this pull request Oct 26, 2022

Implement object shapes for T_CLASS and T_MODULE #6637

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Implement Object Shapes #6386

Implement Object Shapes #6386

jemmaissroff commented Sep 15, 2022

ko1 Sep 22, 2022

k0kubun Sep 22, 2022

jemmaissroff Sep 22, 2022

k0kubun Sep 22, 2022

k0kubun Sep 22, 2022

k0kubun Sep 22, 2022 •

edited

Loading

jemmaissroff Sep 23, 2022

k0kubun commented Sep 22, 2022 •

edited

Loading

k0kubun commented Sep 22, 2022 •

edited

Loading

k0kubun left a comment

ivoanjo commented Sep 27, 2022

YurySolovyov commented Sep 27, 2022

jaynetics commented Dec 24, 2022

		@@ -3724,6 +3724,25 @@ AS_IF([test x"$MJIT_SUPPORT" = "xyes"],

		AC_SUBST(MJIT_SUPPORT)

		AC_ARG_ENABLE(compile-commands,

Implement Object Shapes #6386

Implement Object Shapes #6386

Conversation

jemmaissroff commented Sep 15, 2022

ko1 Sep 22, 2022

Choose a reason for hiding this comment

k0kubun Sep 22, 2022

Choose a reason for hiding this comment

jemmaissroff Sep 22, 2022

Choose a reason for hiding this comment

k0kubun Sep 22, 2022

Choose a reason for hiding this comment

k0kubun Sep 22, 2022

Choose a reason for hiding this comment

k0kubun Sep 22, 2022 • edited Loading

Choose a reason for hiding this comment

jemmaissroff Sep 23, 2022

Choose a reason for hiding this comment

k0kubun commented Sep 22, 2022 • edited Loading

k0kubun commented Sep 22, 2022 • edited Loading

k0kubun left a comment

Choose a reason for hiding this comment

ivoanjo commented Sep 27, 2022

YurySolovyov commented Sep 27, 2022

jaynetics commented Dec 24, 2022

k0kubun Sep 22, 2022 •

edited

Loading

k0kubun commented Sep 22, 2022 •

edited

Loading

k0kubun commented Sep 22, 2022 •

edited

Loading