4 ms·

If you care about performance, you should consider using Abseil's hash tables instead of unordered_set and unordered_map. The Abseil containers are mostly drop

If you care about performance, you should consider using Abseil's hash tables instead of unordered_set and unordered_map. The Abseil containers are mostly drop in replacements for the standard unordered containers, except they have a tweaked API (e.g. erase() returning void) that admits important performance optimizations and (except the node based ones) use open addressed hash tables instead of chaining (i.e. each hash bucket is no longer a linked list). You end up with 2x-3x speedups in a lot of scenarios. The standard containers can't be fixed to match the performance of the Abseil ones because 1) the specification API requires pessimization, 2) Linux distributors are reluctant to break C++ "ABI" (such as it is). I mean, of course you should follow this article's advice on noexcept, but there's a whole world of associative container performance optimizations out there.

jeffbee 2y ago
They are good, but I note that there are now hash tables in Boost that may be even better. https://www.boost.org/doc/libs/develop/libs/unordered/doc/html/unordered.html#buckets_fast_closed_addressing_implementation https://www.boost.org/doc/libs/develop/libs/unordered/doc/ht...
- spacechild1 2y ago
  Thanks a lot! I have been looking for fast hashtables and I didn't know about Boost.Unordered. They even have concurrent (lockfree) versions!
  - senderista 2y ago
    I didn't see a lock-free hashtable there. They describe a concurrent hashtable with fine-grained locking: https://www.boost.org/doc/libs/develop/libs/unordered/doc/html/unordered.html#structures_concurrent_containers https://www.boost.org/doc/libs/develop/libs/unordered/doc/ht...
    - spacechild1 2y ago
      Ah, I assumed it was lockfree. Thanks for the clarification.
- quotemstr 2y ago
  Sure. Anything but the standard library. :-)
forrestthewoods 2y ago
Adding libraries like Abseil, Folly, or Boost is kind of a huge pain in the ass. They’re monstrously huge libraries with a kajillion headers. I recently tried to compile Folly on Windows and gave up. Maybe Abseil is better? I’m not sure. But it’s still a HUGE dependency to take on.
- leni536 2y ago
  Use conan or vcpkg.
  - binary132 2y ago
    Dependencies giving you trouble? Try adding a dependency to handle them!
    - leni536 2y ago
      Adding one dependency to your toolchain which in turn helps you with dealing with an open-ended set of 3rd party dependencies is a good deal.
  - forrestthewoods 2y ago
    No. conan and vcpkg come with their own can of worms and heartaches.
    - davisp 2y ago
      FWIW, I’ve been working on a project that has transitioned from a standard-ish CMake super build to vcpkg and it has been a fantastic upgrade in terms of usability and reliability. There are huge swaths of the C++ lands map I’ve not visited, so I’m sure there are areas where it wouldn’t be a good choice, but I personally think vcpkg has been great.
      - carlmr 2y ago
        vcpkg is well-designed and doesn't get in the way like conan does.
jcalvinowens 2y ago
I 100% agree with the other comment: Abseil and Folly are both broken monstrosities by design... the build system garbage is just one reason almost nobody uses them outside facebook and google. The chaining hashtable in liburcu is truly lock free, based on a real build system, and in my experience outperforms everything facebook and google have ever published: https://github.com/urcu/userspace-rcu https://github.com/urcu/userspace-rcu
- jeffbee 2y ago
  Calling cmake, bazel, and buck "garbage" while recommending an autotools project is one way to have a take, I guess.
  - nemetroid 2y ago
    A pretty reasonable one, too. Getting liburcu to build is trivial.
    - jeffbee 2y ago
      It is also pointless, because the question is not how to build the library, the question is how to integrate and reference it in the project where you want to use it.
      - jcalvinowens 2y ago
        ...yes, and that problem was completely solved a decade before Bazel and Buck reinvented a shittier wheel. You don't have a leg to stand on here. I can build and run liburcu on everything. You can barely build Folly on FreeBSD...
      - nemetroid 2y ago
        Sure, and packaging the artifacts of the liburcu build is going to be trivial in any package management system. It makes very few assumptions about how it's going to be used. Using Folly requires you to ascribe to the Folly worldview of dependency management. Abseil isn't too bad.

jeffbee 2y ago

They are good, but I note that there are now hash tables in Boost that may be even better. https://www.boost.org/doc/libs/develop/libs/unordered/doc/html/unordered.html#buckets_fast_closed_addressing_implementation https://www.boost.org/doc/libs/develop/libs/unordered/doc/ht...

spacechild1 2y ago
Thanks a lot! I have been looking for fast hashtables and I didn't know about Boost.Unordered. They even have concurrent (lockfree) versions!
- senderista 2y ago
  I didn't see a lock-free hashtable there. They describe a concurrent hashtable with fine-grained locking: https://www.boost.org/doc/libs/develop/libs/unordered/doc/html/unordered.html#structures_concurrent_containers https://www.boost.org/doc/libs/develop/libs/unordered/doc/ht...
  - spacechild1 2y ago
    Ah, I assumed it was lockfree. Thanks for the clarification.
quotemstr 2y ago
Sure. Anything but the standard library. :-)

forrestthewoods 2y ago

Adding libraries like Abseil, Folly, or Boost is kind of a huge pain in the ass. They’re monstrously huge libraries with a kajillion headers. I recently tried to compile Folly on Windows and gave up. Maybe Abseil is better? I’m not sure. But it’s still a HUGE dependency to take on.

leni536 2y ago
Use conan or vcpkg.
- binary132 2y ago
  Dependencies giving you trouble? Try adding a dependency to handle them!
  - leni536 2y ago
    Adding one dependency to your toolchain which in turn helps you with dealing with an open-ended set of 3rd party dependencies is a good deal.
- forrestthewoods 2y ago
  No. conan and vcpkg come with their own can of worms and heartaches.
  - davisp 2y ago
    FWIW, I’ve been working on a project that has transitioned from a standard-ish CMake super build to vcpkg and it has been a fantastic upgrade in terms of usability and reliability. There are huge swaths of the C++ lands map I’ve not visited, so I’m sure there are areas where it wouldn’t be a good choice, but I personally think vcpkg has been great.
    - carlmr 2y ago
      vcpkg is well-designed and doesn't get in the way like conan does.

jcalvinowens 2y ago

I 100% agree with the other comment: Abseil and Folly are both broken monstrosities by design... the build system garbage is just one reason almost nobody uses them outside facebook and google. The chaining hashtable in liburcu is truly lock free, based on a real build system, and in my experience outperforms everything facebook and google have ever published: https://github.com/urcu/userspace-rcu https://github.com/urcu/userspace-rcu

jeffbee 2y ago
Calling cmake, bazel, and buck "garbage" while recommending an autotools project is one way to have a take, I guess.
- nemetroid 2y ago
  A pretty reasonable one, too. Getting liburcu to build is trivial.
  - jeffbee 2y ago
    It is also pointless, because the question is not how to build the library, the question is how to integrate and reference it in the project where you want to use it.
    - jcalvinowens 2y ago
      ...yes, and that problem was completely solved a decade before Bazel and Buck reinvented a shittier wheel. You don't have a leg to stand on here. I can build and run liburcu on everything. You can barely build Folly on FreeBSD...
    - nemetroid 2y ago
      Sure, and packaging the artifacts of the liburcu build is going to be trivial in any package management system. It makes very few assumptions about how it's going to be used. Using Folly requires you to ascribe to the Folly worldview of dependency management. Abseil isn't too bad.