This is the mail archive of the
binutils@sourceware.org
mailing list for the binutils project.
Re: [PATCH v3] gold: Fix non-deterministic behaviour of Mips gold.
- From: Cary Coutant <ccoutant at gmail dot com>
- To: Vladimir Radosavljevic <Vladimir dot Radosavljevic at imgtec dot com>
- Cc: "binutils at sourceware dot org" <binutils at sourceware dot org>, Petar Jovanovic <Petar dot Jovanovic at imgtec dot com>
- Date: Wed, 30 Mar 2016 11:17:19 -0700
- Subject: Re: [PATCH v3] gold: Fix non-deterministic behaviour of Mips gold.
- Authentication-results: sourceware.org; auth=none
- References: <3060420525346945A0ADBD567348A91723740CBE at BADAG02 dot ba dot imgtec dot org> <CAJimCsFUEXT1D6-WWvTtvARteOqRwV_EPkuBk+U5YYDaXTZ_DA at mail dot gmail dot com> <3060420525346945A0ADBD567348A91723740E41 at BADAG02 dot ba dot imgtec dot org>
> I could use hash algorithm like in Reloc_stub::hash_value(), but what do you think about using FNV-1a hash algorithm ?
> It would be look like this:
>
> + size_t name_hash_value = gold::string_hash<char>(
> + (this->symndx_ != -1U)
> + ? this->d.object->name().c_str()
> + : this->d.sym->name());
> +
> + uint64_t h = 14695981039346656037ULL; // FNV offset basis.
> + uint64_t prime = 1099511628211ULL;
> + h = (h ^ static_cast<uint64_t>(name_hash_value)) * prime;
> + h = (h ^ static_cast<uint64_t>(this->symndx_)) * prime;
> + h = (h ^ static_cast<uint64_t>(this->addend_)) * prime;
> + return h;
I think you could get away without that last multiplication.
This is clearly a much better hash than the simple XOR, but adds some
cost to the hash computation. I think libiberty's iterative_hash() is
less expensive and nearly as effective, though.
One or two strategically placed shifts would make the simple XOR
strategy more effective (though not as effective as the more robust
alternatives) at almost no extra cost in hash computation. I'll leave
it to your judgement (or measurement) whether improvement in hash
lookup justifies extra cost in hash computation.
-cary