Project

General

Profile

Feature #17109

Eliminate the performance impact of operands' order in array's | and &

Added by andrey.samsonov@gmail.com (Andrey Samsonov) 4 months ago. Updated 4 months ago.

Status:
Rejected
Priority:
Normal
Assignee:
-
Target version:
-
[ruby-core:99526]

Description

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 andb for the best performance. The right answers for current implementation are longer & shorter andlonger | 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.

#1

Updated by andrey.samsonov@gmail.com (Andrey Samsonov) 4 months ago

  • Subject changed from Eliminate the performance impact of operands in array's | and & to Eliminate the performance impact of operands order in array's | and &

Updated by sawa (Tsuyoshi Sawada) 4 months ago

a & b returns different result from b & a. a | b returns different result from b | a. You cannot substitute one with another.

Furthermore, your idea is implementation-dependent.

It does not make sense at all.

#3

Updated by sawa (Tsuyoshi Sawada) 4 months ago

  • Backport deleted (2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN)
  • ruby -v deleted (2.8)
  • 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 greggzst (Grzegorz Jakubiak) 4 months ago

I mean these operations essentially perform Set union and intersection, am I correct? Then the order of the operands doesn't affect the outcome.

Updated by mame (Yusuke Endoh) 4 months ago

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.

Updated by andrey.samsonov@gmail.com (Andrey Samsonov) 4 months ago

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.

Updated by Eregon (Benoit Daloze) 4 months ago

set.rb has this optimization for intersection and IMHO Set should be used explicitly if you expect high-performance Set operations.

#8

Updated by Eregon (Benoit Daloze) 4 months ago

  • Status changed from Open to Rejected

Also available in: Atom PDF