[ruby-core:99541] [Ruby master Feature#17109] Eliminate the performance impact of operands' order in array's | and &
From:
eregontp@...
Date:
2020-08-10 13:28:39 UTC
List:
ruby-core #99541
Issue #17109 has been updated by Eregon (Benoit Daloze).
[set.rb](https://github.com/ruby/ruby/blob/master/lib/set.rb) has this optimization for `intersection` and IMHO `Set` should be used explicitly if you expect high-performance Set operations.
----------------------------------------
Feature #17109: Eliminate the performance impact of operands' order in array's | and &
https://bugs.ruby-lang.org/issues/17109#change-87000
* Author: andrey.samsonov@gmail.com (Andrey Samsonov)
* Status: Open
* Priority: Normal
----------------------------------------
When I do intersection (`a & b`) or union (`a | b`), usually the array in one position is more likely longer than the one in the other position. I always try to remember in what order I should write `a` and` b` for the best performance. The right answers for current implementation are `longer & shorter` and` longer | shorter`.
[Here](https://github.com/kryzhovnik/ruby/commit/3b5923746792db5a73bc80a2cb9fe982d41a9fa3) I suggest to make it simpler and eliminate the difference.
Sorry I don't know C. Though I suppose my solution might be too blunt and verbose, I hope it demonstrates the idea.
make benchmark ITEM=array_union COMPARE_RUBY=~/.rbenv/versions/2.8.0-dev/bin/ruby
| |compare-ruby|built-ruby|
|:-------------------------|-----------:|---------:|
|small-& | 4.315M| 4.228M|
| | 1.02x| -|
|small-intersection | 4.157M| 4.106M|
| | 1.01x| -|
|big-& | 107.258k| 132.051k|
| | -| 1.23x|
|big-intersection | 103.245k| 128.052k|
| | -| 1.24x|
|big-reverse-intersection | 96.544k| 159.201k|
| | -| 1.65x|
My own [test](https://gist.github.com/kryzhovnik/288953a5c89df10e2611668703a1511c) shows 20-30% perf improvement of Array#union.
--
https://bugs.ruby-lang.org/
Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>