Skip to content

pool/multislab: erase is O(S) #5

Closed

Description

@aotodev

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

  1. 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).
  2. 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).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

enhancementNew feature or request

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions