* [ruby-core:99526] [Ruby master Bug#17109] Eliminate the performance impact of operands in array's | and &
@ 2020-08-09 21:52 andrey.samsonov
2020-08-09 22:51 ` [ruby-core:99527] [Ruby master Bug#17109] Eliminate the performance impact of operands order " sawadatsuyoshi
` (4 more replies)
0 siblings, 5 replies; 6+ messages in thread
From: andrey.samsonov @ 2020-08-09 21:52 UTC (permalink / raw)
To: ruby-core
Issue #17109 has been reported by andrey.samsonov@gmail.com (Andrey Samsonov).
----------------------------------------
Bug #17109: Eliminate the performance impact of operands in array's | and &
https://bugs.ruby-lang.org/issues/17109
* Author: andrey.samsonov@gmail.com (Andrey Samsonov)
* Status: Open
* Priority: Normal
* ruby -v: 2.8
* Backport: 2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN
----------------------------------------
When I do intersection (`a & b`) or union (` a | b`) usually one of the arrays is more likely longer than the second one. I always try to remember in what order should I 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/
^ permalink raw reply [flat|nested] 6+ messages in thread
* [ruby-core:99527] [Ruby master Bug#17109] Eliminate the performance impact of operands order in array's | and &
2020-08-09 21:52 [ruby-core:99526] [Ruby master Bug#17109] Eliminate the performance impact of operands in array's | and & andrey.samsonov
@ 2020-08-09 22:51 ` sawadatsuyoshi
2020-08-10 8:12 ` [ruby-core:99534] [Ruby master Feature#17109] Eliminate the performance impact of operands' " grzegorz.jakubiak
` (3 subsequent siblings)
4 siblings, 0 replies; 6+ messages in thread
From: sawadatsuyoshi @ 2020-08-09 22:51 UTC (permalink / raw)
To: ruby-core
Issue #17109 has been updated by sawa (Tsuyoshi Sawada).
`a & b` returns different result from `b & a`. `a | b` returns different result from `b | a`. You cannot substitute one with another.
----------------------------------------
Bug #17109: Eliminate the performance impact of operands order in array's | and &
https://bugs.ruby-lang.org/issues/17109#change-86987
* Author: andrey.samsonov@gmail.com (Andrey Samsonov)
* Status: Open
* Priority: Normal
* ruby -v: 2.8
* Backport: 2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN
----------------------------------------
When I do intersection (`a & b`) or union (` a | b`) usually one of the arrays is more likely longer than the second one. I always try to remember in what order should I 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/
^ permalink raw reply [flat|nested] 6+ messages in thread
* [ruby-core:99534] [Ruby master Feature#17109] Eliminate the performance impact of operands' order in array's | and &
2020-08-09 21:52 [ruby-core:99526] [Ruby master Bug#17109] Eliminate the performance impact of operands in array's | and & andrey.samsonov
2020-08-09 22:51 ` [ruby-core:99527] [Ruby master Bug#17109] Eliminate the performance impact of operands order " sawadatsuyoshi
@ 2020-08-10 8:12 ` grzegorz.jakubiak
2020-08-10 8:32 ` [ruby-core:99536] " mame
` (2 subsequent siblings)
4 siblings, 0 replies; 6+ messages in thread
From: grzegorz.jakubiak @ 2020-08-10 8:12 UTC (permalink / raw)
To: ruby-core
Issue #17109 has been updated by greggzst (Grzegorz Jakubiak).
I mean these operations essentially perform Set union and intersection, am I correct? Then the order of the operands doesn't affect the outcome.
----------------------------------------
Feature #17109: Eliminate the performance impact of operands' order in array's | and &
https://bugs.ruby-lang.org/issues/17109#change-86994
* 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/
^ permalink raw reply [flat|nested] 6+ messages in thread
* [ruby-core:99536] [Ruby master Feature#17109] Eliminate the performance impact of operands' order in array's | and &
2020-08-09 21:52 [ruby-core:99526] [Ruby master Bug#17109] Eliminate the performance impact of operands in array's | and & andrey.samsonov
2020-08-09 22:51 ` [ruby-core:99527] [Ruby master Bug#17109] Eliminate the performance impact of operands order " sawadatsuyoshi
2020-08-10 8:12 ` [ruby-core:99534] [Ruby master Feature#17109] Eliminate the performance impact of operands' " grzegorz.jakubiak
@ 2020-08-10 8:32 ` mame
2020-08-10 12:27 ` [ruby-core:99540] " andrey.samsonov
2020-08-10 13:28 ` [ruby-core:99541] " eregontp
4 siblings, 0 replies; 6+ messages in thread
From: mame @ 2020-08-10 8:32 UTC (permalink / raw)
To: ruby-core
Issue #17109 has been updated by mame (Yusuke Endoh).
I like the idea very much, but very unfortunately, the document of `Array#&` says:
> The order is preserved from the original array.
https://docs.ruby-lang.org/en/2.7.0/Array.html#method-i-26
Personally I agree with you that this is a set operation so the guarantee of the order looks strange, but anyway, this optimization brings a change of the spec.
----------------------------------------
Feature #17109: Eliminate the performance impact of operands' order in array's | and &
https://bugs.ruby-lang.org/issues/17109#change-86996
* 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/
^ permalink raw reply [flat|nested] 6+ messages in thread
* [ruby-core:99540] [Ruby master Feature#17109] Eliminate the performance impact of operands' order in array's | and &
2020-08-09 21:52 [ruby-core:99526] [Ruby master Bug#17109] Eliminate the performance impact of operands in array's | and & andrey.samsonov
` (2 preceding siblings ...)
2020-08-10 8:32 ` [ruby-core:99536] " mame
@ 2020-08-10 12:27 ` andrey.samsonov
2020-08-10 13:28 ` [ruby-core:99541] " eregontp
4 siblings, 0 replies; 6+ messages in thread
From: andrey.samsonov @ 2020-08-10 12:27 UTC (permalink / raw)
To: ruby-core
Issue #17109 has been updated by andrey.samsonov@gmail.com (Andrey Samsonov).
> > The order is preserved from the original array.
My bad, I missed the comment. In this case, I think the optimisation is not worth a change in the spec.
----------------------------------------
Feature #17109: Eliminate the performance impact of operands' order in array's | and &
https://bugs.ruby-lang.org/issues/17109#change-86999
* 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/
^ permalink raw reply [flat|nested] 6+ messages in thread
* [ruby-core:99541] [Ruby master Feature#17109] Eliminate the performance impact of operands' order in array's | and &
2020-08-09 21:52 [ruby-core:99526] [Ruby master Bug#17109] Eliminate the performance impact of operands in array's | and & andrey.samsonov
` (3 preceding siblings ...)
2020-08-10 12:27 ` [ruby-core:99540] " andrey.samsonov
@ 2020-08-10 13:28 ` eregontp
4 siblings, 0 replies; 6+ messages in thread
From: eregontp @ 2020-08-10 13:28 UTC (permalink / raw)
To: ruby-core
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/
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2020-08-10 13:28 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-08-09 21:52 [ruby-core:99526] [Ruby master Bug#17109] Eliminate the performance impact of operands in array's | and & andrey.samsonov
2020-08-09 22:51 ` [ruby-core:99527] [Ruby master Bug#17109] Eliminate the performance impact of operands order " sawadatsuyoshi
2020-08-10 8:12 ` [ruby-core:99534] [Ruby master Feature#17109] Eliminate the performance impact of operands' " grzegorz.jakubiak
2020-08-10 8:32 ` [ruby-core:99536] " mame
2020-08-10 12:27 ` [ruby-core:99540] " andrey.samsonov
2020-08-10 13:28 ` [ruby-core:99541] " eregontp
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).