Creating an Array just to use Enumerable#max or Enumerable#min leads to significant performance overhead

[puni073]

Creating an Array just to use Enumerable#max or Enumerable#min leads to significant performance overhead.
This issue does not exist on Ruby.
crystal version

Crystal 1.16.0 [53cead6be] (2025-04-09)

LLVM: 18.1.8
Default target: x86_64-unknown-linux-gnu

cat /etc/lsb-release

DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=24.04
DISTRIB_CODENAME=noble
DISTRIB_DESCRIPTION="Ubuntu 24.04.2 LTS"

Crystal
cat main.cr

require "benchmark"

def operator(numbers : Array(Array(Int32)))
  numbers.map { |a| a[0] > a[1] ? a[0] : a[1] }
end

def enumerable_max(numbers : Array(Array(Int32)))
  numbers.map { |a| [a[0], a[1]].max }
end

random_numbers = Array.new(100_000) { [rand(1..100), rand(1..100)] }

Benchmark.ips do |x|
  x.report("Operator") { operator(random_numbers) }
  x.report("Enumerable#max") { enumerable_max(random_numbers) }
end

crystal build --release main.cr && ./main

      Operator   5.33k (187.69µs) (± 2.49%)   391kB/op        fastest
Enumerable#max 372.85  (  2.68ms) (± 1.06%)  4.96MB/op  14.29× slower

Ruby
cat main.rb

require "benchmark/ips"

def operator(numbers)
  numbers.map { |a| a[0] > a[1] ? a[0] : a[1] }
end

def enumerable_max(numbers)
  numbers.map { |a| [a[0], a[1]].max }
end

random_numbers = Array.new(100_000) { [rand(1..100), rand(1..100)] }

Benchmark.ips do |x|
  x.report("Operator") { operator(random_numbers) }
  x.report("Enumerable#max") { enumerable_max(random_numbers) }
end

ruby main.rb

ruby 3.4.2 (2025-02-15 revision d2930f8e7a) +PRISM [x86_64-linux]
Warming up --------------------------------------
            Operator    24.000 i/100ms
      Enumerable#max    25.000 i/100ms
Calculating -------------------------------------
            Operator    246.669 (± 2.0%) i/s    (4.05 ms/i) -      1.248k in   5.061202s
      Enumerable#max    259.661 (± 1.5%) i/s    (3.85 ms/i) -      1.300k in   5.007469s

[HertzDevil]

You should use a Tuple instead, i.e. {a[0], a[1]}.max.

[beta-ziliani]

OTOH it'd be neat to have array literals that are never written into/modified to be created as StaticArrays

[straight-shoota]

I don't see anything actionable here. If you allocate an array, you get an array's performance.

In order to optimize performance, there are more efficient alternatives.
Tuple has already been mentioned ({a[0], a[1]}.max).
Math.max(a[0], a[1]) would also be an option for exactly two operands.

[beta-ziliani]

Tuples serve a different purpose. Here you are looking for a static array, as mentioned. And yes, you can write StaticArray[a[0], a[1]].max, but I don't see what's wrong with the compiler being smart about it 🤔

EDIT: Nothing wrong with using tuples in this particular case though, I just mean that conceptually, if you have a fixed list of elements of the same type, you're better of with StaticArray.

[straight-shoota]

I wonder if we could subsume such a runtime optimization as an effect of RFC 0004: HEAP escape analysis?
That should implicitly cover allocating the Array instance itself on the stack.

Moving the array buffer to the stack would require some extra work though.

Some idea about that: Perhaps we could allocate both, instance and buffer memory, for array literals together? Growing capacity would then most likely mean to abandon the original buffer (i.e. realloc the combined allocation to just the instance size of Array) and allocate a fresh buffer.
This still wouldn't enable implicit stack allocation, but might make the extra work for that a bit easier? And it could be a good optimization anyway, even for regular array literals (i.e. ones that are not immediately thrown away), to reduce the number of allocations from two to one.

[HertzDevil]

That would mean #15494 can never discard the original buffer even if the array's size is less than the initial size, so I don't think it is universally applicable.

[HertzDevil]

It is perhaps more interesting to understand why the code doesn't have a similar penalty on Ruby.

It turns out Ruby's VM byetcode compiler optimizes the particular case where a #max call immediately follows an array literal, transforming it into a specialized opt_newarray_send instruction. It was introduced as opt_newarray_max in Ruby 2.4, and there are now similar optimizations for #min, #hash, #pack, and #include?. The specialized instructions take the original array literal's size as an operand, then operate directly on that many elements on the top of the VM stack, as if a method of Array is called. Hence, there are no additional allocations involved in the array literal.

If you replace max with an unsupported method, that optimization is gone; there is only an opt_newarray followed by an opt_send_without_block on lines 53-54 in the listing, and this will indeed run slower than the Crystal equivalent.

Crystal's interpreter is also a stack VM, so we could try something similar, but for compiled code every allocation is an observable side effect and can rarely be optimized away automatically.

[ysbaddaden]

Unlike Ruby we have alternatives to explicitly use the stack: Tuple and StaticArray. We don't need to optimize Array literals specifically.

We also can't trust the min or max method to not have been monkey-patched (thus need to know that), or need to detect the Array mutability in the called method...

IMO this is where Ameba could help: it's simple to detect without semantic analysis and easier to fix in the source code, than in the compiler trying to be smart about it.