sparse_hash_set seems slower and consumes more memory than Google sparsehash about sparsepp HOT 3 CLOSED

Yes, your findings are correct, however:

1. your test program uses a very specific sequence of keys (all consecutive integers)
2. Google sparsehash just uses the integer key as the hash value (pass-through hashing)

This makes the insertion very fast, as there are no collisions. However, it makes finding that a key is not present in the set extremely slow. For that reason, I have chosen to not use pass-through hashing, even though it can look better in simple tests.

To see for yourself, you can add the following lines in your test program, after the insertion:

  size_t count = 0;
  for (int i = 0; i < n; i++)
      if (s.find(rand()) != s.end())
          ++count;
  printf("count = %zu\n", count);

This will demonstrate that the pass-through hashing, which looks very good on insertion-only tests, is probably not advisable in general.

from sparsepp.

I don't advise to use pass-through hashing, but it can easily be done with sparsepp as well. For example define:

struct Hash32 {
   size_t operator()(uint32_t k) const { return k; }
};

and your set as: spp::sparse_hash_set<int, Hash32> s;

You will see that the insertion is now faster than with Google's sparse_hash_set, and that the memory usage is reduced to ~1.2GB, still a little bit more than Google's version.

However the lookup of non-present keys will be very slow, so it is probably not a very good idea.

from sparsepp.

Closing the issue, please reopen is you still have some questions.

from sparsepp.