Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add robin_map/set::erase_fast() method (fixes #75) #76

Merged
merged 3 commits into from
Apr 19, 2024
Merged

Add robin_map/set::erase_fast() method (fixes #75) #76

merged 3 commits into from
Apr 19, 2024

Conversation

wjakob
Copy link
Contributor

@wjakob wjakob commented Apr 17, 2024

This commit introduces a new method void erase_it(iterator) to both set and map classes resembling the existing iterator erase(iterator).

The main difference is that it does not return an iterator, which is useful to avoid a performance pitfall explained in issue #75.

This commit introduces a new method ``void erase_it(iterator)`` to both
set and map classes resembling the existing ``iterator
erase(iterator)``.

The main difference is that it does _not_ return an iterator, which is
useful to avoid a performance pitfall explained in issue #75.
@wjakob
Copy link
Contributor Author

wjakob commented Apr 17, 2024

FWIW There are two locations that call .erase_from_bucket, and they both set m_try_shrink_on_next_insert = true;. So I moved that assignment directly into the function.

@wjakob
Copy link
Contributor Author

wjakob commented Apr 18, 2024

I expanded the README.md paragraph a bit to add a broader discussion of performance pitfalls. People seem to run into the case #1 regularly because of bad hash functions, so I think it might be worth pointing out more specifically what can go wrong.

@wjakob
Copy link
Contributor Author

wjakob commented Apr 18, 2024

By the way: alternatives to erase_it could be:

  • erase_iterator
  • erase_fast or
  • remove

Just a few ideas.

@Tessil
Copy link
Owner

Tessil commented Apr 18, 2024

Thank you for this!

Minor comments:

  • As another alternative name, I was thinking of erase_void. Your erase_fast would also suit me. erase_it is maybe not explicit enough?
  • Would it be possible to add in robin_map/set an API description of the erase_it method? As the reason of this method may not be intuitive;
  • Regarding the bad hash performance pitfall, there's a mention at the start of the README:

Four classes are provided: tsl::robin_map, tsl::robin_set, tsl::robin_pg_map and tsl::robin_pg_set. The first two are faster and use a power of two growth policy, the last two use a prime growth policy instead and are able to cope better with a poor hash function. Use the prime version if there is a chance of repeating patterns in the lower bits of your hash (e.g. you are storing pointers with an identity hash function). See GrowthPolicy for details.

But being more explicit with a dedicated section may be good.

@wjakob
Copy link
Contributor Author

wjakob commented Apr 18, 2024

I renamed the function to erase_fast and added documentation to the headers.

Regarding the other point: looking back through the issue tracker history, a number of people seem to have run into performance pitfalls, so I think it is useful to spell out in more detail what can go wrong in a worst-case scenario.

@wjakob
Copy link
Contributor Author

wjakob commented Apr 18, 2024

If these changes are acceptable to you, it would be great to merge them and declare a new minor version (1.3.0).

@wjakob wjakob changed the title Add robin_map/set::erase_it() method (fixes #75) Add robin_map/set::erase_fast() method (fixes #75) Apr 18, 2024
@Tessil Tessil merged commit 149ff45 into Tessil:master Apr 19, 2024
11 checks passed
@Tessil
Copy link
Owner

Tessil commented Apr 19, 2024

Looks good, thanks! I merged the changes and will check to create a release later today.

@wjakob
Copy link
Contributor Author

wjakob commented Apr 19, 2024

Awesome, thank you!

wjakob added a commit to wjakob/nanobind that referenced this pull request Apr 19, 2024
See Tessil/robin-map#76 and
#507 for context.

(This is still a pre-release version of robin-map, I will update
 the referenced commit once a proper release has been made)
@Tessil
Copy link
Owner

Tessil commented Apr 20, 2024

Change included in the latest release: https://github.com/Tessil/robin-map/releases/tag/v1.3.0

@wjakob
Copy link
Contributor Author

wjakob commented Apr 20, 2024

Hooray! Thank you for including this change, it makes my life much easier :).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants