aboutsummaryrefslogtreecommitdiff
path: root/absl/container
Commit message (Collapse)AuthorAgeFilesLines
* Optimize GrowIntoSingleGroupShuffleControlBytes.Connal de Souza2024-05-281-50/+100
| | | | | | | 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().Paul Rigge2024-05-221-1/+6
| | | | | PiperOrigin-RevId: 636218177 Change-Id: I9f58ccbb468fcc0c44ef12162415f7b721a745bf
* Move `prepare_insert` out of the line as type erased `PrepareInsertNonSoo`.Vitaly Goldshteyn2024-05-204-161/+295
| | | | | | | | | 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
* Add public aliases for default hash/eq types in hash-based containersDennis Kormalev2024-04-247-28/+92
| | | | | | | | | | | | | | | Generic user code sometimes wants to provide more flexibility for its own users and provide type arguments that are used as Hash/Eq in underlying containers. However, there is no sensible publicly available default value for it yet. This CL fixes this issue and provides publicly visible aliases that such user code can use. PiperOrigin-RevId: 627844757 Change-Id: I4c393007244ad8d998da02883c623eae1715c0df
* [absl] Re-use the existing `std::type_identity` backfill instead of ↵Lawrence Wolf-Sonkin2024-04-183-11/+4
| | | | | | | | | 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.Vitaly Goldshteyn2024-04-021-2/+6
| | | | | PiperOrigin-RevId: 621258501 Change-Id: Id094f3f0d0bc4a9fa8f3d1f90cfcd4c53beeb776
* Roll forward: enable small object optimization in swisstable.Evan Brown2024-03-281-2/+2
| | | | | PiperOrigin-RevId: 619984581 Change-Id: I68fc9d6e9dd447bdccdbfd270073e11865f85965
* Optimize InsertMiss for tables without kDeleted slots.Vitaly Goldshteyn2024-03-271-32/+72
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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.Vitaly Goldshteyn2024-03-273-25/+52
| | | | | PiperOrigin-RevId: 619649335 Change-Id: I8b3380816418a363fb6686db7966248cb530c491
* Disable small object optimization while debugging some failing tests.Evan Brown2024-03-271-2/+2
| | | | | PiperOrigin-RevId: 619598530 Change-Id: Ie4b808a3b826db8c271c81914c7a88d2c6216eb2
* Introduce GrowthInfo with tests, but without usage.Vitaly Goldshteyn2024-03-262-0/+154
| | | | | | | 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.Evan Brown2024-03-261-2/+2
| | | | | | | 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.Evan Brown2024-03-261-36/+52
| | | | | | Motivation: there are new uninitialized memory warnings when we enable small object optimization. PiperOrigin-RevId: 619295212 Change-Id: If10762bab0e43c9619fc03f6d1eef5b8836bbf9a
* Respect `NDEBUG_SANITIZER`Abseil Team2024-03-262-6/+8
| | | | | | | | | | | | | | | | | | | | | 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.Vitaly Goldshteyn2024-03-252-0/+61
| | | | | PiperOrigin-RevId: 618970135 Change-Id: Ifb9d0b425904d5cb37d80ec28ab7845957209313
* Record sizeof(key_type), sizeof(value_type) in hashtable profiles.Chris Kennelly2024-03-255-23/+117
| | | | | | | | This can identify situations where flat_hash_* is suboptimal for large elements. PiperOrigin-RevId: 618937993 Change-Id: I2bde069bc3526b14ad1718ba6f50467002aeed16
* Fix ClangTidy warnings in btree.h.Evan Brown2024-03-253-6/+5
| | | | | PiperOrigin-RevId: 618872032 Change-Id: I9fdfadff906494eb64cee976c02a1fff57923c79
* Use Layout::WithStaticSizes in btree.Evan Brown2024-03-211-21/+14
| | | | | PiperOrigin-RevId: 617877687 Change-Id: I29c52f9288f099255c4adb7c1f9fa8831ac55b05
* `layout`: Delete outdated comments about ElementType alias not being used ↵Dino Radakovic2024-03-211-6/+0
| | | | | | | | | 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 MyAlignDino Radakovic2024-03-201-2/+1
| | | | | PiperOrigin-RevId: 617573381 Change-Id: I0ddab2ab7cf68651424b3cf385b484d27106dd59
* Do hashtablez sampling on the first insertion into an empty SOO hashtable.Evan Brown2024-03-197-92/+348
| | | | | | | | | 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.Evan Brown2024-03-181-2/+2
| | | | | | | 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.Evan Brown2024-03-181-2/+2
| | | | | PiperOrigin-RevId: 616895950 Change-Id: I9dc9099e779df4b692496aa5ee5573ef0e7fd826
* Add a feature to container_internal::Layout that lets you specify some array ↵Abseil Team2024-03-183-66/+753
| | | | | | | | | 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 ↵Dino Radakovic2024-03-151-4/+5
| | | | | | | | | | | | | | 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 ↵Dino Radakovic2024-03-151-6/+2
| | | | | | | | | | 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 ↵Evan Brown2024-03-1311-341/+7
| | | | | | | increases in shared libraries. PiperOrigin-RevId: 615497725 Change-Id: Ic29db8923ea4ea7cd0b01b396896fa9fff8c74b0
* Test that rehash(0) reduces capacity to minimum.Vitaly Goldshteyn2024-03-131-1/+6
| | | | | PiperOrigin-RevId: 615380243 Change-Id: I5400b40a6bc5ac52ece5d4fa6da7df9e4ff50855
* Add extern templates for common swisstable types.Evan Brown2024-03-1211-7/+341
| | | | | | | | 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.Evan Brown2024-03-121-8/+3
| | | | | PiperOrigin-RevId: 615131303 Change-Id: I68fcbdd943594983c67f8e07810b05d5fa9a6f2e
* Move GCC uninitialized memory warning suppression into MaybeInitializedPtr.Evan Brown2024-03-111-16/+21
| | | | | PiperOrigin-RevId: 614701769 Change-Id: I7c2143dd467e376eb4936ef894f3413bba681419
* Replace usages of absl::move, absl::forward, and absl::exchange with theirDerek Mauro2024-03-114-15/+15
| | | | | | | std:: equivalents PiperOrigin-RevId: 614687225 Change-Id: I07421db08ee9c221e561f42e3bf8345fb5321401
* Avoid MSan: use-of-uninitialized-value error in find_non_soo.Evan Brown2024-03-071-2/+1
| | | | | PiperOrigin-RevId: 613590317 Change-Id: I69f095681102e5492916085ada0eed085a75765b
* Add ABSL_ATTRIBUTE_UNUSED to variables used in an ABSL_ASSUME.Evan Brown2024-03-061-2/+2
| | | | | PiperOrigin-RevId: 613305668 Change-Id: Ifc247f48ea476745eaaf0dd41dbdab8404a6cafb
* Implement small object optimization in swisstable - disabled for now.Evan Brown2024-03-066-371/+1091
| | | | | | | | | 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.Vitaly Goldshteyn2024-03-042-13/+27
| | | | | PiperOrigin-RevId: 612560213 Change-Id: Id75dfd1222a0bed8ec72ce21e4a97b1d09fc9eaa
* PR #1632: inlined_vector: Use trivial relocation for `erase`Arthur O'Dwyer2024-03-033-8/+86
| | | | | | | | | | | | | | | 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`.Vitaly Goldshteyn2024-03-031-0/+13
| | | | | PiperOrigin-RevId: 612201313 Change-Id: Ia9e7f146f5e1ecaffcb15de694049b716db38d02
* Rework casting in raw_hash_set's `IsFull()`.Paul Rigge2024-02-281-1/+3
| | | | | | | 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
* Add braces for conditional statements in raw_hash_map functions.Evan Brown2024-02-231-3/+5
| | | | | | | The current version violates the Google C++ style guide - see https://google.github.io/styleguide/cppguide.html#Formatting_Looping_Branching. This code does not fit into the historical exception that "the curly braces for the controlled statement or the line breaks inside the curly braces may be omitted if as a result the entire statement appears on either a single line (in which case there is a space between the closing parenthesis and the controlled statement) or on two lines (in which case there is a line break after the closing parenthesis and there are no braces)." PiperOrigin-RevId: 609789188 Change-Id: Id7ae9596e454dac5581d19939564c07670077f92
* Optimize `prepare_insert`, when resize happens. It removes single ↵Vitaly Goldshteyn2024-02-221-11/+13
| | | | | | | unnecessary probing before resize that is beneficial for small tables the most. PiperOrigin-RevId: 609547787 Change-Id: If6584919b4c93945ea078b1c1a9f57b355dce924
* Change find_or_prepare_insert to return std::pair<iterator, bool> to match ↵Evan Brown2024-02-212-22/+21
| | | | | | | return type of insert. PiperOrigin-RevId: 609058024 Change-Id: I2f7cc2daf862e7e2d23acd6dd3fe85cb1945d5f0
* PR #1618: inlined_vector: Use trivial relocation for `SwapInlinedElements`Arthur O'Dwyer2024-02-212-17/+47
| | | | | | | | | | | | | | Imported from GitHub PR https://github.com/abseil/abseil-cpp/pull/1618 I noticed while working on #1615 that `inlined_vector` could use the trivial relocatability trait here, too. Here the memcpy codepath already exists; we just have to opt in to using it. Merge 567a1dd9b6b3352f649e900b24834b59e39cfa14 into a7012a5bfcf26a41b9dd32d4c429004773503dd6 Merging this change closes #1618 COPYBARA_INTEGRATE_REVIEW=https://github.com/abseil/abseil-cpp/pull/1618 from Quuxplusone:trivial-swap 567a1dd9b6b3352f649e900b24834b59e39cfa14 PiperOrigin-RevId: 609019296 Change-Id: I4055ab790245752179e405b490fcd479e7389726
* Improve raw_hash_set tests.Abseil Team2024-02-211-14/+29
| | | | | PiperOrigin-RevId: 608947694 Change-Id: Ie53a91c4d78dcb80c57227616b488ec64b23c588
* Use const_cast to avoid duplicating the implementation of ↵Evan Brown2024-02-201-2/+1
| | | | | | | | raw_hash_set::find(key). Motivation: the implementation becomes more complicated with small object optimization. PiperOrigin-RevId: 608742838 Change-Id: I55fc42321b1967f9c7bbee49817a2f2d4ee44b56
* Introduce `Group::MaskNonFull` without usage.Abseil Team2024-02-153-0/+68
| | | | | | | | 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
* Make `begin()` to return `end()` on empty tables.Abseil Team2024-02-081-5/+6
| | | | | PiperOrigin-RevId: 605460827 Change-Id: I57007a7ad18829e7bfed27ba65871afbd227d012
* Switch rank structs to be consistent with written guidance in ↵Matt Kulukundis2024-02-071-9/+10
| | | | | | | go/ranked-overloads PiperOrigin-RevId: 605125821 Change-Id: I2ee260eaf283acafd80abfd2b7419a0e9f597a78
* Avoid hash computation and `Group::Match` in small tables copy and use ↵Abseil Team2024-02-072-22/+102
| | | | | | | `IterateOverFullSlots` for iterating for all tables. PiperOrigin-RevId: 605116090 Change-Id: Ia65c664421f7630225b00f1c45c636b4681121ce
* Add absl_container_hash-based HashEq specializationDennis Kormalev2024-02-078-6/+270
| | | | | | | | | | | | | | SwissTable provides support for heterogeneous lookup in associative containers through transparent Hash and Eq types. However, it is not possible for user types to provide additional specializations to allow their types to use this functionality. This CL brings ability for user types to specify their own transparent absl_container_hash and (optionally) absl_container_eq inner types to achieve the same functionality. PiperOrigin-RevId: 604994859 Change-Id: I302486d292c9a18b7d4c77033227008f5539e354
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-15 10:11:06 +0000