summaryrefslogtreecommitdiff
path: root/absl/container/internal
Commit message (Collapse)AuthorAge
* Clarify that lazy_emplace returns an iterator to the new element when lookup ↵Gravatar Abseil Team2023-07-05
| | | | | | | fails. PiperOrigin-RevId: 545683736 Change-Id: Ic0abec5037e160898e2f24de1b1489caff7d06fd
* roll forward: Make data members of CommonFields be private so that it's ↵Gravatar Evan Brown2023-06-30
| | | | | | | easier to change how we store this information internally. PiperOrigin-RevId: 544732832 Change-Id: I0c9a30f18edc71b3c7fffe94e2002ff6c52050f8
* rollback: Make data members of CommonFields be private so that it's easier ↵Gravatar Evan Brown2023-06-30
| | | | | | | to change how we store this information internally. PiperOrigin-RevId: 544718317 Change-Id: I0ff3e4df7e810be9f7c5db4328995e172eb704a5
* Make data members of CommonFields be private so that it's easier to change ↵Gravatar Evan Brown2023-06-30
| | | | | | | how we store this information internally. PiperOrigin-RevId: 544667586 Change-Id: I9b1943ca71ea1c1f8699832422cd7bc095ac8b2d
* Fix typoGravatar Abseil Team2023-06-29
| | | | | PiperOrigin-RevId: 544401753 Change-Id: Ie5bb48bb46c8c1bf41ef902242cefefd739e7c37
* Use std::is_final instead of a non-portable implementationGravatar Derek Mauro2023-06-16
| | | | | PiperOrigin-RevId: 540928490 Change-Id: Idf022b28ce101a948be4efd5336888a66f5eacf9
* Convert `raw_hash_set` comments from imperative to indicative mood.Gravatar Bradley C. Kuszmaul2023-05-31
| | | | https://google.github.io/styleguide/cppguide.html#Function_Comments
* Merge pull request #1462 from kuszmaul:fix-typoGravatar Copybara-Service2023-05-31
|\ | | | | | | | | PiperOrigin-RevId: 536785792 Change-Id: I2963dea81a75b01b7275d784f6a2908816d0c7bf
| * Typo gardeningGravatar Bradley C. Kuszmaul2023-05-30
| |
* | Migrate most RAW_LOGs and RAW_CHECKs in tests to regular LOG and CHECK.Gravatar Andy Getzendanner2023-05-23
|/ | | | | | | | | | | 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
* Add tests for btrees in which slot_type is overaligned and slot_type is ↵Gravatar Evan Brown2023-05-04
| | | | | | | | | equal to field_type. Also do some minor refactoring in btree.h. PiperOrigin-RevId: 529460378 Change-Id: I278833ada93bbb7652e149fceed08ce3485e4312
* Add lifetimebound attribute to more Abseil container methods and remove them ↵Gravatar Abseil Team2023-05-04
| | | | | | | from internal ones. PiperOrigin-RevId: 529423722 Change-Id: Ib1cc427299100956c0f2ae6cb5214467ef5a3790
* Add lifetimebound attribute to some Abseil containersGravatar Abseil Team2023-05-03
| | | | | PiperOrigin-RevId: 529119690 Change-Id: If585274c409e2a344c8d60759da6f8f990023d29
* Add pointer-stability validation in btree.Gravatar Evan Brown2023-05-02
| | | | | | | When we insert a new element, when ASan is enabled, we replace the node that the new element is on in order to try to detect cases of code depending on pointer/reference-stability. PiperOrigin-RevId: 528826645 Change-Id: Ie5c15c13016a8aa831a0d1edc3ad33c1f5ca4d65
* Merge pull request #1434 from Vertexwahn:fix-spellingGravatar Copybara-Service2023-04-25
|\ | | | | | | | | PiperOrigin-RevId: 527066823 Change-Id: Ifa1e9a43c7490b34f9f4dbfa12d3acbed6b49777
| * Fix some spelling mistakesGravatar Vertexwahn2023-04-24
|/
* Minor optimization in btree: avoid redundant stores to node->position when ↵Gravatar Evan Brown2023-04-20
| | | | | | | constructing nodes. PiperOrigin-RevId: 525792213 Change-Id: I4386385e6e05d74a4ccc18cea505530e919f0e28
* In debug mode, detect cases of btree comparators that violate transitivity, ↵Gravatar Evan Brown2023-04-12
| | | | | | | | | i.e. comp(A,B) && comp(B,C) -> comp(A,C). When inserting a new element, we verify that the key is ordered correctly with respect to all the other values on the node, which can be done in constant time. PiperOrigin-RevId: 523729309 Change-Id: Idb5a5912a9aa5411d086cb9fa76791523046778a
* Replace absl::type_traits_internal::is_trivially_copyable withGravatar Derek Mauro2023-04-12
| | | | | | | std::is_trivially_copyable PiperOrigin-RevId: 523724345 Change-Id: Id68c79c3bbb253d892bdef4659ac8a926e023d12
* inlined_vector: fix incorrect restrictions on the copy constructor fast path.Gravatar Aaron Jacobs2023-04-11
| | | | | | | This has nothing to do with copy assignment or with destruction. PiperOrigin-RevId: 523576913 Change-Id: Iddb6ab73bcfd8b01a29880cdf4db4bc2b5aead8a
* inlined_vector: fix incorrect restrictions on the swap fast path.Gravatar Aaron Jacobs2023-04-11
| | | | | | | This has nothing to do with copy construction or copy assignment. PiperOrigin-RevId: 523571907 Change-Id: I338b5a40616594406ca8c80b747540c8935798e9
* inlined_vector: fix incorrect restrictions on the move-assignment fast path.Gravatar Aaron Jacobs2023-04-11
| | | | | | | This has nothing to do with copy construction or copy assignment. PiperOrigin-RevId: 523557887 Change-Id: I332d6ceaf738305157605f1271cb577a83d198c5
* inlined_vector: relax the requirements on the move-construction fast path.Gravatar Aaron Jacobs2023-04-11
| | | | | | | | | Don't require a trivial move constructor and trivial destructor. This excludes types that have declared themselves trivially relocatable by another means, like std::unique_ptr. Instead use "is trivially relocatable" directly, which includes all previous types as well as those that have opted in. PiperOrigin-RevId: 523557136 Change-Id: Icea2dbb8f36f99623308155f2e5b1edd8e5bd36b
* Add heterogeneous lookup support for wstring/u16string/u32string.Gravatar Abseil Team2023-04-03
| | | | | PiperOrigin-RevId: 521556211 Change-Id: I1e1812eb11bfc5772abbf38ce348580c3afa5612
* inlined_vector: fix incorrect conditions for move constructor fast paths.Gravatar Aaron Jacobs2023-03-29
| | | | | | | | | These have nothing to do with copy construction or copy assignment, and using "is trivially copy constructible" can in theory even give the wrong result if the copy constructor is trivial but the move constructor is not. PiperOrigin-RevId: 520488816 Change-Id: I6da4d57f3ce23b03044e0bf9aa70a14b51651fa3
* inlined_vector: destroy all types with trivial destructors efficiently.Gravatar Aaron Jacobs2023-03-27
| | | | | | | | | There's no reason to require the type to be trivially copy-constructible/assignable in order to avoid running destructors—those traits have nothing to do with destruction. PiperOrigin-RevId: 519822201 Change-Id: I2ed7bbb53f0c1a512017115ff29fb27a24c6b11a
* 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
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-23 03:30:47 +0000