[ruby-core:98647] [Ruby master Feature#16897] Can a Ruby 3.0 compatible general purpose memoizer be written in such a way that it matches Ruby 2 performance?

Issue #16897 has been updated by jeremyevans0 (Jeremy Evans).


I'm able to get a correct 2.7 general purpose memoization method within 6% of the basic ruby2_keywords approach.  By correct, I mean it handles a positional hash differently than keywords.

Code:

```ruby
require 'benchmark/ips'

class A
  def self.memoize_26(method_name)
    cache = {}

    uncached = "#{method_name}_without_cache"
    alias_method uncached, method_name

    m = (define_method(method_name) do |*arguments|
      found = true
      data = cache.fetch(arguments) { found = false }
      unless found
        cache[arguments] = data = public_send(uncached, *arguments)
      end
      data
    end)

    if Module.respond_to?(:ruby2_keywords, true)
      ruby2_keywords(m)
    end
  end

  def self.memoize_26o(method_name)
    cache = {}

    uncached = "#{method_name}_without_cache"
    alias_method uncached, method_name

    m = (define_method(method_name) do |*arguments|
      cache.fetch(arguments) { cache[arguments] = send(uncached, *arguments) }
    end)

    if Module.respond_to?(:ruby2_keywords, true)
      ruby2_keywords(m)
    end
  end

  def self.memoize_27(method_name)
    uncached = "#{method_name}_without_cache"
    alias_method uncached, method_name

    cache = {}
    kache = {}
    ruby2_keywords(define_method(method_name) do |*arguments|
      last_arg = arguments.last
      if Hash === last_arg && Hash.ruby2_keywords_hash?(last_arg)
        kache.fetch(arguments) { kache[arguments] = send(uncached, *arguments) }
      else
        cache.fetch(arguments) { cache[arguments] = send(uncached, *arguments) }
      end
    end)
  end

  memoize_26 def a26(*args)
    args
  end
  memoize_26 def kw26(*args, **kw)
    [args, kw]
  end
  class_eval "def x26; #{'a26(1); a26({k: 1}); a26(k: 1); kw26(1); kw26(1, k: 1); kw26(k: 1);'*100} end"

  memoize_26o def a26o(*args)
    args
  end
  memoize_26o def kw26o(*args, **kw)
    [args, kw]
  end
  class_eval "def x26o; #{'a26o(1); a26o({k: 1}); a26o(k: 1); kw26o(1); kw26o(1, k: 1); kw26o(k: 1);'*100} end"

  memoize_27 def a27(*args)
    args
  end
  memoize_27 def kw27(*args, **kw)
    [args, kw]
  end
  class_eval "def x27; #{'a27(1); a27({k: 1}); a27(k: 1); kw27(1); kw27(1, k: 1); kw27(k: 1);'*100} end"
end

return unless __FILE__ == $0

a = A.new

Benchmark.ips do |x|
  x.report("26"){a.x26}
  x.report("26o"){a.x26o}
  x.report("27"){a.x27}
  x.compare!
end
```

Output:

```
Calculating -------------------------------------
                  26    376.379  (_ 0.3%) i/s -      1.887k in   5.013620s
                 26o    380.271  (_ 0.3%) i/s -      1.938k in   5.096377s
                  27    358.914  (_ 0.6%) i/s -      1.820k in   5.071030s

Comparison:
                 26o:      380.3 i/s
                  26:      376.4 i/s - 1.01x  (_ 0.00) slower
                  27:      358.9 i/s - 1.06x  (_ 0.00) slower
```

I think a 6% difference in a microbenchmark is close enough that we need not consider changes to the language or interpreter.  Especially considering we can probably get the difference less than 6% if #16697 is accepted.

----------------------------------------
Feature #16897: Can a Ruby 3.0 compatible general purpose memoizer be written in such a way that it matches Ruby 2 performance?
https://bugs.ruby-lang.org/issues/16897#change-85977

* Author: sam.saffron (Sam Saffron)
* Status: Open
* Priority: Normal
----------------------------------------
```ruby
require 'benchmark/ips'

module Memoizer
def memoize_26(method_name)
  cache = {}

  uncached = "#{method_name}_without_cache"
  alias_method uncached, method_name

  define_method(method_name) do |*arguments|
    found = true
    data = cache.fetch(arguments) { found = false }
    unless found
      cache[arguments] = data = public_send(uncached, *arguments)
    end
    data
  end
end

  def memoize_27(method_name)
    cache = {}

    uncached = "#{method_name}_without_cache"
    alias_method uncached, method_name

    define_method(method_name) do |*args, **kwargs|
      found = true
      all_args = [args, kwargs]
      data = cache.fetch(all_args) { found = false }
      unless found
        cache[all_args] = data = public_send(uncached, *args, **kwargs)
      end
      data
    end
  end

  def memoize_27_v2(method_name)
    uncached = "#{method_name}_without_cache"
    alias_method uncached, method_name

    cache = "MEMOIZE_#{method_name}"

    params = instance_method(method_name).parameters
    has_kwargs = params.any? {|t, name| "#{t}".start_with? "key"}
    has_args = params.any? {|t, name| !"#{t}".start_with? "key"}

    args = []

    args << "args" if has_args
    args << "kwargs" if has_kwargs

    args_text = args.map do |n|
      n == "args" ? "*args" : "**kwargs"
    end.join(",")

    class_eval <<~RUBY
      #{cache} = {}
      def #{method_name}(#{args_text})
        found = true
        all_args = #{args.length === 2 ? "[args, kwargs]" : args[0]}
        data = #{cache}.fetch(all_args) { found = false }
        unless found
          #{cache}[all_args] = data = public_send(:#{uncached} #{args.empty? ? "" : ", #{args_text}"})
        end
        data
      end
    RUBY

  end

end

module Methods
  def args_only(a, b)
    sleep 0.1
    "#{a} #{b}"
  end

  def kwargs_only(a:, b: nil)
    sleep 0.1
    "#{a} #{b}"
  end

  def args_and_kwargs(a, b:)
    sleep 0.1
    "#{a} #{b}"
  end
end

class OldMethod
  extend Memoizer
  include Methods

  memoize_26 :args_and_kwargs
  memoize_26 :args_only
  memoize_26 :kwargs_only
end

class NewMethod
  extend Memoizer
  include Methods

  memoize_27 :args_and_kwargs
  memoize_27 :args_only
  memoize_27 :kwargs_only
end

class OptimizedMethod
  extend Memoizer
  include Methods

  memoize_27_v2 :args_and_kwargs
  memoize_27_v2 :args_only
  memoize_27_v2 :kwargs_only
end

OptimizedMethod.new.args_only(1,2)


methods = [
  OldMethod.new,
  NewMethod.new,
  OptimizedMethod.new
]

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

  methods.each do |m|
    x.report("#{m.class} args only") do |times|
      while times > 0
        m.args_only(10, b: 10)
        times -= 1
      end
    end

    x.report("#{m.class} kwargs only") do |times|
      while times > 0
        m.kwargs_only(a: 10, b: 10)
        times -= 1
      end
    end

    x.report("#{m.class} args and kwargs") do |times|
      while times > 0
        m.args_and_kwargs(10, b: 10)
        times -= 1
      end
    end
  end

  x.compare!
end


# # Ruby 2.6.5
# #
# OptimizedMethod args only:   974266.9 i/s
#  OldMethod args only:   949344.9 i/s - 1.03x  slower
# OldMethod args and kwargs:   945951.5 i/s - 1.03x  slower
# OptimizedMethod kwargs only:   939160.2 i/s - 1.04x  slower
# OldMethod kwargs only:   868229.3 i/s - 1.12x  slower
# OptimizedMethod args and kwargs:   751797.0 i/s - 1.30x  slower
#  NewMethod args only:   730594.4 i/s - 1.33x  slower
# NewMethod args and kwargs:   727300.5 i/s - 1.34x  slower
# NewMethod kwargs only:   665003.8 i/s - 1.47x  slower
#
# #
# # Ruby 2.7.1
#
# OptimizedMethod kwargs only:  1021707.6 i/s
# OptimizedMethod args only:   955694.6 i/s - 1.07x  (0.00) slower
# OldMethod args and kwargs:   940911.3 i/s - 1.09x  (ア 0.00) slower
#  OldMethod args only:   930446.1 i/s - 1.10x  (ア 0.00) slower
# OldMethod kwargs only:   858238.5 i/s - 1.19x  (ア 0.00) slower
# OptimizedMethod args and kwargs:   773773.5 i/s - 1.32x  (ア 0.00) slower
# NewMethod args and kwargs:   772653.3 i/s - 1.32x  (ア 0.00) slower
#  NewMethod args only:   771253.2 i/s - 1.32x  (ア 0.00) slower
# NewMethod kwargs only:   700604.1 i/s - 1.46x  (ア 0.00) slower
```

The bottom line is that a generic delegator often needs to make use of all the arguments provided to a method.

```ruby
def count(*args, **kwargs)
  counter[[args, kwargs]] += 1
  orig_count(*args, **kwargs)
end
```

The old pattern meant we could get away with one less array allocation per:

```ruby
def count(*args)
  counter[args] += 1
  orig_count(*args, **kwargs)
end
```

I would like to propose some changes to Ruby 3 to allow to recover this performance. 

Perhaps:

```ruby
def count(...)
  args = ...
  counter[args] += 1
  orig_count(...)
end
```

Or:

```ruby
def count(***args)

  counter[args] += 1
  orig_count(***args)
end
```

Thoughts? 



-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:[e-mail]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>