Cache results of computing model type

We faced a significant performance decrease when we started using STI
without storing full namespaced class name in type column (because of PostgreSQL
length limit for ENUM types).
We realized that the cause of it is the slow STI model instantiation. Problematic
method appears to be `ActiveRecord::Base.compute_type`, which is used to find
the right class for STI model on every instantiation.
It builds an array of candidate types and then iterates through it calling
`safe_constantize` on every type until it finds appropriate constant. So if
desired type isn't the first element in this array there will be at least one
unsuccessful call to `safe_constantize`, which is very expensive, since it's
defined in terms of `begin; rescue; end`.

This commit is an attempt to speed up `compute_type` method simply by caching
results of previous calls.

```ruby
class MyCompany::MyApp::Business::Accounts::Base < ApplicationRecord
  self.table_name = 'accounts'
  self.store_full_sti_class = false
end

class MyCompany::MyApp::Business::Accounts::Free < Base
end

class MyCompany::MyApp::Business::Accounts::Standard < Base
  # patch .compute_type there
end

puts '======================= .compute_type ======================='
Benchmark.ips do |x|
  x.report("original method") do
    MyCompany::MyApp::Business::Accounts::Free.send :compute_type, 'Free'
  end
  x.report("with types cached") do
    MyCompany::MyApp::Business::Accounts::Standard.send :compute_type, 'Standard'
  end
  x.compare!
end
```

```
======================= .compute_type =======================
  with types cached:  1529019.4 i/s
    original method:     2850.2 i/s - 536.46x  slower
```

```ruby
5_000.times do |i|
  MyCompany::MyApp::Business::Accounts::Standard.create!(name: "standard_#{i}")
end

5_000.times do |i|
  MyCompany::MyApp::Business::Accounts::Free.create!(name: "free_#{i}")
end

puts '====================== .limit(100).to_a ======================='
Benchmark.ips do |x|
  x.report("without .compute_type patch") do
    MyCompany::MyApp::Business::Accounts::Free.limit(100).to_a
  end
  x.report("with .compute_type patch") do
    MyCompany::MyApp::Business::Accounts::Standard.limit(100).to_a
  end
  x.compare!
end
```

```
====================== .limit(100).to_a =======================
     with .compute_type patch:      360.5 i/s
  without .compute_type patch:       24.7 i/s - 14.59x  slower
```

4 files changed, 33 insertions, 10 deletions

diff --git a/activerecord/CHANGELOG.md b/activerecord/CHANGELOG.md
index b59d24f88d..5069c6666f 100644
--- a/activerecord/CHANGELOG.md
+++ b/activerecord/CHANGELOG.md
@@ -1,3 +1,7 @@
+*   Optimize slow model instantiation when using STI and `store_full_sti_class = false` option.
+
+    *Konstantin Lazarev*
+
 *   Add `touch` option to counter cache modifying methods.
 
     Works when updating, resetting, incrementing and decrementing counters:
diff --git a/activerecord/lib/active_record/inheritance.rb b/activerecord/lib/active_record/inheritance.rb
index a1d4f47372..fbdaeaae51 100644
--- a/activerecord/lib/active_record/inheritance.rb
+++ b/activerecord/lib/active_record/inheritance.rb
@@ -130,16 +130,26 @@ module ActiveRecord
         store_full_sti_class ? name : name.demodulize
       end
 
+      def inherited(subclass)
+        subclass.instance_variable_set(:@_type_candidates_cache, Concurrent::Map.new)
+        super
+      end
+
       protected
 
         # Returns the class type of the record using the current module as a prefix. So descendants of
         # MyApp::Business::Account would appear as MyApp::Business::AccountSubclass.
         def compute_type(type_name)
-          if type_name.match(/^::/)
+          if type_name.start_with?("::".freeze)
             # If the type is prefixed with a scope operator then we assume that
             # the type_name is an absolute reference.
             ActiveSupport::Dependencies.constantize(type_name)
           else
