Project

General

Profile

Feature #13437

Improve performance of Enumerable#{sort_by,min_by,max_by,minmax_by}

Added by watson1978 (Shizuo Fujita) over 2 years ago. Updated over 2 years ago.

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

Description

Improve performance of Enumerable#{sort_by,min_by,max_by,minmax_by}

Before

                user     system      total        real
sort_by     1.810000   0.010000   1.820000 (  1.824355)
min_by(n)   2.530000   0.000000   2.530000 (  2.534154)
min_by      2.450000   0.000000   2.450000 (  2.456396)
max_by(n)   3.240000   0.000000   3.240000 (  3.238680)
max_by      2.440000   0.010000   2.450000 (  2.444972)
minmax_by   3.080000   0.000000   3.080000 (  3.083867)

After

                user     system      total        real
sort_by     1.100000   0.020000   1.120000 (  1.122831)
min_by(n)   1.650000   0.000000   1.650000 (  1.657220)
min_by      1.600000   0.010000   1.610000 (  1.625084)
max_by(n)   1.930000   0.010000   1.940000 (  1.953623)
max_by      1.630000   0.010000   1.640000 (  1.639236)
minmax_by   1.760000   0.000000   1.760000 (  1.759928)

Test code

require 'benchmark'

Benchmark.bmbm do |x|

  enum = (1..1000).to_a.each

  x.report "sort_by" do
    10000.times do
      enum.sort_by { |a| a }
    end
  end

  x.report "min_by(n)" do
    20000.times do
      enum.min_by(2) { |a| a }
    end
  end

  x.report "min_by" do
    20000.times do
      enum.min_by { |a| a }
    end
  end

  x.report "max_by(n)" do
    10000.times do
      enum.max_by(2) { |a| a }
    end
  end

  x.report "max_by" do
    20000.times do
      enum.max_by { |a| a }
    end
  end

  x.report "minmax_by" do
    20000.times do
      enum.minmax_by { |a| a }
    end
  end

end

Patch

https://github.com/ruby/ruby/pull/1584

Associated revisions

Revision cf02692f
Added by watson1978 (Shizuo Fujita) over 2 years ago

Improve performance of Enumerable#{sort_by,min_by,max_by,minmax_by}

This is totally same approach with r58964.

enum.c (sort_by_cmp): use OPTIMIZED_CMP() to compare the objects instead of
`<=>' method dispatching for Fixnum/Float/String object.

enum.c (nmin_cmp): ditto.
enum.c (min_by_i): ditto.
enum.c (max_by_i): ditto.
enum.c (minmax_by_i_update): ditto.
enum.c (minmax_by_i): ditto.

Enumerable#sort_by   -> 51 % up
Enumerable#min_by(n) -> 34 % up
Enumerable#min_by    -> 37 % up
Enumerable#max_by(n) -> 61 % up
Enumerable#max_by    -> 40 % up
Enumerable#minmax_by -> 67 % up

[ruby-core:80689] [Bug #13437] [Fix GH-1584]

Before

Enumerable#sort_by 5.692k (± 2.2%) i/s - 28.611k in 5.028861s
Enumerable#min_by(n) 8.496k (± 0.5%) i/s - 43.146k in 5.078394s
Enumerable#min_by 8.678k (± 0.5%) i/s - 43.911k in 5.060128s
Enumerable#max_by(n) 3.306k (± 3.0%) i/s - 16.562k in 5.014727s
Enumerable#max_by 8.322k (± 2.8%) i/s - 42.400k in 5.099400s
Enumerable#minmax_by 6.769k (± 2.6%) i/s - 34.100k in 5.041354s

After

Enumerable#sort_by 8.591k (± 3.0%) i/s - 43.316k in 5.046836s
Enumerable#min_by(n) 11.489k (± 1.2%) i/s - 57.732k in 5.025504s
Enumerable#min_by 11.835k (± 2.7%) i/s - 60.150k in 5.086450s
Enumerable#max_by(n) 5.322k (± 1.1%) i/s - 26.650k in 5.008289s
Enumerable#max_by 11.705k (± 0.6%) i/s - 59.262k in 5.062997s
Enumerable#minmax_by 11.323k (± 1.3%) i/s - 57.018k in 5.036565s

Test code

require 'benchmark/ips'

Benchmark.ips do |x|
enum = (1..1000).to_a.to_enum

x.report "Enumerable#sort_by" do
enum.sort_by { |a| a }
end

x.report "Enumerable#min_by(n)" do
enum.min_by(2) { |a| a }
end

x.report "Enumerable#min_by" do
enum.min_by { |a| a }
end

x.report "Enumerable#max_by(n)" do
enum.max_by(2) { |a| a }
end

x.report "Enumerable#max_by" do
enum.max_by { |a| a }
end

x.report "Enumerable#minmax_by" do
enum.minmax_by { |a| a }
end
end

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@58968 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

Revision 58968
Added by watson1978 (Shizuo Fujita) over 2 years ago

Improve performance of Enumerable#{sort_by,min_by,max_by,minmax_by}

This is totally same approach with r58964.

enum.c (sort_by_cmp): use OPTIMIZED_CMP() to compare the objects instead of
`<=>' method dispatching for Fixnum/Float/String object.

