PATCH: speed up --detect-odr-violations

[csilvers at google dot com (Craig Silverstein)]

I've committed this patch to CVS, to speed up slow odr-detection by
caching dwarf info.  This was motivated by a single testcase found by
a user, where linking with --detect-odr-violations was about 1000x
slower than linking without.  This brings it down to less than a 2x
slowdown.  It may be possible to improve that further (via tuning the
size of the cache, and improvements in the replacement algorithm).

craig

--cut here--

2008-04-29  Craig Silverstein  <csilvers@google.com>

	* dwarf_reader.cc (next_generation_count): New static var.
	(Addr2line_cache_entry): New struct.
	(addr2line_cache): New static var.
	(Dwarf_line_info::one_addr2line): Added caching.
	(Dwarf_line_info::clear_addr2line_cache): New function.
	* dwarf_reader.h (Dwarf_line_info::one_addr2line): Add
	cache-size parameter.
	(Dwarf_line_info::one_addr2line_cache): New function.
	* symtab.cc (Symbol_table::detect_odr_violations): Pass
	new cache-size argument to one_addr2line(), and clear cache.

Index: dwarf_reader.cc
===================================================================
RCS file: /cvs/src/src/gold/dwarf_reader.cc,v
retrieving revision 1.20
diff -u -r1.20 dwarf_reader.cc
--- dwarf_reader.cc	19 Apr 2008 18:30:58 -0000	1.20
+++ dwarf_reader.cc	30 Apr 2008 05:08:40 -0000
@@ -23,6 +23,7 @@
 #include "gold.h"
 
 #include <algorithm>
+#include <vector>
 
 #include "elfcpp_swap.h"
 #include "dwarf.h"
@@ -799,35 +800,120 @@
 
 // Dwarf_line_info routines.
 
+static int next_generation_count = 0;
+
+struct Addr2line_cache_entry
+{
+  Object* object;
+  unsigned int shndx;
+  Dwarf_line_info* dwarf_line_info;
+  unsigned int generation_count;
+  unsigned int access_count;
+
+  Addr2line_cache_entry(Object* o, unsigned int s, Dwarf_line_info* d)
+      : object(o), shndx(s), dwarf_line_info(d),
+        generation_count(next_generation_count), access_count(0)
+  {
+    if (next_generation_count < (1U << 31))
+      ++next_generation_count;
+  }
+};
+// We expect this cache to be small, so don't bother with a hashtable
+// or priority queue or anything: just use a simple vector.
+static std::vector<Addr2line_cache_entry> addr2line_cache;
+
 std::string
 Dwarf_line_info::one_addr2line(Object* object,
-                               unsigned int shndx, off_t offset)
+                               unsigned int shndx, off_t offset,
+                               size_t cache_size)
 {
-  switch (parameters->size_and_endianness())
+  Dwarf_line_info* lineinfo = NULL;
+  std::vector<Addr2line_cache_entry>::iterator it;
+
+  // First, check the cache.  If we hit, update the counts.
+  for (it = addr2line_cache.begin(); it != addr2line_cache.end(); ++it)
     {
+      if (it->object == object && it->shndx == shndx)
+        {
+          lineinfo = it->dwarf_line_info;
+          it->generation_count = next_generation_count;
+          // We cap generation_count at 2^31 -1 to avoid overflow.
+          if (next_generation_count < (1U << 31))
+            ++next_generation_count;
+          // We cap access_count at 31 so 2^access_count doesn't overflow
+          if (it->access_count < 31)
+            ++it->access_count;
+          break;
+        }
+    }
+
+  // If we don't hit the cache, create a new object and insert into the
+  // cache.
+  if (lineinfo == NULL)
+  {
+    switch (parameters->size_and_endianness())
+      {
 #ifdef HAVE_TARGET_32_LITTLE
-    case Parameters::TARGET_32_LITTLE:
-      return Sized_dwarf_line_info<32, false>(object, shndx).addr2line(shndx,
-                                                                       offset);
+        case Parameters::TARGET_32_LITTLE:
+          lineinfo = new Sized_dwarf_line_info<32, false>(object, shndx); break;
 #endif
 #ifdef HAVE_TARGET_32_BIG
-    case Parameters::TARGET_32_BIG:
-      return Sized_dwarf_line_info<32, true>(object, shndx).addr2line(shndx,
-                                                                      offset);
+        case Parameters::TARGET_32_BIG:
+          lineinfo = new Sized_dwarf_line_info<32, true>(object, shndx); break;
 #endif
 #ifdef HAVE_TARGET_64_LITTLE
-    case Parameters::TARGET_64_LITTLE:
-      return Sized_dwarf_line_info<64, false>(object, shndx).addr2line(shndx,
-                                                                       offset);
+        case Parameters::TARGET_64_LITTLE:
+          lineinfo = new Sized_dwarf_line_info<64, false>(object, shndx); break;
 #endif
 #ifdef HAVE_TARGET_64_BIG
-    case Parameters::TARGET_64_BIG:
-      return Sized_dwarf_line_info<64, true>(object, shndx).addr2line(shndx,
-                                                                      offset);
+        case Parameters::TARGET_64_BIG:
+          lineinfo = new Sized_dwarf_line_info<64, true>(object, shndx); break;
 #endif
-    default:
-      gold_unreachable();
+        default:
+          gold_unreachable();
+      }
+    addr2line_cache.push_back(Addr2line_cache_entry(object, shndx, lineinfo));
+  }
+
+  // Now that we have our object, figure out the answer
+  std::string retval = lineinfo->addr2line(shndx, offset);
+
+  // Finally, if our cache has grown too big, delete old objects.  We
+  // assume the common (probably only) case is deleting only one object.
+  // We use a pretty simple scheme to evict: function of LRU and MFU.
+  while (addr2line_cache.size() > cache_size)
+    {
+      unsigned int lowest_score = ~0U;
+      std::vector<Addr2line_cache_entry>::iterator lowest
+          = addr2line_cache.end();
+      for (it = addr2line_cache.begin(); it != addr2line_cache.end(); ++it)
+        {
+          const unsigned int score = (it->generation_count
+                                      + (1U << it->access_count));
+          if (score < lowest_score)
+            {
+              lowest_score = score;
+              lowest = it;
+            }
+        }
+      if (lowest != addr2line_cache.end())
+        {
+          delete lowest->dwarf_line_info;
+          addr2line_cache.erase(lowest);
+        }
     }
+
+  return retval;
+}
+
+void
+Dwarf_line_info::clear_addr2line_cache()
+{
+  for (std::vector<Addr2line_cache_entry>::iterator it = addr2line_cache.begin();
+       it != addr2line_cache.end();
+       ++it)
+    delete it->dwarf_line_info;
+  addr2line_cache.clear();
 }
 
 #ifdef HAVE_TARGET_32_LITTLE
