| Age | Commit message (Collapse) | Author |
|---|
| Notes: Merged: https://.com/ruby/ruby/pull/13283 |
| Notes: Merged: https://.com/ruby/ruby/pull/13283 |
| Notes: Merged: https://.com/ruby/ruby/pull/13283 |
| Notes: Merged: https://.com/ruby/ruby/pull/13283 |
| Notes: Merged: https://.com/ruby/ruby/pull/13283 |
| Notes: Merged: https://.com/ruby/ruby/pull/13283 |
| As well as `rb_shape_edges_count` and `rb_shape_memsize`. Notes: Merged: https://.com/ruby/ruby/pull/13283 |
| Notes: Merged: https://.com/ruby/ruby/pull/13283 |
| Notes: Merged: https://.com/ruby/ruby/pull/13283 |
| And get rid of the `obj_to_id_tbl` It's no longer needed, the `object_id` is now stored inline in the object alongside instance variables. We still need the inverse table in case `_id2ref` is invoked, but we lazily build it by walking the heap if that happens. The `object_id` concern is also no longer a GC implementation concern, but a generic implementation. Co-Authored-By: Matt Valentine-House <[email protected]> Notes: Merged: https://.com/ruby/ruby/pull/13159 |
| This opens the door to store more informations in shapes, such as the `object_id` or object address in case it has been observed and the object has to be moved. Notes: Merged: https://.com/ruby/ruby/pull/13159 |
| Also refactor checks for `->type == SHAPE_OBJ_TOO_COMPLEX`. Notes: Merged: https://.com/ruby/ruby/pull/13159 |
| Ivars will longer be the only thing stored inline via shapes, so keeping the `iv_index` and `ivptr` names would be confusing. Instance variables won't be the only thing stored inline via shapes, so keeping the `ivptr` name would be confusing. `field` encompass anything that can be stored in a VALUE array. Similarly, `gen_ivtbl` becomes `gen_fields_tbl`. Notes: Merged: https://.com/ruby/ruby/pull/13159 |
| Notes: Merged: https://.com/ruby/ruby/pull/13257 |
| Most of this code use the `type * name` style, while the overwhemling majority of the rest of ruby use the `type *name` style. This is a cosmetic change, but helps with readability. |
| Now that we've inlined the eden_heap into the size_pool, we should rename the size_pool to heap. So that Ruby contains multiple heaps, with different sized objects. The term heap as a collection of memory pages is more in memory management nomenclature, whereas size_pool was a name chosen out of necessity during the development of the Variable Width Allocation features of Ruby. The concept of size pools was introduced in order to facilitate different sized objects (other than the default 40 bytes). They wrapped the eden heap and the tomb heap, and some related state, and provided a reasonably simple way of duplicating all related concerns, to provide multiple pools that all shared the same structure but held different objects. Since then various changes have happend in Ruby's memory layout: * The concept of tomb heaps has been replaced by a global free pages list, with each page having it's slot size reconfigured at the point when it is resurrected * the eden heap has been inlined into the size pool itself, so that now the size pool directly controls the free_pages list, the sweeping page, the compaction cursor and the other state that was previously being managed by the eden heap. Now that there is no need for a heap wrapper, we should refer to the collection of pages containing Ruby objects as a heap again rather than a size pool Notes: Merged: https://.com/ruby/ruby/pull/11771 |
| [Bug #20522] If `Warning.warn` is redefined in Ruby, emitting a warning would invoke Ruby code, which can't safely be done when YJIT is compiling. |
| |
| |
| |
| On 32-bit systems, the shape cache size is 1048576 (value of REDBLACK_CACHE_SIZE), but a 16-bit unsigned integer can only go up to 65536. This means that the redblack_id_t can overflow and lead to a corrupted red-black tree. The following script crashes on 32-bit systems: o = Object.new 1_000_000.times do |i| o.instance_variable_set(:"@i#{i}", i) end |
| Too complex classes use a hash table to store ivs, and should always pin their IVs. We shouldn't touch those classes in compaction. |
| 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. |
| This reverts commit 5f3fb4f4e397735783743fe52a7899b614bece20. |
| This reverts commit f6910a61122931e4193bcc0fad18d839c319b720. We're seeing crashes in the test suite of Shopify's core monolith after this change. |
| 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. |
| 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. |
| 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 <[email protected]> |
| This commit makes every initial size pool shape a root shape and assigns it a capacity of 0. |
| `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. |
| If they are only used there, we might as well not expose them. |
| 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. |
| If it runs out of shapes, or new variations aren't allowed, it will return "too complex" |
| |
| |
| |
| 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. |
| This reverts commit e3afc212ec059525fe4e5387b2a3be920ffe0f0e. |
| 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. |
| This way the groth factor is encapsulated, which allows rb_shape_transition_shape_capa to be smarter about ideal sizes. |
| 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. Notes: Merged: https://.com/ruby/ruby/pull/7719 |
| Notes: Merged: https://.com/ruby/ruby/pull/7393 |
| 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) { | ^~ ``` |
| These functions don't need to be in the header file, we can declare them as static. Notes: Merged: https://.com/ruby/ruby/pull/7512 |
| 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 <[email protected]> Notes: Merged: https://.com/ruby/ruby/pull/7556 |
| 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 <[email protected]> Notes: Merged: https://.com/ruby/ruby/pull/7560 |
| Notes: Merged: https://.com/ruby/ruby/pull/7459 |
| Notes: Merged-By: k0kubun <[email protected]> |
| 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 Notes: Merged: https://.com/ruby/ruby/pull/7188 |
| Notes: Merged: https://.com/ruby/ruby/pull/7200 |
