summaryrefslogtreecommitdiff
path: root/absl/container/internal/raw_hash_set.h
Commit message (Collapse)AuthorAge
* Speed up `raw_hash_map::[]` with ABSL hardening enabled by unchecking ↵Gravatar Abseil Team2024-01-12
| | | | | | | dereference of iterator returned by `try_emplace`. PiperOrigin-RevId: 597920257 Change-Id: I1b2e8f10a2f1efa763a6f0760294beafdb6fd9c0
* Enable ABSL_BTREE_ENABLE_GENERATIONS and ABSL_SWISSTABLE_ENABLE_GENERATIONS ↵Gravatar Abseil Team2024-01-11
| | | | | | | | | | | | | | with ABSL_HAVE_HWADDRESS_SANITIZER. It will detect bugs similar to Asan. Also updated related tests to pass with HWASAN. They are still flaky because of nature of HWASAN algorithm, but test can be update to avoid flakiness, which I will do in followup patches. PiperOrigin-RevId: 597613798 Change-Id: Ic8af36a268ca041c002eb561b946aa2d9b93996a
* Speed up `raw_hash_set::contains()` when ABSL hardening is enabled by ↵Gravatar Abseil Team2024-01-03
| | | | | | | removing the iterator invalidation check from the comparison that contains performs. PiperOrigin-RevId: 595460301 Change-Id: I9a5d6c81385e38184f4848c58209adc5d32bb7be
* Refactor `EraseMetaOnly` to speed up single group tables.Gravatar Abseil Team2023-12-19
| | | | | PiperOrigin-RevId: 592272653 Change-Id: I895c5786555227bdc88ab0a4cce8cf5ba65222a1
* Add `MaskFull` to `Group`.Gravatar Abseil Team2023-12-12
| | | | | | | | | It is not used at the moment. Usage is planned to be submitted separately. Useful for faster iterating over all slots in the internal functions. PiperOrigin-RevId: 590300049 Change-Id: I081f33113268761db868771d29796d94c24e4e7a
* Small table growth optimization.Gravatar Abseil Team2023-12-07
| | | | | | | | | Details: - In case the table entirely fits into a single group size (`capacity <= Group::kWidth`), the order of elements is not important. - For growing upto Group::kWidth we rotate control bytes and slots deterministically (using memcpy). - We also avoid second find_first_non_full right after resize for small growing. PiperOrigin-RevId: 588825966 Change-Id: I09bd7fd489e3868dcf56c36b436805d08dae7ab5
* Partial roll forward of reentrant validation with the validation itself ↵Gravatar Evan Brown2023-11-13
| | | | | | | disabled. This will make it easier to roll back and forwards in the future (if needed) without causing merge conflicts in unrelated code. PiperOrigin-RevId: 582059046 Change-Id: I66dc6527e7a0b351367b7a391c2d653fe793143f
* Roll back due to leak sanitizer reports.Gravatar Aaron Jacobs2023-11-08
| | | | | PiperOrigin-RevId: 580726428 Change-Id: I12b0f22c2084aef90bcca67536220a6bb550b57e
* Add control()/slot() functions to iterator/const_iterator.Gravatar Evan Brown2023-11-07
| | | | | | | | | This allows for avoiding e.g. it.inner_.slot_ on const iterators. Also, refactor HashtableDebugAccess::AllocatedByteSize to use regular iteration instead of looking directly at control/slot_array of the table in order to support small object optimization. PiperOrigin-RevId: 580194253 Change-Id: I64cd69287834ee5c7a8daf867c532258806bfb7b
* Add sanitizer mode validation for use of references to swisstables elements ↵Gravatar Evan Brown2023-11-01
| | | | | | | that may have been invalidated by a container move. PiperOrigin-RevId: 578649798 Change-Id: Icfee98d3a0399b545ec6ec59c5b52ae5e006218b
* Roll forward: Add sanitizer mode checks that element ↵Gravatar Evan Brown2023-10-30
| | | | | | | constructors/destructors don't make reentrant calls to raw_hash_set member functions. PiperOrigin-RevId: 577877803 Change-Id: I254c589b00cadec6ff95dfd60a8a38ab303c1af5
* Rollback: Add sanitizer mode checks that element constructors/destructors ↵Gravatar Evan Brown2023-10-17
| | | | | | | don't make reentrant calls to raw_hash_set member functions. PiperOrigin-RevId: 574232718 Change-Id: I8ef25fec00b76ee5fb9424e7614ca55edd6ba81b
* Add sanitizer mode checks that element constructors/destructors don't make ↵Gravatar Evan Brown2023-10-16
| | | | | | | reentrant calls to raw_hash_set member functions. PiperOrigin-RevId: 573897598 Change-Id: If40c23ac3cd9fff315ee18774e27c480cbca3a81
* Add iterator invalidation checking for when the hashtable is moved.Gravatar Evan Brown2023-10-16
| | | | | | Motivation: once we enable small object optimization in swisstable, iterators can be invalidated when the table is moved. PiperOrigin-RevId: 573884505 Change-Id: I4278129829143d3747dfd0ef0ff92f321c2633dc
* The current implementation of control by checking on x86 has an unnecessary ↵Gravatar Abseil Team2023-10-12
| | | | | | | | | sign extension after the doing the control byte comparison. Changing the bitmask object to explicitly track only 16 bits (instead of 32) eliminates this, saving an instruction / cycle. This speeds up hit checking by up to 6% on Milan and up to 15% on CLX PiperOrigin-RevId: 572965182 Change-Id: Ifda0e3250d409266d6dcef89cba6ada91d879291
* Correct the grammar of an IWYU pragma.Gravatar Abseil Team2023-10-06
| | | | | PiperOrigin-RevId: 571322393 Change-Id: I0e227b0075d3133ee28c8f766a1be7872c101176
* Use ABSL_RAW_LOG and ABSL_PREDICT_* for all debug checks in swisstable ↵Gravatar Evan Brown2023-10-03
| | | | | | | | | including sanitizer mode checks. Sanitizer mode can be used for canaries so performance is still relevant. This change also makes the code more uniform. PiperOrigin-RevId: 570438923 Change-Id: I62859160eb9323e6420680a43fd23e97e8a62389
* Refactor swisstable copy/move assignment to fix issues with allocator ↵Gravatar Evan Brown2023-10-03
| | | | | | | | | | | | | | | | | propagation and improve performance. Correctness: - We use swap to implement copy assignment and move assignment, which means that allocator propagation in copy/move assignment depends on `propagate_on_container_swap` in addition to `propagate_on_container_copy_assignment`/`propagate_on_container_move_assignment`. - In swap, if `propagate_on_container_swap` is `false` and `get_allocator() != other.get_allocator()`, the behavior is undefined (https://en.cppreference.com/w/cpp/container/unordered_set/swap) - we should assert that this UB case isn't happening. For this reason, we also delete the NoPropagateOn_Swap test case in raw_hash_set_allocator_test. Performance: - Don't rely on swap so we don't have to do unnecessary copying into the moved-from sets. - Don't use temp sets in move assignment. - Default the move constructor of CommonFields. - Avoid using exchange in raw_hash_set move constructor. - In `raw_hash_set(raw_hash_set&& that, const allocator_type& a)` with unequal allocators and in move assignment with non-propagating unequal allocators, move set keys instead of copying them. PiperOrigin-RevId: 570419290 Change-Id: I499e54f17d9cb0b0836601f5c06187d1f269a5b8
* Export common.h from raw_hash_set.h to prevent IWYU from linting when using ↵Gravatar Abseil Team2023-09-27
| | | | | | | node_handle PiperOrigin-RevId: 568997790 Change-Id: I9899ccc95eeb9c8b92d0dceec7e2fc4a2b1102c0
* Use ABSL_PREDICT_FALSE and ABSL_RAW_LOG for shared safety checks in ↵Gravatar Daniel Cheng2023-09-20
| | | | | | | | | | | | | raw_hash_set. `SwisstableDebugEnabled()` is also true for release builds with hardening enabled. To minimize their impact in those builds: - use `ABSL_PREDICT_FALSE()` to provide a compiler hint for code layout - use `ABSL_RAW_LOG()` with a format string to reduce code size and improve the chances that the hot paths will be inlined. PiperOrigin-RevId: 567102494 Change-Id: I6734bd491d7b2e1fb9df0e86f4e29e6ad0a03102
* Remove the unused LowerBoundAllocatedByteSize function.Gravatar Evan Brown2023-09-05
| | | | | PiperOrigin-RevId: 562832827 Change-Id: If37f83e67b3b2ea350f74dd6bffae51ea5508f12
* Optimize Resize and Iteration on ArmGravatar Connal de Souza2023-08-30
| | | | | | | | | | | | | There is a few cycles of overhead when transfering between GPR and Neon registers. We pay this cost for GroupAarch64Impl, largely because the speedup we get in Match() makes it profitable. After a Match call, if we do subsequent Group operations, we don't have to pay the full GPR <-> Neon cost, so it makes sense to do them with Neon instructions as well. However, in iteration and find_first_non_full(), we do not do a prior Match(), so the Mask/Count EmptyOrDeleted calls pay the full GPR <-> Neon cost. We can avoid this by using the GPR versions of the functions in the portable implementation of Group instead. We slightly change the order of operations in these functions (should be functionally a nop) in order to take advantage of Arm's free flexible second operand shifts with Logical operations. Iteration and Resize are roughly 8% and 12.6% faster respectively. This is not profitable on x86 because there is much lower GPR <-> xmm register latency and we use a 16-bit wide Group size. PiperOrigin-RevId: 561415183 Change-Id: I660b5bb84afedb05a12dcdf04d5b2e1514902760
* Make raw_hash_set::destroy_slots no longer public. It was never meant to be ↵Gravatar Evan Brown2023-08-29
| | | | | | | a public member of the API. PiperOrigin-RevId: 561061460 Change-Id: Ib804d3d3cf427ebfc9e622db9915287eb8045e26
* Remove the has_element function and use FindElement instead.Gravatar Evan Brown2023-08-17
| | | | | PiperOrigin-RevId: 557920808 Change-Id: I1eb0ca1ea9e9de542321fbc23d82218c5d449fbf
* Update an old comment that refers to obsolete types.Gravatar Evan Brown2023-08-15
| | | | | PiperOrigin-RevId: 557187112 Change-Id: I7c3e4be0ab5a7451173da7a0ded53a3d227bb093
* Add missing includes in raw_hash_set.h.Gravatar Evan Brown2023-08-11
| | | | | PiperOrigin-RevId: 556065631 Change-Id: I7e69b1495946c42fab185a1bc23e9564bfbd5e41
* Store infoz on the heap instead of inline and store it only when we are ↵Gravatar Evan Brown2023-08-04
| | | | | | | sampling the current allocation. PiperOrigin-RevId: 553847957 Change-Id: Idd131d0362bf36bd22d9bd20df54bd9ae50f0e28
* Optimize Swissmap Match on Arm.Gravatar Connal de Souza2023-08-04
| | | | | | | | | | | | | | | | | Currently we require only a single bit to be set in each abstract bit for iterable bitmasks. However, in most cases, where we have a single match, or no matches in a group, iteration is not needed. We move the masking to the iteration function instead of having it as a requirement for iterable Bitmask construction. This is 4-8% faster for Find and Insert operations. This can hurt performance if we need to iterate many times (there are many matches in the same Group), however this is unlikely, even if we assume the table is completely full. If there are 0 or 1 matches in a group, or the first match is the correct item we are looking for, we save 1 instruction/cycle (most cases) If there are 2 matches in a group, and the first is a false positive, this is neutral (< 3%) If there are more than 2 matches in a group and the first two are false positives, this can be slower by 1 cycle/instruction per additional iteration (< 0.1%) No change to x86. PiperOrigin-RevId: 553831814 Change-Id: I08620899847eaf0086da989d829a1029ea24173a
* Update the comment for capacity_ to mention recent experiments to compress ↵Gravatar Evan Brown2023-08-03
| | | | | | | the field and store it together with size_. PiperOrigin-RevId: 553499768 Change-Id: Ia6eec6d580475a2b76a2415bfb35bcc08131ae34
* Refactor raw_hash_set deallocation to pass CommonFields instead of passing ↵Gravatar Evan Brown2023-07-27
| | | | | | | | the results of a bunch of accessors of CommonFields. Motivation: this makes it easier to refactor CommonFields to be smaller. PiperOrigin-RevId: 551616928 Change-Id: I3710443fb156537d716944584bea02f945559e99
* Change the API constraints of erase(const_iterator, const_iterator) so that ↵Gravatar Evan Brown2023-07-26
| | | | | | | calling erase(begin(), end()) resets reserved growth. PiperOrigin-RevId: 551248712 Change-Id: I34755c63e3ee40da4ba7047e0d24eec567d28173
* Add a special case for erase(begin(), end()) to reset the control bytes. The ↵Gravatar Evan Brown2023-07-20
| | | | | | | | motivation is to avoid potentially expanding the table unnecessarily later. Note: I prefer doing this as a special case in erase(iterator, iterator) rather than special casing erase(iterator) for size==1 because IIUC that changes the time complexity of erase(iterator) from O(1) to O(N) and in pathological cases, it could change loops from O(N) to O(N^2). PiperOrigin-RevId: 549661855 Change-Id: I8603324260f51a98809db32f840ff09f25cf2481
* Rename CommonFields::slots_ptr to slot_array to match the name of the ↵Gravatar Evan Brown2023-07-19
| | | | | | | corresponding function in raw_hash_set. PiperOrigin-RevId: 549379884 Change-Id: I305745dbea2c15821b2092441c9b4546fc7aabbe
* Move growth_left to the backing array.Gravatar Evan Brown2023-07-17
| | | | | PiperOrigin-RevId: 548794485 Change-Id: Ie82d5f8ad752518ef05b38144ca1e32b21c9def8
* Clarify that lazy_emplace returns an iterator to the new element when lookup ↵Gravatar Abseil Team2023-07-05
| | | | | | | fails. PiperOrigin-RevId: 545683736 Change-Id: Ic0abec5037e160898e2f24de1b1489caff7d06fd
* roll forward: Make data members of CommonFields be private so that it's ↵Gravatar Evan Brown2023-06-30
| | | | | | | easier to change how we store this information internally. PiperOrigin-RevId: 544732832 Change-Id: I0c9a30f18edc71b3c7fffe94e2002ff6c52050f8
* rollback: Make data members of CommonFields be private so that it's easier ↵Gravatar Evan Brown2023-06-30
| | | | | | | to change how we store this information internally. PiperOrigin-RevId: 544718317 Change-Id: I0ff3e4df7e810be9f7c5db4328995e172eb704a5
* Make data members of CommonFields be private so that it's easier to change ↵Gravatar Evan Brown2023-06-30
| | | | | | | how we store this information internally. PiperOrigin-RevId: 544667586 Change-Id: I9b1943ca71ea1c1f8699832422cd7bc095ac8b2d
* Convert `raw_hash_set` comments from imperative to indicative mood.Gravatar Bradley C. Kuszmaul2023-05-31
| | | | https://google.github.io/styleguide/cppguide.html#Function_Comments
* Merge pull request #1462 from kuszmaul:fix-typoGravatar Copybara-Service2023-05-31
|\ | | | | | | | | PiperOrigin-RevId: 536785792 Change-Id: I2963dea81a75b01b7275d784f6a2908816d0c7bf
| * Typo gardeningGravatar Bradley C. Kuszmaul2023-05-30
|/
* Add lifetimebound attribute to some Abseil containersGravatar Abseil Team2023-05-03
| | | | | PiperOrigin-RevId: 529119690 Change-Id: If585274c409e2a344c8d60759da6f8f990023d29
* Merge pull request #1434 from Vertexwahn:fix-spellingGravatar Copybara-Service2023-04-25
|\ | | | | | | | | PiperOrigin-RevId: 527066823 Change-Id: Ifa1e9a43c7490b34f9f4dbfa12d3acbed6b49777
| * Fix some spelling mistakesGravatar Vertexwahn2023-04-24
|/
* Use multiple empty generations so that we can detect when iterators from ↵Gravatar Evan Brown2023-03-02
| | | | | | | different empty hashtables are compared. PiperOrigin-RevId: 513568915 Change-Id: I3f387d0bae0e86749dff540e4fdd5037304ac975
* Optimize ConvertSpecialToEmptyAndFullToDeleted on ArmGravatar Connal de Souza2023-02-23
| | | | | | | BM_DropDeletes 73.4µs ± 0% 68.9µs ± 1% -6.22% (p=0.008 n=5+5) PiperOrigin-RevId: 511813266 Change-Id: Id28cece454d583e2dfe060e27cfc4720f987f009
* Merge pull request #1402 from AtariDreams:workaroundGravatar Copybara-Service2023-02-22
|\ | | | | | | | | PiperOrigin-RevId: 511695308 Change-Id: I502cdc75e993582eaca5cd91ed068238936a9640
* | Refactor swisstable iterator debug messages code. The motivations are (a) ↵Gravatar Evan Brown2023-02-21
| | | | | | | | | | | | | | distinguish between the "likely erased" and "could have rehashed" cases when generations are enabled, (b) suggest running under ASan when generations aren't enabled and doing so would narrow down the possible error cases, and (c) make ABSL_INTERNAL_ASSERT_IS_FULL not be a macro. PiperOrigin-RevId: 511255275 Change-Id: I5a44a813cd310837d0bd0209d2187b100be201e7
| * Remove workaround for gcc 5.1Gravatar Rose2023-02-21
|/ | | | We support GCC 7 and up, so we can remove this.
* Make default-constructed swisstable iterators use EmptyGroup() for ctrl_ so ↵Gravatar Evan Brown2023-02-14
| | | | | | | that we can distinguish between end() iterators and default-constructed iterators in debug mode. PiperOrigin-RevId: 509606271 Change-Id: I77b68590b3904a4cf7809b75d814d74cb89603b6
generated by cgit v1.2.3 (git 2.39.1) at 2025-02-08 14:19:32 +0000