3
\$\begingroup\$

I am trying to write a program to get the count of the maximum number in an array of integers. The below code is what I have written. Is there any better way to write this code in Ruby?

def max_number_count(my_array)
    max_num, max_num_count = my_array.inject([0, 0]) { 
                               |arr, age| age > arr[0] ? 
                               [arr[0] = age, arr[1] = 1] : age == arr[0] ?
                               arr[1] += 1 : arr[1] = arr[1]; 
                               arr 
                             }
    max_num_count
end

max_number_count([1,2,3,3,3])
#3
```
Improve this question
\$\endgroup\$
0

3 Answers 3

Reset to default
7
\$\begingroup\$

Your method shouldn't call the given array my_array. It's not the method's array, it's the caller's array. Just call it array, which is also shorter, so less clutter.

And you're making it very complicated. The array already offers all you need:

def max_number_count(array)
  array.count(array.max)
end

That's also much faster:

            user     system      total        real
yours   1.696091   0.034977   1.731068 (  3.476805)
mine    0.074057   0.000000   0.074057 (  0.131310)

Benchmark code:

require 'benchmark'

def max_number_count1(my_array)
    max_num, max_num_count = my_array.inject([0, 0]) { 
                               |arr, age| age > arr[0] ? 
                               [arr[0] = age, arr[1] = 1] : age == arr[0] ?
                               arr[1] += 1 : arr[1] = arr[1]; 
                               arr 
                             }
    max_num_count
end

def max_number_count2(array)
  array.count(array.max)
end

n = 5
array = (1..1000).to_a * 1000
Benchmark.bmbm do |x|
  x.report("yours") { n.times { max_number_count1(array) } }
  x.report("mine")  { n.times { max_number_count2(array) } }
end
Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ Is Ruby smart enough to optimize this into a single pass over the array? (If not, I suppose interpreter overhead would kill any attempt to manually loop over the array and check a[i] >= current_max, then choose whether it's a new max + reset count to 1 or increment count of same max. In a compiled or JITed language that one-pass way would probably be fastest. Although with SIMD a 2-pass way could be faster for small arrays, like maybe a dozen SIMD vectors, to avoid needing to branch on each SIMD chunk containing a new max.) \$\endgroup\$
    – Peter Cordes
    Sep 10, 2020 at 1:22
  • \$\begingroup\$ @PeterCordes I don't know Ruby much, but I highly doubt it'll make it single-pass. But that's exactly why I felt compelled to add the benchmark, for the people who think that's automatically slower than single-pass (I don't think you do, I just mean I've seen people say that many times). Manual used to be faster for min because the builtin used to be slow, but apparently that got fixed. \$\endgroup\$
    – superb rain
    Sep 10, 2020 at 1:59
  • \$\begingroup\$ @superbrain I actually thought that it would be slower if I find max and then count the max. So I wrote the above code. Thanks for your answer. I learnt a very simple way to implement. But I was also looking to implement the algorithm. That is also the reason why I wrote it like that. But yes I did not specify it in the question. So that is my mistake. \$\endgroup\$
    – Lax_Sam
    Sep 11, 2020 at 13:04
  • 1
    \$\begingroup\$ @PeterCordes: Most language implementations are not able able to rewrite algorithms. GHC has some hand-written rewrite rules in its optimizer for things like map-fusion that might even trigger in this case, but I feel that hand-written pattern-rewrite rules are somewhat cheating. Supercompilation can do amazing things, but the only supercompilers I know of are REFAL (the language for which supercompilation was invented), a Java compiler by the designer of REFAL, and Supero, a long-since abandoned grad-student research compiler for Haskell. I don't know of any Ruby supercompilers. However, … \$\endgroup\$
    – Jörg W Mittag
    Oct 7, 2020 at 20:49
  • 1
    \$\begingroup\$ … both the RPython framework and the Truffle framework come pretty darn close, and there is an (abandoned) Ruby implementation in RPython called Topaz, and a very much alive TruffleRuby. The TruffleRuby guys have shown some quite amazing things. In one example, TruffleRuby compiled a complex Ruby program using dynamic techniques and Hash lookup into a single constant. In another example, they were able to beat a YARV C extension with pure Ruby. I myself have seen 1000 x speedups over Ruby 2.7 with JIT. \$\endgroup\$
    – Jörg W Mittag
    Oct 7, 2020 at 20:53
3
\$\begingroup\$

Following the discussion in the comments to superb rain's answer, I got interested to

  • Write an extremely low-level looping answer and
  • Benchmark all the versions on several different Ruby implementations

Another thing I did was to run a linter (Rubocop) on the OP's code from the question and see what happens.

So, let's start with Rubocop. When I ran Rubocop on the OP's code, it detected 28 offenses, of which it could automatically correct 25. Most of them were related to indentation or other layout issues, I will ignore those. Here is the non-layout related ones that were auto-corrected:

test2.rb:2:39: C: [Corrected] Style/EachWithObject: Use each_with_object instead of inject.
    max_num, max_num_count = my_array.inject([0, 0]) {
                                      ^^^^^^
test2.rb:3:43: C: [Corrected] Style/MultilineTernaryOperator: Avoid multi-line ternary operators, use if or unless instead.
                               |arr, age| age > arr[0] ? ...
                                          ^^^^^^^^^^^^^^

test2.rb:4:3: W: Lint/UselessAssignment: Useless assignment to variable - max_num. Use _ or _max_num as a variable name to indicate that it won't be used.
  max_num, max_num_count = my_array.each_with_object([0, 0]) do |age, arr|
  ^^^^^^^

test2.rb:4:61: C: [Corrected] Style/NestedTernaryOperator: Ternary operators must not be nested. Prefer if or else constructs instead.
                               [arr[0] = age, arr[1] = 1] : age == arr[0] ? ...
                                                            ^^^^^^^^^^^^^^^

test2.rb:7:3: C: [Corrected] Style/MultilineTernaryOperator: Avoid multi-line ternary operators, use if or unless instead.
  age == arr[0] ? ...
  ^^^^^^^^^^^^^^^

And this is what the result looks like:

def max_number_count(my_array)
  max_num, max_num_count = my_array.each_with_object([0, 0]) do |age, arr|
    if age > arr[0]
      [arr[0] = age, arr[1] = 1]
    else
      if age == arr[0]
        arr[1] += 1
      else
        arr[1] = arr[1]
      end
    end
  end
  max_num_count
end

There are essentially two things that Rubocop did. For one, it replaced the Enumerable#inject with Enumerable#each_object. inject is a functional method, and it makes sense to use it when you program in a functional style and want to return a new accumulator after each invocation of the block. But here, you mutate the accumulator, and there is a method which expresses this better, namely Enumerable#each_with_object.

The other thing it did was to replace the conditional operator (? / :) with the conditional expression (if / then / [else]). Here's my short rant on the conditional operator in Ruby: the conditional operator is needed in C, because the conditional statement (if) is a statement, and thus you need the conditional operator because operators are expressions. So, without the conditional operator, it would be impossible to write a conditional expression.

But in Ruby, the conditional expression already is … well … an expression! Duh! So, the conditional operator is never needed. You can always replace

foo ? bar : baz

with

if foo then bar else baz end

There is never a need to use the conditional operator. Never.

And there is the additional advantage that the precedence of the conditional expression is somewhat more sensible than the precedence of the conditional operator. If you pop on over to the Ruby tag on Stack Overflow, you will find quite a number of questions where the problem was that the OP got confused about the precedence of the conditional operator. And mostly, the answers either suggest inserting parentheses or rewriting the expression altogether, but actually, in every single case, the problem would also be solved by doing a completely stupid search&replace and replace the conditional operator with the conditional expression, because the conditional expression has exactly the precedence you would expect it to have.

That's why I, in general, always prefer the conditional expression over the conditional operator. Don't you think that the version that Rubocop produced is much easier to read than the original?

So, let's look at what Rubocop didn't fix automatically:

test2.rb:3:1: C: Metrics/MethodLength: Method has too many lines. [12/10]
def max_number_count(my_array) ...
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

test2.rb:4:3: W: Lint/UselessAssignment: Useless assignment to variable - max_num. Use _ or _max_num as a variable name to indicate that it won't be used.
  max_num, max_num_count = my_array.each_with_object([0, 0]) do |age, arr|
  ^^^^^^^

test2.rb:8:7: C: Style/IfInsideElse: Convert if nested inside else to elsif.
      if age == arr[0]
      ^^

So, the method is too long, there is an unused variable, and the conditional expression can be simplified.

I prefer to start with the stupid mechanical things first, which is why I am going to ignore the first for now. (It often turns out that when you follow the stupid mechanical advice given by Rubocop, the more complex ones also go away.)

The unused variable is easy: Ruby warns about unused variables, which is a good thing™️ because it almost always indicates a bug. If, for some reason, you really, absolutely must have an unused variable, there is a convention in the Ruby community that is also followed by Ruby itself, that the name of an unused variable should start with _ or be just _.

Ruby will not issue unused variable warnings for variables starting with _, and also, it will allow you to use _ multiple times as a parameter, which would otherwise be an error:

def foo(bar, bar) end
# SyntaxError

but

def foo(_, _) end

is valid.

The last suggestion is to replace the if nested inside the else with an elsif.

So, if we do that, we end up with this:

def max_number_count(my_array)
  _, max_num_count = my_array.each_with_object([0, 0]) do |age, arr|
    if age > arr[0]
      [arr[0] = age, arr[1] = 1]
    elsif age == arr[0]
      arr[1] += 1
    else
      arr[1] = arr[1]
    end
  end
  max_num_count
end

And this has actually also fixed the too many lines offense, without us having to do anything.

Now, isn't this much more readable than the original? And the powerful things is: we didn't have to do anything! There was no thinking involved. Almost everything was auto-corrected by Rubocop, and even for the issues that weren't auto-corrected we just stupidly followed the instructions.

And now that we have some nice, readable code without the doubly-nested conditional operator, it's easy to spot that the else branch isn't actually doing anything! It is completely useless, so let's just delete it.

We also see that we are needlessly constructing an array in the if branch that we are not using anywhere, so can get rid of that, too.

And lastly, we see that arr[0] is computed twice, so we pull that out into a variable, and this is the result:

def max_number_count(my_array)
  _, max_num_count = my_array.each_with_object([0, 0]) do |age, arr|
    max = arr[0]

    if age > max
      arr[0] = age
      arr[1] = 1
    elsif age == max
      arr[1] += 1
    end
  end

  max_num_count
end

I mentioned in the beginning that I wrote a very low-level, completely un-Ruby version as well, that guarantees only one pass and uses low-level loops instead of high-level iterators, and this is what it looks like:

def max_count(array)
  size = array.size
  num = idx = 1
  max = array.first

  while idx < size
    el = array[idx]
    if el > max
      max = el
      num = 1
    elsif el == max
      num += 1
    end

    idx += 1
  end

  num
end

I took

and benchmarked them on

  • YARV 2.7.2 (default)
  • YARV 2.7.2 (with --jit)
  • YARV 3.0.0-preview1 (default)
  • YARV 3.0.0-preview1 (with --jit)
  • JRuby 9.2.13.0 running on OpenJDK 14.0.2 (default, i.e. on the Client VM)
  • JRuby 9.2.13.0 running on OpenJDK 14.0.2 (with --server, i.e. on the Server VM)
  • TruffleRuby from GraalVM 20.2 (default, i.e. native)
  • TruffleRuby from GraalVM 20.2 (with --jvm, i.e. running on OpenJDK 14.0.2)

I used the test data and test parameters from superb rains answer for my benchmarks, but I used benchmark-ips as the benchmark harness. Unfortunately, there are no really good benchmark harnesses for Ruby (comparable to e.g. jmh), but benchmark-ips is at least not completely horrible:

require 'benchmark/ips'

array = (1..1000).to_a * 1000

Benchmark.ips do |x|
  x.config(time: 30, warmup: 10)

  x.report('Lax_Sam') do
    max_num, max_num_count = array.inject([0, 0]) {
                              |arr, age| age > arr[0] ?
                              [arr[0] = age, arr[1] = 1] : age == arr[0] ?
                              arr[1] += 1 : arr[1] = arr[1];
                              arr
                            }
    max_num_count
  end

  x.report('Rubocop') do
    _, max_num_count = array.each_with_object([0, 0]) do |age, arr|
      max = arr[0]

      if age > max
        arr[0] = age
        arr[1] = 1
      elsif age == max
        arr[1] += 1
      end
    end

    max_num_count
  end

  x.report('superb rain') do
    array.count(array.max)
  end

  x.report('nullTerminator 1') do
    array.select { |e| e == array.max }.count
  end

  x.report('nullTerminator 2') do
    max = array.max
    array.select { |e| e == max }.count
  end

  x.report('superb rain comment') do
    max = array.max
    array.count { |e| e == max }
  end

  x.report('Jörg comment') do
    max = array.max
    array.count(&max.method(:==))
  end

  x.report('alt Jörg comment') do
    array.count(&array.max.method(:==))
  end

  x.report('Jörg') do
    size = array.size
    num = idx = 1
    max = array.first

    while idx < size
      el = array[idx]
      if el > max
        max = el
        num = 1
      elsif el == max
        num += 1
      end

      idx += 1
    end

    num
  end

  x.compare!
end

Unfortunately, I had to disable nullTerminator's first solution because it would have taken hours with the test data from superb rain's benchmark. (Quadratic complexity at its finest.)

Here are the results:

YARV 2.7.2
Warming up --------------------------------------
             Lax_Sam     1.000  i/100ms
             Rubocop     1.000  i/100ms
         superb rain     9.000  i/100ms
    nullTerminator 2     2.000  i/100ms
 superb rain comment     2.000  i/100ms
        Jörg comment     2.000  i/100ms
    alt Jörg comment     2.000  i/100ms
                Jörg     2.000  i/100ms
Calculating -------------------------------------
             Lax_Sam     11.857  (± 0.0%) i/s -    356.000  in  30.058305s
             Rubocop     14.472  (± 6.9%) i/s -    429.000  in  30.143883s
         superb rain    103.444  (± 5.8%) i/s -      3.096k in  30.021317s
    nullTerminator 2     26.671  (± 0.0%) i/s -    800.000  in  30.004352s
 superb rain comment     26.331  (± 3.8%) i/s -    790.000  in  30.033501s
        Jörg comment     20.527  (± 4.9%) i/s -    616.000  in  30.057100s
    alt Jörg comment     20.492  (± 4.9%) i/s -    616.000  in  30.083978s
                Jörg     30.119  (± 3.3%) i/s -    904.000  in  30.027649s

Comparison:
         superb rain:      103.4 i/s
                Jörg:       30.1 i/s - 3.43x  (± 0.00) slower
    nullTerminator 2:       26.7 i/s - 3.88x  (± 0.00) slower
 superb rain comment:       26.3 i/s - 3.93x  (± 0.00) slower
        Jörg comment:       20.5 i/s - 5.04x  (± 0.00) slower
    alt Jörg comment:       20.5 i/s - 5.05x  (± 0.00) slower
             Rubocop:       14.5 i/s - 7.15x  (± 0.00) slower
             Lax_Sam:       11.9 i/s - 8.72x  (± 0.00) slower

This is expected. YARV does not have any sophisticated optimizations, so an implementation that simply calls into internal C functions should be much faster. Of the implementations that use significant amounts of Ruby code, I also would have expected mine to be the fastest, because it is the most-straightforward one.

Warming up --------------------------------------
             Lax_Sam     1.000  i/100ms
             Rubocop     2.000  i/100ms
         superb rain    11.000  i/100ms
    nullTerminator 2     3.000  i/100ms
 superb rain comment     3.000  i/100ms
        Jörg comment     2.000  i/100ms
    alt Jörg comment     2.000  i/100ms
                Jörg     3.000  i/100ms
Calculating -------------------------------------
             Lax_Sam     16.548  (± 0.0%) i/s -    497.000  in  30.059499s
             Rubocop     20.852  (± 4.8%) i/s -    626.000  in  30.050299s
         superb rain    106.282  (± 3.8%) i/s -      3.190k in  30.058346s
    nullTerminator 2     31.768  (± 3.1%) i/s -    954.000  in  30.072028s
 superb rain comment     30.981  (± 3.2%) i/s -    930.000  in  30.064810s
        Jörg comment     20.582  (± 4.9%) i/s -    618.000  in  30.065961s
    alt Jörg comment     20.679  (± 4.8%) i/s -    620.000  in  30.016374s
                Jörg     30.319  (± 3.3%) i/s -    909.000  in  30.024552s

Comparison:
         superb rain:      106.3 i/s
    nullTerminator 2:       31.8 i/s - 3.35x  (± 0.00) slower
 superb rain comment:       31.0 i/s - 3.43x  (± 0.00) slower
                Jörg:       30.3 i/s - 3.51x  (± 0.00) slower
             Rubocop:       20.9 i/s - 5.10x  (± 0.00) slower
    alt Jörg comment:       20.7 i/s - 5.14x  (± 0.00) slower
        Jörg comment:       20.6 i/s - 5.16x  (± 0.00) slower
             Lax_Sam:       16.5 i/s - 6.42x  (± 0.00) slower

The interesting thing here is that superb rain's answer did not profit much from the JIT. That is the problem when large parts of your core and standard library are written in C: Making your Ruby interpreter better does not actually speed up the code, because most of the code isn't Ruby!

YARV 3.0.0-preview1
Warming up --------------------------------------
             Lax_Sam     1.000  i/100ms
             Rubocop     1.000  i/100ms
         superb rain    15.000  i/100ms
    nullTerminator 2     2.000  i/100ms
 superb rain comment     2.000  i/100ms
        Jörg comment     2.000  i/100ms
    alt Jörg comment     2.000  i/100ms
                Jörg     2.000  i/100ms
Calculating -------------------------------------
             Lax_Sam     10.816  (± 0.0%) i/s -    325.000  in  30.082046s
             Rubocop     12.942  (± 7.7%) i/s -    388.000  in  30.075579s
         superb rain    167.287  (± 6.6%) i/s -      5.010k in  30.071105s
    nullTerminator 2     26.439  (± 3.8%) i/s -    794.000  in  30.044673s
 superb rain comment     25.678  (± 3.9%) i/s -    770.000  in  30.037176s
        Jörg comment     27.056  (± 3.7%) i/s -    812.000  in  30.070840s
    alt Jörg comment     27.879  (± 3.6%) i/s -    836.000  in  30.002903s
                Jörg     25.197  (±27.8%) i/s -    666.000  in  30.085013s

Comparison:
         superb rain:      167.3 i/s
    alt Jörg comment:       27.9 i/s - 6.00x  (± 0.00) slower
        Jörg comment:       27.1 i/s - 6.18x  (± 0.00) slower
    nullTerminator 2:       26.4 i/s - 6.33x  (± 0.00) slower
 superb rain comment:       25.7 i/s - 6.51x  (± 0.00) slower
                Jörg:       25.2 i/s - 6.64x  (± 0.00) slower
             Rubocop:       12.9 i/s - 12.93x  (± 0.00) slower
             Lax_Sam:       10.8 i/s - 15.47x  (± 0.00) slower

In YARV 3.0.0-preview1, performance has improved somewhat, but only superb rain's code really benefits. I suspect again that this may be due to improvements in the C libraries, not in the interpreter.

In fact, we see again that it does not benefit from JIT:

Warming up --------------------------------------
             Lax_Sam     1.000  i/100ms
             Rubocop     1.000  i/100ms
         superb rain     9.000  i/100ms
    nullTerminator 2     2.000  i/100ms
 superb rain comment     2.000  i/100ms
        Jörg comment     2.000  i/100ms
    alt Jörg comment     2.000  i/100ms
                Jörg     1.000  i/100ms
Calculating -------------------------------------
             Lax_Sam     14.049  (± 7.1%) i/s -    421.000  in  30.032181s
             Rubocop     17.339  (± 5.8%) i/s -    518.000  in  30.050563s
         superb rain    167.254  (± 4.2%) i/s -      5.013k in  30.027938s
    nullTerminator 2     28.321  (± 3.5%) i/s -    850.000  in  30.044948s
 superb rain comment     29.456  (± 3.4%) i/s -    884.000  in  30.039652s
        Jörg comment     26.970  (± 3.7%) i/s -    808.000  in  30.012719s
    alt Jörg comment     27.412  (± 3.6%) i/s -    822.000  in  30.022766s
                Jörg     30.465  (± 3.3%) i/s -    913.000  in  30.018464s

Comparison:
         superb rain:      167.3 i/s
                Jörg:       30.5 i/s - 5.49x  (± 0.00) slower
 superb rain comment:       29.5 i/s - 5.68x  (± 0.00) slower
    nullTerminator 2:       28.3 i/s - 5.91x  (± 0.00) slower
    alt Jörg comment:       27.4 i/s - 6.10x  (± 0.00) slower
        Jörg comment:       27.0 i/s - 6.20x  (± 0.00) slower
             Rubocop:       17.3 i/s - 9.65x  (± 0.00) slower
             Lax_Sam:       14.0 i/s - 11.91x  (± 0.00) slower

Everything only gets slightly faster with JIT.

JRuby 9.2.13.0
Warming up --------------------------------------
             Lax_Sam     1.000  i/100ms
             Rubocop     1.000  i/100ms
         superb rain    24.000  i/100ms
    nullTerminator 2     1.000  i/100ms
 superb rain comment     1.000  i/100ms
        Jörg comment     9.000  i/100ms
    alt Jörg comment     9.000  i/100ms
                Jörg     2.000  i/100ms
Calculating -------------------------------------
             Lax_Sam     10.050  (± 0.0%) i/s -    302.000  in  30.084528s
             Rubocop     15.374  (± 6.5%) i/s -    461.000  in  30.031534s
         superb rain    318.038  (±17.3%) i/s -      9.216k in  30.045246s
    nullTerminator 2     16.119  (± 6.2%) i/s -    480.000  in  30.012794s
 superb rain comment     16.837  (± 5.9%) i/s -    504.000  in  29.994138s
        Jörg comment     94.309  (± 5.3%) i/s -      2.826k in  30.054033s
    alt Jörg comment     88.040  (± 9.1%) i/s -      2.619k in  30.013846s
                Jörg     28.873  (± 6.9%) i/s -    864.000  in  30.025918s

Comparison:
         superb rain:      318.0 i/s
        Jörg comment:       94.3 i/s - 3.37x  (± 0.00) slower
    alt Jörg comment:       88.0 i/s - 3.61x  (± 0.00) slower
                Jörg:       28.9 i/s - 11.02x  (± 0.00) slower
 superb rain comment:       16.8 i/s - 18.89x  (± 0.00) slower
    nullTerminator 2:       16.1 i/s - 19.73x  (± 0.00) slower
             Rubocop:       15.4 i/s - 20.69x  (± 0.00) slower
             Lax_Sam:       10.1 i/s - 31.64x  (± 0.00) slower

It starts to get interesting! We see some significant improvements in performance, but more interestingly, we also see a significant change in the order!

My two comments get a significant performance boost. I believe this is due to the fact that JRuby does some significant optimizations of blocks and &block arguments. There is a question on Stack Overflow somewhere, where I speculated that it might be possible to optimize &block arguments, and it looks like JRuby is able to do that, considering that my two comments are 5 x faster than superb rain's despite essentially being equivalent.

Warming up --------------------------------------
             Lax_Sam     1.000  i/100ms
             Rubocop     1.000  i/100ms
         superb rain    25.000  i/100ms
    nullTerminator 2     2.000  i/100ms
 superb rain comment     2.000  i/100ms
        Jörg comment    10.000  i/100ms
    alt Jörg comment     9.000  i/100ms
                Jörg     2.000  i/100ms
Calculating -------------------------------------
             Lax_Sam     11.510  (± 0.0%) i/s -    345.000  in  30.018452s
             Rubocop     19.436  (± 5.1%) i/s -    583.000  in  30.039970s
         superb rain    382.561  (±18.8%) i/s -     10.975k in  30.016459s
    nullTerminator 2     21.196  (± 9.4%) i/s -    632.000  in  30.069497s
 superb rain comment     21.665  (± 9.2%) i/s -    646.000  in  30.066157s
        Jörg comment     94.816  (± 3.2%) i/s -      2.850k in  30.093806s
    alt Jörg comment     93.373  (± 6.4%) i/s -      2.790k in  30.016488s
                Jörg     25.982  (± 7.7%) i/s -    774.000  in  30.009033s

Comparison:
         superb rain:      382.6 i/s
        Jörg comment:       94.8 i/s - 4.03x  (± 0.00) slower
    alt Jörg comment:       93.4 i/s - 4.10x  (± 0.00) slower
                Jörg:       26.0 i/s - 14.72x  (± 0.00) slower
 superb rain comment:       21.7 i/s - 17.66x  (± 0.00) slower
    nullTerminator 2:       21.2 i/s - 18.05x  (± 0.00) slower
             Rubocop:       19.4 i/s - 19.68x  (± 0.00) slower
             Lax_Sam:       11.5 i/s - 33.24x  (± 0.00) slower

superb rain's answer is the only one that gets a significant performance boost from switching from the client JVM with the C0 compiler to the server VM with the C1 compiler.

I believe that this might be due to that answer being the only one that is actually executed often enough to even be compiled. (I think the default threshold for compilation on the HotSpot server JVM is several thousand invocations.)

I must admit that I did not spend too much time trying to tweak the benchmark and the various compiler and VM settings. Ideally, even the slowest implementation should be executed at least 20000 times during warmup, to ensure that all caches are warmed up and all code is compiled, before the actual benchmark run even starts. However, that would have meant a warmup time of over half an hour for just Lax Sam's original version on just YARV 2.7.2 without JIT alone. That doesn't even account for the actual benchmark run, and now add in the fact that we have 7 other versions per VM, and 8 VMs in total, and you can understand why I didn't do that.

But I should've.

TruffleRuby 20.2
Warming up --------------------------------------
             Lax_Sam    39.000  i/100ms
             Rubocop    19.000  i/100ms
         superb rain    16.000  i/100ms
    nullTerminator 2    26.000  i/100ms
 superb rain comment    10.000  i/100ms
        Jörg comment     3.000  i/100ms
    alt Jörg comment     2.000  i/100ms
                Jörg    33.000  i/100ms
Calculating -------------------------------------
             Lax_Sam      1.128k (± 7.8%) i/s -     33.579k in  30.019660s
             Rubocop    811.797  (± 5.3%) i/s -     24.282k in  30.013340s
         superb rain    681.764  (± 7.8%) i/s -     20.112k in  29.997715s
    nullTerminator 2    268.225  (±19.0%) i/s -      7.670k in  30.060797s
 superb rain comment    528.931  (± 3.0%) i/s -     15.850k in  30.000811s
        Jörg comment     31.826  (±22.0%) i/s -    897.000  in  30.002193s
    alt Jörg comment     31.255  (±25.6%) i/s -    852.000  in  30.051522s
                Jörg    346.747  (± 7.5%) i/s -     10.362k in  30.070039s

Comparison:
             Lax_Sam:     1127.5 i/s
             Rubocop:      811.8 i/s - 1.39x  (± 0.00) slower
         superb rain:      681.8 i/s - 1.65x  (± 0.00) slower
 superb rain comment:      528.9 i/s - 2.13x  (± 0.00) slower
                Jörg:      346.7 i/s - 3.25x  (± 0.00) slower
    nullTerminator 2:      268.2 i/s - 4.20x  (± 0.00) slower
        Jörg comment:       31.8 i/s - 35.43x  (± 0.00) slower
    alt Jörg comment:       31.3 i/s - 36.08x  (± 0.00) slower

Hello! All of a sudden, Lax Sam's version, which was consistently the slowest on YARV and JRuby is the fastest. Not only is it literally a hundred times faster than on YARV and JRuby, it is also the fastest of the pack.

Warming up --------------------------------------
             Lax_Sam   122.000  i/100ms
             Rubocop    25.000  i/100ms
         superb rain    24.000  i/100ms
    nullTerminator 2    60.000  i/100ms
 superb rain comment    15.000  i/100ms
        Jörg comment     4.000  i/100ms
    alt Jörg comment    15.000  i/100ms
                Jörg   105.000  i/100ms
Calculating -------------------------------------
             Lax_Sam      1.223k (± 1.8%) i/s -     36.722k in  30.029216s
             Rubocop      1.218k (± 3.4%) i/s -     36.500k in  29.999182s
         superb rain    855.216  (± 4.0%) i/s -     25.464k in  30.022110s
    nullTerminator 2    635.845  (± 3.5%) i/s -     19.080k in  30.046283s
 superb rain comment    778.807  (± 2.6%) i/s -     23.355k in  30.010292s
        Jörg comment     82.560  (±21.8%) i/s -      2.304k in  30.022217s
    alt Jörg comment    721.277  (± 5.5%) i/s -     21.570k in  30.013936s
                Jörg      1.068k (± 5.1%) i/s -     32.025k in  30.067412s

Comparison:
             Lax_Sam:     1223.3 i/s
             Rubocop:     1218.4 i/s - same-ish: difference falls within error
                Jörg:     1068.3 i/s - 1.15x  (± 0.00) slower
         superb rain:      855.2 i/s - 1.43x  (± 0.00) slower
 superb rain comment:      778.8 i/s - 1.57x  (± 0.00) slower
    alt Jörg comment:      721.3 i/s - 1.70x  (± 0.00) slower
    nullTerminator 2:      635.8 i/s - 1.92x  (± 0.00) slower
        Jörg comment:       82.6 i/s - 14.82x  (± 0.00) slower

Stuff gets significantly faster when running on the JVM as opposed to native. That is to be expected. In native mode, GraalVM starts up much faster, but it lacks the sophisticated optimizations that the JVM has. It's trade-off of startup time vs. steady-state throughput.

Not sure what happened with my comment there, I think there must have been some disturbance on my laptop. I wasn't able to have a really separate idle test system, unfortunately, I was running these in the background while working.

I would like to draw your attention to the performance of superb rain's solution. Above, it was consistently the fastest, since it is simply calling into C code (or Java code on JRuby). But I would like to compare it not to the others running on the same VM, but rather to itself running on a different VM: it is 2.23 times faster than when running on JRuby --server and 8.27 times faster than running on YARV.

Now, you might say, okay, I have heard of code written in Java running faster than code written in C in some circumstances, but here's the kicker: it's not written in Java. TruffleRuby's Array#max and Array#count are written in pure Ruby. Only Array#each is written in Java. (More precisely, it is written as Truffle AST Nodes, the Java code is really only there to construct the Nodes).

So, in some very narrow sense, we have just proven that Ruby is 8 x faster than C ;-)

For completeness' sake, I also ran the benchmarks with a 100000 item array instead of 1000000, so that I could include the original O(n²)version from NullTerminator's answer.

It doesn't offer any significant insights other than the obvious "O(n²) is slow". There is some strangeness going on here as well with the performance of that version. E.g. on TruffleRuby, it is faster on native than on JVM, and it doesn't seem to benefit from JITting nearly as much as I would expect.

Although thinking about it, it makes sense. While Array#max and Integer#== are called 100000 times, and thus should be sped up significantly by JITting, Integer#== is probably a highly-optimized builtin which gets special-cased already, and Array#max is too simple to reap any significant benefit. And the benchmark loop itself is only run once.

YARV 2.7.2
Warming up --------------------------------------
             Lax_Sam    12.000  i/100ms
             Rubocop    15.000  i/100ms
         superb rain   112.000  i/100ms
    nullTerminator 1     1.000  i/100ms
    nullTerminator 2    26.000  i/100ms
 superb rain comment    26.000  i/100ms
        Jörg comment    21.000  i/100ms
    alt Jörg comment    20.000  i/100ms
                Jörg    31.000  i/100ms
Calculating -------------------------------------
             Lax_Sam    122.064  (± 2.5%) i/s -      3.660k in  30.009487s
             Rubocop    152.157  (± 2.0%) i/s -      4.575k in  30.082788s
         superb rain      1.127k (± 2.0%) i/s -     33.824k in  30.029655s
    nullTerminator 1      0.036  (± 0.0%) i/s -      2.000  in  54.944267s
    nullTerminator 2    269.498  (± 1.5%) i/s -      8.086k in  30.012557s
 superb rain comment    263.736  (± 2.3%) i/s -      7.930k in  30.085927s
        Jörg comment    213.588  (± 1.9%) i/s -      6.426k in  30.095600s
    alt Jörg comment    212.821  (± 2.8%) i/s -      6.380k in  30.008460s
                Jörg    312.213  (± 2.6%) i/s -      9.362k in  30.005331s

Comparison:
         superb rain:     1126.8 i/s
                Jörg:      312.2 i/s - 3.61x  (± 0.00) slower
    nullTerminator 2:      269.5 i/s - 4.18x  (± 0.00) slower
 superb rain comment:      263.7 i/s - 4.27x  (± 0.00) slower
        Jörg comment:      213.6 i/s - 5.28x  (± 0.00) slower
    alt Jörg comment:      212.8 i/s - 5.29x  (± 0.00) slower
             Rubocop:      152.2 i/s - 7.41x  (± 0.00) slower
             Lax_Sam:      122.1 i/s - 9.23x  (± 0.00) slower
    nullTerminator 1:        0.0 i/s - 30956.35x  (± 0.00) slower

Warming up --------------------------------------
             Lax_Sam    17.000  i/100ms
             Rubocop    20.000  i/100ms
         superb rain   113.000  i/100ms
    nullTerminator 1     1.000  i/100ms
    nullTerminator 2    32.000  i/100ms
 superb rain comment    30.000  i/100ms
        Jörg comment    21.000  i/100ms
    alt Jörg comment    20.000  i/100ms
                Jörg    31.000  i/100ms
Calculating -------------------------------------
             Lax_Sam    171.256  (± 2.9%) i/s -      5.134k in  30.004456s
             Rubocop    213.270  (± 2.3%) i/s -      6.400k in  30.025421s
         superb rain      1.122k (± 3.0%) i/s -     33.674k in  30.031110s
    nullTerminator 1      0.036  (± 0.0%) i/s -      2.000  in  55.154473s
    nullTerminator 2    297.029  (± 7.1%) i/s -      8.896k in  30.111224s
 superb rain comment    289.555  (± 7.6%) i/s -      8.640k in  30.014487s
        Jörg comment    198.056  (± 5.0%) i/s -      5.943k in  30.095264s
    alt Jörg comment    200.426  (± 5.5%) i/s -      6.000k in  30.031566s
                Jörg    707.428  (±59.1%) i/s -     13.981k in  30.015974s

Comparison:
         superb rain:     1122.4 i/s
                Jörg:      707.4 i/s - same-ish: difference falls within error
    nullTerminator 2:      297.0 i/s - 3.78x  (± 0.00) slower
 superb rain comment:      289.6 i/s - 3.88x  (± 0.00) slower
             Rubocop:      213.3 i/s - 5.26x  (± 0.00) slower
    alt Jörg comment:      200.4 i/s - 5.60x  (± 0.00) slower
        Jörg comment:      198.1 i/s - 5.67x  (± 0.00) slower
             Lax_Sam:      171.3 i/s - 6.55x  (± 0.00) slower
    nullTerminator 1:        0.0 i/s - 30952.98x  (± 0.00) slower

YARV 3.0.0-preview1
Warming up --------------------------------------
             Lax_Sam    10.000  i/100ms
             Rubocop    14.000  i/100ms
         superb rain   173.000  i/100ms
    nullTerminator 1     1.000  i/100ms
    nullTerminator 2    24.000  i/100ms
 superb rain comment    26.000  i/100ms
        Jörg comment    26.000  i/100ms
    alt Jörg comment    28.000  i/100ms
                Jörg    30.000  i/100ms
Calculating -------------------------------------
             Lax_Sam    112.428  (± 3.6%) i/s -      3.370k in  30.011516s
             Rubocop    145.914  (± 2.7%) i/s -      4.382k in  30.056886s
         superb rain      1.772k (± 2.5%) i/s -     53.284k in  30.083199s
    nullTerminator 1      0.108  (± 0.0%) i/s -      4.000  in  37.125165s
    nullTerminator 2    264.817  (± 3.4%) i/s -      7.944k in  30.032986s
 superb rain comment    265.206  (± 3.0%) i/s -      7.956k in  30.029620s
        Jörg comment    281.578  (± 2.5%) i/s -      8.450k in  30.029642s
    alt Jörg comment    267.871  (± 8.6%) i/s -      7.952k in  30.019412s
                Jörg    309.680  (± 2.3%) i/s -      9.300k in  30.049396s

Comparison:
         superb rain:     1772.4 i/s
                Jörg:      309.7 i/s - 5.72x  (± 0.00) slower
        Jörg comment:      281.6 i/s - 6.29x  (± 0.00) slower
    alt Jörg comment:      267.9 i/s - 6.62x  (± 0.00) slower
 superb rain comment:      265.2 i/s - 6.68x  (± 0.00) slower
    nullTerminator 2:      264.8 i/s - 6.69x  (± 0.00) slower
             Rubocop:      145.9 i/s - 12.15x  (± 0.00) slower
             Lax_Sam:      112.4 i/s - 15.76x  (± 0.00) slower
    nullTerminator 1:        0.1 i/s - 16446.42x  (± 0.00) slower

Warming up --------------------------------------
             Lax_Sam    15.000  i/100ms
             Rubocop    17.000  i/100ms
         superb rain   179.000  i/100ms
    nullTerminator 1     1.000  i/100ms
    nullTerminator 2    29.000  i/100ms
 superb rain comment    29.000  i/100ms
        Jörg comment    27.000  i/100ms
    alt Jörg comment    28.000  i/100ms
                Jörg    30.000  i/100ms
Calculating -------------------------------------
             Lax_Sam    145.516  (± 2.1%) i/s -      4.365k in  30.007498s
             Rubocop    184.778  (± 2.7%) i/s -      5.542k in  30.015867s
         superb rain      1.795k (± 2.3%) i/s -     53.879k in  30.035743s
    nullTerminator 1      0.108  (± 0.0%) i/s -      4.000  in  36.988133s
    nullTerminator 2    297.031  (± 3.4%) i/s -      8.903k in  30.011491s
 superb rain comment    294.181  (± 4.8%) i/s -      8.816k in  30.046669s
        Jörg comment    282.395  (± 2.1%) i/s -      8.478k in  30.033645s
    alt Jörg comment    281.245  (± 2.5%) i/s -      8.456k in  30.083727s
                Jörg    755.737  (±55.7%) i/s -     15.240k in  30.023659s

Comparison:
         superb rain:     1794.9 i/s
                Jörg:      755.7 i/s - 2.37x  (± 0.00) slower
    nullTerminator 2:      297.0 i/s - 6.04x  (± 0.00) slower
 superb rain comment:      294.2 i/s - 6.10x  (± 0.00) slower
        Jörg comment:      282.4 i/s - 6.36x  (± 0.00) slower
    alt Jörg comment:      281.2 i/s - 6.38x  (± 0.00) slower
             Rubocop:      184.8 i/s - 9.71x  (± 0.00) slower
             Lax_Sam:      145.5 i/s - 12.33x  (± 0.00) slower
    nullTerminator 1:        0.1 i/s - 16596.95x  (± 0.00) slower

JRuby 9.2.13.0
Warming up --------------------------------------
             Lax_Sam    11.000  i/100ms
             Rubocop    16.000  i/100ms
         superb rain   291.000  i/100ms
    nullTerminator 1     1.000  i/100ms
    nullTerminator 2    18.000  i/100ms
 superb rain comment    18.000  i/100ms
        Jörg comment    85.000  i/100ms
    alt Jörg comment    88.000  i/100ms
                Jörg    27.000  i/100ms
Calculating -------------------------------------
             Lax_Sam    100.805  (± 6.0%) i/s -      3.014k in  30.017257s
             Rubocop    156.208  (± 5.1%) i/s -      4.688k in  30.090375s
         superb rain      3.916k (± 6.7%) i/s -    116.982k in  30.018596s
    nullTerminator 1      0.078  (± 0.0%) i/s -      3.000  in  38.298137s
    nullTerminator 2    179.632  (± 2.8%) i/s -      5.400k in  30.087853s
 superb rain comment    186.696  (± 3.2%) i/s -      5.598k in  30.020062s
        Jörg comment    906.260  (± 3.5%) i/s -     27.200k in  30.051472s
    alt Jörg comment    886.155  (± 4.5%) i/s -     26.576k in  30.056778s
                Jörg    315.734  (± 3.5%) i/s -      9.477k in  30.056682s

Comparison:
         superb rain:     3915.9 i/s
        Jörg comment:      906.3 i/s - 4.32x  (± 0.00) slower
    alt Jörg comment:      886.2 i/s - 4.42x  (± 0.00) slower
                Jörg:      315.7 i/s - 12.40x  (± 0.00) slower
 superb rain comment:      186.7 i/s - 20.97x  (± 0.00) slower
    nullTerminator 2:      179.6 i/s - 21.80x  (± 0.00) slower
             Rubocop:      156.2 i/s - 25.07x  (± 0.00) slower
             Lax_Sam:      100.8 i/s - 38.85x  (± 0.00) slower
    nullTerminator 1:        0.1 i/s - 49987.27x  (± 0.00) slower

Warming up --------------------------------------
             Lax_Sam    10.000  i/100ms
             Rubocop    16.000  i/100ms
         superb rain   270.000  i/100ms
    nullTerminator 1     1.000  i/100ms
    nullTerminator 2    20.000  i/100ms
 superb rain comment    16.000  i/100ms
        Jörg comment    93.000  i/100ms
    alt Jörg comment    93.000  i/100ms
                Jörg    31.000  i/100ms
Calculating -------------------------------------
             Lax_Sam    105.366  (± 2.8%) i/s -      3.160k in  30.011009s
             Rubocop    161.379  (± 3.1%) i/s -      4.848k in  30.077855s
         superb rain      4.217k (± 3.3%) i/s -    126.360k in  30.003990s
    nullTerminator 1      0.062  (± 0.0%) i/s -      2.000  in  32.717686s
    nullTerminator 2    182.726  (±12.0%) i/s -      5.360k in  30.016244s
 superb rain comment    171.714  (±15.1%) i/s -      4.960k in  29.997313s
        Jörg comment    920.739  (±11.8%) i/s -     26.877k in  29.999270s
    alt Jörg comment    945.642  (± 4.5%) i/s -     28.365k in  30.061167s
                Jörg    299.195  (± 4.3%) i/s -      8.959k in  30.008053s

Comparison:
         superb rain:     4216.8 i/s
    alt Jörg comment:      945.6 i/s - 4.46x  (± 0.00) slower
        Jörg comment:      920.7 i/s - 4.58x  (± 0.00) slower
                Jörg:      299.2 i/s - 14.09x  (± 0.00) slower
    nullTerminator 2:      182.7 i/s - 23.08x  (± 0.00) slower
 superb rain comment:      171.7 i/s - 24.56x  (± 0.00) slower
             Rubocop:      161.4 i/s - 26.13x  (± 0.00) slower
             Lax_Sam:      105.4 i/s - 40.02x  (± 0.00) slower
    nullTerminator 1:        0.1 i/s - 67484.66x  (± 0.00) slower

TruffleRuby 20.2
Warming up --------------------------------------
             Lax_Sam     1.188k i/100ms
             Rubocop   739.000  i/100ms
         superb rain   648.000  i/100ms
    nullTerminator 1     1.000  i/100ms
    nullTerminator 2   243.000  i/100ms
 superb rain comment   281.000  i/100ms
        Jörg comment    15.000  i/100ms
    alt Jörg comment    26.000  i/100ms
                Jörg   371.000  i/100ms
Calculating -------------------------------------
             Lax_Sam     11.608k (± 4.9%) i/s -    348.084k in  30.062217s
             Rubocop      8.132k (± 5.3%) i/s -    243.870k in  30.074370s
         superb rain      6.759k (± 5.5%) i/s -    202.176k in  30.010548s
    nullTerminator 1      0.081  (± 0.0%) i/s -      3.000  in  43.395539s
    nullTerminator 2      2.497k (±20.4%) i/s -     70.713k in  29.999344s
 superb rain comment      6.563k (±10.9%) i/s -    189.113k in  30.043814s
        Jörg comment    386.749  (±36.2%) i/s -      9.495k in  30.002080s
    alt Jörg comment    356.131  (±21.9%) i/s -      9.906k in  30.019783s
                Jörg      3.725k (± 5.0%) i/s -    111.671k in  30.057561s

Comparison:
             Lax_Sam:    11608.3 i/s
             Rubocop:     8132.2 i/s - 1.43x  (± 0.00) slower
         superb rain:     6759.3 i/s - 1.72x  (± 0.00) slower
 superb rain comment:     6562.7 i/s - 1.77x  (± 0.00) slower
               Jörg:     3725.0 i/s - 3.12x  (± 0.00) slower
    nullTerminator 2:     2497.0 i/s - 4.65x  (± 0.00) slower
       Jörg comment:      386.7 i/s - 30.02x  (± 0.00) slower
   alt Jörg comment:      356.1 i/s - 32.60x  (± 0.00) slower
    nullTerminator 1:        0.1 i/s - 142749.98x  (± 0.00) slower

Warming up --------------------------------------
             Lax_Sam     1.091k i/100ms
             Rubocop     1.140k i/100ms
         superb rain   138.000  i/100ms
    nullTerminator 1     1.000  i/100ms
    nullTerminator 2   139.000  i/100ms
 superb rain comment   120.000  i/100ms
        Jörg comment    32.000  i/100ms
    alt Jörg comment   140.000  i/100ms
                Jörg     1.061k i/100ms
Calculating -------------------------------------
             Lax_Sam     12.065k (± 2.5%) i/s -    362.212k in  30.041589s
             Rubocop     11.798k (± 4.8%) i/s -    353.400k in  30.029941s
         superb rain      1.382k (± 5.7%) i/s -     41.262k in  30.010554s
    nullTerminator 1      0.017  (± 0.0%) i/s -      1.000  in  58.565986s
    nullTerminator 2      1.369k (± 5.0%) i/s -     41.005k in  30.026253s
 superb rain comment      1.386k (± 4.3%) i/s -     41.520k in  30.016684s
        Jörg comment    596.986  (± 8.0%) i/s -     17.728k in  30.071800s
    alt Jörg comment      1.301k (±21.7%) i/s -     35.140k in  30.020553s
                Jörg     10.311k (± 4.9%) i/s -    308.751k in  30.023219s

Comparison:
             Lax_Sam:    12065.1 i/s
             Rubocop:    11797.7 i/s - same-ish: difference falls within error
               Jörg:    10310.9 i/s - 1.17x  (± 0.00) slower
 superb rain comment:     1385.9 i/s - 8.71x  (± 0.00) slower
         superb rain:     1381.6 i/s - 8.73x  (± 0.00) slower
    nullTerminator 2:     1369.2 i/s - 8.81x  (± 0.00) slower
   alt Jörg comment:     1301.1 i/s - 9.27x  (± 0.00) slower
       Jörg comment:      597.0 i/s - 20.21x  (± 0.00) slower
    nullTerminator 1:        0.0 i/s - 706606.12x  (± 0.00) slower
```
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ I think it's a reasonable assumption, and true with my test data which you reused, that most values are not a new maximum. So your solution would be faster if it optimized for the common case by only checking >= maximum at first (and distinguishing the two cases only inside). So putting all the loser elements through only one comparison instead of two. See repl.it/repls/EsteemedWateryDecagon#main.rb \$\endgroup\$
    – superb rain
    Oct 9, 2020 at 18:33
  • \$\begingroup\$ Now I can't decide if I should re-benchmark with your optimization or with a monotonically increasing array :-D \$\endgroup\$
    – Jörg W Mittag
    Oct 9, 2020 at 18:37
  • \$\begingroup\$ Just increasing or strictly increasing? :-) Either way I think my data is more realistic and less of a special case (that's why I created it like that). \$\endgroup\$
    – superb rain
    Oct 9, 2020 at 18:45
  • \$\begingroup\$ Fascinating, especially Lax Sam's sprint to the finish. For better readabiity of that method you might consider max_num, max_num_count = array.inject([0, 0]) { |(max_num, max_num_count), age| ... \$\endgroup\$
    – Cary Swoveland
    Jan 21, 2021 at 19:38
0
\$\begingroup\$

Ruby's Enumerable has a large number of useful methods, which often have additional behaviours when you pass in parameters or a block. It's well worth the time invested in reading about them, as pretty much anything you want to do with an iterator has already been implemented. I learned something new about count today from @superb rain, because I'd originally gone with

def count_max(ary)
  ary.select { |e| e == ary.max }.count
end

then decided that executing ary.max on every iteration was a waste of machine time and changed it to

def count_max(ary)
  max = ary.max
  ary.select { |e| e == max }.count
end

only to discover that count(n) is a shorthand for ary.select { |e| e == n }.count, which is how we arrive at the achingly-elegant array.count(array.max)

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Another way: ary.count { |e| e == max } \$\endgroup\$
    – superb rain
    Sep 9, 2020 at 22:27
  • \$\begingroup\$ Or in point-free style ary.count(&max.method(:==)), taking advantage of the symmetry of equality. \$\endgroup\$
    – Jörg W Mittag
    Sep 14, 2020 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.