Noexcept affects libstdc++’s unordered_set

https://quuxplusone.github.io/blog/2024/08/16/libstdcxx-noexcept-hash/

by signa11 • 2 years ago

95 76 2 years ago

quuxplusone.github.io

Money quote

The outcome is that libstdc++’s unordered_set has performance characteristics that subtly depend on the true name and noexceptness of the hash function.
- A user-defined struct H : std::hash<std::string> {} will see smaller allocations and more calls to the hash function, than if you had just used std::hash<std::string> directly. (Because std::hash<std::string> is on the blacklist and H is not.)
- A user-defined hasher with size_t operator() const noexcept will see smaller allocations and more calls to the hash function (especially during rehashing). One with size_t operator() const will see larger allocations and fewer calls to the hash function.

z_open• 2 years ago

somewhat unrelated but it's worth pointing out that noexcept is more specific for move semantics.

In fact most c++ developers believe that throwing an exception in a noexcept function is undefined behavior. It is not. The behavior is defined to call std::terminate. Which would lead one to ask how does it know to call that. Because noexcept functions have a hidden try catch to see if it should call it. The result is that noexcept can hurt performance, which is surprising behavior. C++ is just complicated.

colejohnson66• 2 years ago

I’m not well versed in C++’s exception system, but why can’t the unwind system itself call std::terminate? Why does it need to be the annotated method (that unwinding returns to)?

epcoa• 2 years ago

Because the exception can’t be allowed to escape the function marked noexcept. No matter the actual implementation, the exception has to be effectively caught in that no except function.

layer8• 2 years ago

It doesn’t need to be, but the annotated function can still miss optimization opportunities, because it must be compiled as if it had a try-catch block if the compiler can’t prove the absence of exceptions, and this places constraints on reordering and inlining.

On the other hand, the guarantee given by noexcept can enable optimizations in the caller.

klyrs• 2 years ago

Way more history than you asked for about how we got into this situation with noexcept:

Up to 2011:

https://akrzemi1.wordpress.com/2011/06/10/using-noexcept/

As of '17:

https://devblogs.microsoft.com/oldnewthing/20180928-00/?p=99...

(I think this is the final word; I don't see any changes to exceptions in high-level release notes for c++20 and c++23 -- did I miss anything?)

leni5366• 2 years ago

It can, and it does on decent runtimes.

quotemstr5• 2 years ago

Yeah. Throwing from a noexcept function is often a better abort() than abort() itself because the std::terminate machinery will print information about whatever caused the termination, whereas abort will just SIGABRT.

flamedoge• 2 years ago

what.. noexcept throws exception..? what kind of infinite wisdom led to this

pavlov• 2 years ago

Noexcept terminates if an exception is thrown within. That's a very C++ way to ensure that the exception can't propagate.

api3• 2 years ago

There’s a reason both Go and Rust eschew exceptions. They’re something that superficially seemed like a great idea but that in practice complicate things by creating two exit paths for every function. They also don’t play nice with any form of async or dynamic programming.

C++ should never have had them, but we have sane clean C++ now. It’s called Rust.

chipdart4• 2 years ago

what.. noexcept throws exception..? what kind of infinite wisdom led to this

Not wisdom at all, just a very basic and predictable failsafe.

If a function that is declared to not throw any exception happens to throw one, the runtime handles that scenario as an eggregious violation of its contract. Consequently, as it does with any malformed code, it terminates the application.

chipdart4• 2 years ago

(...) throwing an exception in a noexcept function is undefined behavior.

Small but critical correction: noexcept functions can throw exceptions. What they cannot do is allow exceptions to bubble up to function invokers. This means that it is trivial to define noexcept functions: just add a try-catch block that catches all exceptions.

tredre3• 2 years ago

I suppose you are technically correct that noexcept can throw to themselves. But that's just being pedantic, isn't it? From the observer/caller point of view the function won't ever throw. It will always return (or abort).

fluoridation2• 2 years ago

Hmm... If you were reading the documentation for function foo() and it read "if the argument is negative, foo() throws an exception", would you understand that the function throws an exception and catches it internally before doing something else, or that it throws an exception that the caller must catch?

yosefk• 2 years ago

-fno-exceptions FTW. (Of course you can't always do this. Great to do this early on before it's too late and the code is full of exceptions IMO.)

ryandrake• 2 years ago

-fno-exceptions doesn't get rid of exceptions, it just causes your program to abort when one is thrown, which sounds--kind of worse? How do you deal with (for example) a constructor that fails? And if you're using the Standard Library, it is very difficult to avoid code that might throw an exception.

mgaunard2• 2 years ago

I believe the original proposal for noexcept was that throwing was UB, and the original author believed strongly it should have been that way.

In the end what got into the standard is that it is well-defined: it calls std::terminate. If I recall that change wasn't made without drama.

quotemstr5• 2 years ago

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.

jeffbee3• 2 years 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/ht...

spacechild12• 2 years 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!

quotemstr5• 2 years ago

Sure. Anything but the standard library. :-)

forrestthewoods5• 2 years 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.

leni5366• 2 years ago

Use conan or vcpkg.

jcalvinowens2• 2 years 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

jeffbee3• 2 years ago

Calling cmake, bazel, and buck "garbage" while recommending an autotools project is one way to have a take, I guess.

leni5366• 2 years ago

Also, I hope that if you’re reading this post in a year or two (say, December 2025), these specific examples won’t even reproduce anymore. I hope libstdc++ gets on the ball and eliminates some of this weirdness. (In short: They should get rid of the blacklist; pay the 8 bytes by default; introduce a whitelist for trivial hashers specifically; stop checking noexceptness for any reason.)

I think this would be an ABI break.

davisp2• 2 years ago

Probably so! Although, given that C++ doesn’t have ABI contracts to begin with, I’m not sure how it would matter in practice.

Iwan-Zotow• 2 years ago

Platforms have ABIs

leni5366• 2 years ago

All three of the major C++ standard library implementations have stable ABI contracts.

quuxplusone• 2 years ago

FWIW: I've had your comment at the back of my mind for the past 5 days, and I haven't yet come up with any clever way to work around it. I think you're simply right: to "fix" this in "new code" would break ABI for anyone who passed e.g. `vector<unordered_set<T>>` across an ABI boundary. (I.e., anywhere that "new code" might construct an unordered_set object according to the "new ABI," which object might later be destroyed by "old code" which assumed the "old ABI," leading to heap corruption.)

So yeah, it is probably physically impossible for libstdc++ to "get on the ball" in the way I'd hoped. Darn.

mgaunard2• 2 years ago

if you want a fast hash map, just use a library that is built specifically around a particular implementation strategy.

std unordered map is slow by design for several reasons.

Things of interest are:

- open addressing method: linear, quadratic, robinhood, hybrid

- the default hash function

- the logic for the number of buckets (power of two, prime) and associated hash projection (fibonacci, modulo).

Boost seems to be doing a decent job at this now.

Noexcept affects libstdc++’s unordered_set

Related Stories