This is the mail archive of the binutils@sourceware.org mailing list for the binutils project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH v3] gold: Fix non-deterministic behaviour of Mips gold.


> 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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]