summaryrefslogtreecommitdiff
path: root/absl/container/internal
Commit message (Collapse)AuthorAge
* inlined_vector: get rid of IsMemcpyOk.Gravatar Abseil Team2023-03-24
| | | | | | | | | | | | | | This type trait had no precise definition, and indeed not even any documentation at all. Giving the ill-defined concept a name was harmful, because it obscured several places where the concept was used too conservatively, or even flat-out incorrectly. This CL has no behavior change: it simply expands IsMemcpyOk to the same conditions it previously had. It leaves TODOs for each place where this was too conservative or incorrect. PiperOrigin-RevId: 519278325 Change-Id: I25bc89f299f6e40b5c3bce7370ed90f33a95612f
* Use multiple empty generations so that we can detect when iterators from ↵Gravatar Evan Brown2023-03-02
| | | | | | | different empty hashtables are compared. PiperOrigin-RevId: 513568915 Change-Id: I3f387d0bae0e86749dff540e4fdd5037304ac975
* Optimize ConvertSpecialToEmptyAndFullToDeleted on ArmGravatar Connal de Souza2023-02-23
| | | | | | | 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:workaroundGravatar Copybara-Service2023-02-22
|\ | | | | | | | | PiperOrigin-RevId: 511695308 Change-Id: I502cdc75e993582eaca5cd91ed068238936a9640
* | Refactor swisstable iterator debug messages code. The motivations are (a) ↵Gravatar Evan Brown2023-02-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
| * 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
* 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
* 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
* 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
* 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
* | `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
* | 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
* Apply clang-format to btree.h.Gravatar Evan Brown2022-09-13
| | | | | PiperOrigin-RevId: 474060540 Change-Id: Ie0f24dfa6ec724eaa9eca82de5f73bbd8d622e38
* Fix "unsafe narrowing" warnings in absl, 8/n.Gravatar Abseil Team2022-09-12
| | | | | | | | | | | | | | | Addresses failures with the following, in some files: -Wshorten-64-to-32 -Wimplicit-int-conversion -Wsign-compare -Wsign-conversion -Wtautological-unsigned-zero-compare (This specific CL focuses on .cc files in */internal/.) Bug: chromium:1292951 PiperOrigin-RevId: 473868797 Change-Id: Ibe0b76e33f9e001d59862beaac54fb47bacd39b2
generated by cgit v1.2.3 (git 2.39.1) at 2024-10-08 11:26:53 +0000