Project

General

Profile

Feature #14794

Primitive arrays (Ruby 3x3)

Added by ahorek (Pavel Rosický) almost 3 years ago. Updated almost 3 years ago.

Status:
Open
Priority:
Normal
Assignee:
-
Target version:
-
[ruby-core:87298]

Description

dynamic arrays in ruby can contain various object types:

[1, 1.0, 'text', Object.new]

however if I create a primitive array, let say only with integers (very common case). It should be more efficient.

[1, 2, 3]

let me show you an example. I have an array and I want to find a maximum. I can use a native method(:max) or a naive pure ruby implementation.
I expect that the native function will always be much faster because it’s written in C right?

require 'benchmark/ips'
arr_int = Array.new(50000) { rand 10000 }

def max_ruby(arr)
  max = arr[0]
  size = arr.size
  i = 1
  while i < size
    if arr[i] > max
      max = arr[i]
    end
    i += 1
  end
  max
end

benchmark.ips do |x|
  x.report('native') { arr_int.max }
  x.report('pure')   { max_ruby(arr_int) }
  x.compare!
end

here's a comparsion chart of different ruby & python's runtimes (lower is better)

as expected on ruby 2.6, the native function was faster.

Let’s compare it if we use a JIT
native – no difference
pure ruby – sometimes even faster than native

It's because JIT can't do anything with native functions (inlining, type checks etc.). Native fuctions should be as fast as possible.

MRI implementation of rb_ary_max
https://github.com/ruby/ruby/blob/trunk/array.c#L4335

for (i = 0; i < RARRAY_LEN(ary); i++) {
       v = RARRAY_AREF(ary, i);
       if (result == Qundef || OPTIMIZED_CMP(v, result, cmp_opt) > 0) {
           result = v;
       }
}

this is great for mixed arrays, but for primitive arrays it's quite ineffective. C compiler can't optimize it.
1/ unbox it if possible, don't dereference objects and load it in chunks
2/ if <=> is not redefined, we can use a simplier algorithm
3/ it’s a trivial example that can be written in SIMD #14328, there's even a special instruction for it https://software.intel.com/en-us/node/524201
C compiler can do it for us, but this metod it too complex for auto-vectorization and the data type isn't known during compile time.

Array max is just an example, but the same strategy could be applied for many other methods.

I found a great article about it, check it out.

http://tratt.net/laurie/research/pubs/html/bolz_diekmann_tratt__storage_strategies_for_collections_in_dynamically_typed_languages/

I think this feature could speed-up real ruby applications significantly and it shouldn’t be very hard to implement. We also don't have to change ruby syntax, define types etc. No compatibility issues.

Also available in: Atom PDF