[gold][patch] Reduce heap usage for string merge sections
Cary Coutant
ccoutant@google.com
Tue Aug 3 20:36:00 GMT 2010
>> + // Count the number of strings in the section and size the list.
>> + size_t count = 0;
>> + for (const Char_type* pl = p; pl < pend; ++pl)
>> + {
>> + if (*pl == 0)
>> + ++count;
>> + }
>
> In the case where Char_type is char, I have a feeling this loop would be
> a tiny bit faster if written as
>
> const Char_type* pl = p;
> while (pl < pend)
> {
> pl += strlen(pl) + 1;
> if (pl > pend)
> warning(...);
> ++count;
> }
>
> This is simply because the compiler will optimize strlen for the
> specific compilation target. See
> Stringpool_template<char>::string_length for a similar optimization in
> the Stringpool code.
Good idea -- that got a little over 1% speedup (measured with -O2). I
pulled the string_length template and its char specialization out of
the Stringpool_template class, and used that in both the counting and
the add-to-pool loops, after checking for string sections that don't
end in a null.
> Also, since you have the exact count, it would be a tiny bit better to
> allocate the vector at that size rather than allocating a default vector
> and then using reserve. You could this by adding a parameter to the
> Merged_strings_list constructor which is passed to merged_strings.
That turned out to hurt performance a bit (maybe -- the difference was
close to the noise), probably because of the default constructor for
each allocated element. I left this part as is.
Here's the patch as committed.
-cary
* merge.cc (Output_merge_string::do_add_input_section): Count strings
to reserve space in merged_strings vector. Keep total input size
for stats.
(Output_merge_string::do_print_merge_stats): Print total input size.
* merge.h (Output_merge_string): Add input_size_ field.
* stringpool.cc (Stringpool_template::string_length): Move
implementations out of Stringpool_template class and place in
stringpool.h.
* stringpool.h (string_length): Move out of Stringpool_template.
-------------- next part --------------
diff --git a/gold/merge.cc b/gold/merge.cc
index 6c512a8..9fb5845 100644
--- a/gold/merge.cc
+++ b/gold/merge.cc
@@ -533,6 +533,7 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
const Char_type* p = reinterpret_cast<const Char_type*>(pdata);
const Char_type* pend = p + len / sizeof(Char_type);
+ const Char_type* pend0 = pend;
if (len % sizeof(Char_type) != 0)
{
@@ -543,39 +544,54 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
return false;
}
- size_t count = 0;
+ if (pend[-1] != 0)
+ {
+ gold_warning(_("%s: last entry in mergeable string section '%s' "
+ "not null terminated"),
+ object->name().c_str(),
+ object->section_name(shndx).c_str());
+ // Find the end of the last NULL-terminated string in the buffer.
+ while (pend0 > p && pend0[-1] != 0)
+ --pend0;
+ }
Merged_strings_list* merged_strings_list =
new Merged_strings_list(object, shndx);
this->merged_strings_lists_.push_back(merged_strings_list);
Merged_strings& merged_strings = merged_strings_list->merged_strings;
+ // Count the number of strings in the section and size the list.
+ size_t count = 0;
+ for (const Char_type* pt = p; pt < pend0; pt += string_length(pt) + 1)
+ ++count;
+ if (pend0 < pend)
+ ++count;
+ merged_strings.reserve(count + 1);
+
// The index I is in bytes, not characters.
section_size_type i = 0;
- while (i < len)
+ while (p < pend0)
{
- const Char_type* pl;
- for (pl = p; *pl != 0; ++pl)
- {
- if (pl >= pend)
- {
- gold_warning(_("%s: last entry in mergeable string section '%s' "
- "not null terminated"),
- object->name().c_str(),
- object->section_name(shndx).c_str());
- break;
- }
- }
+ size_t len = string_length(p);
+
+ Stringpool::Key key;
+ this->stringpool_.add_with_length(p, len, true, &key);
+
+ merged_strings.push_back(Merged_string(i, key));
+
+ p += len + 1;
+ i += (len + 1) * sizeof(Char_type);
+ }
+ if (p < pend)
+ {
+ size_t len = pend - p;
Stringpool::Key key;
- this->stringpool_.add_with_length(p, pl - p, true, &key);
+ this->stringpool_.add_with_length(p, len, true, &key);
- section_size_type bytelen_with_null = ((pl - p) + 1) * sizeof(Char_type);
merged_strings.push_back(Merged_string(i, key));
- p = pl + 1;
- i += bytelen_with_null;
- ++count;
+ i += (len + 1) * sizeof(Char_type);
}
// Record the last offset in the input section so that we can
@@ -583,6 +599,7 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
merged_strings.push_back(Merged_string(i, 0));
this->input_count_ += count;
+ this->input_size_ += len;
// For script processing, we keep the input sections.
if (this->keeps_input_sections())
@@ -701,7 +718,9 @@ Output_merge_string<Char_type>::do_print_merge_stats(const char* section_name)
{
char buf[200];
snprintf(buf, sizeof buf, "%s merged %s", section_name, this->string_name());
- fprintf(stderr, _("%s: %s input: %zu\n"),
+ fprintf(stderr, _("%s: %s input bytes: %zu\n"),
+ program_name, buf, this->input_size_);
+ fprintf(stderr, _("%s: %s input strings: %zu\n"),
program_name, buf, this->input_count_);
this->stringpool_.print_stats(buf);
}
diff --git a/gold/merge.h b/gold/merge.h
index b1284ae..675739e 100644
--- a/gold/merge.h
+++ b/gold/merge.h
@@ -462,7 +462,7 @@ class Output_merge_string : public Output_merge_base
public:
Output_merge_string(uint64_t addralign)
: Output_merge_base(sizeof(Char_type), addralign), stringpool_(),
- merged_strings_lists_(), input_count_(0)
+ merged_strings_lists_(), input_count_(0), input_size_(0)
{
gold_assert(addralign <= sizeof(Char_type));
this->stringpool_.set_no_zero_null();
@@ -566,6 +566,8 @@ class Output_merge_string : public Output_merge_base
Merged_strings_lists merged_strings_lists_;
// The number of entries seen in input files.
size_t input_count_;
+ // The total size of input sections.
+ size_t input_size_;
};
} // End namespace gold.
diff --git a/gold/stringpool.cc b/gold/stringpool.cc
index 10d6d27..4ddba8d 100644
--- a/gold/stringpool.cc
+++ b/gold/stringpool.cc
@@ -87,28 +87,6 @@ Stringpool_template<Stringpool_char>::reserve(unsigned int n)
this->string_set_.swap(new_string_set);
}
-// Return the length of a string of arbitrary character type.
-
-template<typename Stringpool_char>
-size_t
-Stringpool_template<Stringpool_char>::string_length(const Stringpool_char* p)
-{
- size_t len = 0;
- for (; *p != 0; ++p)
- ++len;
- return len;
-}
-
-// Specialize string_length for char. Maybe we could just use
-// std::char_traits<>::length?
-
-template<>
-inline size_t
-Stringpool_template<char>::string_length(const char* p)
-{
- return strlen(p);
-}
-
// Compare two strings of arbitrary character type for equality.
template<typename Stringpool_char>
diff --git a/gold/stringpool.h b/gold/stringpool.h
index f353c9d..2f9a313 100644
--- a/gold/stringpool.h
+++ b/gold/stringpool.h
@@ -32,6 +32,28 @@ namespace gold
class Output_file;
+// Return the length of a string in units of Char_type.
+
+template<typename Char_type>
+inline size_t
+string_length(const Char_type* p)
+{
+ size_t len = 0;
+ for (; *p != 0; ++p)
+ ++len;
+ return len;
+}
+
+// Specialize string_length for char. Maybe we could just use
+// std::char_traits<>::length?
+
+template<>
+inline size_t
+string_length(const char* p)
+{
+ return strlen(p);
+}
+
// A Stringpool is a pool of unique strings. It provides the
// following features:
@@ -266,10 +288,6 @@ class Stringpool_template
Stringpool_template(const Stringpool_template&);
Stringpool_template& operator=(const Stringpool_template&);
- // Return the length of a string in units of Stringpool_char.
- static size_t
- string_length(const Stringpool_char*);
-
// Return whether two strings are equal.
static bool
string_equal(const Stringpool_char*, const Stringpool_char*);
More information about the Binutils
mailing list