+            type_candidate = @_type_candidates_cache[type_name]
+            if type_candidate && type_constant = ActiveSupport::Dependencies.safe_constantize(type_candidate)
+              return type_constant
+            end
+
             # Build a list of candidates to search for
             candidates = []
             name.scan(/::|$/) { candidates.unshift "#{$`}::#{type_name}" }
@@ -147,7 +157,10 @@ module ActiveRecord
 
             candidates.each do |candidate|
               constant = ActiveSupport::Dependencies.safe_constantize(candidate)
-              return constant if candidate == constant.to_s
+              if candidate == constant.to_s
+                @_type_candidates_cache[type_name] = candidate
+                return constant
+              end
             end
 
             raise NameError.new("uninitialized constant #{candidates.first}", candidates.first)
diff --git a/activerecord/test/cases/inheritance_test.rb b/activerecord/test/cases/inheritance_test.rb
index 9ad4664567..e570e9ac1d 100644
--- a/activerecord/test/cases/inheritance_test.rb
+++ b/activerecord/test/cases/inheritance_test.rb
@@ -58,21 +58,21 @@ class InheritanceTest < ActiveRecord::TestCase
   end
 
   def test_compute_type_success
-    assert_equal Author, ActiveRecord::Base.send(:compute_type, "Author")
+    assert_equal Author, Company.send(:compute_type, "Author")
   end
 
   def test_compute_type_nonexistent_constant
     e = assert_raises NameError do
-      ActiveRecord::Base.send :compute_type, "NonexistentModel"
+      Company.send :compute_type, "NonexistentModel"
     end
-    assert_equal "uninitialized constant ActiveRecord::Base::NonexistentModel", e.message
-    assert_equal "ActiveRecord::Base::NonexistentModel", e.name
+    assert_equal "uninitialized constant Company::NonexistentModel", e.message
+    assert_equal "Company::NonexistentModel", e.name
   end
 
   def test_compute_type_no_method_error
     ActiveSupport::Dependencies.stub(:safe_constantize, proc { raise NoMethodError }) do
       assert_raises NoMethodError do
-        ActiveRecord::Base.send :compute_type, "InvalidModel"
+        Company.send :compute_type, "InvalidModel"
       end
     end
   end
@@ -90,7 +90,7 @@ class InheritanceTest < ActiveRecord::TestCase
     ActiveSupport::Dependencies.stub(:safe_constantize, proc { raise e }) do
 
       exception = assert_raises NameError do
-        ActiveRecord::Base.send :compute_type, "InvalidModel"
+        Company.send :compute_type, "InvalidModel"
       end
       assert_equal error.message, exception.message
     end
@@ -99,7 +99,7 @@ class InheritanceTest < ActiveRecord::TestCase
   def test_compute_type_argument_error
     ActiveSupport::Dependencies.stub(:safe_constantize, proc { raise ArgumentError }) do
       assert_raises ArgumentError do
-        ActiveRecord::Base.send :compute_type, "InvalidModel"
+        Company.send :compute_type, "InvalidModel"
       end
     end
   end
diff --git a/activerecord/test/cases/reflection_test.rb b/activerecord/test/cases/reflection_test.rb
index a90058e8bb..0ef51272b9 100644
--- a/activerecord/test/cases/reflection_test.rb
+++ b/activerecord/test/cases/reflection_test.rb
@@ -100,7 +100,13 @@ class ReflectionTest < ActiveRecord::TestCase
   end
 
   def test_reflection_klass_for_nested_class_name
-    reflection = ActiveRecord::Reflection.create(:has_many, nil, nil, { class_name: "MyApplication::Business::Company" }, ActiveRecord::Base)
+    reflection = ActiveRecord::Reflection.create(
+      :has_many,
+      nil,
+      nil,
+      { class_name: "MyApplication::Business::Company" },
+      Customer
+    )
     assert_nothing_raised do
       assert_equal MyApplication::Business::Company, reflection.klass
     end