Skip to content

GitLab

  • Menu
Projects Groups Snippets
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Sign in / Register
  • C chashmap
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
  • Issues 12
    • Issues 12
    • List
    • Boards
    • Service Desk
    • Milestones
  • Merge requests 3
    • Merge requests 3
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
  • Deployments
    • Deployments
    • Environments
    • Releases
  • Packages & Registries
    • Packages & Registries
    • Container Registry
  • Monitor
    • Monitor
    • Incidents
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Repository
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • redox-os
  • chashmap
  • Issues
  • #2
Closed
Open
Created Jul 16, 2019 by Alex Hornby@ahornbyContributor

CHashMap::shrink_to_fit and CHashMap::with_capacity reserving ~3.4x buckets needed by ::insert

Hi, I have a CHashMap where I know I will insert N elements, N is large, and each element is quite small, so CHashMaps own memory usage is significant.

Unfortunately if I ::insert then ::shrink_to_fit or if I pre-allocate with_capacity(N) CHashMap reserves 4x N buckets rather than the expected N*loadfactor_denom/loadfactor_num that ::insert/::expand would check for.

This can result in maps growing significantly when ::shrink_to_fit is called, and means that one has to fudge the number passed to ::with_capacity to avoid over allocation of buckets in the "size known" usecase.

Two underling issues/questions:

  1. Is there a reason LENGTH_MULTIPLIER is 4 rather than 2? I think 2 is all that is needed to amortize the reallocation on growth when an insert/expand needs to expand.
  2. In known-length use cases CHashMap::shrink_to_fit and CHashMap::with_capacity is it an oversight that LENGTH_MULTIPLIER rather than MAX_LOAD_FACTOR_DENOM/MAX_LOAD_FACTOR_NUM is being applied to the length? Applying load factor would be considerably more space efficient, and more consistent with the bounds checked by insert/expand.

Happy to contribute changes if that helps.

Edited Jul 16, 2019 by Alex Hornby
Assignee
Assign to
Time tracking