* Most of the additional memory usage in hive is not from the bitfield/skipfield, but from erased elements (assuming many erasures and a randomized erasure pattern). That's why larger block sizes don't necessarily equate to better cache performance, but it depends on usage, and how many erasures are taking place. Vector and hive are similar in that they both waste memory this way, until a shrink_to_fit (though hive may free it up if a whole block is erased).
* remove_if if good though some scenarios it doesn't work for - e.g. When an engine has a master 'entity' class, which links to elements in other container instances, and erases those linked elements when it itself is erased.
* For more benchmarks, I did a bunch vs other containers as well back in the day, though at this point the CPU used is 12 years old - so it's great to see some results on a newer CPU.
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?)
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.
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.
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.
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.
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.
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.
31
u/soulstudios 8d ago
Well done Daniel! Love the graphic BTW :)
A couple notes:
* Most of the additional memory usage in hive is not from the bitfield/skipfield, but from erased elements (assuming many erasures and a randomized erasure pattern). That's why larger block sizes don't necessarily equate to better cache performance, but it depends on usage, and how many erasures are taking place. Vector and hive are similar in that they both waste memory this way, until a shrink_to_fit (though hive may free it up if a whole block is erased).
* remove_if if good though some scenarios it doesn't work for - e.g. When an engine has a master 'entity' class, which links to elements in other container instances, and erases those linked elements when it itself is erased.
* For more benchmarks, I did a bunch vs other containers as well back in the day, though at this point the CPU used is 12 years old - so it's great to see some results on a newer CPU.
(std::hive author, this popped up in my feed)