diff options
author | Aaron Patterson <tenderlove@ruby-lang.org> | 2024-03-30 17:29:09 -0700 |
---|---|---|
committer | Aaron Patterson <aaron.patterson@gmail.com> | 2024-03-30 19:24:36 -0700 |
commit | 9579cf45d59f313e70a6a8dab2e9173743513e91 (patch) | |
tree | 53ac08e962c95fd75bd2f6c42e6184cf6546a5be | |
parent | 376ae22235dd50fee32ab7660c17137b7f3a245e (diff) |
If we have a shape cache we should use it
If there is a shape cache, then we should believe the results instead of
doing a linear search for non-existent items
This fixes a case where checking the index of an undefined ivar would
result in an O(n) search. Now we get O(log n).
Benchmark is as follows:
```ruby
N = ARGV[0].to_i
class ManyIVs
class_eval "def initialize;" +
N.times.map { "@a#{_1} = #{_1}" }.join("\n") +
"end"
def check
defined?(@not)
end
end
class Subclass < ManyIVs
def initialize
super
@foo = 123
end
end
def t
s = Process.clock_gettime Process::CLOCK_MONOTONIC
yield
Process.clock_gettime(Process::CLOCK_MONOTONIC) - s
end
def test
a = ManyIVs.new
b = Subclass.new
t { 200000.times { a.check; b.check } }
end
puts "#{N},#{test}"
```
On the master branch:
```
$ for i in (seq 1 3 32); ./miniruby test.rb $i; end
1,0.015619999991031364
4,0.013061000005109236
7,0.013365999999223277
10,0.015474999992875382
13,0.017674999980954453
16,0.020055999979376793
19,0.02260500000556931
22,0.0254080000158865
25,0.02806599999894388
28,0.031244999991031364
31,0.034568000002764165
```
On this branch:
```
$ for i in (seq 1 3 32); ./miniruby test.rb $i; end
1,0.015848999988520518
4,0.013225000002421439
7,0.013049000001046807
10,0.010697999998228624
13,0.010902000009082258
16,0.011448000004747882
19,0.01151199999731034
22,0.011539999977685511
25,0.01173300002119504
28,0.011900000012246892
31,0.012278999987756833
```
-rw-r--r-- | shape.c | 8 |
1 files changed, 7 insertions, 1 deletions
@@ -863,7 +863,13 @@ rb_shape_get_iv_index(rb_shape_t *shape, ID id, attr_index_t *value) RUBY_ASSERT(rb_shape_id(shape) != OBJ_TOO_COMPLEX_SHAPE_ID); if (!shape_cache_get_iv_index(shape, id, value)) { - return shape_get_iv_index(shape, id, value); + // If it wasn't in the ancestor cache, then don't do a linear search + if (shape->ancestor_index && shape->next_iv_index >= ANCESTOR_CACHE_THRESHOLD) { + return false; + } + else { + return shape_get_iv_index(shape, id, value); + } } return true; |