diff options
author | Aaron Patterson <tenderlove@ruby-lang.org> | 2023-02-07 17:46:42 -0800 |
---|---|---|
committer | Aaron Patterson <aaron.patterson@gmail.com> | 2023-10-24 10:52:06 -0700 |
commit | 84e4453436c3549b4fda6014cdd5fcc9e0b80755 (patch) | |
tree | f0fdc61a51a8f1cfa5eb9b534103d1534a29b5ae /benchmark | |
parent | 5c4978c11c4ea9569d5d99a86936fbef0ab7fa52 (diff) | |
download | ruby-84e4453436c3549b4fda6014cdd5fcc9e0b80755.tar.gz |
Use a functional red-black tree for indexing the shapes
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.
Diffstat (limited to 'benchmark')
-rw-r--r-- | benchmark/vm_ivar_ic_miss.yml | 20 |
1 files changed, 20 insertions, 0 deletions
diff --git a/benchmark/vm_ivar_ic_miss.yml b/benchmark/vm_ivar_ic_miss.yml new file mode 100644 index 0000000000..f20ca7efac --- /dev/null +++ b/benchmark/vm_ivar_ic_miss.yml @@ -0,0 +1,20 @@ +prelude: | + class Foo + def initialize diverge + if diverge + @a = 1 + end + + @a0 = @a1 = @a2 = @a3 = @a4 = @a5 = @a6 = @a7 = @a8 = @a9 = @a10 = @a11 = @a12 = @a13 = @a14 = @a15 = @a16 = @a17 = @a18 = @a19 = @a20 = @a21 = @a22 = @a23 = @a24 = @a25 = @a26 = @a27 = @a28 = @a29 = @a30 = @a31 = @a32 = @a33 = @a34 = @a35 = @a36 = @a37 = @a38 = @a39 = @a40 = @a41 = @a42 = @a43 = @a44 = @a45 = @a46 = @a47 = @a48 = @a49 = @a50 = @a51 = @a52 = @a53 = @a54 = @a55 = @a56 = @a57 = @a58 = @a59 = @a60 = @a61 = @a62 = @a63 = @a64 = @a65 = @a66 = @a67 = @a68 = @a69 = @a70 = @a71 = @a72 = @a73 = @a74 = @b = 1 + end + + def b; @b; end + end + + a = Foo.new false + b = Foo.new true +benchmark: + vm_ivar_ic_miss: | + a.b + b.b +loop_count: 30000000 |