[applied] Bug 29303 - Cache the result of structural aggregate comparison

Message ID 87fsjme2nv.fsf@redhat.com
State New
Headers
Series [applied] Bug 29303 - Cache the result of structural aggregate comparison |

Commit Message

Dodji Seketeli June 30, 2022, 12:50 p.m. UTC
  Hello,

When we are forced to structurally compare aggregate types (classes
and function types), some sub-types pairs can be compared an
innumerable number of times over and over again.  This leads to having
extremely slow comparison times for the portions of the code that are
subject to structural comparison because canonical comparison has not
yet been setup.  For instance, this happens in the dwarf-reader in the
function read_context::resolve_declaration_only_classes or, in the ir
module in the function type_base::get_canonical_type_for when type
canonicalization is being done.

To overcome this, this patch caches the result of comparing two pairs
of aggregate (class or function) type, ensuring that a pair of
aggregate sub-type is compared at most once during the structural
comparison of a given type.

Note that this caching scheme is used only during declaration classes
resolution and type canonicalization.

This sped up things quite noticeably as self comparing both binutils
and dovecot package sets in Fedora 36 was literally taking forever
prior to the patch and is now completing with this patch.

	* src/abg-ir-priv.h (struct uint64_t_pair_hash): Define new type.
	(uint64_t_pair_type, uint64_t_pairs_set_type)
	(type_comparison_result_type): Define new typedefs.
	(environment::priv::{classes_being_compared_,
	fn_types_being_compared_}): Use the new uint64_t_pairs_set_type
	type for these.
	(environment::priv::{type_comparison_results_cache_,
	allow_type_comparison_results_caching_}): Define new data members.
	(environment::priv::priv): Initialize the new
	allow_type_comparison_results_caching_ scalar data member.
	(environment::priv::{allow_type_comparison_results_caching,
	cache_type_comparison_result, is_type_comparison_cached,
	clear_type_comparison_results_cache}): Define new member
	functions.
	(environment::priv::{mark_as_being_compared,
	unmark_as_being_compared, comparison_started}): Take a pair of
	types.
	(struct function_type::priv): Move this here, from ...
	* src/abg-ir.cc (struct function_type::priv): ... here.
	(is_comparison_cycle_detected, mark_types_as_being_compared)
	(unmark_types_as_being_compared): Adjust call to the new
	environment::priv::{comparison_started, mark_as_being_compared,
	unmark_as_being_compared}.
	(type_base::get_canonical_type_for): Use aggregate types
	comparison result caching when doing type comparison.
	(equals): In the overload for function_type, class_or_union and
	class_decl, cache the result of aggregate type comparison and
	re-use that cached result when it's available.
	* src/abg-dwarf-reader.cc
	(read_context::compare_before_canonicalisation): Use aggregate
	types comparison result caching when doing type comparison.

Signed-off-by: Dodji Seketeli <dodji@redhat.com>
Applied to master.
---
 src/abg-dwarf-reader.cc |   3 +
 src/abg-ir-priv.h       | 362 +++++++++++++++++++++++++++++++++-------
 src/abg-ir.cc           | 141 ++++++++--------
 3 files changed, 377 insertions(+), 129 deletions(-)
  

Patch

diff --git a/src/abg-dwarf-reader.cc b/src/abg-dwarf-reader.cc
index 7c8ec012..3b75ddf1 100644
--- a/src/abg-dwarf-reader.cc
+++ b/src/abg-dwarf-reader.cc
@@ -4156,10 +4156,13 @@  public:
     const environment* e = l->get_environment();
     ABG_ASSERT(!e->canonicalization_is_done());
 
+    e->priv_->allow_type_comparison_results_caching(true);
     bool s0 = e->decl_only_class_equals_definition();
     e->decl_only_class_equals_definition(true);
     bool equal = l == r;
     e->decl_only_class_equals_definition(s0);
+    e->priv_->clear_type_comparison_results_cache();
+    e->priv_->allow_type_comparison_results_caching(false);
     return equal;
   }
 
diff --git a/src/abg-ir-priv.h b/src/abg-ir-priv.h
index ddca3a1f..0a5ab00d 100644
--- a/src/abg-ir-priv.h
+++ b/src/abg-ir-priv.h
@@ -301,6 +301,31 @@  struct type_base::priv
 }; // end struct type_base::priv
 
 // <environment definitions>
