| Age | Commit message (Collapse) | Author |
|---|
|
This commit allows the shape tree to be traversed to locate an existing
shape, but it doesn't necessarily allow you to create new variations.
|
|
We always create new shapes until we run out!
|
|
|
|
|
|
We're only going to create a redblack tree on platforms that have mmap
|
|
|
|
|
|
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.
|
|
|
|
Previously the growth was 3(embed), 6, 12, 24, ...
With this change it's now 3(embed), 8, 16, 32, 64, ... by default.
However, since power of two isn't the best size for all allocators,
if `malloc_usable_size` is vailable, we use it to discover the best
offset.
On Linux/glibc 2.35 for instance, the growth will be 3(embed), 7, 15, 31
to avoid wasting 8B per object.
Test program:
```c
size_t test(size_t slots) {
size_t allocated = slots * VALUE_SIZE;
void *test_ptr = malloc(allocated);
size_t wasted = malloc_usable_size(test_ptr) - allocated;
free(test_ptr);
fprintf(stderr, "slots = %lu, wasted_bytes = %lu\n", slots, wasted);
return wasted;
}
int main(int argc, char *argv[]) {
size_t best_padding = 0;
size_t padding = 0;
for (padding = 0; padding <= 2; padding++) {
size_t wasted = test(8 - padding);
if (wasted == 0) {
best_padding = padding;
break;
}
}
size_t index = 0;
fprintf(stderr, "=============== naive ================\n");
size_t list_size = 4;
for (index = 0; index < 10; index++) {
test(list_size);
list_size *= 2;
}
fprintf(stderr, "=============== auto-padded (-%lu) ================\n", best_padding);
list_size = 4;
for (index = 0; index < 10; index ++) {
test(list_size - best_padding);
list_size *= 2;
}
fprintf(stderr, "\n\n");
return 0;
}
```
```
===== glibc ======
slots = 8, wasted_bytes = 8
slots = 7, wasted_bytes = 0
=============== naive ================
slots = 4, wasted_bytes = 8
slots = 8, wasted_bytes = 8
slots = 16, wasted_bytes = 8
slots = 32, wasted_bytes = 8
slots = 64, wasted_bytes = 8
slots = 128, wasted_bytes = 8
slots = 256, wasted_bytes = 8
slots = 512, wasted_bytes = 8
slots = 1024, wasted_bytes = 8
slots = 2048, wasted_bytes = 8
=============== auto-padded (-1) ================
slots = 3, wasted_bytes = 0
slots = 7, wasted_bytes = 0
slots = 15, wasted_bytes = 0
slots = 31, wasted_bytes = 0
slots = 63, wasted_bytes = 0
slots = 127, wasted_bytes = 0
slots = 255, wasted_bytes = 0
slots = 511, wasted_bytes = 0
slots = 1023, wasted_bytes = 0
slots = 2047, wasted_bytes = 0
```
```
========== jemalloc =======
slots = 8, wasted_bytes = 0
=============== naive ================
slots = 4, wasted_bytes = 0
slots = 8, wasted_bytes = 0
slots = 16, wasted_bytes = 0
slots = 32, wasted_bytes = 0
slots = 64, wasted_bytes = 0
slots = 128, wasted_bytes = 0
slots = 256, wasted_bytes = 0
slots = 512, wasted_bytes = 0
slots = 1024, wasted_bytes = 0
slots = 2048, wasted_bytes = 0
=============== auto-padded (-0) ================
slots = 4, wasted_bytes = 0
slots = 8, wasted_bytes = 0
slots = 16, wasted_bytes = 0
slots = 32, wasted_bytes = 0
slots = 64, wasted_bytes = 0
slots = 128, wasted_bytes = 0
slots = 256, wasted_bytes = 0
slots = 512, wasted_bytes = 0
slots = 1024, wasted_bytes = 0
slots = 2048, wasted_bytes = 0
```
|
|
This way the groth factor is encapsulated, which allows
rb_shape_transition_shape_capa to be smarter about ideal sizes.
|
|
|
|
[Feature #19538]
Since that category is not enabled by default, making it a
verbose warning is redundant. Enabling performance warning should
work with the default verbosity level.
Notes:
Merged: https://github.com/ruby/ruby/pull/7733
|
|
During compaction we must fix up shapes on objects who were extended but
then became embedded. `rb_shape_traverse_from_new_root` is supposed to
walk shape trees looking for a matching shape. When a shape has a
"single child" we weren't returning NULL when the edge names didn't
match.
In the case of a single outgoing edge, this patch returns NULL when the
child edge name doesn't match (similar to the case when a shape has a
hash of outgoing edges)
Notes:
Merged: https://github.com/ruby/ruby/pull/7735
|
|
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://github.com/ruby/ruby/pull/7719
|
|
[Feature #19538]
This new `peformance` warning category is disabled by default.
It needs to be specifically enabled via `-W:performance` or `Warning[:performance] = true`
Notes:
Merged: https://github.com/ruby/ruby/pull/7708
|
|
NEWOBJ_OF is now our canonical newobj macro. It takes an optional ec
Notes:
Merged: https://github.com/ruby/ruby/pull/7393
|
|
Notes:
Merged: https://github.com/ruby/ruby/pull/7393
|
|
This patch lazily allocates id tables for shape children. If a shape
has only one single child, it tags the child with a bit. When we read
children, if the id table has the bit set, we know it's a single child.
If we need to add more children, then we create a new table and evacuate
the child to the new table.
Co-Authored-By: Matt Valentine-House <matt@eightbitraptor.com>
Notes:
Merged: https://github.com/ruby/ruby/pull/7512
|
|
Notes:
Merged: https://github.com/ruby/ruby/pull/7512
|
|
Notes:
Merged: https://github.com/ruby/ruby/pull/7512
|
|
These functions don't need to be in the header file, we can declare them
as static.
Notes:
Merged: https://github.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 <jemmaissroff@gmail.com>
Notes:
Merged: https://github.com/ruby/ruby/pull/7556
|
|
[Bug #19536]
When objects are moved between size pools, their frozen status is lost
in the shape. This will cause the frozen check to be bypassed when there
is an inline cache. For example, the following script should raise a
FrozenError, but doesn't on Ruby 3.2 and master.
class A
def add_ivars
@a = @b = @c = @d = 1
end
def set_a
@a = 10
end
end
a = A.new
a.add_ivars
a.freeze
b = A.new
b.add_ivars
b.set_a # Set the inline cache in set_a
GC.verify_compaction_references(expand_heap: true, toward: :empty)
a.set_a
Notes:
Merged: https://github.com/ruby/ruby/pull/7553
|
|
This reverts commit 69465df4242f3b2d8e55fbe18d7c45b47b40a626.
|
|
This makes the behavior of classes and modules when there are too many instance variables match the behavior of objects with too many instance variables.
Notes:
Merged: https://github.com/ruby/ruby/pull/7349
|
|
Notes:
Merged: https://github.com/ruby/ruby/pull/7459
|
|
Notes:
Merged: https://github.com/ruby/ruby/pull/7459
|
|
Notes:
Merged: https://github.com/ruby/ruby/pull/7314
|
|
Co-authored-by: Adam Hess <hparker@github.com>
Notes:
Merged: https://github.com/ruby/ruby/pull/7314
|
|
[Feature #19425]
Notes:
Merged: https://github.com/ruby/ruby/pull/7273
|
|
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://github.com/ruby/ruby/pull/7188
|
|
Notes:
Merged: https://github.com/ruby/ruby/pull/7200
|
|
This reverts commit 78fcc9847a9db6d42c8c263154ec05903a370b6b.
|
|
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.
Notes:
Merged: https://github.com/ruby/ruby/pull/7183
|
|
Under strict aliasing, writing to the memory location of a different
type is not allowed and will result in undefined behavior. This was
happening in shape.c due to `rb_id_table_lookup` writing to the memory
location of `VALUE *` that was casted from a `rb_shape_t **`.
This was causing test failures when compiled with LTO.
Fixes [Bug #19248]
Co-Authored-By: Alan Wu <alanwu@ruby-lang.org>
Notes:
Merged: https://github.com/ruby/ruby/pull/7067
|
|
RubyVM::Shape is usually not available (you need SHAPE_DEBUG macro,
which is not defined by default). So it seems confusing to leave
RubyVM::Shape in the document.
This hides only method definitions because, well, I can't find a way to
hide things defined by rb_define_const or rb_struct_define_under. I gave
up making the C-based documentation right. You should define things in
Ruby instead.
|
|
Make printing shapes better, use a struct instead of specific methods
for each field on a shape.
Co-Authored-By: Aaron Patterson <tenderlove@ruby-lang.org>
Notes:
Merged: https://github.com/ruby/ruby/pull/6942
|
|
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>
Notes:
Merged: https://github.com/ruby/ruby/pull/6938
|
|
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>
Notes:
Merged: https://github.com/ruby/ruby/pull/6931
|
|
Count how many "variations" each class creates. A "variation" is a a
unique ordering of instance variables on a particular class. This can
also be thought of as a branch in the shape tree.
For example, the following Foo class will have 2 variations:
```ruby
class Foo ; end
Foo.new.instance_variable_set(:@a, 1) # case 1: creates one variation
Foo.new.instance_variable_set(:@b, 1) # case 2: creates another variation
foo = Foo.new
foo.instance_variable_set(:@a, 1) # does not create a new variation
foo.instance_variable_set(:@b, 1) # does not create a new variation (a continuation of the variation in case 1)
```
We will use this number to limit the amount of shapes that a class can
create and fallback to using a hash iv lookup.
Co-Authored-By: Aaron Patterson <tenderlove@ruby-lang.org>
Notes:
Merged: https://github.com/ruby/ruby/pull/6931
|
|
This reverts commit 9c54466e299aa91af225bc2d92a3d7755730948f.
We're seeing crashes in Shopify CI after this commit.
|
|
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>
Notes:
Merged: https://github.com/ruby/ruby/pull/6926
|
|
If the rb_id_table_lookup fails, then res is not updated so it cannot be
any value other than null.
Notes:
Merged: https://github.com/ruby/ruby/pull/6928
|
|
Since edc7af48acd12666a2945f30901d16b62a39f474, we now no longer have
undef ivar transitions. Instead, we rebuild the shapes table. When we do
this, we need to ensure that we retain our capacities on shapes.
Notes:
Merged: https://github.com/ruby/ruby/pull/6894
|
|
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.
Notes:
Merged: https://github.com/ruby/ruby/pull/6868
|
|
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>
Notes:
Merged: https://github.com/ruby/ruby/pull/6866
|
|
Notes:
Merged-By: k0kubun <takashikkbn@gmail.com>
|
|
Notes:
Merged: https://github.com/ruby/ruby/pull/6767
|
|
Notes:
Merged: https://github.com/ruby/ruby/pull/6767
|
