Issue #13884 has been updated by DmitryBochkarev (Dmitry Bochkarev).

File bmlog-20170911-205052.26491.tsv added
File bmlog-20170911-205459.26568.tsv added
File array_opt2.diff added

The fixed remark about comparison method. Added benchmarks and results.

After this benchmark, i've noticed there are no profits when array size between 17 and 32 elements, but some degradation of speed for "diff" operation.

Results

~~~
$ SMALL_ARRAY_MIN=1 SMALL_ARRAY_MAX=8 SMALL_ARRAY_ITERATIONS=10000 ./ruby benchmark/driver.rb --pattern='array_small' --executables='HEAD
::../ruby_dest/bin/ruby; PATCH::./ruby;' -r 10

-----------------------------------------------------------
benchmark results:
Execution time (sec)
name    HEAD    PATCH
array_small_and 0.615   0.263
array_small_diff        0.676   0.282
array_small_or  0.953   0.463

Speedup ratio: compare with the result of `HEAD' (greater is better)
name    PATCH
array_small_and 2.343
array_small_diff        2.392
array_small_or  2.056

Log file: bmlog-20170911-205052.26491.tsv
~~~

~~~
$ SMALL_ARRAY_MIN=9 SMALL_ARRAY_MAX=16 SMALL_ARRAY_ITERATIONS=10000 ./ruby benchmark/driver.rb --pattern='array_small' --executables='HEA
D::../ruby_dest/bin/ruby; PATCH::./ruby;' -r 10

-----------------------------------------------------------
benchmark results:
Execution time (sec)
name    HEAD    PATCH
array_small_and 1.429   1.005
array_small_diff        1.493   0.878
array_small_or  1.672   1.152

Speedup ratio: compare with the result of `HEAD' (greater is better)
name    PATCH
array_small_and 1.422
array_small_diff        1.700
array_small_or  1.452

Log file: bmlog-20170911-205459.26568.tsv
~~~


----------------------------------------
Misc #13884: Reduce number of memory allocations for "and", "or" and "diff" operations on small arrays
https://bugs.ruby-lang.org/issues/13884#change-66607

* Author: DmitryBochkarev (Dmitry Bochkarev)
* Status: Open
* Priority: Normal
* Assignee: DmitryBochkarev (Dmitry Bochkarev)
----------------------------------------
Very often, arrays are used to filter parameters and to select interesting items from 2 collections and very often these collections are small enough, for example:

~~~ ruby
SAFE_COLUMNS = [:id, :title, :created_at]

def columns
  @all_columns & SAFE_COLUMNS
end
~~~


In this patch, I got rid of unnecessary memory allocations for small arrays when "and", "or" and "diff" operations are performed.

I tested this patch on 64 architecture and found out that in arrays with 32 elements, element search is performed faster than retrieving an element from the hash (tested on collections with 16, 32, 64 and 128 elements).

---Files--------------------------------
array_opt.diff (5.21 KB)
bmlog-20170911-205052.26491.tsv (391 Bytes)
bmlog-20170911-205459.26568.tsv (391 Bytes)
array_opt2.diff (7.78 KB)


-- 
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>