+
+/// The hashing functor for a pair of uint64_t.
+struct uint64_t_pair_hash
+{
+  /// Hashing function for a pair of uint64_t.
+  ///
+  /// @param p the pair to hash.
+  uint64_t
+  operator()(const std::pair<uint64_t, uint64_t>& p) const
+  {return abigail::hashing::combine_hashes(p.first, p.second);}
+};
+
+/// A convenience typedef for a pair of uint64_t which is initially
+/// intended to store a pair of pointer values.
+typedef std::pair<uint64_t, uint64_t> uint64_t_pair_type;
+
+/// A convenience typedef for a set of @ref uint64_t_pair
+typedef unordered_set<uint64_t_pair_type,
+		      uint64_t_pair_hash> uint64_t_pairs_set_type;
+/// A convenience typedef for a map which key is a pair of uint64_t
+/// and which value is a boolean.  This is initially intended to cache
+/// the result of comparing two (sub-)types.
+typedef unordered_map<uint64_t_pair_type, bool,
+		      uint64_t_pair_hash> type_comparison_result_type;
+
 /// The private data of the @ref environment type.
 struct environment::priv
 {
@@ -309,8 +334,20 @@  struct environment::priv
   mutable vector<type_base_sptr>	sorted_canonical_types_;
   type_base_sptr			void_type_;
   type_base_sptr			variadic_marker_type_;
-  unordered_set<const class_or_union*>	classes_being_compared_;
-  unordered_set<const function_type*>	fn_types_being_compared_;
+  // The set of pairs of class types being currently compared.  It's
+  // used to avoid endless loops while recursively comparing types.
+  // This should be empty when none of the 'equal' overloads are
+  // currently being invoked.
+  uint64_t_pairs_set_type		classes_being_compared_;
+  // The set of pairs of function types being currently compared.  It's used
+  // to avoid endless loops while recursively comparing types.  This
+  // should be empty when none of the 'equal' overloads are currently
+  // being invoked.
+  uint64_t_pairs_set_type		fn_types_being_compared_;
+  // This is a cache for the result of comparing two sub-types (of
+  // either class or function types) that are designated by their
+  // memory address in the IR.
+  type_comparison_result_type		type_comparison_results_cache_;
   vector<type_base_sptr>		extra_live_types_;
   interned_string_pool			string_pool_;
   // The two vectors below represent the stack of left and right
@@ -386,6 +423,7 @@  struct environment::priv
   bool					do_on_the_fly_canonicalization_;
   bool					decl_only_class_equals_definition_;
   bool					use_enum_binary_only_equality_;
+  bool					allow_type_comparison_results_caching_;
 #ifdef WITH_DEBUG_SELF_COMPARISON
   bool					self_comparison_debug_on_;
 #endif
@@ -410,7 +448,8 @@  struct environment::priv
     : canonicalization_is_done_(),
       do_on_the_fly_canonicalization_(true),
       decl_only_class_equals_definition_(false),
-      use_enum_binary_only_equality_(true)
+      use_enum_binary_only_equality_(true),
+      allow_type_comparison_results_caching_(false)
 #ifdef WITH_DEBUG_SELF_COMPARISON
     ,
       self_comparison_debug_on_(false)
@@ -423,6 +462,90 @@  struct environment::priv
 #endif
   {}
 
+  /// Allow caching of the sub-types comparison results during the
+  /// invocation of the @ref equal overloads for class and function
+  /// types.
+  ///
+  /// @param f if true, allow type comparison result caching.
+  void
+  allow_type_comparison_results_caching(bool f)
+  {allow_type_comparison_results_caching_ = f;}
+
+  /// Check whether if caching of the sub-types comparison results during the
+  /// invocation of the @ref equal overloads for class and function
+  /// types is in effect.
+  ///
+  /// @return true iff caching of the sub-types comparison results
+  /// during the invocation of the @ref equal overloads for class and
+  /// function types is in effect.
+  bool
+  allow_type_comparison_results_caching() const
+  {return allow_type_comparison_results_caching_;}
+
+  /// Cache the result of comparing two sub-types.
+  ///
+  /// @param first the first sub-type that has been compared. Its
+  /// address is going to be stored in the cache.
+  ///
+  /// @param second the second sub-type that has been compared. Its
+  /// address is going to be stored in the cache.
+  ///
+  /// @param r the result of comparing @p first and @p second.  This
+  /// is going to be stored in the cache, as well as the addresses of
+  /// @p first and @p second.
+  template<typename T>
+  void
+  cache_type_comparison_result(T& first, T& second, bool r)
+  {
+    if (allow_type_comparison_results_caching())
+      type_comparison_results_cache_.emplace
+	(std::make_pair(reinterpret_cast<uint64_t>(&first),
+			reinterpret_cast<uint64_t>(&second)),
+	 r);
+  }
+
+  /// Retrieve the result of comparing two sub-types from the cache,
+  /// if it was previously stored.
+  ///
+  /// @param first the first sub-type to consider.
+  ///
+  /// @param second the second sub-type to consider.  The pair of
+  /// addresses of {@p first, @p second} is going to be looked up in
+  /// the cache.  If it's present, then the associated result of the
+  /// comparison of @p first against @p second is present as well, and
+  /// is returned.
+  ///
+  /// @param r this is an out parameter which is set to the result of
+  /// the comparison of @p first against @p second if the pair of
+  /// addresses of {@p first, @p second} is present in the cache.
+  ///
+  /// @return true iff the pair of addresses of {@p first, @p second}
+  /// is present in the cache.  In that case, the associated result of
+  /// the comparison of @p first against @p second is returned in the
+  /// argument of @p r.
+  template<typename T>
+  bool
+  is_type_comparison_cached(T& first, T& second, bool& r)
+  {
+    if (!allow_type_comparison_results_caching())
+      return false;
+
+    type_comparison_result_type::const_iterator it =
+      type_comparison_results_cache_.find
+	 (std::make_pair(reinterpret_cast<uint64_t>(&first),
+			 reinterpret_cast<uint64_t>(&second)));
+    if (it == type_comparison_results_cache_.end())
+      return false;
+
+    r = it->second;
+    return true;
+  }
+
+  /// Clear the cache type comparison results.
+  void
+  clear_type_comparison_results_cache()
+  {type_comparison_results_cache_.clear();}
+
   /// Push a pair of operands on the stack of operands of the current
   /// type comparison, during type canonicalization.
   ///
@@ -808,56 +931,70 @@  struct class_or_union::priv
 	non_static_data_members_.push_back(*i);
   }
 