Index: symtab.cc
===================================================================
RCS file: /cvs/src/src/gold/symtab.cc,v
retrieving revision 1.94
diff -u -r1.94 symtab.cc
--- symtab.cc	19 Apr 2008 18:30:58 -0000	1.94
+++ symtab.cc	30 Apr 2008 05:08:40 -0000
@@ -2343,10 +2343,12 @@
 	  // want to run this in a general Task for better
 	  // performance, we will need one Task for object, plus
 	  // appropriate locking to ensure that we don't conflict with
-	  // other uses of the object.
+	  // other uses of the object.  Also note, one_addr2line is not
+          // currently thread-safe.
 	  Task_lock_obj<Object> tl(task, locs->object);
+          // 16 is the size of the object-cache that one_addr2line should use.
           std::string lineno = Dwarf_line_info::one_addr2line(
-              locs->object, locs->shndx, locs->offset);
+              locs->object, locs->shndx, locs->offset, 16);
           if (!lineno.empty())
             line_nums.insert(lineno);
         }
@@ -2362,6 +2364,8 @@
             fprintf(stderr, "  %s\n", it2->c_str());
         }
     }
+  // We only call one_addr2line() in this function, so we can clear its cache.
+  Dwarf_line_info::clear_addr2line_cache();
 }
 
 // Warnings functions.
Index: dwarf_reader.h
===================================================================
RCS file: /cvs/src/src/gold/dwarf_reader.h,v
retrieving revision 1.13
diff -u -r1.13 dwarf_reader.h
--- dwarf_reader.h	19 Apr 2008 18:30:58 -0000	1.13
+++ dwarf_reader.h	30 Apr 2008 05:08:40 -0000
@@ -72,12 +72,20 @@
   addr2line(unsigned int shndx, off_t offset)
   { return do_addr2line(shndx, offset); }
 
-  // A helper function for a single addr2line lookup.  It uses
-  // parameters() to figure out the size and endianness.  This is less
-  // efficient than using the templatized size and endianness, so only
-  // call this from an un-templatized context.
+  // A helper function for a single addr2line lookup.  It also keeps a
+  // cache of the last CACHE_SIZE Dwarf_line_info objects it created;
+  // set to 0 not to cache at all.  The larger CACHE_SIZE is, the more
+  // chance this routine won't have to re-create a Dwarf_line_info
+  // object for its addr2line computation; such creations are slow.
+  // NOTE: Not thread-safe, so only call from one thread at a time.
   static std::string
-  one_addr2line(Object* object, unsigned int shndx, off_t offset);
+  one_addr2line(Object* object, unsigned int shndx, off_t offset,
+                size_t cache_size);
+
+  // This reclaims all the memory that one_addr2line may have cached.
+  // Use this when you know you will not be calling one_addr2line again.
+  static void
+  clear_addr2line_cache();
 
  private:
   virtual std::string