ruby-concurrency / concurrent-ruby

Modern concurrency tools including agents, futures, promises, thread pools, supervisors, and more. Inspired by Erlang, Clojure, Scala, Go, Java, JavaScript, and classic concurrency patterns.
https://ruby-concurrency.github.io/concurrent-ruby/
Other
5.71k stars 420 forks source link

Consider falsy value on `Concurrent::Map#compute_if_absent` fast non-blocking path #879

Closed mtsmfm closed 4 years ago

mtsmfm commented 4 years ago

Currently, compute_if_absent with falsy value is much slower than truthy value because non-blocking path only considers truthy one. https://github.com/ruby-concurrency/concurrent-ruby/blob/f749b81cb6c6291640c0004b57e60dbc2b59a72b/lib/concurrent-ruby/concurrent/collection/map/mri_map_backend.rb#L22

require 'bundler/inline'

gemfile do
  source 'https://rubygems.org'

  gem 'benchmark-ips', require: 'benchmark/ips'
  gem 'concurrent-ruby', require: 'concurrent'
end

concurrent_map = Concurrent::Map.new
concurrent_map[:nil] = nil
concurrent_map[:non_nil] = 1

Benchmark.ips do |x|
  x.report("[Concurrent::Map] :nil") do
    concurrent_map.compute_if_absent(:nil) { raise }
  end

  x.report("[Concurrent::Map] :non_nil") do
    concurrent_map.compute_if_absent(:non_nil) { raise }
  end

  x.compare!
end
Warming up --------------------------------------
[Concurrent::Map] :nil
                       312.584k i/100ms
[Concurrent::Map] :non_nil
                       704.894k i/100ms
Calculating -------------------------------------
[Concurrent::Map] :nil
                          2.404M (± 6.6%) i/s -     12.191M in   5.095349s
[Concurrent::Map] :non_nil
                          6.757M (± 9.3%) i/s -     33.835M in   5.054357s

Comparison:
[Concurrent::Map] :non_nil:  6756566.7 i/s
[Concurrent::Map] :nil:  2404077.4 i/s - 2.81x  (± 0.00) slower

This patch makes it faster and keeps same-ish speed for truthy value.

require 'bundler/inline'

gemfile do
  source 'https://rubygems.org'

  gem 'benchmark-ips', require: 'benchmark/ips'
  gem 'concurrent-ruby', require: 'concurrent'
end

concurrent_map = Concurrent::Map.new
concurrent_map[:nil] = nil
concurrent_map[:non_nil] = 1

patched_concurrent_map = Concurrent::Map.new
patched_concurrent_map.extend(Module.new do
  def compute_if_absent(key)
    if Concurrent::NULL != (stored_value = @backend.fetch(key, Concurrent::NULL))
      stored_value
    else
      @write_lock.synchronize { super }
    end
  end
end)
patched_concurrent_map[:nil] = nil
patched_concurrent_map[:non_nil] = 1

Benchmark.ips do |x|
  x.report("[Concurrent::Map] :nil") do
    concurrent_map.compute_if_absent(:nil) { raise }
  end

  x.report("[Concurrent::Map] :non_nil") do
    concurrent_map.compute_if_absent(:non_nil) { raise }
  end

  x.report("[Concurrent::Map with patch] :nil") do
    patched_concurrent_map.compute_if_absent(:nil) { raise }
  end

  x.report("[Concurrent::Map with patch] :non_nil") do
    patched_concurrent_map.compute_if_absent(:non_nil) { raise }
  end

  x.compare!
end
Warming up --------------------------------------
[Concurrent::Map] :nil
                       310.135k i/100ms
[Concurrent::Map] :non_nil
                       923.645k i/100ms
[Concurrent::Map with patch] :nil
                       928.247k i/100ms
[Concurrent::Map with patch] :non_nil
                       840.197k i/100ms
Calculating -------------------------------------
[Concurrent::Map] :nil
                          2.049M (±11.4%) i/s -     10.234M in   5.060933s
[Concurrent::Map] :non_nil
                          7.181M (± 7.5%) i/s -     36.022M in   5.048215s
[Concurrent::Map with patch] :nil
                          7.479M (± 5.0%) i/s -     38.058M in   5.103572s
[Concurrent::Map with patch] :non_nil
                          7.413M (± 6.9%) i/s -     36.969M in   5.013929s

Comparison:
[Concurrent::Map with patch] :nil:  7478557.1 i/s
[Concurrent::Map with patch] :non_nil:  7413277.4 i/s - same-ish: difference falls within error
[Concurrent::Map] :non_nil:  7181043.9 i/s - same-ish: difference falls within error
[Concurrent::Map] :nil:  2049352.8 i/s - 3.65x  (± 0.00) slower