-  /// Mark a class or union or union as being currently compared using
-  /// the class_or_union== operator.
+  /// Mark a pair of classes or unions as being currently compared
+  /// using the class_or_union== operator.
   ///
-  /// Note that is marking business is to avoid infinite loop when
-  /// comparing a class or union or union. If via the comparison of a
-  /// data member or a member function a recursive re-comparison of
-  /// the class or union is attempted, the marking business help to
+  /// Note that this marking business is to avoid infinite loop when
+  /// comparing a pair of classes or unions. If via the comparison of
+  /// a data member or a member function a recursive re-comparison of
+  /// the class or union is attempted, the marking process helps to
   /// detect that infinite loop possibility and avoid it.
   ///
-  /// @param klass the class or union or union to mark as being
+  /// @param first the class or union (of the pair) to mark as being
   /// currently compared.
+  ///
+  /// @param second the second class or union (of the pair) to mark as
+  /// being currently compared.
   void
-  mark_as_being_compared(const class_or_union& klass) const
+  mark_as_being_compared(const class_or_union& first,
+			 const class_or_union& second) const
   {
-    const environment* env = klass.get_environment();
+    const environment* env = first.get_environment();
     ABG_ASSERT(env);
-    env->priv_->classes_being_compared_.insert(&klass);
+    env->priv_->classes_being_compared_.insert
+      (std::make_pair(reinterpret_cast<uint64_t>(&first),
+		      reinterpret_cast<uint64_t>(&second)));
   }
 
-  /// Mark a class or union as being currently compared using the
-  /// class_or_union== operator.
+  /// Mark a pair of classes or unions as being currently compared
+  /// using the class_or_union== operator.
   ///
