Project

General

Profile

Actions

Feature #13437

closed

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

Added by watson1978 (Shizuo Fujita) almost 7 years ago. Updated almost 7 years ago.

Status:
Closed
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

Actions #1

Updated by watson1978 (Shizuo Fujita) almost 7 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
Actions #2

Updated by nobu (Nobuyoshi Nakada) almost 7 years ago

  • Tracker changed from Bug to Feature
Actions

Also available in: Atom PDF

Like0
Like0Like0