On Mon Oct 16 14:34:36 2023 +0000, Giovanni Mascellani wrote:
I'm not yet convinced by the rebalancing algorithm, particularly by the fact that `rebalance_threshold` can theoretically grow arbitrarily large and the fact that, independently of how large `rebalance_threshold` might become, you still transfer no more than `REBALANCE_SIZE` objects at each operation. Also, if you transfer objects in packets of `REBALANCE_SIZE` anyway, you could directly allocate them in packets of `REBALANCE_SIZE` and store in the rebalance just one pointer instead of many for each packet (so you waste less time in the critical `memcpy()`'s).
I looked at this during development. When an object is freed it must be marked as free within its `REBALANCE_SIZE` packet, and the only way to make that object available for reuse is to add the packet to the cache. So we end up adding packets containing only one free object. But we can't send packets to the rebalancing array unless they are completely free, otherwise multiple threads can allocate and free objects within the same packet, and we are back to square one.
It may be slightly advantageous to transfer more than `REBALANCE_SIZE` because of cache coherence and the overhead of mutex locking/unlocking. Do you see any other advantages?