-  /// Note that is marking business is to avoid infinite loop when
-  /// comparing a class or union. If via the comparison of a data
-  /// member or a member function a recursive re-comparison of the
-  /// class or union is attempted, the marking business help to detect
-  /// that infinite loop possibility and avoid it.
+  /// Note that this marking business is to avoid infinite loop when
+  /// comparing a pair of classes or unions. If via the comparison of
+  /// a data member or a member function a recursive re-comparison of
+  /// the class or union is attempted, the marking process helps to
+  /// detect that infinite loop possibility and avoid it.
+  ///
+  /// @param first the class or union (of the pair) to mark as being
+  /// currently compared.
   ///
-  /// @param klass the class or union to mark as being currently
-  /// compared.
+  /// @param second the second class or union (of the pair) to mark as
+  /// being currently compared.
   void
-  mark_as_being_compared(const class_or_union* klass) const
-  {mark_as_being_compared(*klass);}
+  mark_as_being_compared(const class_or_union* first,
+			 const class_or_union* second) const
+  {mark_as_being_compared(*first, *second);}
 
-  /// Mark a class or union as being currently compared using the
-  /// class_or_union== operator.
+  /// Mark a pair of classes or unions as being currently compared
+  /// using the class_or_union== operator.
   ///
-  /// Note that is marking business is to avoid infinite loop when
-  /// comparing a class or union. If via the comparison of a data
-  /// member or a member function a recursive re-comparison of the
-  /// class or union is attempted, the marking business help to detect
-  /// that infinite loop possibility and avoid it.
+  /// Note that this marking business is to avoid infinite loop when
+  /// comparing a pair of classes or unions. If via the comparison of
+  /// a data member or a member function a recursive re-comparison of
+  /// the class or union is attempted, the marking process helps to
+  /// detect that infinite loop possibility and avoid it.
+  ///
+  /// @param first the class or union (of the pair) to mark as being
+  /// currently compared.
   ///
-  /// @param klass the class or union to mark as being currently
-  /// compared.
+  /// @param second the second class or union (of the pair) to mark as
+  /// being currently compared.
   void
-  mark_as_being_compared(const class_or_union_sptr& klass) const
-  {mark_as_being_compared(*klass);}
+  mark_as_being_compared(const class_or_union_sptr& first,
+			 const class_or_union_sptr& second) const
+  {mark_as_being_compared(*first, *second);}
 
-  /// If the instance of class_or_union has been previously marked as
+  /// If a pair of class_or_union has been previously marked as
   /// being compared -- via an invocation of mark_as_being_compared()
   /// this method unmarks it.  Otherwise is has no effect.
   ///
@@ -866,59 +1003,164 @@  struct class_or_union::priv
   /// multi-threaded environment you should probably protect the
   /// access to that static data member with a mutex or somesuch.
   ///
-  /// @param klass the instance of class_or_union to unmark.
+  /// @param first the first instance of class_or_union (of the pair)
+  /// to unmark.
+  ///
+  /// @param second the second instance of class_or_union (of the
+  /// pair) to unmark.
   void
-  unmark_as_being_compared(const class_or_union& klass) const
+  unmark_as_being_compared(const class_or_union& first,
+			   const class_or_union& second) const
   {
-    const environment* env = klass.get_environment();
+    const environment* env = first.get_environment();
     ABG_ASSERT(env);
-    env->priv_->classes_being_compared_.erase(&klass);
+    env->priv_->classes_being_compared_.erase
+      (std::make_pair(reinterpret_cast<uint64_t>(&first),
+		      reinterpret_cast<uint64_t>(&second)));
   }
 
-  /// If the instance of class_or_union has been previously marked as
+  /// If a pair of class_or_union has been previously marked as
   /// being compared -- via an invocation of mark_as_being_compared()
   /// this method unmarks it.  Otherwise is has no effect.
   ///
-  /// @param klass the instance of class_or_union to unmark.
+  /// This method is not thread safe because it uses the static data
+  /// member classes_being_compared_.  If you wish to use it in a
+  /// multi-threaded environment you should probably protect the
+  /// access to that static data member with a mutex or somesuch.
+  ///
+  /// @param first the first instance of class_or_union (of the pair)
+  /// to unmark.
+  ///
+  /// @param second the second instance of class_or_union (of the
+  /// pair) to unmark.
   void
