Why does std::barrier allocate?

Question

Why does std::barrier allocate memory on the heap while std::latch doesn't?

The main difference between them is that std::barrier can be reused while std::latch can't, but I can't find an explanation on why this would make the former allocate memory.

Answer 1

While it is true that a naive barrier could be implemented with a constant amount of storage as part of the std::barrier object, real-world barrier implementations use structures that have > O(1) storage, but better concurrency properties. The naive, constant-storage barrier can suffer from a large number of threads contending on the same counter. Such contention can lead to O(N) runtime to release threads from the barrier.

As an example of a "better" implementation, the gcc libstdc++ implementation uses a tree barrier. This avoids the contention on a single counter/mutex shared among all threads, and a tree barrier can propagate the "barrier done, time to release" signal in logarithmic time, at the expense of needing linear space to represent the thread tree.

It's not too difficult to imagine enhanced tree-style barrier implementations that are aware of cache/socket/memory bus hierarchy, and group threads in the tree based on their physical location to minimize cross-core, cross-die, and cross-socket polling to the minimum required.

On the other hand, a latch is a much more lightweight synchronization tool. However, I'm not quite sure why a latch would be forbidden to allocate - cppreference states,

The latch class is a downward counter of type std::ptrdiff_t

which would indicate that it should not allocate (i.e. it's just a counter and has no space to hold a pointer to an allocated object). On other hand, [thread.latch] in the standard says nothing more than "A latch maintains an internal counter that is initialized when the latch is created" without forbidding it from allocating.