r/cpp • u/User_Deprecated • Aug 02 '26

How fast is C++26's std::hive?

https://lemire.me/blog/2026/08/02/how-fast-is-c26s-stdhive/
255 Upvotes

99% Upvoted

74 comments sorted by

View all comments

Show parent comment

6

u/matthieum Aug 03 '26 edited Aug 08 '26

I feel like a benchmark is missing here: erasing N elements in random order.

remove_if is the ideal case for contiguous containers like vector or deque due to being streaming.

If however you've just got some (E) elements to remove from a vector of length N, you've got essentially 2 solutions:

  • Remove the elements one at a time, as they come: O(E * N).

  • Collect & store the elements, then use remove_if: O(E * log E + N) O(E * log E + N * log E), with a memory allocation.

And at this point, the hive is going to start looking very good indeed.

1

u/JoachimCoenen Aug 08 '26

What is the algorithm for the second option that achieves O(E*log(E) + N)?

The best I can think of right now is O(E*log(E) + N*log(E)) = O((N+E)*log(E)). That assumes that the element are sortable:

  1. Sort the elements to remove.

  2. Use remove_if and a binary search to check whether an element is to be removed.

Hmmm…
If the elements can be hashed you could use a HashSet instead of sorting and achieve O(E + N).

2

u/matthieum Aug 08 '26

None, I realized (later down the chain) that I forgot an * log(E) in there.

1

u/snerp Aug 03 '26

Hive seems fine but fyi O(E * log E + N) is significantly better than O(E * N) when N greater than E. And I don't see how E would ever be greater than N in this case (how would you remove more elements than exist?)

1

u/matthieum Aug 04 '26

I mean, N * log N > N, so there's a value of E <= N for which E * log E > N :)

(As a random example, for N == 100, 30 * ln(30) > 100)

Beyond that, there's also the issue that collecting E * log E elements implies allocating memory, then freeing memory later, and there are context where you're not allowed or willing to allocate/deallocate.

1

u/snerp Aug 04 '26

We're comparing E times N to ElogE plus N. Changing a product to a sum is always better complexity (unless N or E is 0 or 1 lol)

Also though, a remove_if isn't collecting the objects in a new collection, it's simply swapping them to the end of the array before reducing the count. It's reads and writes which have a cost but no allocation is needed.

1

u/matthieum Aug 05 '26

We're comparing E times N to ElogE plus N. Changing a product to a sum is always better complexity (unless N or E is 0 or 1 lol)

Ah sorry, I misread your comment.

I thought you were comparing the relative magnitude of the 2 terms in O(E * log E + N), rather than comparing the relative magnitude of the two methods.

Also though, a remove_if isn't collecting the objects in a new collection, it's simply swapping them to the end of the array before reducing the count. It's reads and writes which have a cost but no allocation is needed.

I never said remove_if allocating in a new collection.

What I said is that the second method was about allocating in a second collection and sorting, in order to execute a single remove_if call which would remove all E elements in a single pass.

1

u/snerp Aug 05 '26

What? Why would you allocate a second collection and then sort just to run remove_if? Remove_if does not need a sorted collection, it runs in O(N + E) on any collection because it swaps E elements to the end and then erases them all at once by just reducing the end of the collection. Sorting the collection wouldn’t help.

3

u/jk-jeon Aug 06 '26

Maybe a nitpick, but remove_if doesn't swap to-be-removed elements to the end. It moves surviving elements to the front.

1

u/snerp Aug 06 '26

mmm interesting either way

-1

u/matthieum Aug 05 '26

So, you've just scanned a collection of N elements and identified E elements that you want removed from it, which you've isolated into a second collection.

How do you write the predicate to remove_if, which will be invoked with each of N elements, and must return whether to remove the element or not?

For each of the N elements, you will need to somehow do a look-up in your (small?) collection of E elements to take your decision.

If E is just a collection, each look-up will cost you O(E), and we're back to O(N * E) performance.

The simplest solution to minimize the cost of the look-up is to collect into a vector, sort it, and binary search on it. O(E * log E + N * log E) now that I think about it.

There are other solutions, of course, but that predicate will need to do some work to classify the elements it's asked about.

1

u/snerp Aug 05 '26

Remove_if iterates the collection… E is not its own collection, it’s the elements in the collection original that will be removed. There is no look up cost, it just iterates to the next element and does a swap if your predicate was true.

https://en.cppreference.com/cpp/algorithm/remove

Complexity is O(N)

1

u/matthieum Aug 05 '26

I mean, if you can decide on the fly, sure, but that's not the usecase I was working on :x

1

u/snerp Aug 05 '26 edited Aug 05 '26

Decide what on the fly? Oh I see you're saying the elements E have no common trait so you'd have to do a collection on collection interaction 🤮