-  unmark_as_being_compared(const class_or_union* klass) const
+  unmark_as_being_compared(const class_or_union* first,
+			   const class_or_union* second) const
   {
-    if (klass)
-      return unmark_as_being_compared(*klass);
+    if (!first || !second)
+      return;
+    unmark_as_being_compared(*first, *second);
   }
 
-  /// Test if a given instance of class_or_union is being currently
-  /// compared.
+  /// Test if a pair of class_or_union is being currently compared.
   ///
-  ///@param klass the class or union to test.
+  ///@param first the first class or union (of the pair) to test for.
   ///
-  /// @return true if @p klass is being compared, false otherwise.
+  ///@param second the second class or union (of the pair) to test for.
+  ///
+  /// @return true if the pair {@p first, @p second} is being
+  /// compared, false otherwise.
   bool
-  comparison_started(const class_or_union& klass) const
+  comparison_started(const class_or_union& first,
+		     const class_or_union& second) const
   {
-    const environment* env = klass.get_environment();
+    const environment* env = first.get_environment();
     ABG_ASSERT(env);
-    return env->priv_->classes_being_compared_.count(&klass);
+    return env->priv_->
+      classes_being_compared_.count
+      (std::make_pair(reinterpret_cast<uint64_t>(&first),
+		      reinterpret_cast<uint64_t>((&second))));
   }
 
-  /// Test if a given instance of class_or_union is being currently
-  /// compared.
+  /// Test if a pair of class_or_union is being currently compared.
+  ///
+  ///@param first the first class or union (of the pair) to test for.
   ///
-  ///@param klass the class or union to test.
+  ///@param second the second class or union (of the pair) to test for.
   ///
-  /// @return true if @p klass is being compared, false otherwise.
+  /// @return true if the pair {@p first, @p second} is being
+  /// compared, false otherwise.
   bool
-  comparison_started(const class_or_union* klass) const
+  comparison_started(const class_or_union* first,
+		     const class_or_union* second) const
   {
-    if (klass)
-      return comparison_started(*klass);
+    if (first && second)
+      return comparison_started(*first, *second);
     return false;
   }
 }; // end struct class_or_union::priv
 
+// <function_type::priv definitions>
+
+/// The type of the private data of the @ref function_type type.
+struct function_type::priv
+{
+  parameters parms_;
+  type_base_wptr return_type_;
+  interned_string cached_name_;
+  interned_string internal_cached_name_;
+  interned_string temp_internal_cached_name_;
+
+  priv()
+  {}
+
+  priv(const parameters&	parms,
+       type_base_sptr		return_type)
+    : parms_(parms),
+      return_type_(return_type)
+  {}
+
+  priv(type_base_sptr return_type)
+    : return_type_(return_type)
+  {}
+
+  /// Mark a given pair of @ref function_type as being compared.
+  ///
+  /// @param first the first @ref function_type of the pair being
+  /// compared, to mark.
+  ///
+  /// @param second the second @ref function_type of the pair being
+  /// compared, to mark.
+  void
+  mark_as_being_compared(const function_type& first,
+			 const function_type& second) const
+  {
+    const environment* env = first.get_environment();
+    ABG_ASSERT(env);
+    env->priv_->fn_types_being_compared_.insert
+      (std::make_pair(reinterpret_cast<uint64_t>(&first),
+		      reinterpret_cast<uint64_t>(&second)));
+  }
+
+  /// Mark a given pair of @ref function_type as being compared.
+  ///
+  /// @param first the first @ref function_type of the pair being
+  /// compared, to mark.
+  ///
+  /// @param second the second @ref function_type of the pair being
+  /// compared, to mark.
+  void
+  unmark_as_being_compared(const function_type& first,
+			   const function_type& second) const
+  {
+    const environment* env = first.get_environment();
+    ABG_ASSERT(env);
+    env->priv_->fn_types_being_compared_.erase
+      (std::make_pair(reinterpret_cast<uint64_t>(&first),
+		      reinterpret_cast<uint64_t>(&second)));
+  }
+
+  /// Tests if a @ref function_type is currently being compared.
+  ///
+  /// @param type the function type to take into account.
+  ///
+  /// @return true if @p type is being compared.
+  bool
+  comparison_started(const function_type& first,
+		     const function_type& second) const
+  {
+    const environment* env = first.get_environment();
+    ABG_ASSERT(env);
+    return env->priv_->fn_types_being_compared_.count
+      (std::make_pair(reinterpret_cast<uint64_t>(&first),
+		      reinterpret_cast<uint64_t>(&second)));
+  }
+};// end struc function_type::priv
+
+// </function_type::priv definitions>
+
 } // end namespace ir
 
 } // end namespace abigail
 
 #endif // __ABG_IR_PRIV_H__
