aboutsummaryrefslogtreecommitdiffstats
path: root/shape.h
Commit message (Collapse)AuthorAgeFilesLines
* Don't try compacting ivars on Classes that are "too complex"Aaron Patterson2023-11-201-8/+0
| | | | | Too complex classes use a hash table to store ivs, and should always pin their IVs. We shouldn't touch those classes in compaction.
* Refactor rb_obj_evacuate_ivs_to_hash_tableJean Boussier2023-11-171-1/+0
| | | | | | | | | | | | | | | | | | That function is a bit too low level to called from multiple places. It's always used in tandem with `rb_shape_set_too_complex` and both have to know how the object is laid out to update the `iv_ptr`. So instead we can provide two higher level function: - `rb_obj_copy_ivs_to_hash_table` to prepare a `st_table` from an arbitrary oject. - `rb_obj_convert_to_too_complex` to assign the new `st_table` to the old object, and safely free the old `iv_ptr`. Unfortunately both can't be combined into one, because `rb_obj_copy_ivar` need `rb_obj_copy_ivs_to_hash_table` to copy from one object to another.
* Revert "Revert "Remove SHAPE_CAPACITY_CHANGE shapes""Peter Zhu2023-11-131-1/+0
| | | | This reverts commit 5f3fb4f4e397735783743fe52a7899b614bece20.
* Revert "Remove SHAPE_CAPACITY_CHANGE shapes"Peter Zhu2023-11-101-0/+1
| | | | | | | This reverts commit f6910a61122931e4193bcc0fad18d839c319b720. We're seeing crashes in the test suite of Shopify's core monolith after this change.
* Remove SHAPE_CAPACITY_CHANGE shapesPeter Zhu2023-11-091-1/+0
| | | | | We don't need to create a shape to transition capacity as we can transition the capacity when the capacity of the SHAPE_IVAR changes.
* Refactor rb_shape_transition_shape_capa outJean Boussier2023-11-081-1/+0
| | | | | | | | | | | | | | | | Right now the `rb_shape_get_next` shape caller need to first check if there is capacity left, and if not call `rb_shape_transition_shape_capa` before it can call `rb_shape_get_next`. And on each of these it needs to checks if we got a TOO_COMPLEX back. All this logic is duplicated in the interpreter, YJIT and RJIT. Instead we can have `rb_shape_get_next` do the capacity transition when needed. The caller can compare the old and new shapes capacity to know if resizing is needed. It also can check for TOO_COMPLEX only once.
* vm_getivar: assume the cached shape_id like have a common ancestorJean Boussier2023-11-031-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | When an inline cache misses, it is very likely that the stale shape_id and the current instance shape_id have a close common ancestor. For example if the instance variable is sometimes frozen sometimes not, one of the two shape will be the direct parent of the other. Another pattern that commonly cause IC misses is "memoization", in such case the object will have a "base common shape" and then a number of close descendants. In addition, when we find a common ancestor, we store it in the inline cache instead of the current shape. This help prevent the cache from flip-flopping, ensuring the next lookup will be marginally faster and more generally avoid writing in memory too much. However, now that shapes have an ancestors index, we only check for a few ancestors before falling back to use the index. So overall this change speeds up what is assumed to be the more common case, but makes what is assumed to be the less common case a bit slower. ``` compare-ruby: ruby 3.3.0dev (2023-10-26T05:30:17Z master 701ca070b4) [arm64-darwin22] built-ruby: ruby 3.3.0dev (2023-10-26T09:25:09Z shapes_double_sear.. a723a85235) [arm64-darwin22] warming up...... | |compare-ruby|built-ruby| |:------------------------------------|-----------:|---------:| |vm_ivar_stable_shape | 11.672M| 11.679M| | | -| 1.00x| |vm_ivar_memoize_unstable_shape | 7.551M| 10.506M| | | -| 1.39x| |vm_ivar_memoize_unstable_shape_miss | 11.591M| 11.624M| | | -| 1.00x| |vm_ivar_unstable_undef | 9.037M| 7.981M| | | 1.13x| -| |vm_ivar_divergent_shape | 8.034M| 6.657M| | | 1.21x| -| |vm_ivar_divergent_shape_imbalanced | 10.471M| 9.231M| | | 1.13x| -| ``` Co-Authored-By: John Hawthorn <john@hawthorn.email>
* Make every initial size pool shape a root shapePeter Zhu2023-11-021-1/+0
| | | | | This commit makes every initial size pool shape a root shape and assigns it a capacity of 0.
* remove_instance_variable: Handle running out of shapesJean Boussier2023-11-011-1/+1
| | | | | | | | `remove_shape_recursive` wasn't considering that if we run out of shapes, it might have to transition to SHAPE_TOO_COMPLEX. When this happens, we now return with an error and the caller initiates the evacuation.
* Move some defines from shape.h to shape.cJean Boussier2023-10-261-3/+0
| | | | If they are only used there, we might as well not expose them.
* Remove SHAPE_MAX_NUM_IVSAaron Patterson2023-10-241-1/+0
| | | | | | | | There is no longer a limit on the number of IVs you can store. SHAPE_MAX_NUM_IVS was used to work around the IV10K problem (the well known problem where setting 10k instance variables in a row would be too slow). The redblack tree works well at any shape depth, even depths greater than 80, and solves the IV10K problem.
* `get_next_shape_internal` should always return a shapeAaron Patterson2023-10-241-5/+5
| | | | | If it runs out of shapes, or new variations aren't allowed, it will return "too complex"
* geniv objects can become too complexAaron Patterson2023-10-241-2/+2
|
* remove IV limit / support complex shapes on classesAaron Patterson2023-10-241-2/+2
|
* increase the maximum number of ivsAaron Patterson2023-10-241-10/+10
|
* Use a functional red-black tree for indexing the shapesAaron Patterson2023-10-241-0/+15
| | | | | | | | | | | | | | | | | | | | | | | This is an experimental commit that uses a functional red-black tree to create an index of the ancestor shapes. It uses an Okasaki style functional red black tree: https://www.cs.tufts.edu/comp/150FP/archive/chris-okasaki/redblack99.pdf This tree is advantageous because: * It offers O(n log n) insertions and O(n log n) lookups. * It shares memory with previous "versions" of the tree When we insert a node in the tree, only the parts of the tree that need to be rebalanced are newly allocated. Parts of the tree that don't need to be rebalanced are not reallocated, so "new trees" are able to share memory with old trees. This is in contrast to a sorted set where we would have to duplicate the set, and also resort the set on each insertion. I've added a new stat to RubyVM.stat so we can understand how the red black tree increases.
* Revert "shape.h: Make attr_index_t uint8_t"Katherine Oelsner2023-10-181-2/+3
| | | | This reverts commit e3afc212ec059525fe4e5387b2a3be920ffe0f0e.
* shape.h: Make attr_index_t uint8_tJean Boussier2023-10-111-3/+2
| | | | | | | | | | Given `SHAPE_MAX_NUM_IVS 80`, we transition to TOO_COMPLEX way before we could overflow a 8bit counter. This reduce the size of `rb_shape_t` from 32B to 24B. If we decide to raise `SHAPE_MAX_NUM_IVS` we can always increase that type again.
* Refactor rb_shape_transition_shape_capa to not accept capacityJean Boussier2023-10-101-1/+1
| | | | | This way the groth factor is encapsulated, which allows rb_shape_transition_shape_capa to be smarter about ideal sizes.
* Move shape ID to flags for classes on 32 bitPeter Zhu2023-04-161-26/+22
| | | | | | Moves shape ID to FL_USER4 to FL_USER19 for the shape ID on 32 bit systems. This makes the rb_classext_struct smaller so that it can be embedded.
* Pull the shape tree out of the vm objectMatt Valentine-House2023-04-061-0/+15
|
* Adjust SHAPE_BUFFER_SIZE with shape_id_tNobuyoshi Nakada2023-03-241-3/+3
| | | | | | | | | | | | On platforms where `shape_id_t` is 16-bits, 0x80000 is out of range of this type. ``` ../src/shape.c: In function ‘shape_alloc’: ../src/shape.c:129:18: warning: comparison is always false due to limited range of data type [-Wtype-limits] 129 | if (shape_id == MAX_SHAPE_ID) { | ^~ ```
* Make shape functions staticAaron Patterson2023-03-221-4/+0
| | | | | These functions don't need to be in the header file, we can declare them as static.
* Fix shape allocation limitsAaron Patterson2023-03-221-2/+2
| | | | | | | | | | We can only allocate enough shapes to fit in the shape buffer. MAX_SHAPE_ID was based on the theoretical maximum number of shapes we could have, not on the amount of memory we can actually consume. This commit changes the MAX_SHAPE_ID to be based on the amount of memory we're allowed to consume. Co-Authored-By: Jemma Issroff <jemmaissroff@gmail.com>
* Use an st table for "too complex" objectsAaron Patterson2023-03-201-3/+3
| | | | | | | | | | st tables will maintain insertion order so we can marshal dump / load objects with instance variables in the same order they were set on that particular instance [ruby-core:112926] [Bug #19535] Co-Authored-By: Jemma Issroff <jemmaissroff@gmail.com>
* Stop exporting symbols for MJITTakashi Kokubun2023-03-061-4/+0
|
* Bump SHAPE_MAX_NUM_IVS to 80 (#7344)Takashi Kokubun2023-02-211-1/+1
|
* Limit maximum number of IVs on a shape on T_OBJECTSJemma Issroff2023-02-061-0/+1
| | | | | | | | | | | Create SHAPE_MAX_NUM_IVS (currently 50) and limit all shapes of T_OBJECTS to that number of IVs. When a shape with a T_OBJECT has more than 50 IVs, fall back to the obj_too_complex shape which uses hash lookup for ivs. Note that a previous version of this commit 78fcc9847a9db6d42c8c263154ec05903a370b6b was reverted in 88f2b94065be3fcd6769a3f132cfee8ecfb663b8 because it did not account for non-T_OBJECTS
* Remove dead code in shapes.c and shapes.hPeter Zhu2023-01-301-3/+0
|
* Revert "Limit maximum number of IVs on a shape"Aaron Patterson2023-01-261-1/+0
| | | | This reverts commit 78fcc9847a9db6d42c8c263154ec05903a370b6b.
* Limit maximum number of IVs on a shapeJemma Issroff2023-01-251-0/+1
| | | | | | Create SHAPE_MAX_NUM_IVS (currently 50) and limit all shapes to that number of IVs. When a shape has more than 50 IVs, fallback to the obj_too_complex shape which uses hash lookup for ivs.
* Remove unused function `rb_shape_flags_mask`Jemma Issroff2023-01-061-1/+0
|
* MJIT: Export fewer shape functions (#7007)Takashi Kokubun2022-12-231-6/+8
|
* Move definition of SIZE_POOL_COUNT back to gc.hPeter Zhu2022-12-151-8/+3
| | | | | | | | SIZE_POOL_COUNT is a GC macro, it should belong in gc.h and not shape.h. SIZE_POOL_COUNT doesn't depend on shape.h so we can have shape.h depend on gc.h. Co-Authored-By: Matt Valentine-House <matt@eightbitraptor.com>
* Fix Object Movement allocation in GCMatt Valentine-House2022-12-151-0/+2
| | | | | | | | | | | | | | | | | | | When moving Objects between size pools we have to assign a new shape. This happened during updating references - we tried to create a new shape tree that mirrored the existing tree, but based on the root shape of the new size pool. This causes allocations to happen if the new tree doesn't already exist, potentially triggering a GC, during GC. This commit changes object movement to look for a pre-existing new tree during object movement, and if that tree does not exist, we don't move the object to the new pool. This allows us to remove the shape allocation from update references. Co-Authored-By: Peter Zhu <peter@peterzhu.ca>
* Transition complex objects to "too complex" shapeJemma Issroff2022-12-151-3/+42
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | When an object becomes "too complex" (in other words it has too many variations in the shape tree), we transition it to use a "too complex" shape and use a hash for storing instance variables. Without this patch, there were rare cases where shape tree growth could "explode" and cause performance degradation on what would otherwise have been cached fast paths. This patch puts a limit on shape tree growth, and gracefully degrades in the rare case where there could be a factorial growth in the shape tree. For example: ```ruby class NG; end HUGE_NUMBER.times do NG.new.instance_variable_set(:"@unique_ivar_#{_1}", 1) end ``` We consider objects to be "too complex" when the object's class has more than SHAPE_MAX_VARIATIONS (currently 8) leaf nodes in the shape tree and the object introduces a new variation (a new leaf node) associated with that class. For example, new variations on instances of the following class would be considered "too complex" because those instances create more than 8 leaves in the shape tree: ```ruby class Foo; end 9.times { Foo.new.instance_variable_set(":@uniq_#{_1}", 1) } ``` However, the following class is *not* too complex because it only has one leaf in the shape tree: ```ruby class Foo def initialize @a = @b = @c = @d = @e = @f = @g = @h = @i = nil end end 9.times { Foo.new } `` This case is rare, so we don't expect this change to impact performance of most applications, but it needs to be handled. Co-Authored-By: Aaron Patterson <tenderlove@ruby-lang.org>
* Revert "Fix Object Movement allocation in GC"Peter Zhu2022-12-151-2/+0
| | | | | | This reverts commit 9c54466e299aa91af225bc2d92a3d7755730948f. We're seeing crashes in Shopify CI after this commit.
* Fix Object Movement allocation in GCMatt Valentine-House2022-12-151-0/+2
| | | | | | | | | | | | | | | | | | | When moving Objects between size pools we have to assign a new shape. This happened during updating references - we tried to create a new shape tree that mirrored the existing tree, but based on the root shape of the new size pool. This causes allocations to happen if the new tree doesn't already exist, potentially triggering a GC, during GC. This commit changes object movement to look for a pre-existing new tree during object movement, and if that tree does not exist, we don't move the object to the new pool. This allows us to remove the shape allocation from update references. Co-Authored-By: Peter Zhu <peter@peterzhu.ca>
* ObjectSpace.dump_all: dump shapes as wellJean Boussier2022-12-081-1/+8
| | | | | | | | | | | | | | | | | | | | | | | | | I see several arguments in doing so. First they use a non trivial amount of memory, so for various memory profiling/mapping tools it is relevant to have visibility of the space occupied by shapes. Then, some pathological code can create a tons of shape, so it is valuable to have a way to have a way to observe shapes without having to compile Ruby with `SHAPE_DEBUG=1`. And additionally it's likely much faster to dump then this way than to use `RubyVM::Shape`. There are however a few open questions: - Shapes can't respect the `since:` argument. Not sure what to do when it is provided. Would probably make sense to not dump them. - Maybe it would make more sense to have a separate `ObjectSpace.dump_shapes`? - Maybe instead `dump_all` should take a `shapes: false` argument? Additionally, `ObjectSpace.dump_shapes` is added for the use case of debugging the evolution of the shape tree.
* Stop transitioning to UNDEF when undefining an instance variableAaron Patterson2022-12-071-2/+2
| | | | | | | | | | | | | | | | | | | | | | | Cases like this: ```ruby obj = Object.new loop do obj.instance_variable_set(:@foo, 1) obj.remove_instance_variable(:@foo) end ``` can cause us to use many more shapes than we want (and even run out). This commit changes the code such that when an instance variable is removed, we'll walk up the shape tree, find the shape, then rebuild any child nodes that happened to be below the "targetted for removal" IV. This also requires moving any instance variables so that indexes derived from the shape tree will work correctly. Co-Authored-By: Jemma Issroff <jemmaissroff@gmail.com> Co-authored-by: John Hawthorn <jhawthorn@github.com>
* Remove unused rb_shape_flag_shift and rb_shape_flag_maskJemma Issroff2022-12-021-2/+0
|
* Extracted rb_shape_id_offsetJemma Issroff2022-12-021-0/+1
|
* implement IV writesAaron Patterson2022-12-021-0/+2
|
* Use consistent style [ci skip]Nobuyoshi Nakada2022-12-021-1/+2
|
* Let SHAPE_BITS take 32 bits on debug buildsPeter Zhu2022-11-211-12/+2
| | | | | The ractor_belonging_id has been moved out of the headers, so object shapes can take the top 32 bits of the flags on debug builds.
* 32 bit comparison on shape idAaron Patterson2022-11-181-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This commit changes the shape id comparisons to use a 32 bit comparison rather than 64 bit. That means we don't need to load the shape id to a register on x86 machines. Given the following program: ```ruby class Foo def initialize @foo = 1 @bar = 1 end def read [@foo, @bar] end end foo = Foo.new foo.read foo.read foo.read foo.read foo.read puts RubyVM::YJIT.disasm(Foo.instance_method(:read)) ``` The machine code we generated _before_ this change is like this: ``` == BLOCK 1/4, ISEQ RANGE [0,3), 65 bytes ====================== # getinstancevariable 0x559a18623023: mov rax, qword ptr [r13 + 0x18] # guard object is heap 0x559a18623027: test al, 7 0x559a1862302a: jne 0x559a1862502d 0x559a18623030: cmp rax, 4 0x559a18623034: jbe 0x559a1862502d # guard shape, embedded, and T_OBJECT 0x559a1862303a: mov rcx, qword ptr [rax] 0x559a1862303d: movabs r11, 0xffff00000000201f 0x559a18623047: and rcx, r11 0x559a1862304a: movabs r11, 0xb000000002001 0x559a18623054: cmp rcx, r11 0x559a18623057: jne 0x559a18625046 0x559a1862305d: mov rax, qword ptr [rax + 0x18] 0x559a18623061: mov qword ptr [rbx], rax == BLOCK 2/4, ISEQ RANGE [3,6), 0 bytes ======================= == BLOCK 3/4, ISEQ RANGE [3,6), 47 bytes ====================== # gen_direct_jmp: fallthrough # getinstancevariable # regenerate_branch # getinstancevariable # regenerate_branch 0x559a18623064: mov rax, qword ptr [r13 + 0x18] # guard shape, embedded, and T_OBJECT 0x559a18623068: mov rcx, qword ptr [rax] 0x559a1862306b: movabs r11, 0xffff00000000201f 0x559a18623075: and rcx, r11 0x559a18623078: movabs r11, 0xb000000002001 0x559a18623082: cmp rcx, r11 0x559a18623085: jne 0x559a18625099 0x559a1862308b: mov rax, qword ptr [rax + 0x20] 0x559a1862308f: mov qword ptr [rbx + 8], rax ``` After this change, it's like this: ``` == BLOCK 1/4, ISEQ RANGE [0,3), 41 bytes ====================== # getinstancevariable 0x5560c986d023: mov rax, qword ptr [r13 + 0x18] # guard object is heap 0x5560c986d027: test al, 7 0x5560c986d02a: jne 0x5560c986f02d 0x5560c986d030: cmp rax, 4 0x5560c986d034: jbe 0x5560c986f02d # guard shape 0x5560c986d03a: cmp word ptr [rax + 6], 0x19 0x5560c986d03f: jne 0x5560c986f046 0x5560c986d045: mov rax, qword ptr [rax + 0x10] 0x5560c986d049: mov qword ptr [rbx], rax == BLOCK 2/4, ISEQ RANGE [3,6), 0 bytes ======================= == BLOCK 3/4, ISEQ RANGE [3,6), 23 bytes ====================== # gen_direct_jmp: fallthrough # getinstancevariable # regenerate_branch # getinstancevariable # regenerate_branch 0x5560c986d04c: mov rax, qword ptr [r13 + 0x18] # guard shape 0x5560c986d050: cmp word ptr [rax + 6], 0x19 0x5560c986d055: jne 0x5560c986f099 0x5560c986d05b: mov rax, qword ptr [rax + 0x18] 0x5560c986d05f: mov qword ptr [rbx + 8], rax ``` The first ivar read is a bit more complex, but the second ivar read is much simpler. I think eventually we could teach the context about the shape, then emit only one shape guard.
* rename SHAPE_BITS to SHAPE_ID_NUM_BITSAaron Patterson2022-11-181-7/+7
|
* Differentiate T_OBJECT shapes from other objectsAaron Patterson2022-11-181-1/+2
| | | | | | | We would like to differentiate types of objects via their shape. This commit adds a special T_OBJECT shape when we allocate an instance of T_OBJECT. This allows us to avoid testing whether an object is an instance of a T_OBJECT or not, we can just check the shape.
* Remove unused function rb_shape_transition_shapePeter Zhu2022-11-141-1/+0
|
* Extract `rb_shape_get_parent` helperJemma Issroff2022-11-101-0/+1
| | | | | Extract an `rb_shape_get_parent` method instead of continually calling `rb_shape_get_shape_by_id(shape->parent_id)`
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-25 21:18:48 +0000