Re: Optimizing hash table lookup in symbol binding

[Adhemerval Zanella <adhemerval dot zanella at linaro dot org>]

On 20/11/2019 22:55, Carlos O'Donell wrote:
> On 11/18/19 8:58 AM, Florian Weimer wrote:
>> On a second-generation AMD EPYC, I didn't see a difference at all for
>> some reason.  On Cascade Lake, I see a moderate improvement for the
>> dlsym test, but I don't know how realistic this microbenchmark is.  Both
>> patches had performance that was on par.
>>
>> I also tried to remove the bitmask check altogether, but it was not an
>> improvement.  I suspect the bitmasks are much smaller, so consulting
>> them avoids the cache misses in the full table lookup.
>>
>> If any of the architecture maintainers think this is worth doing, we can
>> still incorporate it.
> 
> At this point you are probably straying to the realm of special purpose
> proprietary analysis programs provided by hardware vendors to get the
> most performance out of a given program (stalls, cache misses, interlocks
> etc.).
> 
> Have you used perf at all to look into aspects beyond just performance?
> That is say confirming the cache misses saved vs. the full table lookup?
> 
> What about PGO for this case? I often wonder in cases like this if we
> fed "normative" workloads into a PGO build if we could get better
> results from generated code like this, but it's an entire project
> just to do this.
> 
> To accept this code I'd want a microbenchmark added, and then we'd
> commit the code, and ask the machine maintainers to review that nothing
> got terribly worse or was out of kilter with the microbenchmark numbers.
> 
> Thoughts?
> 

I see that such changes are hard to measure over different architectures
and get even more tricker with different implementations within the
architectures.

This change seems a straighfoward optimization for architectures that issues
a libcall for module operation, such as arm, alpha, and hppa.

However it seems to be a performance regression on other architectures where
the 32x32->64 multiplier *also* requires a libcall, such as csky, microblaze,
nios2, and sparcv8.

And it become even less obvious for architectures that depending of the
compiler flags might generate better code, for instance on armv7-a where
modulus is done with udiv instead of a libcall.  And there is even riscv64
where provides a specific instruction for that, remuw (although I couldn't
find the expected latency/throughput for that).

Also, some architectures might show better latency over chips version. For
instance aarch A57 has a udiv latency of 4-20 and execution throughput of
1/20 - 1/4, where A55 has a latency of 3-12 and throughput of 1/12 - 1/3.
It might the case where this trick might show better performance on some
chips where newer ones it would be worse than a simple modules operation.

So it would require a lot of testing and deliberation for each arch 
maintainer to check if this optimization is worth, it would add another
build permutation we need to maintained, and it would need to be constantly
checked on every new releases to see implementation get modulus operand
better.

Instead I would try to focus and use a better hashtable scheme, as Wilco
has suggested. To give a crude estimative of the possible gain, on the
simple benchmark bellow the power2 rehash policy with mask ranging showed
better performance on multiple architectures ranging from 17% - 50%. 
Even for more embedded oriented architectures, such as sh4, I see that
avoid a modules hashing scheme showed about 30% better results on insertion.

And I fully agree with that we should at least have some of synthetic
benchmark to evaluate it.

--

#include <iostream>
#include <unordered_map>
#include <chrono>

using hash_power2_t = std::_Hashtable<
  uint32_t, std::pair<const uint32_t, uint32_t>,
  std::allocator<uint32_t>,
  std::__detail::_Select1st,
  std::equal_to<uint32_t>,
  std::hash<uint32_t>,
  std::__detail::_Mask_range_hashing,
  std::__detail::_Default_ranged_hash,
  std::__detail::_Power2_rehash_policy,
  std::__ummap_traits<true>>;

using hash_mod_t = std::_Hashtable<
  uint32_t, std::pair<const uint32_t, uint32_t>,
  std::allocator<uint32_t>,
  std::__detail::_Select1st,
  std::equal_to<uint32_t>,
  std::hash<uint32_t>,
  std::__detail::_Mod_range_hashing,
  std::__detail::_Default_ranged_hash,
  std::__detail::_Prime_rehash_policy,
  std::__ummap_traits<true>>;

int main ()
{
  const int sz = 30000000;

  hash_mod_t hash_mod;
  hash_mod.reserve (sz);

  hash_power2_t hash_power2;
  hash_power2.reserve (sz);

  double mod_time, power2_time;
  {
  auto start = std::chrono::steady_clock::now();
  for (int i = 0; i < sz; i++)
    hash_mod.emplace (std::make_pair (i, i));
  auto end = std::chrono::steady_clock::now();
  auto diff = end - start;
  mod_time = std::chrono::duration <double, std::nano> (diff).count();
  std::cout << "mod hash   : " << mod_time << " ns" << std::endl;
  }

  {
  auto start = std::chrono::steady_clock::now();
  for (int i = 0; i < sz; i++)
    hash_power2.emplace (std::make_pair (i, i));
  auto end = std::chrono::steady_clock::now();
  auto diff = end - start;
  power2_time = std::chrono::duration <double, std::nano> (diff).count();
  std::cout << "power2 hash: " << power2_time << " ns" << std::endl;
  }

  std::cout << "speedup    : " << 1 / (power2_time / mod_time) << std::endl;
}