aboutsummaryrefslogtreecommitdiff
path: root/absl/container/BUILD.bazel
Commit message (Collapse)AuthorAgeFilesLines
* Create `absl::container_internal::c_for_each_fast` for SwissTable.Vitaly Goldshteyn2024-06-201-2/+10
| | | | | | | | | | | | | | | | | | 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
* Use `IterateOverFullSlots` in `absl::erase_if` for hash table.Vitaly Goldshteyn2024-06-101-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | `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, ↵Evan Brown2024-06-061-0/+2
| | | | | | | | | k2) -> hash(k1) == hash(k2)`. Also add missing includes/dependencies in flat_hash_map_test. PiperOrigin-RevId: 640959222 Change-Id: I8d99544af05e97310045e6149f6ef6f7c82e552d
* Add public aliases for default hash/eq types in hash-based containersDennis Kormalev2024-04-241-4/+15
| | | | | | | | | | | | | | | 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-181-0/+1
| | | | | | | | | 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
* Add `BM_EraseIf` benchmark.Vitaly Goldshteyn2024-03-251-0/+1
| | | | | PiperOrigin-RevId: 618970135 Change-Id: Ifb9d0b425904d5cb37d80ec28ab7845957209313
* Fix ClangTidy warnings in btree.h.Evan Brown2024-03-251-1/+1
| | | | | PiperOrigin-RevId: 618872032 Change-Id: I9fdfadff906494eb64cee976c02a1fff57923c79
* Do hashtablez sampling on the first insertion into an empty SOO hashtable.Evan Brown2024-03-191-0/+2
| | | | | | | | | 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
* Roll back extern template instatiations in swisstable due to binary size ↵Evan Brown2024-03-131-10/+0
| | | | | | | increases in shared libraries. PiperOrigin-RevId: 615497725 Change-Id: Ic29db8923ea4ea7cd0b01b396896fa9fff8c74b0
* Add extern templates for common swisstable types.Evan Brown2024-03-121-0/+10
| | | | | | | | 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
* Add absl_container_hash-based HashEq specializationDennis Kormalev2024-02-071-0/+4
| | | | | | | | | | | | | | 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
* Type erased hash_slot_fn that depends only on key types (and hash function).Abseil Team2024-01-311-0/+4
| | | | | PiperOrigin-RevId: 603148301 Change-Id: Ie2e5702995c9e1ef4d5aaab23bc89a1eb5007a86
* Replace `testonly = 1` with `testonly = True` in abseil BUILD files.Shahriar Rouf2024-01-311-20/+20
| | | | | | | https://bazel.build/build/style-guide#other-conventions PiperOrigin-RevId: 603084345 Change-Id: Ibd7c9573d820f88059d12c46ff82d7d322d002ae
* Early return from destroy_slots for trivially destructible types in ↵Abseil Team2024-01-301-0/+2
| | | | | | | flat_hash_{*}. PiperOrigin-RevId: 602813933 Change-Id: I744fe438281755a141b2fd47e54ab9c6c0fad5a3
* Use absl::NoDestructor for global HashtablezSampler.Abseil Team2024-01-241-0/+1
| | | | | PiperOrigin-RevId: 601156448 Change-Id: Id6d19bda7eb3acee11cfab3a95e611996d6ef4cc
* Migrate static objects to NoDestructor in tests, testing libraries and ↵Abseil Team2023-12-261-0/+4
| | | | | | | benchmarks. PiperOrigin-RevId: 593918110 Change-Id: Ide100c69b10e28011af17c7f82bb10eea072cad4
* Add a pragma to disable a maybe-uninitialized warning for GCC12+Abseil Team2023-12-191-0/+1
| | | | | PiperOrigin-RevId: 592301543 Change-Id: I97e4df805c7313896228430a50a7f991127f3e30
* Unit-tests to verify ABSL raw_hash_set does not double-hash in prodAbseil Team2023-12-121-0/+4
| | | | | PiperOrigin-RevId: 590337123 Change-Id: Ib98bbb5a5dadbce5e891567038e016f4da2efc0b
* Make `FlatHashMapPolicy` return `std::true_type` for relocatable objects.Abseil Team2023-11-201-0/+2
| | | | | | | This reduces produced binary size and can trigger even more optimizations in the future. PiperOrigin-RevId: 584136517 Change-Id: I3854833799f88f28b755ec53132925f0c3d468ab
* Roll back due to leak sanitizer reports.Aaron Jacobs2023-11-081-2/+0
| | | | | PiperOrigin-RevId: 580726428 Change-Id: I12b0f22c2084aef90bcca67536220a6bb550b57e
* Roll forward: Add sanitizer mode checks that element ↵Evan Brown2023-10-301-0/+2
| | | | | | | constructors/destructors don't make reentrant calls to raw_hash_set member functions. PiperOrigin-RevId: 577877803 Change-Id: I254c589b00cadec6ff95dfd60a8a38ab303c1af5
* Rollback: Add sanitizer mode checks that element constructors/destructors ↵Evan Brown2023-10-171-2/+0
| | | | | | | don't make reentrant calls to raw_hash_set member functions. PiperOrigin-RevId: 574232718 Change-Id: I8ef25fec00b76ee5fb9424e7614ca55edd6ba81b
* Add sanitizer mode checks that element constructors/destructors don't make ↵Evan Brown2023-10-161-0/+2
| | | | | | | reentrant calls to raw_hash_set member functions. PiperOrigin-RevId: 573897598 Change-Id: If40c23ac3cd9fff315ee18774e27c480cbca3a81
* Add missing headers in raw_hash_map.h.Evan Brown2023-10-121-0/+2
| | | | | PiperOrigin-RevId: 572979536 Change-Id: I4fceee0c52e4e6877e639860327462c7874719e7
* Bazel: Enable the header_modules featureDerek Mauro2023-10-111-0/+1
| | | | | PiperOrigin-RevId: 572575394 Change-Id: Ic1c5ac2423b1634e50c43bad6daa14e82a8f3e2c
* Bazel: Support layering_check and parse_headersDerek Mauro2023-10-101-1/+32
| | | | | | | | | | | | | The layering_check feature ensures that rules that include a header explicitly depend on a rule that exports that header. Compiler support is required, and currently only Clang 16+ supports diagnoses layering_check failures. The parse_headers feature ensures headers are self-contained by compiling them with -fsyntax-only on supported compilers. PiperOrigin-RevId: 572350144 Change-Id: I37297f761566d686d9dd58d318979d688b7e36d1
* Minor build rule changes.Evan Brown2023-10-021-5/+1
| | | | | PiperOrigin-RevId: 570180405 Change-Id: If14b21a4d0df19546a47923a1f2a359b38fe6f93
* Re-submit with a fix for platforms without RTTI.Abseil Team2023-10-021-0/+1
| | | | | | | We test for `ABSL_INTERNAL_HAS_RTTI` in `absl::container_internal::TypeName` before calling `typeid`. PiperOrigin-RevId: 570101013 Change-Id: I1f2f9b2f475a6beae50d0b88718b17b296311155
* Add an internal wrapper for `abi::__cxa_demangle()`.Abseil Team2023-09-261-1/+0
| | | | | PiperOrigin-RevId: 568665135 Change-Id: I42ec9bc6cfe923777f7b60ea032c7b64428493c9
* Add an internal wrapper for `abi::__cxa_demangle()`.Abseil Team2023-09-261-0/+1
| | | | | PiperOrigin-RevId: 568652465 Change-Id: I9f72a11cb514eaf694dae589a19dc139891e7af2
* Replace BtreeAllocatorTest with individual test cases for copy/move/swap ↵Evan Brown2023-09-211-2/+5
| | | | | | | | | propagation (defined in test_allocator.h) and minimal alignment. Also remove some extraneous value_types from typed tests. The motivation is to reduce btree_test compile time. PiperOrigin-RevId: 567376572 Change-Id: I6ac6130b99faeadaedab8c2c7b05d5e23e77cc1e
* Move CountingAllocator into test_allocator.h and add some other allocators ↵Evan Brown2023-09-151-5/+6
| | | | | | | that can be shared between different container tests. PiperOrigin-RevId: 565693736 Change-Id: I59af987e30da03a805ce59ff0fb7eeae3fc08293
* Make PolicyTraits::transfer_uses_memcpy() true for node_hash_* tables.Evan Brown2023-09-121-0/+2
| | | | | | | This should enable binary size savings for now and more efficiency improvements with small buffer optimization. PiperOrigin-RevId: 564741270 Change-Id: Icf204d88256243eb60464439a52dd589d7a559cb
* Add a flat_hash_set_test that we use value_type member functions to ↵Evan Brown2023-09-121-0/+2
| | | | | | | | | read/write from value_types when we aren't allowed to memcpy them. The motivation is to prevent a bug in small buffer optimization for swisstables. PiperOrigin-RevId: 564726325 Change-Id: Id0df5d28d65c7586428001fcb266886988cd481e
* Include what you spellDmitri Gribenko2023-08-111-2/+2
| | | | | PiperOrigin-RevId: 555894810 Change-Id: I349c94e7c6e7ba1dbd817aa8e4340c1dada84654
* Migrate most RAW_LOGs and RAW_CHECKs in tests to regular LOG and CHECK.Andy Getzendanner2023-05-231-5/+4
| | | | | | | | | | | 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
* In debug mode, detect cases of btree comparators that violate transitivity, ↵Evan Brown2023-04-121-0/+1
| | | | | | | | | 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
* Workaround MSan false positive.Abseil Team2023-02-101-0/+1
| | | | | | | | | 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
* Fix missing includes/dependenciesDerek Mauro2023-02-021-0/+2
| | | | | PiperOrigin-RevId: 506622658 Change-Id: I17ae2d97a6cadb7bdd8ebd0ec0dd3976568cb7e1
* Rollforward: in sanitizer mode, detect when references become invalidated by ↵Evan Brown2023-02-011-0/+1
| | | | | | | | | 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 ↵Abseil Team2023-01-311-1/+0
| | | | | | | | | 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 ↵Evan Brown2023-01-301-0/+1
| | | | | | | rehashing on insertions when there is no reserved growth. PiperOrigin-RevId: 505807487 Change-Id: I9051a04f6a75e579d16e9ae8defd404bcc377fba
* Restrict visibility of absl/container:hash_function_defaults.Chris Kennelly2022-12-191-0/+3
| | | | | PiperOrigin-RevId: 496514638 Change-Id: I45b8dfe01c83915c460711339d2d8c38604c8d81
* In sanitizer mode, add generations to swisstable iterators and backing ↵Evan Brown2022-12-191-0/+1
| | | | | | | arrays so that we can detect invalid iterator use. PiperOrigin-RevId: 496455788 Change-Id: I83df92828098a3ef1181b4e454f3ac5d3ac7a2f2
* Implement btree_iterator::operator-, which is faster than std::distance for ↵Evan Brown2022-10-171-0/+4
| | | | | | | | 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.Abseil Team2022-10-121-0/+1
| | | | | PiperOrigin-RevId: 480601268 Change-Id: I5a639da57b79ae600387c81e662d5c1542b2bf99
* Eliminate use of internal interfacesGennadiy Rozental2022-10-061-1/+1
| | | | | PiperOrigin-RevId: 479325483 Change-Id: I9c4384173ce996818e0cf749c0fc465d6e9aaf8c
* No changes in OSS.Gennadiy Rozental2022-10-041-0/+3
| | | | | PiperOrigin-RevId: 478869244 Change-Id: Id16eb1e5036e95a5e2a990a647f1f7090129a009
* Add common_policy_traits - a subset of hash_policy_traits that can be shared ↵Evan Brown2022-09-281-1/+25
| | | | | | | | | | 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
* Convert algorithm and container benchmarks to cc_binaryDerek Mauro2022-09-061-2/+4
| | | | | PiperOrigin-RevId: 472521745 Change-Id: Ia76cd720d1036dce05f6332f41a2ff748b3ea971
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-08 20:56:30 +0000