Project

General

Profile

Feature #13884

Reduce number of memory allocations for "and", "or" and "diff" operations on small arrays

Added by DmitryBochkarev (Dmitry Bochkarev) 2 months ago. Updated about 2 months ago.

Status:
Closed
Priority:
Normal
Target version:
-
[ruby-core:82725]

Description

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:

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

array_opt.diff (5.21 KB) array_opt.diff DmitryBochkarev (Dmitry Bochkarev), 09/09/2017 02:19 PM
bmlog-20170911-205052.26491.tsv (391 Bytes) bmlog-20170911-205052.26491.tsv DmitryBochkarev (Dmitry Bochkarev), 09/11/2017 03:56 PM
bmlog-20170911-205459.26568.tsv (391 Bytes) bmlog-20170911-205459.26568.tsv DmitryBochkarev (Dmitry Bochkarev), 09/11/2017 03:57 PM
array_opt2.diff (7.78 KB) array_opt2.diff DmitryBochkarev (Dmitry Bochkarev), 09/11/2017 04:11 PM

Associated revisions

Revision 60057
Added by nobu (Nobuyoshi Nakada) about 2 months ago

array.c: improve operations on small arrays

[Feature #13884]

Reduce number of memory allocations for "and", "or" and "diff"
operations on small arrays

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:

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.

name HEAD PATCH
array_small_and 0.615 0.263
array_small_diff 0.676 0.282
array_small_or 0.953 0.463
name PATCH
array_small_and 2.343
array_small_diff 2.392
array_small_or 2.056
name HEAD PATCH
array_small_and 1.429 1.005
array_small_diff 1.493 0.878
array_small_or 1.672 1.152
name PATCH
array_small_and 1.422
array_small_diff 1.700
array_small_or 1.452

Author: Dmitry Bochkarev dimabochkarev@gmail.com

History

#1 [ruby-core:82739] Updated by Eregon (Benoit Daloze) 2 months ago

Note that this would change the semantics as it uses #== and not #eql? to compare elements.
The comparison should always be done with #eql? to remain compatible.

It also does not call #hash but that is likely a much smaller problem.

#2 [ruby-core:82742] Updated by DmitryBochkarev (Dmitry Bochkarev) 2 months ago

Eregon (Benoit Daloze) wrote:

Note that this would change the semantics as it uses #== and not #eql? to compare elements.
The comparison should always be done with #eql? to remain compatible.

Yes, it is, I've missed this part, will fix.

#3 [ruby-core:82750] Updated by DmitryBochkarev (Dmitry Bochkarev) 2 months ago

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

name HEAD PATCH
array_small_and 0.615 0.263
array_small_diff 0.676 0.282
array_small_or 0.953 0.463
name PATCH
array_small_and 2.343
array_small_diff 2.392
array_small_or 2.056

SMALL_ARRAY_MIN=9 SMALL_ARRAY_MAX=16 SMALL_ARRAY_ITERATIONS=10000

name HEAD PATCH
array_small_and 1.429 1.005
array_small_diff 1.493 0.878
array_small_or 1.672 1.152
name PATCH
array_small_and 1.422
array_small_diff 1.700
array_small_or 1.452

#4 Updated by DmitryBochkarev (Dmitry Bochkarev) about 2 months ago

  • Tracker changed from Misc to Feature

#5 [ruby-core:82951] Updated by DmitryBochkarev (Dmitry Bochkarev) about 2 months ago

Can anyone review this patch?

#7 [ruby-core:83049] Updated by matz (Yukihiro Matsumoto) about 2 months ago

I like the idea. Nobu, could you review?

Matz.

#8 Updated by nobu (Nobuyoshi Nakada) about 2 months ago

  • Status changed from Open to Closed

Applied in changeset trunk|r60057.


array.c: improve operations on small arrays

[Feature #13884]

Reduce number of memory allocations for "and", "or" and "diff"
operations on small arrays

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:

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.

name HEAD PATCH
array_small_and 0.615 0.263
array_small_diff 0.676 0.282
array_small_or 0.953 0.463
name PATCH
array_small_and 2.343
array_small_diff 2.392
array_small_or 2.056
name HEAD PATCH
array_small_and 1.429 1.005
array_small_diff 1.493 0.878
array_small_or 1.672 1.152
name PATCH
array_small_and 1.422
array_small_diff 1.700
array_small_or 1.452

Author: Dmitry Bochkarev dimabochkarev@gmail.com

Also available in: Atom PDF