aboutsummaryrefslogtreecommitdiff
path: root/absl/container/internal/raw_hash_set.h
Commit message (Collapse)AuthorAgeFilesLines
...
* Roll forward: Add sanitizer mode checks that element ↵Evan Brown2023-10-301-12/+27
| | | | | | | 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 ↵Evan Brown2023-10-171-27/+12
| | | | | | | 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 ↵Evan Brown2023-10-161-12/+27
| | | | | | | reentrant calls to raw_hash_set member functions. PiperOrigin-RevId: 573897598 Change-Id: If40c23ac3cd9fff315ee18774e27c480cbca3a81
* Add iterator invalidation checking for when the hashtable is moved.Evan Brown2023-10-161-6/+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 ↵Abseil Team2023-10-121-11/+15
| | | | | | | | | 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.Abseil Team2023-10-061-1/+1
| | | | | PiperOrigin-RevId: 571322393 Change-Id: I0e227b0075d3133ee28c8f766a1be7872c101176
* Use ABSL_RAW_LOG and ABSL_PREDICT_* for all debug checks in swisstable ↵Evan Brown2023-10-031-28/+27
| | | | | | | | | 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 ↵Evan Brown2023-10-031-47/+94
| | | | | | | | | | | | | | | | | 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 ↵Abseil Team2023-09-271-1/+1
| | | | | | | node_handle PiperOrigin-RevId: 568997790 Change-Id: I9899ccc95eeb9c8b92d0dceec7e2fc4a2b1102c0
* Use ABSL_PREDICT_FALSE and ABSL_RAW_LOG for shared safety checks in ↵Daniel Cheng2023-09-201-15/+24
| | | | | | | | | | | | | 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.Evan Brown2023-09-051-12/+0
| | | | | PiperOrigin-RevId: 562832827 Change-Id: If37f83e67b3b2ea350f74dd6bffae51ea5508f12
* Optimize Resize and Iteration on ArmConnal de Souza2023-08-301-4/+16
| | | | | | | | | | | | | 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 ↵Evan Brown2023-08-291-11/+11
| | | | | | | a public member of the API. PiperOrigin-RevId: 561061460 Change-Id: Ib804d3d3cf427ebfc9e622db9915287eb8045e26
* Remove the has_element function and use FindElement instead.Evan Brown2023-08-171-20/+4
| | | | | PiperOrigin-RevId: 557920808 Change-Id: I1eb0ca1ea9e9de542321fbc23d82218c5d449fbf
* Update an old comment that refers to obsolete types.Evan Brown2023-08-151-2/+2
| | | | | PiperOrigin-RevId: 557187112 Change-Id: I7c3e4be0ab5a7451173da7a0ded53a3d227bb093
* Add missing includes in raw_hash_set.h.Evan Brown2023-08-111-0/+4
| | | | | PiperOrigin-RevId: 556065631 Change-Id: I7e69b1495946c42fab185a1bc23e9564bfbd5e41
* Store infoz on the heap instead of inline and store it only when we are ↵Evan Brown2023-08-041-44/+88
| | | | | | | sampling the current allocation. PiperOrigin-RevId: 553847957 Change-Id: Idd131d0362bf36bd22d9bd20df54bd9ae50f0e28
* Optimize Swissmap Match on Arm.Connal de Souza2023-08-041-3/+6
| | | | | | | | | | | | | | | | | 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 ↵Evan Brown2023-08-031-2/+7
| | | | | | | 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 ↵Evan Brown2023-07-271-48/+52
| | | | | | | | 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 ↵Evan Brown2023-07-261-2/+25
| | | | | | | 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 ↵Evan Brown2023-07-201-4/+10
| | | | | | | | 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 ↵Evan Brown2023-07-191-6/+6
| | | | | | | corresponding function in raw_hash_set. PiperOrigin-RevId: 549379884 Change-Id: I305745dbea2c15821b2092441c9b4546fc7aabbe
* Move growth_left to the backing array.Evan Brown2023-07-171-40/+67
| | | | | PiperOrigin-RevId: 548794485 Change-Id: Ie82d5f8ad752518ef05b38144ca1e32b21c9def8
* Clarify that lazy_emplace returns an iterator to the new element when lookup ↵Abseil Team2023-07-051-1/+2
| | | | | | | fails. PiperOrigin-RevId: 545683736 Change-Id: Ic0abec5037e160898e2f24de1b1489caff7d06fd
* roll forward: Make data members of CommonFields be private so that it's ↵Evan Brown2023-06-301-46/+64
| | | | | | | 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 ↵Evan Brown2023-06-301-62/+46
| | | | | | | 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 ↵Evan Brown2023-06-301-46/+62
| | | | | | | how we store this information internally. PiperOrigin-RevId: 544667586 Change-Id: I9b1943ca71ea1c1f8699832422cd7bc095ac8b2d
* Convert `raw_hash_set` comments from imperative to indicative mood.Bradley C. Kuszmaul2023-05-311-3/+3
| | | | https://google.github.io/styleguide/cppguide.html#Function_Comments
* Merge pull request #1462 from kuszmaul:fix-typoCopybara-Service2023-05-311-10/+10
|\ | | | | | | | | PiperOrigin-RevId: 536785792 Change-Id: I2963dea81a75b01b7275d784f6a2908816d0c7bf
| * Typo gardeningBradley C. Kuszmaul2023-05-301-1/+1
|/
* Add lifetimebound attribute to some Abseil containersAbseil Team2023-05-031-27/+47
| | | | | PiperOrigin-RevId: 529119690 Change-Id: If585274c409e2a344c8d60759da6f8f990023d29
* Merge pull request #1434 from Vertexwahn:fix-spellingCopybara-Service2023-04-251-3/+3
|\ | | | | | | | | PiperOrigin-RevId: 527066823 Change-Id: Ifa1e9a43c7490b34f9f4dbfa12d3acbed6b49777
| * Fix some spelling mistakesVertexwahn2023-04-241-2/+2
|/
* Use multiple empty generations so that we can detect when iterators from ↵Evan Brown2023-03-021-13/+25
| | | | | | | different empty hashtables are compared. PiperOrigin-RevId: 513568915 Change-Id: I3f387d0bae0e86749dff540e4fdd5037304ac975
* Optimize ConvertSpecialToEmptyAndFullToDeleted on ArmConnal de Souza2023-02-231-3/+4
| | | | | | | 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:workaroundCopybara-Service2023-02-221-8/+2
|\ | | | | | | | | PiperOrigin-RevId: 511695308 Change-Id: I502cdc75e993582eaca5cd91ed068238936a9640
| * Remove workaround for gcc 5.1Rose2023-02-211-8/+2
| | | | | | | | We support GCC 7 and up, so we can remove this.
* | Refactor swisstable iterator debug messages code. The motivations are (a) ↵Evan Brown2023-02-211-44/+80
|/ | | | | | | 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
* Make default-constructed swisstable iterators use EmptyGroup() for ctrl_ so ↵Evan Brown2023-02-141-20/+33
| | | | | | | that we can distinguish between end() iterators and default-constructed iterators in debug mode. PiperOrigin-RevId: 509606271 Change-Id: I77b68590b3904a4cf7809b75d814d74cb89603b6
* In sanitizer mode, detect when end iterators from different swisstables are ↵Evan Brown2023-02-091-5/+32
| | | | | | | | | compared. We change AssertSameContainer to be after AssertIsValidForComparison calls so that we can have more specific failure messages. PiperOrigin-RevId: 508472485 Change-Id: Iff2f7512086948a4aca7fd403596e8d4fde53b2a
* Rollforward: in sanitizer mode, detect when references become invalidated by ↵Evan Brown2023-02-011-9/+24
| | | | | | | | | randomly rehashing on insertions when there is no reserved growth. Rollforward of ed59f62f8bbc5f05bcba2f89ee16f107e03813f2 PiperOrigin-RevId: 506314970 Change-Id: I7a654aef36bb169da9ea5c618789ee771f05fe28
* Rollback in sanitizer mode, detect when references become invalidated by ↵Abseil Team2023-01-311-24/+9
| | | | | | | | | randomly rehashing on insertions when there is no reserved growth. Rollback of ed59f62f8bbc5f05bcba2f89ee16f107e03813f2 PiperOrigin-RevId: 506003574 Change-Id: I1766321f279a3226e2821e0390387d5639d28964
* In sanitizer mode, detect when references become invalidated by randomly ↵Evan Brown2023-01-301-9/+24
| | | | | | | rehashing on insertions when there is no reserved growth. PiperOrigin-RevId: 505807487 Change-Id: I9051a04f6a75e579d16e9ae8defd404bcc377fba
* Replace absl::base_internal::Prefetch* calls with absl::Prefetch* callsMartijn Vels2023-01-271-9/+13
| | | | | PiperOrigin-RevId: 505184961 Change-Id: I64482558a76abda6896bec4b2d323833b6cd7edf
* In sanitizer mode, detect when references become invalidated after reserved ↵Evan Brown2023-01-171-9/+35
| | | | | | | growth runs out. PiperOrigin-RevId: 502625638 Change-Id: I1c06b2162dbdaaa6a36cea503ac6d07cd157b2e2
* In sanitizer mode, detect when invalidated iterators are compared.Evan Brown2023-01-051-9/+17
| | | | | PiperOrigin-RevId: 499964205 Change-Id: I45a1d62a5e093921946e7c3c7ab31480252b330e
* Fix a bug in iterator validation code in which we don't update the table's ↵Evan Brown2022-12-221-1/+1
| | | | | | | reserved growth if the reservation wouldn't grow the table. PiperOrigin-RevId: 497246219 Change-Id: I9671236f56d10851c49de71c21899368be6c3a00
* In sanitizer mode, add generations to swisstable iterators and backing ↵Evan Brown2022-12-191-37/+223
| | | | | | | arrays so that we can detect invalid iterator use. PiperOrigin-RevId: 496455788 Change-Id: I83df92828098a3ef1181b4e454f3ac5d3ac7a2f2
* Optimize raw_hash_set CountLeadingEmptyOrDeleted() on ArmConnal de Souza2022-12-191-6/+8
| | | | | | | | name old cpu/op new cpu/op delta BM_Group_CountLeadingEmptyOrDeleted 0.98ns ± 0% 0.78ns ± 0% -20.51% (p=0.000 n=10+10) PiperOrigin-RevId: 496397005 Change-Id: I1c6b325b14566da194f21d3387b6f4d838bf0b34
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-08 05:23:55 +0000