[PATCH 3/3] Add a simple array for CU abbreviations with low codes

[Josh Stone <jistone at redhat dot com>]

At the expense of some memory for a new static array in the CU, we can
now retrieve low abbrev codes directly, without any hash operation.
This relieves a hotspot from the modulus in hash lookup().

Signed-off-by: Josh Stone <jistone@redhat.com>
---
 libdw/ChangeLog         |  7 +++++++
 libdw/dwarf_getabbrev.c | 17 ++++++++++++++---
 libdw/dwarf_tag.c       |  7 +++++--
 libdw/libdwP.h          |  6 +++++-
 libdw/libdw_findcu.c    |  2 ++
 5 files changed, 33 insertions(+), 6 deletions(-)

diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index 93396e404d97..397f0c253348 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,5 +1,12 @@
 2013-12-10  Josh Stone  <jistone@redhat.com>
 
+	* libdwP.h (Dwarf_CU): Add abbrev_array.
+	* libdw_findcu.c (__libdw_intern_next_unit): Initialize it.
+	* dwarf_getabbrev.c (__libdw_getabbrev): Use it.
+	* dwarf_tag.c (__libdw_findabbrev): Use it.
+
+2013-12-10  Josh Stone  <jistone@redhat.com>
+
 	* memory-access.h (get_uleb128_rest_return): Removed.
 	(get_sleb128_rest_return): Removed
 	(get_uleb128_step): Make this a self-contained block.
diff --git a/libdw/dwarf_getabbrev.c b/libdw/dwarf_getabbrev.c
index 87d89c1b816b..75cfea27c1ba 100644
--- a/libdw/dwarf_getabbrev.c
+++ b/libdw/dwarf_getabbrev.c
@@ -85,8 +85,14 @@ __libdw_getabbrev (dbg, cu, offset, lengthp, result)
   /* Check whether this code is already in the hash table.  */
   bool foundit = false;
   Dwarf_Abbrev *abb = NULL;
-  if (cu == NULL
-      || (abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL)) == NULL)
+  if (cu != NULL)
+    {
+      if (code < CU_ABBREV_ARRAY_SIZE)
+	abb = cu->abbrev_array[code];
+      else
+	abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL);
+    }
+  if (cu == NULL || abb == NULL)
     {
       if (result == NULL)
 	abb = libdw_typed_alloc (dbg, Dwarf_Abbrev);
@@ -130,7 +136,12 @@ __libdw_getabbrev (dbg, cu, offset, lengthp, result)
 
   /* Add the entry to the hash table.  */
   if (cu != NULL && ! foundit)
-    (void) Dwarf_Abbrev_Hash_insert (&cu->abbrev_hash, abb->code, abb);
+    {
+      if (abb->code < CU_ABBREV_ARRAY_SIZE)
+	cu->abbrev_array[abb->code] = abb;
+      else
+	(void) Dwarf_Abbrev_Hash_insert (&cu->abbrev_hash, abb->code, abb);
+    }
 
  out:
   return abb;
diff --git a/libdw/dwarf_tag.c b/libdw/dwarf_tag.c
index ff012cf4265c..f76a7fe33c93 100644
--- a/libdw/dwarf_tag.c
+++ b/libdw/dwarf_tag.c
@@ -44,8 +44,11 @@ __libdw_findabbrev (struct Dwarf_CU *cu, unsigned int code)
   if (unlikely (code == 0))
     return DWARF_END_ABBREV;
 
-  /* See whether the entry is already in the hash table.  */
-  abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL);
+  /* See whether the entry is already in the list or hash table.  */
+  if (code < CU_ABBREV_ARRAY_SIZE)
+    abb = cu->abbrev_array[code];
+  else
+    abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL);
   if (abb == NULL)
     while (cu->last_abbrev_offset != (size_t) -1l)
       {
diff --git a/libdw/libdwP.h b/libdw/libdwP.h
index bd668c710029..3cc94a3fc789 100644
--- a/libdw/libdwP.h
+++ b/libdw/libdwP.h
@@ -269,6 +269,8 @@ struct Dwarf_Aranges_s
 };
 
 
+#define CU_ABBREV_ARRAY_SIZE 256
+
 /* CU representation.  */
 struct Dwarf_CU
 {
@@ -283,7 +285,9 @@ struct Dwarf_CU
   size_t type_offset;
   uint64_t type_sig8;
 
-  /* Hash table for the abbreviations.  */
+  /* Simple array for the abbreviations with low codes.  */
+  Dwarf_Abbrev *abbrev_array[CU_ABBREV_ARRAY_SIZE];
+  /* Hash table for the abbreviations with higher codes.  */
   Dwarf_Abbrev_Hash abbrev_hash;
   /* Offset of the first abbreviation.  */
   size_t orig_abbrev_offset;
diff --git a/libdw/libdw_findcu.c b/libdw/libdw_findcu.c
index c0bff2af2a69..831cc4d24b71 100644
--- a/libdw/libdw_findcu.c
+++ b/libdw/libdw_findcu.c
@@ -33,6 +33,7 @@
 
 #include <assert.h>
 #include <search.h>
+#include <string.h>
 #include "libdwP.h"
 
 static int
@@ -105,6 +106,7 @@ __libdw_intern_next_unit (dbg, debug_types)
   newp->version = version;
   newp->type_sig8 = type_sig8;
   newp->type_offset = type_offset;
+  memset(newp->abbrev_array, 0, sizeof(newp->abbrev_array));
   Dwarf_Abbrev_Hash_init (&newp->abbrev_hash, 41);
   newp->orig_abbrev_offset = newp->last_abbrev_offset = abbrev_offset;
   newp->lines = NULL;
-- 
1.8.4.2