[LLVMdev] On LLD performance

[Stephan Tolksdorf]

On 11.03.2015 23:02, Rui Ueyama wrote:
> An idea to make the resolver faster would be to use a concurrent hash
> map to insert new symbols in parallel. Assuming symbols from the same
> file don't conflict each other (I think it's a valid assumption), this
> can be parallelized. I wanted single-thread performance gain, though.
> (Also, concurrent hash maps are not currently available in LLVM.)

Instead of using a concurrent hash map you could fill multiple hash maps 
in parallel and then merge them afterwards. If the implementation caches 
the hash values (which it should for string keys), merging maps doesn't 
require recomputing the hash values and can be a relatively fast 
operation when there is only a small overlap between the maps.

More generally, if hash map operations make up a large share of the run 
time, it might be worth looking for situations where hash values are 
unnecessarily recomputed, e.g. when an item is conditionally inserted or 
when a hash map is grown or copied. (This is just a general observation, 
I don't know anything about LLD's implementation.)

- Stephan