summaryrefslogtreecommitdiff
path: root/absl/container
Commit message (Collapse)AuthorAge
...
| * 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
* Workaround MSan false positive.Gravatar Abseil Team2023-02-10
| | | | | | | | | On Linux Kernels >= 5.4 MSan reports a false positive when accessing thread local storage data from loaded libraries. This was reported on Chromium (which on some build configurations uses absl as a dynamic library). More info here: crbug.com/1414573. PiperOrigin-RevId: 508645053 Change-Id: I5d5a97e1ee7230cc23f3934a4ec5594b883918b4
* In sanitizer mode, detect when end iterators from different swisstables are ↵Gravatar Evan Brown2023-02-09
| | | | | | | | | compared. We change AssertSameContainer to be after AssertIsValidForComparison calls so that we can have more specific failure messages. PiperOrigin-RevId: 508472485 Change-Id: Iff2f7512086948a4aca7fd403596e8d4fde53b2a
* Fix missing includes/dependenciesGravatar Derek Mauro2023-02-02
| | | | | PiperOrigin-RevId: 506622658 Change-Id: I17ae2d97a6cadb7bdd8ebd0ec0dd3976568cb7e1
* Rollforward: in sanitizer mode, detect when references become invalidated by ↵Gravatar Evan Brown2023-02-01
| | | | | | | | | 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 ↵Gravatar Abseil Team2023-01-31
| | | | | | | | | 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 ↵Gravatar Evan Brown2023-01-30
| | | | | | | rehashing on insertions when there is no reserved growth. PiperOrigin-RevId: 505807487 Change-Id: I9051a04f6a75e579d16e9ae8defd404bcc377fba
* Replace absl::base_internal::Prefetch* calls with absl::Prefetch* callsGravatar Martijn Vels2023-01-27
| | | | | PiperOrigin-RevId: 505184961 Change-Id: I64482558a76abda6896bec4b2d323833b6cd7edf
* Sort CMakeList deps for raw_hash_set and raw_hash_set_test.Gravatar Evan Brown2023-01-23
| | | | | PiperOrigin-RevId: 504045295 Change-Id: I110d4573087358e17a719def29e8037adfac6d15
* Add CodegenAbslRawHashSetStringFindNeEnd function, which is useful because ↵Gravatar Evan Brown2023-01-20
| | | | | | | the find isn't inlined but the iterator comparison is. PiperOrigin-RevId: 503473637 Change-Id: I02b8d95b7a1b738314c4f07a863c7606f822f079
* In sanitizer mode, detect when references become invalidated after reserved ↵Gravatar Evan Brown2023-01-17
| | | | | | | growth runs out. PiperOrigin-RevId: 502625638 Change-Id: I1c06b2162dbdaaa6a36cea503ac6d07cd157b2e2
* In sanitizer mode, detect when invalidated iterators are compared.Gravatar Evan Brown2023-01-05
| | | | | PiperOrigin-RevId: 499964205 Change-Id: I45a1d62a5e093921946e7c3c7ab31480252b330e
* Fix a bug in iterator validation code in which we don't update the table's ↵Gravatar Evan Brown2022-12-22
| | | | | | | reserved growth if the reservation wouldn't grow the table. PiperOrigin-RevId: 497246219 Change-Id: I9671236f56d10851c49de71c21899368be6c3a00
* Update `FixedArray` doc comments to match actual template param namesGravatar Lawrence Wolf-Sonkin2022-12-22
| | | | | | | | | | * The template parameter provided to `FixedArray` for the number of inline elements is named `N` * If left defaulted, which is recommended, `FixedArray` chooses the number of inline elements by itself * The `inline_elements` static class member contains the actual number of inlinable elements * Previously the docs referred to the template parameter as `inline_elements` instead of `N`. PiperOrigin-RevId: 497185546 Change-Id: I321092826d956704c0074062d2a7b924b28e36d0
* Restrict visibility of absl/container:hash_function_defaults.Gravatar Chris Kennelly2022-12-19
| | | | | PiperOrigin-RevId: 496514638 Change-Id: I45b8dfe01c83915c460711339d2d8c38604c8d81
* In sanitizer mode, add generations to swisstable iterators and backing ↵Gravatar Evan Brown2022-12-19
| | | | | | | arrays so that we can detect invalid iterator use. PiperOrigin-RevId: 496455788 Change-Id: I83df92828098a3ef1181b4e454f3ac5d3ac7a2f2
* Optimize raw_hash_set CountLeadingEmptyOrDeleted() on ArmGravatar Connal de Souza2022-12-19
| | | | | | | | 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
* Fix some ClangTidy warnings in raw_hash_set code.Gravatar Evan Brown2022-12-08
| | | | | PiperOrigin-RevId: 493993005 Change-Id: I0705be8678022a9e08a1af9972687b7955593994
* Change CommonFields from a private base class of raw_hash_set to be the ↵Gravatar Evan Brown2022-12-08
| | | | | | | | | | | first member of the settings_ CompressedTuple so that we can move growth_left into CommonFields. This allows for removing growth_left as a separate argument for a few functions. Also, move the infoz() accessor functions to be before the data members of CommonFields to comply with the style guide. PiperOrigin-RevId: 493918310 Change-Id: I58474e37d3b16a1513d2931af6b153dea1d809c2
* Add a compilation test for recursive hash map typesGravatar Derek Mauro2022-12-02
| | | | | PiperOrigin-RevId: 492535520 Change-Id: I2e58b39bd4ab3064f675474c5e712c76fac02674
* Move the vtable into a function to delay instantiation until the function isGravatar Samuel Benzaquen2022-12-01
| | | | | | | | | | | | | called. When the variable is a global the compiler is allowed to instantiate it more aggresively and it might happen before the types involved are complete. When it is inside a function the compiler can't instantiate it until after the functions are called. Remove an unused member from the vtable. Replace transfer_slot_fn with a generic function when relocation is available to reduce duplication. PiperOrigin-RevId: 492227302 Change-Id: I07499f63b91c59c0ae42402683387c7b84a6f0ee
* Reduce flat_hash_{set,map} generated code size.Gravatar Abseil Team2022-11-28
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This CL makes a bunch of changes (mostly to raw_hash_set which underlies flat_hash_set and flat_hash_map). Techniques used: * Extract code that does not depend on the specific hash table type into common (non-inlined) functions. * Place ABSL_ATTRIBUTE_NOINLINE directives judiciously. * Out-of-line some slow paths. Reduces sizes of some large binaries by ~0.5%. Has no significant performance impact on a few performance critical binaries. ## Speed of fleetbench micro-benchmarks Following is a histogram of %-age changes in [fleetbench](https://github.com/google/fleetbench) hot_swissmap_benchmark results. Negative numbers indicate a speedup caused by this change. Statistically insignificant changes are mapped to zero. XXX Also run and merge in cold_swissmap_benchmark Across all 351 benchmarks, the average speedup is 0.38%. The best speedup was -25%, worst slowdown was +6.81%. ``` Count: 351 Average: -0.382764 StdDev: 3.77807 Min: -25 Median: 0.435135 Max: 6.81 --------------------------------------------- [ -25, -10) 16 4.558% 4.558% # [ -9, -8) 2 0.570% 5.128% [ -8, -7) 1 0.285% 5.413% [ -7, -6) 1 0.285% 5.698% [ -6, -5) 2 0.570% 6.268% [ -5, -4) 5 1.425% 7.692% [ -4, -3) 13 3.704% 11.396% # [ -3, -2) 15 4.274% 15.670% # [ -2, -1) 26 7.407% 23.077% ## [ -1, 0) 14 3.989% 27.066% # [ 0, 1) 185 52.707% 79.772% ############ [ 1, 2) 14 3.989% 83.761% # [ 2, 3) 8 2.279% 86.040% # [ 3, 4) 7 1.994% 88.034% [ 4, 5) 32 9.117% 97.151% ## [ 5, 6) 6 1.709% 98.860% [ 6, 7) 4 1.140% 100.000% ``` We looked at the slowdowns and they do not seem worth worrying about. E.g., the worst one was: ``` BM_FindHit_Hot<::absl::node_hash_set,64>/set_size:4096/density:0 2.61ns ± 1% 2.79ns ± 1% +6.81% (p=0.008 n=5+5) ``` ## Detailed changes * Out-of-line slow paths in hash table sampler methods. * Explicitly unregister from sampler instead of from destructor. * Introduced a non-templated CommonFields struct that holds some of the hash table fields (infoz, ctrl, slots, size, capacity). This struct can be passed to new non-templated helpers. The struct is a private base class of raw_hash_set. * Made non-inlined InitializeSlots<> that is only templated on allocator and size/alignment of the slot type so that we can share instantiations across types that have the same size/alignment. * Moved some infrequently called code paths into non-inlined type-erased. functions. Pass a suite of type-specific function pointers to these routines for when they need to operate on slots. * Marked some methods as non-inlined. * Avoid unnecessary reinitialization in destructor. * Introduce UpdateSpine type-erased helper that is called from clear() and rehash(). PiperOrigin-RevId: 491413386 Change-Id: Ia5495c5a6ec73622a785a0d260e406ddb9085a7c
* Refactor btree iterator generation code into a base class rather than using ↵Gravatar Evan Brown2022-11-22
| | | | | | | ifdefs inside btree_iterator. PiperOrigin-RevId: 490317784 Change-Id: I4ffe2a1ad2e39890790e278d82eec7223b67908c
* Improve error messages when comparing btree iterators when generations are ↵Gravatar Evan Brown2022-11-21
| | | | | | | | | | enabled. - Add assertions that the iterators haven't been invalidated. - Also refactor some generation-related code to define the functions inside ABSL_BTREE_ENABLE_GENERATIONS ifdef/else branches. PiperOrigin-RevId: 489988637 Change-Id: I34d32ed2e27cf89f7f8bb5d9c1f6770bb40b8794
* Add a new API for `extract_and_get_next()` in b-tree that returns both the ↵Gravatar Evan Brown2022-11-15
| | | | | | | | extracted node and an iterator to the next element in the container. Motivation: it can be useful, when calling `extract` to maintain an iterator next to the location of the extracted element. `std::set`, et al. allow for this because they have iterator stability. `absl::{flat,node}_hash_{set,map}` allow for this because they are guaranteed not to rehash when elements are removed so they also have iterator stability across calls to `extract()`. But b-tree doesn't support this use case without this API because removing elements can cause rebalancing, which invalidates iterators. We can get the next iterator without this API using `lower_bound(node_handle.value())`, but that requires an extra lookup. PiperOrigin-RevId: 488721247 Change-Id: Id66f17311bf53678f536e4e4f070775f5ce0c542
* Stop unnecessary clearing of fields in ~raw_hash_set.Gravatar Abseil Team2022-11-11
| | | | | | | | | | | Previously, ~raw_hash_set() would change *this to have the same representation as an empty hash table. This is unnecessary since nobody should be touching a destroyed hash table, and prevents future optimizations/changes that might not be able to preserve this behavior. PiperOrigin-RevId: 487899950 Change-Id: I2d4470677bdd411c2e48ef511187e39f4e7fc2f4
* Improve error messages when comparing btree iterators.Gravatar Evan Brown2022-11-10
| | | | | | | | - Add assertions that the iterators are either (a) from the same container or (b) both default constructed. Standard says: "The domain of == for forward iterators is that of iterators over the same underlying sequence. However, value-initialized iterators may be compared and shall compare equal to other value-initialized iterators of the same type." - [reference](https://eel.is/c++draft/forward.iterators#2). - Also optimize IsEndIterator a bit. PiperOrigin-RevId: 487617518 Change-Id: Iefba5c3bc8caa93954671793e6929e22f419c298
* Improve error messages when comparing swisstable iterators.Gravatar Evan Brown2022-11-09
| | | | | | | We check for comparisons of swisstable iterators from different heap allocations, which can indicate either iterators from different containers or that there was a rehash between when the iterators were initialized. PiperOrigin-RevId: 487304602 Change-Id: I5c596c5ea07948d66e048f99937f9032a630344f
* Auto increase inlined capacity whenever it does not affect class' size.Gravatar Abseil Team2022-11-09
| | | | | PiperOrigin-RevId: 487292771 Change-Id: I2454e28fe91017fb2954a4ad194712fcafe893d2
* Fix some invalid iterator bugs in btree_test.cc for multi{set,map} ↵Gravatar Evan Brown2022-11-07
| | | | | | | | | | | | | emplace{_hint} tests. Note that multi{set,map}::emplace doesn't specify in which order the new element is inserted if there are equivalent keys in the table, whereas emplace_hint specifies that the new element must be before the hint if possible. https://en.cppreference.com/w/cpp/container/multiset/emplace https://en.cppreference.com/w/cpp/container/multiset/emplace_hint Also refactor to rely on IsAssertEnabled instead of checking for NDEBUG. PiperOrigin-RevId: 486733450 Change-Id: Ie90d33c584a6caccd8301ad6fc0396234dbbfac4
* Merge pull request #1287 from GOGOYAO:patch-1Gravatar Copybara-Service2022-11-03
|\ | | | | | | | | PiperOrigin-RevId: 485886212 Change-Id: Ic7a710913f8376d07b9bdeb987d007ec04e48465
* | Improve error messages when dereferencing invalid swisstable iterators.Gravatar Evan Brown2022-11-01
| | | | | | | | | | | | | | | | | | - Separate the failure cases into different assertions: end/default constructed vs rehashed or erased. - Update the assertion error for AssertIsValid to not mention the end iterator case because end iterators are considered valid by AssertIsValid. - Also fix an out-of-date comment for skip_empty_or_deleted. PiperOrigin-RevId: 485402559 Change-Id: I593056abdc6c3565d0396fb885923fef643bf4e4
* | Add a warning about extract invalidating iterators (not just the iterator of ↵Gravatar Abseil Team2022-10-31
| | | | | | | | | | | | | | the element being extracted). PiperOrigin-RevId: 485120182 Change-Id: Ic54d538721678bed0a748dacbf33c319e62b93b8
* | `absl::InlinedVector::swap` supports non-assignable types.Gravatar Abseil Team2022-10-25
| | | | | | | | | | PiperOrigin-RevId: 483752526 Change-Id: Ie6b63a4a3cc7593e5b8bf255ba571a77d609ce04
* | Improve b-tree error messages when dereferencing invalid iterators.Gravatar Evan Brown2022-10-25
| | | | | | | | | | | | | | | | - Check for invalid generation before checking for other types of invalid iterators. - Check specifically for dereferencing end() iterators. PiperOrigin-RevId: 483725646 Change-Id: Ibca19c48b1b242384683580145be8fb9ae707bc8
* | Use btree iterator subtraction instead of std::distance in erase_range() and ↵Gravatar Evan Brown2022-10-18
| | | | | | | | | | | | | | count(). PiperOrigin-RevId: 481979737 Change-Id: I69f53665b0463a7d8d80f2a3feedfdd95d32b012
* | Implement btree_iterator::operator-, which is faster than std::distance for ↵Gravatar Evan Brown2022-10-17
| | | | | | | | | | | | | | | | btree iterators. Note: btree_iterator::operator- is still O(N) because in the worst case (end()-begin()), we will have at least one operation per node in the tree, and there are at least N/M nodes, where M (a constant) is the maximum number of values per node. PiperOrigin-RevId: 481716874 Change-Id: Ic0225b7509208ed96b75a2dc626d2aa4a24f4946
* | `absl::InlinedVector` supports move assignment with non-assignable types.Gravatar Abseil Team2022-10-12
| | | | | | | | | | PiperOrigin-RevId: 480601268 Change-Id: I5a639da57b79ae600387c81e662d5c1542b2bf99
* | Add static_cast<void*> to the sources for trivial relocations to avoid ↵Gravatar Evan Brown2022-10-07
| | | | | | | | | | | | | | spurious -Wdynamic-class-memaccess errors in the presence of other compilation errors. PiperOrigin-RevId: 479625866 Change-Id: Ia10ad35a2f58ffb3f36f996d357d5e126b181e1c
* | Eliminate use of internal interfacesGravatar Gennadiy Rozental2022-10-06
| | | | | | | | | | PiperOrigin-RevId: 479325483 Change-Id: I9c4384173ce996818e0cf749c0fc465d6e9aaf8c
* | No changes in OSS.Gravatar Gennadiy Rozental2022-10-04
| | | | | | | | | | PiperOrigin-RevId: 478869244 Change-Id: Id16eb1e5036e95a5e2a990a647f1f7090129a009
| * Initialize `Allocation` to eliminate compile errorGravatar GOGOYAO2022-10-04
|/ | | | | | Class `Allocation` is not initialized and I will get a compile error like this. ``` error: ‘worklist.absl::lts_20220623::InlinedVector<absl::lts_20220623::cord_internal::CordRep*, 2, std::allocator<absl::lts_20220623::cord_internal::CordRep*> >::storage_.absl::lts_20220623::inlined_vector_internal::Storage<absl::lts_20220623::cord_internal::CordRep*, 2, std::allocator<absl::lts_20220623::cord_internal::CordRep*> >::data_.absl::lts_20220623::inlined_vector_internal::Storage<absl::lts_20220623::cord_internal::CordRep*, 2, std::allocator<absl::lts_20220623::cord_internal::CordRep*> >::Data::allocated.absl::lts_20220623::inlined_vector_internal::Storage<absl::lts_20220623::cord_internal::CordRep*, 2, std::allocator<absl::lts_20220623::cord_internal::CordRep*> >::Allocated::allocated_capacity’ may be used uninitialized [-Werror=maybe-uninitialized] ```
* Use trivial relocation for transfers in swisstable and b-tree.Gravatar Evan Brown2022-10-03
| | | | | PiperOrigin-RevId: 478547898 Change-Id: Ie20cd0a49df042be912888ee238333a5f5fa0404
* Add common_policy_traits - a subset of hash_policy_traits that can be shared ↵Gravatar Evan Brown2022-09-28
| | | | | | | | | | between raw_hash_set and btree. Also remove the transfer implementations from btree_set.h and flat_hash_set.h, which are equivalent to the default implementations. Motivation: this will simplify upcoming changes related to trivial relocation. PiperOrigin-RevId: 477493403 Change-Id: I75babef4c93dec3a8105f86c58af54199bb1ec9c
* Fix -Wimplicit-int-conversion and -Wsign-conversion warnings in btree.Gravatar Abseil Team2022-09-26
| | | | | | | | | | | Certain core libraries in Chrome build with these warnings [1]; btree_map and btree_set cannot be used in those libraries until these warnings are fixed. [1] https://crbug.com/1292951 PiperOrigin-RevId: 476908396 Change-Id: I32e9ea1eec911e329d6ff00f04fa2e9cfde8660a
* Add sparse and string copy constructor benchmarks for hash table.Gravatar Abseil Team2022-09-20
| | | | | PiperOrigin-RevId: 475601161 Change-Id: I3f67a1597ddfa6de60f19fe4b38d44fbc5630bd8
* Make BTrees work with custom allocators that recycle memory.Gravatar Abseil Team2022-09-19
| | | | | | | | | | | | The btree data structure poisons regions of memory it's not using. It leaves these regions poisoned when it frees memory. This means that a custom memory allocator that tries to reuse freed memory will trigger an ASAN use-after-poison error. The fix is to unpoison each memory region right before freeing it. PiperOrigin-RevId: 475309671 Change-Id: I29d55c298d3d89a83e1f960deb6e93118891ff83
* Add more options for `BM_iteration` in order to see better picture for ↵Gravatar Abseil Team2022-09-14
| | | | | | | | | | | | | | | | | | | | | | | | | | | choosing trade off for iteration optimizations. ``` BM_Iteration/1/1 1.83ns ± 0% BM_Iteration/2/2 2.63ns ±11% BM_Iteration/4/4 5.76ns ±26% BM_Iteration/7/7 3.79ns ± 0% BM_Iteration/10/10 8.49ns ±23% BM_Iteration/15/15 18.2ns ±30% BM_Iteration/16/16 21.2ns ±29% BM_Iteration/54/54 37.2ns ±21% BM_Iteration/100/100 74.7ns ±13% BM_Iteration/400/400 330ns ± 8% BM_Iteration/0/0 0.46ns ± 2% BM_Iteration/10/0 1.26ns ± 1% BM_Iteration/100/0 13.4ns ± 0% BM_Iteration/1000/0 417ns ± 0% BM_Iteration/10000/0 3.30µs ± 0% BM_Iteration/100/1 16.0ns ±12% BM_Iteration/1000/10 453ns ± 5% ``` PiperOrigin-RevId: 474282700 Change-Id: I4b3fcb80292147aa4a8f542ae5c7fc1e8bd5f05b
* Change `EndComparison` benchmark to not measure iteration. Also added ↵Gravatar Abseil Team2022-09-13
| | | | | | | | | | | | | | | | | | `BM_Iteration` separately. ``` BM_EndComparison 0.46ns ± 0% BM_Iteration/10/10 8.09ns ± 7% BM_Iteration/20/20 18.6ns ±16% BM_Iteration/100/100 79.0ns ±15% BM_Iteration/400/400 344ns ± 5% BM_Iteration/100/1 16.6ns ± 1% BM_Iteration/1000/10 454ns ± 3% ``` PiperOrigin-RevId: 474211728 Change-Id: I9bd799a4be3247ca8f2a2144b6e857db8c99c81f
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-08 11:14:15 +0000