Adding ints with poor hash leads to explosive reserve sequence in some cases

Question

Adding ints with poor hash leads to explosive reserve sequence in some cases

Predelnik opened this issue 4 years ago · 1 comments

I run the following simple program. I do believe on libstdc++, wrapper could be replaced just with unsigned long long but I tested with VC++ so I had to write it.

#include "tsl/robin_set.h"

class wrapper
{
public:
  bool operator== (const wrapper &other) const { return x == other.x;}
  unsigned long long x;
};

namespace std
{
  template <>
  struct hash<wrapper>
  {
    size_t operator()(const wrapper &w) const noexcept { return w.x; }
  };
}

int main ()
{
  tsl::robin_set<wrapper> s;
  auto fp = fopen ("a.txt", "r");
  size_t x;
  while (fscanf (fp, "%llu", &x) == 1)
    {
      s.insert (wrapper {x});
      std::cout << s.bucket_count () << '\n';
    }
  fclose (fp);
}

Basically I add numbers from attached a.txt to robin_set

Print results at the end of execution are akin to the following:

With program taking 6-8 GB of RAM in the end. I believe adding a single number to the end of the file results in one more 2x reserved memory increase.
We could observe this problem only after recent update so it probably has to do with some recent changes in robin_map. While I understand that this hash is probably poor it is still default in libstdc++ and it would be nice if such behavior would be fixed.

Edit:
Bisect shows that 73959d6 is where it started to happen

Answer 1 · 2021-12-15T21:16:02.000Z

Unfortunately I don't think there're a lot of solutions without changing the hash function or the hash collision resolution algorithm itself. I could raise the DIST_FROM_IDEAL_BUCKET_LIMIT limit but the problem will remain as the size of distance_type is limited.

The identity hash is a really poor hash function, even more when you only insert even numbers as in the a.txtfile, and I would recommend to change it to something more robust as it would reduce the collisions and improve the performances.