Enumerable#sort_by is not always faster than #sort

Open
#120 7 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
25/100
Issue type
Bug
Clarity
Needs clarification
Activity status
Stale
Tech stack
ruby
Domain
performance

Research direction

Start by running the supplied benchmark-ips example and compare sort_by with sort across the Ruby versions mentioned in the issue. The payload names no repository file, test, or expected change, so the next step is to locate any related benchmark entry and clarify whether the intended outcome is an implementation change, a benchmark update, or documentation.

Written by the indexing model from the issue text.

Description

Array Enumerable

Per the Ruby 2.4.0 docs:

The current implementation of sort_by generates an array of tuples containing the original collection element and the mapped value. This makes sort_by fairly expensive when the keysets are simple.

Here's a concrete example showing sort to be 2.70x faster in Ruby 1.9.3, 2.3.3 and 2.4.0:

require 'benchmark/ips'

Benchmark.ips do |x|
  x.time = 5
  x.warmup = 2

  ARRAY = %w{apple pear fig}

  x.report("sort_by") do
    ARRAY.sort_by(&:length)
  end

  x.report("sort") do
    ARRAY.sort { |a, b| a.length <=> b.length}
  end

  x.compare!
end

Warming up --------------------------------------
             sort_by    56.348k i/100ms
                sort   111.946k i/100ms
Calculating -------------------------------------
             sort_by    635.646k (±16.1%) i/s -      3.099M in   5.074036s
                sort      1.713M (±16.3%) i/s -      8.284M in   5.023904s

Comparison:
                sort:  1713232.1 i/s
             sort_by:   635645.9 i/s - 2.70x slower
Dominant language
Ruby
Stars
5.7k
Forks
370
No merged PRs in 30d

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from fastruby/fast-ruby

All issues in fastruby/fast-ruby

Similar issues

More Ruby issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.