Optimize I18n::Locale::Fallbacks#[] for recursive locale mappings

[uiur]

I found this performance issue when running our service.

Problem

The service had a big locale mapping that is recursive. This takes ~1.5s before cache.

hash = {
  :ja=>[:en, :"zh-CN", :"zh-TW", :"zh-HK", :fr, :ko, :th, :vi],
  :en=>[:ja, :"zh-CN", :"zh-TW", :"zh-HK", :fr, :ko, :th, :vi],
  :"zh-CN"=>[:en, :ja, :"zh-TW", :"zh-HK", :fr, :ko, :th, :vi],
  :"zh-TW"=>[:en, :ja, :"zh-CN", :"zh-HK", :fr, :ko, :th, :vi],
  :"zh-HK"=>[:en, :ja, :"zh-CN", :"zh-TW", :fr, :ko, :th, :vi],
  :fr=>[:en, :ja, :"zh-CN", :"zh-TW", :"zh-HK", :ko, :th, :vi],
  :ko=>[:en, :ja, :"zh-CN", :"zh-TW", :"zh-HK", :fr, :th, :vi],
  :th=>[:en, :ja, :"zh-CN", :"zh-TW", :"zh-HK", :fr, :ko, :vi],
  :vi=>[:en, :ja, :"zh-CN", :"zh-TW", :"zh-HK", :fr, :ko, :th]
}
fallbacks = I18n::Locale::Fallbacks.new(hash)
puts Benchmark.realtime { fallbacks[:en] }
#=> 1.5359459999017417

The cause is from I18n::Locale::Fallbacks#compute. It computes locale fallbacks in a recursive way.

But it can be very slow for a recursive mapping like the above example.

Benchmark

original: 1.571336
new: 0.000546
ratio: 2876x faster

Code

```ruby require 'i18n' require 'benchmark' class Fallbacks < ::I18n::Locale::Fallbacks def compute(tags, include_defaults = true, exclude = []) result = [] Array(tags).each do |tag| tags = I18n::Locale::Tag.tag(tag).self_and_parents.map! { |t| t.to_sym } - exclude result += tags tags.each { |_tag| result += compute(@map[_tag], false, exclude + result) if @map[_tag] } end result.push(*defaults) if include_defaults result.uniq! result.compact! result end end hash = { :ja=>[:en, :"zh-CN", :"zh-TW", :"zh-HK", :fr, :ko, :th, :vi], :en=>[:ja, :"zh-CN", :"zh-TW", :"zh-HK", :fr, :ko, :th, :vi], :"zh-CN"=>[:en, :ja, :"zh-TW", :"zh-HK", :fr, :ko, :th, :vi], :"zh-TW"=>[:en, :ja, :"zh-CN", :"zh-HK", :fr, :ko, :th, :vi], :"zh-HK"=>[:en, :ja, :"zh-CN", :"zh-TW", :fr, :ko, :th, :vi], :fr=>[:en, :ja, :"zh-CN", :"zh-TW", :"zh-HK", :ko, :th, :vi], :ko=>[:en, :ja, :"zh-CN", :"zh-TW", :"zh-HK", :fr, :th, :vi], :th=>[:en, :ja, :"zh-CN", :"zh-TW", :"zh-HK", :fr, :ko, :vi], :vi=>[:en, :ja, :"zh-CN", :"zh-TW", :"zh-HK", :fr, :ko, :th] } original_durations = [] new_durations = [] 10.times do original_fallbacks = ::I18n::Locale::Fallbacks.new(hash) new_fallbacks = ::Fallbacks.new(hash) locale = :en original_durations << Benchmark.realtime { original_fallbacks[locale] } new_durations << Benchmark.realtime { new_fallbacks[locale] } end original_duration = original_durations.sum.to_f / original_durations.size new_duration = new_durations.sum.to_f / new_durations.size ratio = original_duration / new_duration puts "original: #{original_duration.round(6)}" puts "new: #{new_duration.round(6)}" puts "ratio: #{ratio.round}x faster" ```

[radar]

Thank you! Looks good to me.