summaryrefslogtreecommitdiff
path: root/absl/container/internal
Commit message (Collapse)AuthorAge
* Make mutable CompressedTuple::get() constexpr.Gravatar Abseil Team2024-07-01
| | | | | | | | This change makes the mutable overloads of CompressedTuple::get() constexpr. This is consistent with std::get(std::tuple), which is constexpr since C++14. PiperOrigin-RevId: 648603141 Change-Id: Icbd61809f7a06723cf581dbed5488b7bae998cc9
* Static cast instead of reinterpret cast raw hash set slots as casting from ↵Gravatar Abseil Team2024-07-01
| | | | | | | void* to T* is well defined PiperOrigin-RevId: 648352837 Change-Id: I082cd0c007706ae8baa8f26cdc85d51b69bffd54
* Add assertions to detect reentrance in `IterateOverFullSlots` and ↵Gravatar Vitaly Goldshteyn2024-06-27
| | | | | | | | | `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 ↵Gravatar Vitaly Goldshteyn2024-06-20
| | | | | | | | | 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.Gravatar Vitaly Goldshteyn2024-06-20
| | | | | | | | | | | | | | | | | | 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`.Gravatar Vitaly Goldshteyn2024-06-11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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.Gravatar Vitaly Goldshteyn2024-06-10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | `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, ↵Gravatar Evan Brown2024-06-06
| | | | | | | | | k2) -> hash(k1) == hash(k2)`. Also add missing includes/dependencies in flat_hash_map_test. PiperOrigin-RevId: 640959222 Change-Id: I8d99544af05e97310045e6149f6ef6f7c82e552d
* Remove redundant check of is_soo() while prefetching heap blocks.Gravatar Abseil Team2024-06-05
| | | | | PiperOrigin-RevId: 640620462 Change-Id: I72c0a7f0f549404ad8310b8cebd7dd491341390b
* Remove redundant check of is_soo() while prefetching heap blocks.Gravatar Abseil Team2024-06-04
| | | | | PiperOrigin-RevId: 640359514 Change-Id: Ic321d23cad283425c686536ae7be04a490a950d5
* Remove redundant check of is_soo() while prefetching heap blocks.Gravatar Abseil Team2024-06-04
| | | | | PiperOrigin-RevId: 640208455 Change-Id: I4c2b7d3f1adad2078e8a5f805574f71c4d7743d4
* Clarify function comment for `erase` by stating that this idiom only works ↵Gravatar Abseil Team2024-06-03
| | | | | | | | | for "some" standard containers. If you use this idiom with `std::vector` or `absl::btree_map` you can end up either skipping elements or dereferencing an invalid iterator. PiperOrigin-RevId: 639892758 Change-Id: Ic5c213667b4b1e8c39813ee237aaffe320a8eb27
* Optimize GrowIntoSingleGroupShuffleControlBytes.Gravatar Connal de Souza2024-05-28
| | | | | | | This implementation is designed to avoid needing to copy to an intermediate buffer and then read from it again, which is an expensive Read-after-Write hazard. PiperOrigin-RevId: 638071429 Change-Id: I390b4d38b8c1bd7fffba3d403baba6f1511555b0
* Rework casting in raw_hash_set's IsFull().Gravatar Paul Rigge2024-05-22
| | | | | PiperOrigin-RevId: 636218177 Change-Id: I9f58ccbb468fcc0c44ef12162415f7b721a745bf
* Move `prepare_insert` out of the line as type erased `PrepareInsertNonSoo`.Gravatar Vitaly Goldshteyn2024-05-20
| | | | | | | | | 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
* [absl] Re-use the existing `std::type_identity` backfill instead of ↵Gravatar Lawrence Wolf-Sonkin2024-04-18
| | | | | | | | | redefining it again * Specifically, using `absl::internal::type_identity_t` instead of a reimplementation thereof (`NoTypeDeduction`) in the `absl::InlinedVector` code PiperOrigin-RevId: 626055714 Change-Id: I3f5a9a1c25480bc4431edbcc4784e6bc8d257f8d
* Fix bug in BM_EraseIf.Gravatar Vitaly Goldshteyn2024-04-02
| | | | | PiperOrigin-RevId: 621258501 Change-Id: Id094f3f0d0bc4a9fa8f3d1f90cfcd4c53beeb776
* Roll forward: enable small object optimization in swisstable.Gravatar Evan Brown2024-03-28
| | | | | PiperOrigin-RevId: 619984581 Change-Id: I68fc9d6e9dd447bdccdbfd270073e11865f85965
* Optimize InsertMiss for tables without kDeleted slots.Gravatar Vitaly Goldshteyn2024-03-27
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This CL contains two optimizations that were measured together. 1) InsertMiss (i. e. successful insert) optimization: The idea that in case there is no kDeleted, we already know 99% of the information. So we are finding the position to insert with 2 asm instructions (or 3 in case of ARM or portable) and passing that as a hint into `prepare_insert`. `prepare_insert` is out of the line in order to minimize effect on InsertHit (the most important case). `prepare_insert` may use the hint in case we still have growth and no kDeleted is guaranteed. In case of kDeleted, we still call `find_first_non_full` in order to potentially find kDeleted slot earlier. We may consider different ways to do it faster for kDeleted later. 2) `find_first_non_full` optimization: After optimization #1 `find_first_non_full` is used: 1. during resize and copy 2. right after resize 3. during DropDeletedWithoutResize 3. in InsertMiss for tables with kDeleted In cases 1-3 the table is quite sparse. 1. After resize it is 7/16 sparse 2. During resize it is 7/16 maximum, but during first inserts it is much sparser. 3. During copy it may be up to 7/8, but at the beginning it is way sparser. 4. During DropDeletedWithoutResize it is 25/32 sparse, but at the beginning it is way sparser. The only case, where the table is not known to be sparse, with `find_first_non_full` usage is a table with deleted elements. But according to hashz, we have <3% such tables. Adding an extra branch wouldn't hurt much there. PiperOrigin-RevId: 619681885 Change-Id: Id3e2852cc6d85f6c8f90982d7aeb14799696bf39
* Use GrowthInfo without applying any optimizations based on it.Gravatar Vitaly Goldshteyn2024-03-27
| | | | | PiperOrigin-RevId: 619649335 Change-Id: I8b3380816418a363fb6686db7966248cb530c491
* Disable small object optimization while debugging some failing tests.Gravatar Evan Brown2024-03-27
| | | | | PiperOrigin-RevId: 619598530 Change-Id: Ie4b808a3b826db8c271c81914c7a88d2c6216eb2
* Introduce GrowthInfo with tests, but without usage.Gravatar Vitaly Goldshteyn2024-03-26
| | | | | | | The motivation is to use presence of kDeleted slots for optimizing InsertMiss for tables without kDeleted slots. PiperOrigin-RevId: 619411282 Change-Id: Icc30606374aba7ce60b41f93ee8d44894e1b8aa5
* Enable small object optimization in swisstable.Gravatar Evan Brown2024-03-26
| | | | | | | See [implementation commit](https://github.com/abseil/abseil-cpp/commit/1449c9a106b090f61441ba245c781d7d2f89000c) for design details. PiperOrigin-RevId: 619309882 Change-Id: I093c00365dda2268be86ba3d21421b6ffb59a5ce
* Refactor the GCC unintialized memory warning suppression in raw_hash_set.h.Gravatar Evan Brown2024-03-26
| | | | | | Motivation: there are new uninitialized memory warnings when we enable small object optimization. PiperOrigin-RevId: 619295212 Change-Id: If10762bab0e43c9619fc03f6d1eef5b8836bbf9a
* Respect `NDEBUG_SANITIZER`Gravatar Abseil Team2024-03-26
| | | | | | | | | | | | | | | | | | | | | Often code needs to know that it's built with sanitizers. There are two common use for such information: 1. Work around incompatibility with sanitizers 2. Use sanitizers for more aggressive bug detection With the current `ABSL_HAVE_*_SANITIZER` we can't distinguish this two cased, and we didn't need that before. Now user can define `NDEBUG_SANITIZER` to ask code like this to avoid unnecessary checks. I am not 100% sure that `NDEBUG` is not enough. However relying on `NDEBUG` today will relax many tests, which runs in NDEBUG mode only. So new `NDEBUG_SANITIZER` is safer approach. PiperOrigin-RevId: 619268413 Change-Id: I58185cd6886593a3742b8424deccdec366c2a35a
* Add `BM_EraseIf` benchmark.Gravatar Vitaly Goldshteyn2024-03-25
| | | | | PiperOrigin-RevId: 618970135 Change-Id: Ifb9d0b425904d5cb37d80ec28ab7845957209313
* Record sizeof(key_type), sizeof(value_type) in hashtable profiles.Gravatar Chris Kennelly2024-03-25
| | | | | | | | This can identify situations where flat_hash_* is suboptimal for large elements. PiperOrigin-RevId: 618937993 Change-Id: I2bde069bc3526b14ad1718ba6f50467002aeed16
* Fix ClangTidy warnings in btree.h.Gravatar Evan Brown2024-03-25
| | | | | PiperOrigin-RevId: 618872032 Change-Id: I9fdfadff906494eb64cee976c02a1fff57923c79
* Use Layout::WithStaticSizes in btree.Gravatar Evan Brown2024-03-21
| | | | | PiperOrigin-RevId: 617877687 Change-Id: I29c52f9288f099255c4adb7c1f9fa8831ac55b05
* `layout`: Delete outdated comments about ElementType alias not being used ↵Gravatar Dino Radakovic2024-03-21
| | | | | | | | | because of MSVC Code below those comments does use ElementType. PiperOrigin-RevId: 617854731 Change-Id: I7996b8cbaa2fb65855a801f634a57d821408b1f3
* `layout_benchmark`: Replace leftover comment with intended call to MyAlignGravatar Dino Radakovic2024-03-20
| | | | | PiperOrigin-RevId: 617573381 Change-Id: I0ddab2ab7cf68651424b3cf385b484d27106dd59
* Do hashtablez sampling on the first insertion into an empty SOO hashtable.Gravatar Evan Brown2024-03-19
| | | | | | | | | 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
* Add template keyword to example comment for Layout::WithStaticSizes.Gravatar Evan Brown2024-03-18
| | | | | | | Without this keyword, we can sometimes get cryptic compilation failures such as "error: expected ';' after alias declaration". PiperOrigin-RevId: 616933517 Change-Id: I2209f3899a4ac03c031217cec67de25bd376d355
* Fix a typo in a comment.Gravatar Evan Brown2024-03-18
| | | | | PiperOrigin-RevId: 616895950 Change-Id: I9dc9099e779df4b692496aa5ee5573ef0e7fd826
* Add a feature to container_internal::Layout that lets you specify some array ↵Gravatar Abseil Team2024-03-18
| | | | | | | | | sizes at compile-time as template parameters. This can make offset and size calculations faster. In particular, it seems to always improve the performance of AllocSize(), and it sometimes improves the performance of other functions, e.g. when the Layout object outlives the function that created it. PiperOrigin-RevId: 616817169 Change-Id: Id1d318d7d2af68783f9f59090d89c642be6ae558
* `layout`: Mark parameter of Slices with ABSL_ATTRIBUTE_UNUSED, remove old ↵Gravatar Dino Radakovic2024-03-15
| | | | | | | | | | | | | | workaround The workaround was added for a bug in GCC < 6.1., which had since been fixed. Abseil only [supports](https://github.com/google/oss-policies-info/blob/9a9bfe8a4a12be20757497074fc2f0ecb77438ad/foundational-cxx-support-matrix.md) GCC > 7.3.1. However, removing the workaround still trips even more recent GCC, such as 13.1. When `SizeSeq` is empty, `p` is not actually used. Marking it as `ABSL_ATTRIBUTE_UNUSED` silences the GCC warning for that case too. We could disable `Slices` altogether when `SizeSeq` is empty, but that would be a breaking change (even though this API is internal), and possibly hurt generic programming use (they'd have to check if their parameter packs are empty). PiperOrigin-RevId: 616245873 Change-Id: I77f7b0b921dfd63fb01c5223851ad1d8a7da233b
* `layout`: Use auto return type for functions that explicitly instantiate ↵Gravatar Dino Radakovic2024-03-15
| | | | | | | | | | std::tuple in return statements This improves readability by avoiding spelling the same type twice, the first time with even more boilerplate (e.g. `typename`). Return type deduction is a C++14 feature, and Abseil [currently supports](https://github.com/google/oss-policies-info/blob/9a9bfe8a4a12be20757497074fc2f0ecb77438ad/foundational-cxx-support-matrix.md) C++ >= 14. PiperOrigin-RevId: 616218396 Change-Id: I82aeec878dd69001d2cf822db6512f5a62baec02
* Roll back extern template instatiations in swisstable due to binary size ↵Gravatar Evan Brown2024-03-13
| | | | | | | increases in shared libraries. PiperOrigin-RevId: 615497725 Change-Id: Ic29db8923ea4ea7cd0b01b396896fa9fff8c74b0
* Test that rehash(0) reduces capacity to minimum.Gravatar Vitaly Goldshteyn2024-03-13
| | | | | PiperOrigin-RevId: 615380243 Change-Id: I5400b40a6bc5ac52ece5d4fa6da7df9e4ff50855
* Add extern templates for common swisstable types.Gravatar Evan Brown2024-03-12
| | | | | | | | Motivation: mitigate linker input size increase from swisstable optimizations. Note: the changes in raw_hash_set.h are fixing build errors that happened when adding the explicit instantiations. The change in unchecked_deref is because set iterators have const reference access whereas map iterators have mutable reference access and the function is never actually called for sets (it's used in raw_hash_map) so it wasn't needed before. I'm not sure why the soo_slot/soo_iterator problems didn't cause compile errors earlier. PiperOrigin-RevId: 615174043 Change-Id: Iac5eb2332a76e9b70021156fbb2b8def47a5391d
* Make swisstable SOO support GDB pretty printing and still compile in OSS.Gravatar Evan Brown2024-03-12
| | | | | PiperOrigin-RevId: 615131303 Change-Id: I68fcbdd943594983c67f8e07810b05d5fa9a6f2e
* Move GCC uninitialized memory warning suppression into MaybeInitializedPtr.Gravatar Evan Brown2024-03-11
| | | | | PiperOrigin-RevId: 614701769 Change-Id: I7c2143dd467e376eb4936ef894f3413bba681419
* Replace usages of absl::move, absl::forward, and absl::exchange with theirGravatar Derek Mauro2024-03-11
| | | | | | | std:: equivalents PiperOrigin-RevId: 614687225 Change-Id: I07421db08ee9c221e561f42e3bf8345fb5321401
* Avoid MSan: use-of-uninitialized-value error in find_non_soo.Gravatar Evan Brown2024-03-07
| | | | | PiperOrigin-RevId: 613590317 Change-Id: I69f095681102e5492916085ada0eed085a75765b
* Add ABSL_ATTRIBUTE_UNUSED to variables used in an ABSL_ASSUME.Gravatar Evan Brown2024-03-06
| | | | | PiperOrigin-RevId: 613305668 Change-Id: Ifc247f48ea476745eaaf0dd41dbdab8404a6cafb
* Implement small object optimization in swisstable - disabled for now.Gravatar Evan Brown2024-03-06
| | | | | | | | | 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
* Extract `InsertPosition` function to be able to reuse it.Gravatar Vitaly Goldshteyn2024-03-04
| | | | | PiperOrigin-RevId: 612560213 Change-Id: Id75dfd1222a0bed8ec72ce21e4a97b1d09fc9eaa
* PR #1632: inlined_vector: Use trivial relocation for `erase`Gravatar Arthur O'Dwyer2024-03-03
| | | | | | | | | | | | | | | Imported from GitHub PR https://github.com/abseil/abseil-cpp/pull/1632 Prior art for the `vector::erase` optimization: https://github.com/AmadeusITGroup/amc/blob/efcb7be/include/amc/vectorcommon.hpp#L176-L180 https://github.com/bloomberg/bde/blob/e15f05be6/groups/bsl/bslalg/bslalg_arrayprimitives.h#L3787-L3799 https://github.com/facebook/folly/blob/d24bf04/folly/FBVector.h#L1254-L1262 https://github.com/qt/qtbase/blob/fbfee2d/src/corelib/tools/qarraydataops.h#L856-L861 Merge 6ce011079ccf945ae95434ce45ea6c5e3a088af8 into 55d28d4b3b82f9a47b3fa9b811b675a032820621 Merging this change closes #1632 COPYBARA_INTEGRATE_REVIEW=https://github.com/abseil/abseil-cpp/pull/1632 from Quuxplusone:trivial-erase 6ce011079ccf945ae95434ce45ea6c5e3a088af8 PiperOrigin-RevId: 612278964 Change-Id: I327ace8a38292b4610c6be031cc334e77c76fd35
* Create `BM_GroupPortable_Match`.Gravatar Vitaly Goldshteyn2024-03-03
| | | | | PiperOrigin-RevId: 612201313 Change-Id: Ia9e7f146f5e1ecaffcb15de694049b716db38d02
* Rework casting in raw_hash_set's `IsFull()`.Gravatar Paul Rigge2024-02-28
| | | | | | | Instead of casting an int to the enum type where the int does not have an associated enum value, cast the enum to its underlying type. This should be no functional change but make some linters happier. PiperOrigin-RevId: 611172311 Change-Id: I9ae10f8fa2029014236f60a90ee2ab2273c66fa5
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-24 17:36:36 +0000