Eliminate the performance impact of operands' order in array's | and &
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
b for the best performance. The right answers for current implementation are
longer & shorter and
longer | shorter.
Here 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 shows 20-30% perf improvement of Array#union.
Updated by sawa (Tsuyoshi Sawada) 4 months ago
- Backport deleted (
2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN)
- ruby -v deleted (
- Description updated (diff)
- Subject changed from Eliminate the performance impact of operands order in array's | and & to Eliminate the performance impact of operands' order in array's | and &
- Tracker changed from Bug to Feature
Updated by mame (Yusuke Endoh) 4 months ago
I like the idea very much, but very unfortunately, the document of
The order is preserved from the original array.
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.