aboutsummaryrefslogtreecommitdiff
path: root/absl/container/internal/raw_hash_set_test.cc
Commit message (Collapse)AuthorAgeFilesLines
* Add assertions to detect reentrance in `IterateOverFullSlots` and ↵Vitaly Goldshteyn2024-06-271-0/+117
| | | | | | | | | `absl::erase_if`. Since we have potential plans to use this function more widely including `absl::c_for_each`, we need to have good error detection. PiperOrigin-RevId: 647236725 Change-Id: I5035bfb8cef24f80f1bbed83a42380e57d84e428
* Remove not used after all kAllowRemoveReentrance parameter from ↵Vitaly Goldshteyn2024-06-201-38/+3
| | | | | | | | | IterateOverFullSlots. We decided to not allow reentrance in absl::erase_if and absl::container_internal::c_for_each_fast. PiperOrigin-RevId: 645273965 Change-Id: I75dfc73b93ba10f0e051bf0833723af887e1bb36
* Create `absl::container_internal::c_for_each_fast` for SwissTable.Vitaly Goldshteyn2024-06-201-0/+52
| | | | | | | | | | | | | | | | | | This function is aimed to achieve faster iteration through the entire hash table. It is not ready to be used by the public and stays in `container_internal` namespace. Differences with `absl::c_for_each`: 1. No guarantees on order of iteration. Although for the hash table it is partially not guaranteed already. But we do not even guarantee that it is the same order as in the for loop range. De facto, the order is the same at the moment. 2. No mutating reentrance is allowed. Most notably erasing from the hash_table is not allowed. Based on microbenchmarks, there are following conclusions: 1. c_for_each_fast is clearly faster on big tables with 20-60% speedup. 2. Microbenchmarks show regression on a full small table without any empty slots. We should avoid recommending that for small tables. 3. It seems reasonable to use `c_for_each_fast` in places, where `skip_empty_or_deleted` has significant GCU usage. `skip_empty_or_deleted` usage signals that there are "gaps" between elements, so `c_for_each_fast` should be an improvement. PiperOrigin-RevId: 645142512 Change-Id: I279886b8c8b2545504c2bf7e037d27b2545e044d
* Disallow reentrance removal in `absl::erase_if`.Vitaly Goldshteyn2024-06-111-28/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Predicates should generally have no side effects since we do not guarantee the order or quantity for the calls. In this change we forbid one specific side effect: modification of the table we are iterating over. As a positive effect we have performance improvements (less computations and less branches). ``` name old cpu/op new cpu/op delta BM_EraseIf/num_elements:10/num_erased:0 3.02ns ± 2% 2.79ns ± 3% -7.44% (p=0.000 n=35+37) BM_EraseIf/num_elements:1000/num_erased:0 2.41ns ± 5% 2.05ns ± 4% -14.88% (p=0.000 n=37+37) BM_EraseIf/num_elements:10/num_erased:5 4.40ns ± 3% 4.22ns ± 3% -4.19% (p=0.000 n=37+37) BM_EraseIf/num_elements:1000/num_erased:500 9.16ns ± 4% 9.13ns ± 3% ~ (p=0.307 n=37+37) BM_EraseIf/num_elements:10/num_erased:10 5.77ns ± 3% 5.50ns ± 4% -4.62% (p=0.000 n=37+37) BM_EraseIf/num_elements:1000/num_erased:1000 7.84ns ± 3% 7.77ns ± 3% -0.94% (p=0.006 n=37+35) name old time/op new time/op delta BM_EraseIf/num_elements:10/num_erased:0 3.02ns ± 2% 2.79ns ± 3% -7.48% (p=0.000 n=35+36) BM_EraseIf/num_elements:1000/num_erased:0 2.41ns ± 5% 2.05ns ± 4% -14.89% (p=0.000 n=37+37) BM_EraseIf/num_elements:10/num_erased:5 4.42ns ± 3% 4.23ns ± 3% -4.22% (p=0.000 n=37+37) BM_EraseIf/num_elements:1000/num_erased:500 9.18ns ± 4% 9.15ns ± 3% ~ (p=0.347 n=37+37) BM_EraseIf/num_elements:10/num_erased:10 5.79ns ± 3% 5.52ns ± 4% -4.61% (p=0.000 n=37+37) BM_EraseIf/num_elements:1000/num_erased:1000 7.87ns ± 3% 7.79ns ± 3% -0.95% (p=0.007 n=37+35) name old INSTRUCTIONS/op new INSTRUCTIONS/op delta BM_EraseIf/num_elements:10/num_erased:0 14.9 ± 0% 12.9 ± 0% -13.46% (p=0.000 n=37+37) BM_EraseIf/num_elements:1000/num_erased:0 12.7 ± 0% 10.3 ± 0% -18.76% (p=0.000 n=37+37) BM_EraseIf/num_elements:10/num_erased:5 30.9 ± 0% 28.9 ± 0% -6.48% (p=0.000 n=37+37) BM_EraseIf/num_elements:1000/num_erased:500 37.6 ± 0% 35.3 ± 0% -6.33% (p=0.000 n=37+37) BM_EraseIf/num_elements:10/num_erased:10 46.9 ± 0% 44.9 ± 0% -4.27% (p=0.000 n=37+37) BM_EraseIf/num_elements:1000/num_erased:1000 62.6 ± 0% 60.2 ± 0% -3.80% (p=0.000 n=37+36) name old CYCLES/op new CYCLES/op delta BM_EraseIf/num_elements:10/num_erased:0 4.91 ± 1% 4.11 ± 1% -16.35% (p=0.000 n=36+35) BM_EraseIf/num_elements:1000/num_erased:0 7.74 ± 2% 6.54 ± 2% -15.54% (p=0.000 n=37+37) BM_EraseIf/num_elements:10/num_erased:5 9.18 ± 3% 8.45 ± 3% -7.88% (p=0.000 n=37+35) BM_EraseIf/num_elements:1000/num_erased:500 29.5 ± 1% 29.3 ± 1% -0.82% (p=0.000 n=36+37) BM_EraseIf/num_elements:10/num_erased:10 13.5 ± 1% 12.6 ± 0% -7.06% (p=0.000 n=33+34) BM_EraseIf/num_elements:1000/num_erased:1000 25.1 ± 0% 24.9 ± 0% -0.90% (p=0.000 n=37+35) ``` PiperOrigin-RevId: 642318040 Change-Id: I78a4a5a9a5881db0818225f9c7c153c562009f66
* Use `IterateOverFullSlots` in `absl::erase_if` for hash table.Vitaly Goldshteyn2024-06-101-89/+235
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | `EraseIf` itself is not very hot function, but I want to use that as demonstration of the speed of iteration via `IterateOverFullSlots`. Motivation: 1. We are still going to save some resources. 2. It is the first step to implement faster `absl::c_for_each` that may give larger benefits. Will require readability considerations. `BM_EraseIf/num_elements:1000/num_erased:0` is just iteration and it gives 60% speed up. On smaller tables removing all elements shows 25% speed up. Note that on small tables erasing is much faster due to cl/592272653. ``` name old cpu/op new cpu/op delta BM_EraseIf/num_elements:10/num_erased:0 3.41ns ± 5% 3.03ns ± 3% -11.14% (p=0.000 n=37+35) BM_EraseIf/num_elements:1000/num_erased:0 6.06ns ± 3% 2.42ns ± 3% -60.05% (p=0.000 n=34+37) BM_EraseIf/num_elements:10/num_erased:5 5.90ns ± 3% 4.44ns ± 4% -24.88% (p=0.000 n=36+37) BM_EraseIf/num_elements:1000/num_erased:500 11.0ns ± 2% 9.2ns ± 2% -16.60% (p=0.000 n=35+37) BM_EraseIf/num_elements:10/num_erased:10 8.03ns ± 3% 5.77ns ± 2% -28.19% (p=0.000 n=37+37) BM_EraseIf/num_elements:1000/num_erased:1000 9.00ns ± 3% 7.83ns ± 2% -12.98% (p=0.000 n=37+37) name old time/op new time/op delta BM_EraseIf/num_elements:10/num_erased:0 3.42ns ± 5% 3.04ns ± 3% -11.13% (p=0.000 n=37+36) BM_EraseIf/num_elements:1000/num_erased:0 6.07ns ± 3% 2.42ns ± 3% -60.10% (p=0.000 n=34+37) BM_EraseIf/num_elements:10/num_erased:5 5.93ns ± 3% 4.45ns ± 4% -24.89% (p=0.000 n=36+37) BM_EraseIf/num_elements:1000/num_erased:500 11.1ns ± 2% 9.2ns ± 2% -16.61% (p=0.000 n=35+37) BM_EraseIf/num_elements:10/num_erased:10 8.06ns ± 3% 5.79ns ± 2% -28.19% (p=0.000 n=37+37) BM_EraseIf/num_elements:1000/num_erased:1000 9.03ns ± 3% 7.85ns ± 2% -12.98% (p=0.000 n=37+37) name old INSTRUCTIONS/op new INSTRUCTIONS/op delta BM_EraseIf/num_elements:10/num_erased:0 19.5 ± 1% 14.9 ± 0% -23.79% (p=0.000 n=37+37) BM_EraseIf/num_elements:1000/num_erased:0 19.9 ± 0% 12.7 ± 0% -36.20% (p=0.000 n=37+37) BM_EraseIf/num_elements:10/num_erased:5 36.9 ± 1% 30.9 ± 0% -16.47% (p=0.000 n=37+37) BM_EraseIf/num_elements:1000/num_erased:500 44.8 ± 0% 37.6 ± 0% -16.06% (p=0.000 n=37+37) BM_EraseIf/num_elements:10/num_erased:10 53.0 ± 1% 46.9 ± 0% -11.61% (p=0.000 n=37+37) BM_EraseIf/num_elements:1000/num_erased:1000 69.8 ± 0% 62.6 ± 0% -10.32% (p=0.000 n=36+37) name old CYCLES/op new CYCLES/op delta BM_EraseIf/num_elements:10/num_erased:0 6.10 ± 7% 4.91 ± 1% -19.49% (p=0.000 n=37+37) BM_EraseIf/num_elements:1000/num_erased:0 19.4 ± 1% 7.7 ± 2% -60.04% (p=0.000 n=37+37) BM_EraseIf/num_elements:10/num_erased:5 13.9 ± 4% 9.2 ± 3% -33.80% (p=0.000 n=37+37) BM_EraseIf/num_elements:1000/num_erased:500 35.5 ± 0% 29.5 ± 1% -16.74% (p=0.000 n=37+37) BM_EraseIf/num_elements:10/num_erased:10 20.8 ± 5% 13.5 ± 0% -35.07% (p=0.000 n=37+30) BM_EraseIf/num_elements:1000/num_erased:1000 28.9 ± 0% 25.1 ± 0% -13.06% (p=0.000 n=37+37) ``` PiperOrigin-RevId: 642016364 Change-Id: I8be6af5916bd45fd110bb0398c3ffe932a6a083f
* Add validation that hash/eq functors are consistent, meaning that `eq(k1, ↵Evan Brown2024-06-061-0/+34
| | | | | | | | | k2) -> hash(k1) == hash(k2)`. Also add missing includes/dependencies in flat_hash_map_test. PiperOrigin-RevId: 640959222 Change-Id: I8d99544af05e97310045e6149f6ef6f7c82e552d
* Move `prepare_insert` out of the line as type erased `PrepareInsertNonSoo`.Vitaly Goldshteyn2024-05-201-0/+16
| | | | | | | | | This significantly reduces binary size of big binaries and creates a single hot function instead of many cold. That is decreasing cash misses during code execution. We also avoid size related computations for tables with no deleted slots, when resize is necessary. PiperOrigin-RevId: 635527119 Change-Id: I763b135f1f6089051e62e348a07b33536af265ab
* Use GrowthInfo without applying any optimizations based on it.Vitaly Goldshteyn2024-03-271-0/+21
| | | | | PiperOrigin-RevId: 619649335 Change-Id: I8b3380816418a363fb6686db7966248cb530c491
* Introduce GrowthInfo with tests, but without usage.Vitaly Goldshteyn2024-03-261-0/+72
| | | | | | | The motivation is to use presence of kDeleted slots for optimizing InsertMiss for tables without kDeleted slots. PiperOrigin-RevId: 619411282 Change-Id: Icc30606374aba7ce60b41f93ee8d44894e1b8aa5
* Record sizeof(key_type), sizeof(value_type) in hashtable profiles.Chris Kennelly2024-03-251-0/+2
| | | | | | | | This can identify situations where flat_hash_* is suboptimal for large elements. PiperOrigin-RevId: 618937993 Change-Id: I2bde069bc3526b14ad1718ba6f50467002aeed16
* Do hashtablez sampling on the first insertion into an empty SOO hashtable.Evan Brown2024-03-191-21/+163
| | | | | | | | | When sampling triggers, we skip SOO and allocate a backing array. We must do this because the HashtablezInfoHandle is part of the heap allocation (along with the control bytes and slots). By default, we sample 1 in ~1024 hashtables when sampling is enabled. This will impact performance because (a) we won't benefit from SOO so we would have worse data locality (more cache/TLB misses), and (b) the backing array capacity will be 3 instead of 1 so (b.1) we skip the rehash after the second insertion and (b.2) we potentially waste up to two slots worth of memory. We also add an soo_capacity field to HashtablezInfo to allow for distinguishing which sampled tables may otherwise have been SOO - this will allow us to know approximately what fraction of tables are in SOO mode. PiperOrigin-RevId: 617252334 Change-Id: Ib48b7a4870bd74ea3ba923ed8f350a3b75dbb7d3
* Test that rehash(0) reduces capacity to minimum.Vitaly Goldshteyn2024-03-131-1/+6
| | | | | PiperOrigin-RevId: 615380243 Change-Id: I5400b40a6bc5ac52ece5d4fa6da7df9e4ff50855
* Implement small object optimization in swisstable - disabled for now.Evan Brown2024-03-061-126/+324
| | | | | | | | | Details: - We use the space for control/slots pointers as the inline buffer. - We use a max inline capacity of 1 to make the implementation much simpler and to avoid having to randomize the iteration order for inline tables. - For iteration of inline tables, we introduce the kSooControl buffer which just has 1 full control byte followed by 1 sentinel control byte so that incrementing yields an end() iterator. We don't access kSooControl during lookups - only iteration. PiperOrigin-RevId: 613253492 Change-Id: Id98ff11842f8bef27ac7ed88138dc03b46ce4fa6
* Improve raw_hash_set tests.Abseil Team2024-02-211-14/+29
| | | | | PiperOrigin-RevId: 608947694 Change-Id: Ie53a91c4d78dcb80c57227616b488ec64b23c588
* Introduce `Group::MaskNonFull` without usage.Abseil Team2024-02-151-0/+19
| | | | | | | | It can be used instead of `MaskEmptyOrDeleted` in case of inserting to empty table. `MaskNonFull` requires less operations, in particular it eliminates `_mm_set1_epi8` and `_mm_cmpgt_epi8` operations. PiperOrigin-RevId: 607587394 Change-Id: Ia48f922d1ca6de38cc91e7ab0d608c45f8f2c446
* Avoid hash computation and `Group::Match` in small tables copy and use ↵Abseil Team2024-02-071-2/+44
| | | | | | | `IterateOverFullSlots` for iterating for all tables. PiperOrigin-RevId: 605116090 Change-Id: Ia65c664421f7630225b00f1c45c636b4681121ce
* Optimize raw_hash_set destructor.Abseil Team2024-02-011-0/+35
| | | | | | | | | | There are three optimizations here: 1. Early exit in case all slots were destroyed. especially useful for empty tables. 2. MatchFull is used in order to iterate over all full slots. 3. Portable group is used for `MatchFull` in the case of small table. PiperOrigin-RevId: 603434899 Change-Id: I40bc90d17331d579cfbb1b4e0693f0913e5c38e4
* Type erased hash_slot_fn that depends only on key types (and hash function).Abseil Team2024-01-311-2/+17
| | | | | PiperOrigin-RevId: 603148301 Change-Id: Ie2e5702995c9e1ef4d5aaab23bc89a1eb5007a86
* Avoid extra `& msbs` on every iteration over the mask for GroupPortableImpl.Abseil Team2024-01-311-3/+51
| | | | | PiperOrigin-RevId: 602974812 Change-Id: Ic35b41e321b9456a8ddd83470ee2eb07c51e3180
* Enable ABSL_BTREE_ENABLE_GENERATIONS and ABSL_SWISSTABLE_ENABLE_GENERATIONS ↵Abseil Team2024-01-111-3/+3
| | | | | | | | | | | | | | 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
* Refactor `EraseMetaOnly` to speed up single group tables.Abseil Team2023-12-191-0/+17
| | | | | PiperOrigin-RevId: 592272653 Change-Id: I895c5786555227bdc88ab0a4cce8cf5ba65222a1
* Unit-tests to verify ABSL raw_hash_set does not double-hash in prodAbseil Team2023-12-121-0/+67
| | | | | PiperOrigin-RevId: 590337123 Change-Id: Ib98bbb5a5dadbce5e891567038e016f4da2efc0b
* Add `MaskFull` to `Group`.Abseil Team2023-12-121-12/+32
| | | | | | | | | 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.Abseil Team2023-12-071-17/+99
| | | | | | | | | 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 ↵Evan Brown2023-11-131-10/+6
| | | | | | | 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.Aaron Jacobs2023-11-081-74/+10
| | | | | PiperOrigin-RevId: 580726428 Change-Id: I12b0f22c2084aef90bcca67536220a6bb550b57e
* Add sanitizer mode validation for use of references to swisstables elements ↵Evan Brown2023-11-011-0/+7
| | | | | | | that may have been invalidated by a container move. PiperOrigin-RevId: 578649798 Change-Id: Icfee98d3a0399b545ec6ec59c5b52ae5e006218b
* Roll forward: Add sanitizer mode checks that element ↵Evan Brown2023-10-301-10/+74
| | | | | | | 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-74/+10
| | | | | | | 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-10/+74
| | | | | | | 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-0/+13
| | | | | | Motivation: once we enable small object optimization in swisstable, iterators can be invalidated when the table is moved. PiperOrigin-RevId: 573884505 Change-Id: I4278129829143d3747dfd0ef0ff92f321c2633dc
* Refactor swisstable copy/move assignment to fix issues with allocator ↵Evan Brown2023-10-031-10/+22
| | | | | | | | | | | | | | | | | 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
* Replace BtreeAllocatorTest with individual test cases for copy/move/swap ↵Evan Brown2023-09-211-10/+0
| | | | | | | | | propagation (defined in test_allocator.h) and minimal alignment. Also remove some extraneous value_types from typed tests. The motivation is to reduce btree_test compile time. PiperOrigin-RevId: 567376572 Change-Id: I6ac6130b99faeadaedab8c2c7b05d5e23e77cc1e
* Move CountingAllocator into test_allocator.h and add some other allocators ↵Evan Brown2023-09-151-28/+1
| | | | | | | that can be shared between different container tests. PiperOrigin-RevId: 565693736 Change-Id: I59af987e30da03a805ce59ff0fb7eeae3fc08293
* Store infoz on the heap instead of inline and store it only when we are ↵Evan Brown2023-08-041-10/+1
| | | | | | | sampling the current allocation. PiperOrigin-RevId: 553847957 Change-Id: Idd131d0362bf36bd22d9bd20df54bd9ae50f0e28
* raw_hash_set_test: Expect tsan to catch heap-use-after-free on iterators ↵Dino Radakovic2023-08-011-1/+5
| | | | | | | invalidated by rehashing PiperOrigin-RevId: 552901078 Change-Id: I137d01fe87b1bbf591b400305f6f7919982fc1c9
* raw_hash_set_test: Match lowercase "invalid iterator" in death testsDino Radakovic2023-07-311-1/+1
| | | | | PiperOrigin-RevId: 552520562 Change-Id: I5d311871afbc2906894c3b754a503a6abace8ceb
* Change the API constraints of erase(const_iterator, const_iterator) so that ↵Evan Brown2023-07-261-0/+58
| | | | | | | 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-0/+8
| | | | | | | | 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
* Move growth_left to the backing array.Evan Brown2023-07-171-4/+44
| | | | | PiperOrigin-RevId: 548794485 Change-Id: Ie82d5f8ad752518ef05b38144ca1e32b21c9def8
* Migrate most RAW_LOGs and RAW_CHECKs in tests to regular LOG and CHECK.Andy Getzendanner2023-05-231-3/+2
| | | | | | | | | | | The non-RAW_ versions provide better output but weren't available when most of these tests were written. There are just a couple spots where RAW_ is actually needed, e.g. signal handlers and malloc hooks. Also fix a couple warnings in layout_test.cc newly surfaced because the optimizer understands CHECK_XX differently than INTERNAL_CHECK. PiperOrigin-RevId: 534584435 Change-Id: I8d36fa809ffdaae5a3813064bd602cb8611c1613
* Use multiple empty generations so that we can detect when iterators from ↵Evan Brown2023-03-021-7/+27
| | | | | | | different empty hashtables are compared. PiperOrigin-RevId: 513568915 Change-Id: I3f387d0bae0e86749dff540e4fdd5037304ac975
* Refactor swisstable iterator debug messages code. The motivations are (a) ↵Evan Brown2023-02-211-12/+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
* Make default-constructed swisstable iterators use EmptyGroup() for ctrl_ so ↵Evan Brown2023-02-141-13/+8
| | | | | | | 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-17/+45
| | | | | | | | | 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-0/+31
| | | | | | | | | 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-31/+0
| | | | | | | | | 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-0/+31
| | | | | | | 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-1/+1
| | | | | PiperOrigin-RevId: 505184961 Change-Id: I64482558a76abda6896bec4b2d323833b6cd7edf
* In sanitizer mode, detect when references become invalidated after reserved ↵Evan Brown2023-01-171-1/+8
| | | | | | | growth runs out. PiperOrigin-RevId: 502625638 Change-Id: I1c06b2162dbdaaa6a36cea503ac6d07cd157b2e2
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-07 23:51:04 +0000