-
diff --git a/src/abg-ir.cc b/src/abg-ir.cc
index 801a7445..7a5db60f 100644
--- a/src/abg-ir.cc
+++ b/src/abg-ir.cc
@@ -913,8 +913,7 @@  template<typename T>
 bool
 is_comparison_cycle_detected(T& l, T& r)
 {
-  bool result = (l.priv_->comparison_started(l)
-		 || l.priv_->comparison_started(r));
+  bool result = l.priv_->comparison_started(l, r);
   return result ;
 }
 
@@ -962,8 +961,7 @@  template<typename T>
 void
 mark_types_as_being_compared(T& l, T&r)
 {
-  l.priv_->mark_as_being_compared(l);
-  l.priv_->mark_as_being_compared(r);
+  l.priv_->mark_as_being_compared(l, r);
   push_composite_type_comparison_operands(l, r);
 }
 
@@ -982,8 +980,7 @@  template<typename T>
 void
 unmark_types_as_being_compared(T& l, T&r)
 {
-  l.priv_->unmark_as_being_compared(l);
-  l.priv_->unmark_as_being_compared(r);
+  l.priv_->unmark_as_being_compared(l, r);
   pop_composite_type_comparison_operands(l, r);
 }
 
@@ -13907,11 +13904,14 @@  type_base::get_canonical_type_for(type_base_sptr t)
 	  // Compare types by considering that decl-only classes don't
 	  // equal their definition.
 	  env->decl_only_class_equals_definition(false);
+	  env->priv_->allow_type_comparison_results_caching(true);
 	  bool equal = (types_defined_same_linux_kernel_corpus_public(**it, *t)
 			|| compare_types_during_canonicalization(*it, t));
 	  // Restore the state of the on-the-fly-canonicalization and
 	  // the decl-only-class-being-equal-to-a-matching-definition
 	  // flags.
+	  env->priv_->allow_type_comparison_results_caching(false);
+	  env->priv_->clear_type_comparison_results_cache();
 	  env->do_on_the_fly_canonicalization(false);
 	  env->decl_only_class_equals_definition
 	    (saved_decl_only_class_equals_definition);
@@ -18754,68 +18754,6 @@  var_decl::~var_decl()
 
 // </var_decl definitions>
 
-// <function_type>
-
-/// The type of the private data of the @ref function_type type.
-struct function_type::priv
-{
-  parameters parms_;
-  type_base_wptr return_type_;
-  interned_string cached_name_;
-  interned_string internal_cached_name_;
-  interned_string temp_internal_cached_name_;
-
-  priv()
-  {}
-
-  priv(const parameters&	parms,
-       type_base_sptr		return_type)
-    : parms_(parms),
-      return_type_(return_type)
-  {}
-
-  priv(type_base_sptr return_type)
-    : return_type_(return_type)
-  {}
-
-  /// Mark a given @ref function_type as being compared.
-  ///
-  /// @param type the @ref function_type to mark as being compared.
-  void
-  mark_as_being_compared(const function_type& type) const
-  {
-    const environment* env = type.get_environment();
-    ABG_ASSERT(env);
-    env->priv_->fn_types_being_compared_.insert(&type);
-  }
-
-  /// If a given @ref function_type was marked as being compared, this
-  /// function unmarks it.
-  ///
-  /// @param type the @ref function_type to mark as *NOT* being
-  /// compared.
-  void
-  unmark_as_being_compared(const function_type& type) const
-  {
-    const environment* env = type.get_environment();
-    ABG_ASSERT(env);
-    env->priv_->fn_types_being_compared_.erase(&type);
-  }
-
-  /// Tests if a @ref function_type is currently being compared.
-  ///
-  /// @param type the function type to take into account.
-  ///
-  /// @return true if @p type is being compared.
-  bool
-  comparison_started(const function_type& type) const
-  {
-    const environment* env = type.get_environment();
-    ABG_ASSERT(env);
-    return env->priv_->fn_types_being_compared_.count(&type);
-  }
-};// end struc function_type::priv
-
 /// This function is automatically invoked whenever an instance of
 /// this type is canonicalized.
 ///