enum.c (nmin_cmp): ditto.
enum.c (min_by_i): ditto.
enum.c (max_by_i): ditto.
enum.c (minmax_by_i_update): ditto.
enum.c (minmax_by_i): ditto.

Enumerable#sort_by   -> 51 % up
Enumerable#min_by(n) -> 34 % up
Enumerable#min_by    -> 37 % up
Enumerable#max_by(n) -> 61 % up
Enumerable#max_by    -> 40 % up
Enumerable#minmax_by -> 67 % up

[ruby-core:80689] [Bug #13437] [Fix GH-1584]

Before

Enumerable#sort_by 5.692k (± 2.2%) i/s - 28.611k in 5.028861s
Enumerable#min_by(n) 8.496k (± 0.5%) i/s - 43.146k in 5.078394s
Enumerable#min_by 8.678k (± 0.5%) i/s - 43.911k in 5.060128s
Enumerable#max_by(n) 3.306k (± 3.0%) i/s - 16.562k in 5.014727s
Enumerable#max_by 8.322k (± 2.8%) i/s - 42.400k in 5.099400s
Enumerable#minmax_by 6.769k (± 2.6%) i/s - 34.100k in 5.041354s

After

Enumerable#sort_by 8.591k (± 3.0%) i/s - 43.316k in 5.046836s
Enumerable#min_by(n) 11.489k (± 1.2%) i/s - 57.732k in 5.025504s
Enumerable#min_by 11.835k (± 2.7%) i/s - 60.150k in 5.086450s
Enumerable#max_by(n) 5.322k (± 1.1%) i/s - 26.650k in 5.008289s
Enumerable#max_by 11.705k (± 0.6%) i/s - 59.262k in 5.062997s
Enumerable#minmax_by 11.323k (± 1.3%) i/s - 57.018k in 5.036565s

Test code

require 'benchmark/ips'

Benchmark.ips do |x|
enum = (1..1000).to_a.to_enum

x.report "Enumerable#sort_by" do
enum.sort_by { |a| a }
end

x.report "Enumerable#min_by(n)" do
enum.min_by(2) { |a| a }
end

x.report "Enumerable#min_by" do
enum.min_by { |a| a }
end

x.report "Enumerable#max_by(n)" do
enum.max_by(2) { |a| a }
end

x.report "Enumerable#max_by" do
enum.max_by { |a| a }
end

x.report "Enumerable#minmax_by" do
enum.minmax_by { |a| a }
end
end

Revision 58968
Added by watson1978 (Shizuo Fujita) over 2 years ago

Improve performance of Enumerable#{sort_by,min_by,max_by,minmax_by}

This is totally same approach with r58964.

enum.c (sort_by_cmp): use OPTIMIZED_CMP() to compare the objects instead of
`<=>' method dispatching for Fixnum/Float/String object.

enum.c (nmin_cmp): ditto.
enum.c (min_by_i): ditto.
enum.c (max_by_i): ditto.
enum.c (minmax_by_i_update): ditto.
enum.c (minmax_by_i): ditto.

Enumerable#sort_by   -> 51 % up
Enumerable#min_by(n) -> 34 % up
Enumerable#min_by    -> 37 % up
Enumerable#max_by(n) -> 61 % up
Enumerable#max_by    -> 40 % up
Enumerable#minmax_by -> 67 % up

[ruby-core:80689] [Bug #13437] [Fix GH-1584]

Before

Enumerable#sort_by 5.692k (± 2.2%) i/s - 28.611k in 5.028861s
Enumerable#min_by(n) 8.496k (± 0.5%) i/s - 43.146k in 5.078394s
Enumerable#min_by 8.678k (± 0.5%) i/s - 43.911k in 5.060128s
Enumerable#max_by(n) 3.306k (± 3.0%) i/s - 16.562k in 5.014727s
Enumerable#max_by 8.322k (± 2.8%) i/s - 42.400k in 5.099400s
Enumerable#minmax_by 6.769k (± 2.6%) i/s - 34.100k in 5.041354s

After

Enumerable#sort_by 8.591k (± 3.0%) i/s - 43.316k in 5.046836s
Enumerable#min_by(n) 11.489k (± 1.2%) i/s - 57.732k in 5.025504s
Enumerable#min_by 11.835k (± 2.7%) i/s - 60.150k in 5.086450s
Enumerable#max_by(n) 5.322k (± 1.1%) i/s - 26.650k in 5.008289s
Enumerable#max_by 11.705k (± 0.6%) i/s - 59.262k in 5.062997s
Enumerable#minmax_by 11.323k (± 1.3%) i/s - 57.018k in 5.036565s

Test code

require 'benchmark/ips'

Benchmark.ips do |x|
enum = (1..1000).to_a.to_enum

x.report "Enumerable#sort_by" do
enum.sort_by { |a| a }
end

x.report "Enumerable#min_by(n)" do
enum.min_by(2) { |a| a }
end

x.report "Enumerable#min_by" do
enum.min_by { |a| a }
end

x.report "Enumerable#max_by(n)" do
enum.max_by(2) { |a| a }
end

x.report "Enumerable#max_by" do
enum.max_by { |a| a }
end

x.report "Enumerable#minmax_by" do
enum.minmax_by { |a| a }
end
end

Revision 58968
Added by watson1978 (Shizuo Fujita) over 2 years ago

Improve performance of Enumerable#{sort_by,min_by,max_by,minmax_by}

This is totally same approach with r58964.

enum.c (sort_by_cmp): use OPTIMIZED_CMP() to compare the objects instead of
`<=>' method dispatching for Fixnum/Float/String object.

enum.c (nmin_cmp): ditto.
enum.c (min_by_i): ditto.
enum.c (max_by_i): ditto.
enum.c (minmax_by_i_update): ditto.
enum.c (minmax_by_i): ditto.

Enumerable#sort_by   -> 51 % up
Enumerable#min_by(n) -> 34 % up
Enumerable#min_by    -> 37 % up
Enumerable#max_by(n) -> 61 % up
Enumerable#max_by    -> 40 % up
Enumerable#minmax_by -> 67 % up

[ruby-core:80689] [Bug #13437] [Fix GH-1584]

Before

Enumerable#sort_by 5.692k (± 2.2%) i/s - 28.611k in 5.028861s
Enumerable#min_by(n) 8.496k (± 0.5%) i/s - 43.146k in 5.078394s
Enumerable#min_by 8.678k (± 0.5%) i/s - 43.911k in 5.060128s
Enumerable#max_by(n) 3.306k (± 3.0%) i/s - 16.562k in 5.014727s
Enumerable#max_by 8.322k (± 2.8%) i/s - 42.400k in 5.099400s
Enumerable#minmax_by 6.769k (± 2.6%) i/s - 34.100k in 5.041354s

After

Enumerable#sort_by 8.591k (± 3.0%) i/s - 43.316k in 5.046836s
Enumerable#min_by(n) 11.489k (± 1.2%) i/s - 57.732k in 5.025504s
Enumerable#min_by 11.835k (± 2.7%) i/s - 60.150k in 5.086450s
Enumerable#max_by(n) 5.322k (± 1.1%) i/s - 26.650k in 5.008289s
Enumerable#max_by 11.705k (± 0.6%) i/s - 59.262k in 5.062997s
Enumerable#minmax_by 11.323k (± 1.3%) i/s - 57.018k in 5.036565s

Test code

require 'benchmark/ips'

Benchmark.ips do |x|
enum = (1..1000).to_a.to_enum

x.report "Enumerable#sort_by" do
enum.sort_by { |a| a }
end

x.report "Enumerable#min_by(n)" do
enum.min_by(2) { |a| a }
end

x.report "Enumerable#min_by" do
enum.min_by { |a| a }
end

x.report "Enumerable#max_by(n)" do
enum.max_by(2) { |a| a }
end

x.report "Enumerable#max_by" do
enum.max_by { |a| a }
end

x.report "Enumerable#minmax_by" do
enum.minmax_by { |a| a }
end
end

Revision e4cc791f
Added by nobu (Nobuyoshi Nakada) over 2 years ago

enum.c: check if reentered

  • enum.c (cmpint_reenter_check): extract from nmin_cmp and
    nmin_block_cmp.

  • enum.c (nmin_cmp): check if reentered before rb_cmpint.
    [Feature #13437]

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@58971 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

Revision 58971
Added by nobu (Nobuyoshi Nakada) over 2 years ago

enum.c: check if reentered

  • enum.c (cmpint_reenter_check): extract from nmin_cmp and
    nmin_block_cmp.

  • enum.c (nmin_cmp): check if reentered before rb_cmpint.
    [Feature #13437]

Revision 58971
Added by nobu (Nobuyoshi Nakada) over 2 years ago

enum.c: check if reentered

  • enum.c (cmpint_reenter_check): extract from nmin_cmp and
    nmin_block_cmp.

  • enum.c (nmin_cmp): check if reentered before rb_cmpint.
    [Feature #13437]

Revision 58971
Added by nobu (Nobuyoshi Nakada) over 2 years ago

enum.c: check if reentered

  • enum.c (cmpint_reenter_check): extract from nmin_cmp and
    nmin_block_cmp.

  • enum.c (nmin_cmp): check if reentered before rb_cmpint.
    [Feature #13437]

History

#1

Updated by watson1978 (Shizuo Fujita) over 2 years ago

  • Status changed from Open to Closed

Applied in changeset trunk|r58968.


Improve performance of Enumerable#{sort_by,min_by,max_by,minmax_by}

This is totally same approach with r58964.

enum.c (sort_by_cmp): use OPTIMIZED_CMP() to compare the objects instead of
`<=>' method dispatching for Fixnum/Float/String object.

enum.c (nmin_cmp): ditto.
enum.c (min_by_i): ditto.
enum.c (max_by_i): ditto.
enum.c (minmax_by_i_update): ditto.
enum.c (minmax_by_i): ditto.

Enumerable#sort_by   -> 51 % up
Enumerable#min_by(n) -> 34 % up
Enumerable#min_by    -> 37 % up
Enumerable#max_by(n) -> 61 % up
Enumerable#max_by    -> 40 % up
Enumerable#minmax_by -> 67 % up

[ruby-core:80689] [Bug #13437] [Fix GH-1584]

Before

Enumerable#sort_by 5.692k (± 2.2%) i/s - 28.611k in 5.028861s
Enumerable#min_by(n) 8.496k (± 0.5%) i/s - 43.146k in 5.078394s
Enumerable#min_by 8.678k (± 0.5%) i/s - 43.911k in 5.060128s
Enumerable#max_by(n) 3.306k (± 3.0%) i/s - 16.562k in 5.014727s
Enumerable#max_by 8.322k (± 2.8%) i/s - 42.400k in 5.099400s
Enumerable#minmax_by 6.769k (± 2.6%) i/s - 34.100k in 5.041354s

After

Enumerable#sort_by 8.591k (± 3.0%) i/s - 43.316k in 5.046836s
Enumerable#min_by(n) 11.489k (± 1.2%) i/s - 57.732k in 5.025504s
Enumerable#min_by 11.835k (± 2.7%) i/s - 60.150k in 5.086450s
Enumerable#max_by(n) 5.322k (± 1.1%) i/s - 26.650k in 5.008289s
Enumerable#max_by 11.705k (± 0.6%) i/s - 59.262k in 5.062997s
Enumerable#minmax_by 11.323k (± 1.3%) i/s - 57.018k in 5.036565s

Test code

require 'benchmark/ips'

Benchmark.ips do |x|
  enum = (1..1000).to_a.to_enum

  x.report "Enumerable#sort_by" do
    enum.sort_by { |a| a }
  end

  x.report "Enumerable#min_by(n)" do
    enum.min_by(2) { |a| a }
  end

  x.report "Enumerable#min_by" do
    enum.min_by { |a| a }
  end

  x.report "Enumerable#max_by(n)" do
    enum.max_by(2) { |a| a }
  end

  x.report "Enumerable#max_by" do
    enum.max_by { |a| a }
  end

  x.report "Enumerable#minmax_by" do
    enum.minmax_by { |a| a }
  end
end
#2

Updated by nobu (Nobuyoshi Nakada) over 2 years ago

  • Tracker changed from Bug to Feature

Also available in: Atom PDF