Re: [patch] Use a std::vector instead of a std::map to hold Input_merge_map

[Rafael EspÃndola <rafael dot espindola at gmail dot com>]

A new patch with the style fixes is attached.


On 20 May 2015 at 11:30, Sriraman Tallam <tmsriram@google.com> wrote:
> Some minor changes:
>
> +  const Section_merge_maps &maps = this->section_merge_maps_;
> +  for (Section_merge_maps::const_iterator i = maps.begin(), e =maps.end();
> +       i != e; ++i) {
>
> space between '=' and maps.end()
> '{' should come in a new line?
>
> Otherwise patch makes the code simpler and looks good to me.  I do not
> have the authority to approve.
>
> Thanks
> Sri
>
> On Wed, May 20, 2015 at 6:12 AM, Rafael EspÃndola
> <rafael.espindola@gmail.com> wrote:
>> ping
>>
>> On 23 April 2015 at 12:36, Rafael EspÃndola <rafael.espindola@gmail.com> wrote:
>>> A std::map is hardly the best data structure for a small map from
>>> small integers.
>>>
>>> The attached patch uses a std::vector<std::pair>> instead.
>>>
>>> This simplifies the code and speeds up linking of chromium (see
>>> attached perf logs).
>>>
>>> Cheers,
>>> Rafael
>>>
>>> 2015-04-23  Rafael Ãvila de EspÃndola <rafael.espindola@gmail.com>
>>>
>>> * merge.cc (get_input_merge_map): Update for data structure change.
>>> (get_or_make_input_merge_map): Update for data structure change.
>>> * merge.h (Object_merge_map): Use a std::vector<std::pair>> instead of
>>> a std::map.

diff --git a/gold/merge.cc b/gold/merge.cc
index d395312..50d13af 100644
--- a/gold/merge.cc
+++ b/gold/merge.cc
@@ -49,13 +49,13 @@ const Object_merge_map::Input_merge_map*
 Object_merge_map::get_input_merge_map(unsigned int shndx) const
 {
   gold_assert(shndx != -1U);
-  if (shndx == this->first_shnum_)
-    return &this->first_map_;
-  if (shndx == this->second_shnum_)
-    return &this->second_map_;
-  Section_merge_maps::const_iterator p = this->section_merge_maps_.find(shndx);
-  if (p != this->section_merge_maps_.end())
-    return p->second;
+  const Section_merge_maps &maps = this->section_merge_maps_;
+  for (Section_merge_maps::const_iterator i = maps.begin(), e = maps.end();
+       i != e; ++i)
+    {
+      if (i->first == shndx)
+	return i->second;
+    }
   return NULL;
 }
 
@@ -73,23 +73,10 @@ Object_merge_map::get_or_make_input_merge_map(
       return map;
     }
 
-  // We need to create a new entry.
-  if (this->first_shnum_ == -1U)
-    {
-      this->first_shnum_ = shndx;
-      this->first_map_.output_data = output_data;
-      return &this->first_map_;
-    }
-  if (this->second_shnum_ == -1U)
-    {
-      this->second_shnum_ = shndx;
-      this->second_map_.output_data = output_data;
-      return &this->second_map_;
-    }
-
   Input_merge_map* new_map = new Input_merge_map;
   new_map->output_data = output_data;
-  this->section_merge_maps_[shndx] = new_map;
+  Section_merge_maps &maps = this->section_merge_maps_;
+  maps.push_back(std::make_pair(shndx, new_map));
   return new_map;
 }
 
diff --git a/gold/merge.h b/gold/merge.h
index 54caed8..53846ee 100644
--- a/gold/merge.h
+++ b/gold/merge.h
@@ -42,9 +42,7 @@ class Object_merge_map
 {
  public:
   Object_merge_map()
-    : first_shnum_(-1U), first_map_(),
-      second_shnum_(-1U), second_map_(),
-      section_merge_maps_()
+    : section_merge_maps_()
   { }
 
   ~Object_merge_map();
@@ -152,7 +150,8 @@ class Object_merge_map
   };
 
   // Map input section indices to merge maps.
-  typedef std::map<unsigned int, Input_merge_map*> Section_merge_maps;
+  typedef std::vector<std::pair<unsigned int, Input_merge_map*> >
+      Section_merge_maps;
 
   // Return a pointer to the Input_merge_map to use for the input
   // section SHNDX, or NULL.
@@ -165,15 +164,6 @@ class Object_merge_map
                                              this)->get_input_merge_map(shndx));
   }
 
-  // Any given object file will normally only have a couple of input
-  // sections with mergeable contents.  So we keep the first two input
-  // section numbers inline, and push any further ones into a map.  A
-  // value of -1U in first_shnum_ or second_shnum_ means that we don't
-  // have a corresponding entry.
-  unsigned int first_shnum_;
-  Input_merge_map first_map_;
-  unsigned int second_shnum_;
-  Input_merge_map second_map_;
   Section_merge_maps section_merge_maps_;
 };