| Commit message (Collapse) | Author | Age |
|
|
|
|
|
|
| |
fails.
PiperOrigin-RevId: 545683736
Change-Id: Ic0abec5037e160898e2f24de1b1489caff7d06fd
|
|
|
|
|
|
|
| |
easier to change how we store this information internally.
PiperOrigin-RevId: 544732832
Change-Id: I0c9a30f18edc71b3c7fffe94e2002ff6c52050f8
|
|
|
|
|
|
|
| |
to change how we store this information internally.
PiperOrigin-RevId: 544718317
Change-Id: I0ff3e4df7e810be9f7c5db4328995e172eb704a5
|
|
|
|
|
|
|
| |
how we store this information internally.
PiperOrigin-RevId: 544667586
Change-Id: I9b1943ca71ea1c1f8699832422cd7bc095ac8b2d
|
|
|
|
|
| |
PiperOrigin-RevId: 544401753
Change-Id: Ie5bb48bb46c8c1bf41ef902242cefefd739e7c37
|
|
|
|
|
| |
PiperOrigin-RevId: 540928490
Change-Id: Idf022b28ce101a948be4efd5336888a66f5eacf9
|
|
|
|
| |
https://google.github.io/styleguide/cppguide.html#Function_Comments
|
|\
| |
| |
| |
| | |
PiperOrigin-RevId: 536785792
Change-Id: I2963dea81a75b01b7275d784f6a2908816d0c7bf
|
| | |
|
|/
|
|
|
|
|
|
|
|
|
| |
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
|
|
|
|
|
|
|
|
|
| |
equal to field_type.
Also do some minor refactoring in btree.h.
PiperOrigin-RevId: 529460378
Change-Id: I278833ada93bbb7652e149fceed08ce3485e4312
|
|
|
|
|
|
|
| |
from internal ones.
PiperOrigin-RevId: 529423722
Change-Id: Ib1cc427299100956c0f2ae6cb5214467ef5a3790
|
|
|
|
|
| |
PiperOrigin-RevId: 529119690
Change-Id: If585274c409e2a344c8d60759da6f8f990023d29
|
|
|
|
|
|
|
| |
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
|
|\
| |
| |
| |
| | |
PiperOrigin-RevId: 527066823
Change-Id: Ifa1e9a43c7490b34f9f4dbfa12d3acbed6b49777
|
|/ |
|
|
|
|
|
|
|
| |
constructing nodes.
PiperOrigin-RevId: 525792213
Change-Id: I4386385e6e05d74a4ccc18cea505530e919f0e28
|
|
|
|
|
|
|
|
|
| |
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
|
|
|
|
|
|
|
| |
std::is_trivially_copyable
PiperOrigin-RevId: 523724345
Change-Id: Id68c79c3bbb253d892bdef4659ac8a926e023d12
|
|
|
|
|
|
|
| |
This has nothing to do with copy assignment or with destruction.
PiperOrigin-RevId: 523576913
Change-Id: Iddb6ab73bcfd8b01a29880cdf4db4bc2b5aead8a
|
|
|
|
|
|
|
| |
This has nothing to do with copy construction or copy assignment.
PiperOrigin-RevId: 523571907
Change-Id: I338b5a40616594406ca8c80b747540c8935798e9
|
|
|
|
|
|
|
| |
This has nothing to do with copy construction or copy assignment.
PiperOrigin-RevId: 523557887
Change-Id: I332d6ceaf738305157605f1271cb577a83d198c5
|
|
|
|
|
|
|
|
|
| |
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
|
|
|
|
|
| |
PiperOrigin-RevId: 521556211
Change-Id: I1e1812eb11bfc5772abbf38ce348580c3afa5612
|
|
|
|
|
|
|
|
|
| |
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
|
|
|
|
|
|
|
|
|
| |
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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
|
|
|
|
|
|
|
| |
different empty hashtables are compared.
PiperOrigin-RevId: 513568915
Change-Id: I3f387d0bae0e86749dff540e4fdd5037304ac975
|
|
|
|
|
|
|
| |
BM_DropDeletes 73.4µs ± 0% 68.9µs ± 1% -6.22% (p=0.008 n=5+5)
PiperOrigin-RevId: 511813266
Change-Id: Id28cece454d583e2dfe060e27cfc4720f987f009
|
|\
| |
| |
| |
| | |
PiperOrigin-RevId: 511695308
Change-Id: I502cdc75e993582eaca5cd91ed068238936a9640
|
| |
| |
| |
| |
| |
| |
| | |
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
|
|/
|
|
| |
We support GCC 7 and up, so we can remove this.
|
|
|
|
|
|
|
| |
that we can distinguish between end() iterators and default-constructed iterators in debug mode.
PiperOrigin-RevId: 509606271
Change-Id: I77b68590b3904a4cf7809b75d814d74cb89603b6
|
|
|
|
|
|
|
|
|
| |
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
|
|
|
|
|
|
|
|
|
| |
compared.
We change AssertSameContainer to be after AssertIsValidForComparison calls so that we can have more specific failure messages.
PiperOrigin-RevId: 508472485
Change-Id: Iff2f7512086948a4aca7fd403596e8d4fde53b2a
|
|
|
|
|
| |
PiperOrigin-RevId: 506622658
Change-Id: I17ae2d97a6cadb7bdd8ebd0ec0dd3976568cb7e1
|
|
|
|
|
|
|
|
|
| |
randomly rehashing on insertions when there is no reserved growth.
Rollforward of ed59f62f8bbc5f05bcba2f89ee16f107e03813f2
PiperOrigin-RevId: 506314970
Change-Id: I7a654aef36bb169da9ea5c618789ee771f05fe28
|
|
|
|
|
|
|
|
|
| |
randomly rehashing on insertions when there is no reserved growth.
Rollback of ed59f62f8bbc5f05bcba2f89ee16f107e03813f2
PiperOrigin-RevId: 506003574
Change-Id: I1766321f279a3226e2821e0390387d5639d28964
|
|
|
|
|
|
|
| |
rehashing on insertions when there is no reserved growth.
PiperOrigin-RevId: 505807487
Change-Id: I9051a04f6a75e579d16e9ae8defd404bcc377fba
|
|
|
|
|
| |
PiperOrigin-RevId: 505184961
Change-Id: I64482558a76abda6896bec4b2d323833b6cd7edf
|
|
|
|
|
|
|
| |
the find isn't inlined but the iterator comparison is.
PiperOrigin-RevId: 503473637
Change-Id: I02b8d95b7a1b738314c4f07a863c7606f822f079
|
|
|
|
|
|
|
| |
growth runs out.
PiperOrigin-RevId: 502625638
Change-Id: I1c06b2162dbdaaa6a36cea503ac6d07cd157b2e2
|
|
|
|
|
| |
PiperOrigin-RevId: 499964205
Change-Id: I45a1d62a5e093921946e7c3c7ab31480252b330e
|
|
|
|
|
|
|
| |
reserved growth if the reservation wouldn't grow the table.
PiperOrigin-RevId: 497246219
Change-Id: I9671236f56d10851c49de71c21899368be6c3a00
|
|
|
|
|
|
|
| |
arrays so that we can detect invalid iterator use.
PiperOrigin-RevId: 496455788
Change-Id: I83df92828098a3ef1181b4e454f3ac5d3ac7a2f2
|
|
|
|
|
|
|
|
| |
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
|
|
|
|
|
| |
PiperOrigin-RevId: 493993005
Change-Id: I0705be8678022a9e08a1af9972687b7955593994
|
|
|
|
|
|
|
|
|
|
|
| |
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
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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
|