@@ -19050,6 +18988,18 @@  equals(const function_type& l,
 #define RETURN(value) return return_comparison_result(l, r, value)
 
   RETURN_TRUE_IF_COMPARISON_CYCLE_DETECTED(l, r);
+
+  {
+    // First of all, let's see if these two function types haven't
+    // already been compared.  If so, and if the result of the
+    // comparison has been cached, let's just re-use it, rather than
+    // comparing them all over again.
+    bool cached_result = false;
+    if (l.get_environment()->priv_->is_type_comparison_cached(l, r,
+							      cached_result))
+      return cached_result;
+  }
+
   mark_types_as_being_compared(l, r);
 
   bool result = true;
@@ -19178,6 +19128,17 @@  equals(const function_type& l,
 	RETURN(result);
     }
 
+  // We are done comparing these two types and we have a full
+  // understanding of how they might be different, if they are.  Let's
+  // cache the result of this comparison -- in case we are asked in a
+  // very near future to compare them again.
+  //
+  // TODO: If further profiling shows its necessity, maybe we should
+  // perform this caching also on the earlier return points of this
+  // function.  That would basically mean to redefine the RETURN macro
+  // to make it perform this caching for us.
+  l.get_environment()->priv_->cache_type_comparison_result(l, r, result);
+
   RETURN(result);
 #undef RETURN
 }
@@ -21583,6 +21544,16 @@  equals(const class_or_union& l, const class_or_union& r, change_kind* k)
       RETURN(val);
     }
 
+  {
+    // First of all, let's see if these two types haven't already been
+    // compared.  If so, and if the result of the comparison has been
+    // cached, let's just re-use it, rather than comparing them all
+    // over again.
+    bool result = false;
+    if (l.get_environment()->priv_->is_type_comparison_cached(l, r, result))
+      return result;
+  }
+
   // No need to go further if the classes have different names or
   // different size / alignment.
   if (!(l.decl_base::operator==(r) && l.type_base::operator==(r)))
@@ -21704,6 +21675,17 @@  equals(const class_or_union& l, const class_or_union& r, change_kind* k)
 	}
   }
 
+  // We are done comparing these two types and we have a full
+  // understanding of how they might be different, if they are.  Let's
+  // cache the result of this comparison -- in case we are asked in a
+  // very near future to compare them again.
+  //
+  // TODO: If further profiling shows its necessity, maybe we should
+  // perform this caching also on the earlier return points of this
+  // function.  That would basically mean to redefine the RETURN macro
+  // to make it perform this caching for us.
+  l.get_environment()->priv_->cache_type_comparison_result(l, r, result);
+
   RETURN(result);
 #undef RETURN
 }
@@ -23117,6 +23099,16 @@  maybe_cancel_propagated_canonical_type(const class_or_union& t)
 bool
 equals(const class_decl& l, const class_decl& r, change_kind* k)
 {
+  {
+    // First of all, let's see if these two types haven't already been
+    // compared.  If so, and if the result of the comparison has been
+    // cached, let's just re-use it, rather than comparing them all
+    // over again.
+    bool result = false;
+    if (l.get_environment()->priv_->is_type_comparison_cached(l, r, result))
+      return result;
+  }
+
   // if one of the classes is declaration-only then we take a fast
   // path here.
   if (l.get_is_declaration_only() || r.get_is_declaration_only())
@@ -23263,7 +23255,18 @@  equals(const class_decl& l, const class_decl& r, change_kind* k)
 	  }
       }
 
-  RETURN(result);
+    // We are done comparing these two types and we have a full
+    // understanding of how they might be different, if they are.  Let's
+    // cache the result of this comparison -- in case we are asked in a
+    // very near future to compare them again.
+    //
+    // TODO: If further profiling shows its necessity, maybe we should
+    // perform this caching also on the earlier return points of this
+    // function.  That would basically mean to redefine the RETURN macro
+    // to make it perform this caching for us.
+    l.get_environment()->priv_->cache_type_comparison_result(l, r, result);
+
+    RETURN(result);
 #undef RETURN
 }