You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
pool::erase (pool.cppm:389) already holds the node in its iterator but calls multislab::deallocate(void*), whose find_owner (multislab.cppm:583) scans every slab. Slabs are fixed size, so S grows linearly with size. emplace's rollback and make_iterator(ptr) pay the same scan.
Depends on: multislab list rework (stable node handle in the iterator).
Fix
Node-aware deallocation: private multislab::deallocate_at(const iterator&) with pool as friend, or public deallocate(iterator). Node and bit index are known, so there is no scan and no ptr_to_index division. Use it in pool::erase and in emplace rollback (allocate_at already returns the iterator).
Optional, separate issue: O(1) deallocate(void*) by allocating each slab at power-of-two alignment with the header at a fixed offset, so the owner is ptr & ~(slab_bytes - 1). Needs aligned_memory_resource and a padded footprint.
Update docs/complexity.md and the find_owner note in docs/containers.md.
Tests
Erase benchmark over 10k+ slabs. Unit test: erase through deallocate(iterator) leaves the same state as deallocate(ptr).
Activity