[PATCH] gold: reserve up front buckets in comdat/linkonce signatures hash table

[Ian Lance Taylor]

Mikolaj Zalewski <mikolajz@google.com> writes:

>   I haven't yet finished the updated incremental linking patch, but I
> have made a simple patch that may be also interesting as it speeds up
> the normal case. It gives some 2-3% improvement on my test by
> reserving upfront more buckets in the comdat signatures hash
> (previously, the linker was spending something like  3% time of time
> rehashing it - the final number of signatures was 2/3 of the number of
> symbols). The heuristic is similar to the initial symbol table size
> heuristic, but with the result 8 times smaller. In my test this has
> given an average of 2.5 items per bucket and it seems there was no
> need to rehash. Should I test if the numbers are similar in other
> programs?
>   The patch also fixes the parameter of find_or_add_kept_comdat to
> pass string be reference, but I don't know if this makes a big
> difference. I have also kept the code printing statistics about the
> number of signatures, as I thought this may be interesting for others.

Thanks for the patch.  I'm not quite happy with this approach, since a
typical C program will have hardly any linkonce sections, so there is no
reason to allocate a big hash table.  Also, I think your size is a bit
too big--typically the same signature will appear in many input files,
and take up only one slot in the hash table.  Also, the rehash call
doesn't work if we are using __gnu_cxx::hash_map.  I implemented a
similar but slightly different approach as follows.  I also removed the
options_ field from Layout, as it is accessible via parameters.

Ian


2009-04-01  Ian Lance Taylor  <iant@google.com>
	    Mikolaj Zalewski  <mikolajz@google.com>

	* gold.h (reserve_unordered_map): Define, three versions, one for
	each version of Unordered_map.
	* layout.cc (Layout::Layout): Remove options parameter.  Add
	number_of_input_files parameter.  Don't initialize options_.
	Initialize number_of_input_files_ and resized_signatures_.  Move
	sections_are_attached_.
	(Layout::layout_group): Reserve space for group_signatures_.
	(Layout::find_or_add_kept_section): Change name parameter to be a
	reference.  Resize signatures_ map when it gets large enough.
	(Layout::layout_eh_frame): Use parameters->options() instead of
	this->options_.
	(Layout::make_output_section): Likewise.
	(Layout::attach_allocated_section_to_segment): Likewise.
	(Layout::finalize, Layout::create_executable_stack): Likewise.
	(Layout::set_segment_offsets, Layout::create_interp): Likewise.
	(Layout::finish_dynamic_section, Layout::write_binary): Likewise.
	* layout.h (class Layout): Update declarations.  Remove options_
	field.  Add number_of_input_files_ and resized_signatures_
	fields.  Move sections_are_attached_ field.
	* main.cc (main): Pass number of input files to Layout
	constructor.  Don't pass options.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: foo.patch
Type: text/x-patch
Size: 12325 bytes
Desc: Reserve space in signatures
URL: <https://sourceware.org/pipermail/binutils/attachments/20090402/b432c461/attachment.bin>