Optimize array pattern matching by caching #deconstruct value - #3104
Conversation
|
@k-tsj Could you please take a look? |
|
Great work. I am positive to merge this pull request. Could you add some tests? case [0]
in []
in [1] | [0]
true
end |
1c46f5a to
6641f05
Compare
|
@k-tsj Added some tests, found some bugs and fixed them 🙂 Unfortunately, the initial idea of including deconstruct instructions only in the first pattern doesn't work well with constant matching, since it's checked first.
|
998b0fe to
ea253ed
Compare
|
I found a bug. |
ea253ed to
a47b1ab
Compare
|
@k-tsj Fixed (and added a few more tests). |
|
Could you rebase to master? |
9e9373b to
bfa5f0b
Compare
|
@k-tsj Rebased and extracted this functionality into |
|
Oops, it seems that changes in 37cd877 cause conflict. |
bfa5f0b to
c9d05f4
Compare
|
@k-tsj Fixed! |
|
Thanks! |
2 participants
This is follow-up for the discussion started in #2948.
Overview
We can improve array patterns matching performance by keeping the result of the
#deconstructcall (or the fact, that the value doesn't respond to it).The solution proposed in this PR is the following:
compile_case3:#deconstructvalue (with the default valuenil— haven't tried to deconstruct)iseq_compile_pattern_each:deconstructed_posargument which is used to track the distance to the reserved slot (since it could be different depending on the node type).Benchmark
Compared with the current master (benchmark):
first_match ./ruby: 1137096.7 i/s /etc/ruby/bin/ruby: 1112537.0 i/s - 1.02x slower second_match ./ruby: 995800.6 i/s /etc/ruby/bin/ruby: 961526.1 i/s - 1.04x slower third_match ./ruby: 895467.2 i/s /etc/ruby/bin/ruby: 822866.8 i/s - 1.09x slower fourth_match ./ruby: 780673.0 i/s /etc/ruby/bin/ruby: 693164.3 i/s - 1.13x slowerLimitations & future ideas
Currently, only the top-level array patterns are affected. Adding a similar optimization to nested patterns would require additional (and, I think, in most cases useless) stack allocations. Thus, this approach is not optimal, still an ad-hoc optimization.
The proper solution would be to analyze the pattern tree first and generate an optimal execution path, which wouldn't have duplicate structural checks. I plan to work on this too, but that would require much more time than the proposed minor improvement. So, I think this patch is still worth to be considered.