summaryrefslogtreecommitdiff
path: root/absl/strings/internal/cord_rep_ring.h
Commit message (Collapse)AuthorAge
* Fix spelling mistakesGravatar Vertexwahn2023-04-27
|
* Fix some spelling mistakesGravatar Vertexwahn2023-04-24
|
* Export of internal Abseil changesGravatar Abseil Team2021-11-02
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- f49e405201d2ffd5955503fa8ad0f08ec0cdfb2b by Martijn Vels <mvels@google.com>: Add common [container.requirements] type definitions to `CharRange` and `ChunkRange` The presence of these allow these range classes to be used in various utility functions which require some minimum type of container. For example, this change allows tests to use `EXPECT_THAT(cord.Chunks(), ElementsAre(...))` PiperOrigin-RevId: 406941278 -- 0c195f073632e21d9a4bce158047b2ba8551c2d1 by Evan Brown <ezb@google.com>: Use explicit exponential growth in SubstituteAndAppendArray. PiperOrigin-RevId: 406931952 -- afb043bccd809a55cab78abadb7548a057d9eda0 by Jorg Brown <jorg@google.com>: Use longer var names in macro to avoid clang-tidy warning PiperOrigin-RevId: 406930978 -- 80397e2604e6b3d929a34742c3a32581b34d3ac4 by Martijn Vels <mvels@google.com>: Add future kAppendBuffer and kPrependBuffer API trackers for Cordz sampling PiperOrigin-RevId: 406912759 -- e910ce919ef83933f08a690e8b7325c7cc5b6d5d by Martijn Vels <mvels@google.com>: Implement Prepend(string_view) in terms of PrependArray(string_view, MethodIdentifier). PiperOrigin-RevId: 406891665 -- c9cff43d4c0568ed01f2fca0f6ef038ae03112b5 by Martijn Vels <mvels@google.com>: Add 'Rebuild' logic to CordRepBtree There are btree hostile scenarios where an application could perform repeated split/insert/merge operations on a cord leading to a tree exceeding the maximum height. While this should be rare in practice, this change adds a Rebuild() method that will rebuild a tree with a 100% fill factor, and we will invoke this rebuild when a tree exceeds the maximum height. This basically follows the similar 'balance' logic in Concat trees (although the latter is common in Concat uses) PiperOrigin-RevId: 406875739 -- 5b2b8fb88f1ebfdc1c670088152da2cb2ea4c376 by Martijn Vels <mvels@google.com>: Add 'in place' enabled RemoveSuffix An in-place RemoveSuffix is more efficient than SubTree() as it can directly modify privately owned nodes and flats allowing easy re-use of free capacity in right-most flats that may turn into Substring edges when using SubTree. PiperOrigin-RevId: 406431230 -- f09903c0a3d7344f59aaf1380a16ea10829217d4 by Derek Mauro <dmauro@google.com>: Internal change PiperOrigin-RevId: 406430373 -- 9957af575c33bb18dc170572a4ee8cc5901df6b2 by Greg Falcon <gfalcon@google.com>: Initial groundwork to allow storing checksum data inside CordRep instances. This uses a RefcountAndFlags bit that was reserved for this purpose, and will be leveraged in a follow-up change to allow attaching checksums to a Cord's value. This change splits RefcountAndFlags::IsOne() into two distinct operations: * IsOne(): This returns true when the associated CordRep is not shared with other threads. This is useful for functions that consume CordRep instances; for example, code that consumes an unshared CordRep can assume ownership of its children without modifying those refcounts. * IsMutable(): This returns true when the associated CordRep reference is not shared with other threads, *and* does not store an associated checksum value. This is useful for functions that modify a CordRep's contents: code may modify the bytes of a mutable-unshared CordRep without fear of races with other threads, or of invalidating a stored checksum. The tricky part of this CL is ensuring that the correct choice between IsMutable() and IsOne() was made at each point. An incorrect application of IsOne() could lead to correctness bugs in the future. Code conditioned on IsOne() may delete the CordRep in question, or assume ownership of its children, but must not modify the CordRep's data without explicitly adjusting the CRC. PiperOrigin-RevId: 406191103 -- 686544814079e5ab6d4593cca0c068b510be400a by Martijn Vels <mvels@google.com>: Reduce the size in the LargeString test when running with Sanitizers PiperOrigin-RevId: 406186945 -- 735b4490bdb695c35731f06ce4b8de14ce2be6ed by Alex Strelnikov <strel@google.com>: Release absl::SimpleHexAtoi. PiperOrigin-RevId: 406143188 GitOrigin-RevId: f49e405201d2ffd5955503fa8ad0f08ec0cdfb2b Change-Id: Ic6527ac40fa03ea02ca813e8bb7868a219544de4
* Export of internal Abseil changesGravatar Abseil Team2021-08-10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 77cd6291781bc39e8472c706163d6951fe2ae573 by Derek Mauro <dmauro@google.com>: absl::uint128: Use intrinsics for more operations when available This change also inlines the division and modulus operators when intrinsics are available for better code generation. Fixes #987 PiperOrigin-RevId: 389895706 -- fa23339584599e07ebcb4d0a857e2553b017757c by Abseil Team <absl-team@google.com>: only hide retired flags if human-readable output is requested PiperOrigin-RevId: 389835452 -- f1111f2b88359d4b253d4d81681c8a488458a36e by Martijn Vels <mvels@google.com>: Add helpers IsFlat(), IsExternal(), etc to improve readability PiperOrigin-RevId: 389779333 -- 785b8712261e41695ebeeb64b4317f93b37adc11 by Martijn Vels <mvels@google.com>: Split off 'concat' and 'btree' RepMemoryUsageLeaf and RepMemoryUsageDataEdge PiperOrigin-RevId: 389701120 -- 5264bffebffc2b377bf7e18f0ce69a3ed38c6629 by CJ Johnson <johnsoncj@google.com>: Eagerly destroy `Callback` in `absl::Cleanup` PiperOrigin-RevId: 389678813 -- a05312f0668458e97c50ca932c8f974c1508ebf2 by Abseil Team <absl-team@google.com>: Have one instance of empty_group per program, rather than one per translation unit. https://stackoverflow.com/questions/185624/static-variables-in-an-inlined-function PiperOrigin-RevId: 389185845 GitOrigin-RevId: 77cd6291781bc39e8472c706163d6951fe2ae573 Change-Id: Iac8d9cb27707a9562c831c77a552d1fb4bb0405f
* Export of internal Abseil changesGravatar Abseil Team2021-05-12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 9fc37c11b9e46287acef00ee06ed9adcba54dd13 by Greg Falcon <gfalcon@google.com>: Rename absl::hash_internal::HashState to absl::hash_internal::MixingHashState. Before this change, we had two classes named HashState: absl::HashState, the public API used for type erasure, and absl::hash_internal::HashState, the internal concrete implementation ordinarily used. The internal class used to be named `CityHashState`, but we renamed it to `HashState` it when we changed underlying hash implementation to wyhash. This inadvertent naming conflict made the code much harder to read, and this change intends to undo that. PiperOrigin-RevId: 373481959 -- 4aec55ffddebd085c239352a2e20721091f719a1 by Greg Falcon <gfalcon@google.com>: Introduce absl::HashOf(), a convenience wrapper around absl::Hash that calculates hashes from the values of its arguments. PiperOrigin-RevId: 373461406 -- 86b5fd8db50bbc8bd0aa9258523527381fe0445d by Abseil Team <absl-team@google.com>: Improve speed of BlockingCounter by making its most common path lock free. With the new implementation, the fast path of BlockingCounter::DecrementCount() is only a fetch_sub operation. This is most times much more efficient than the previous implementation (full mutex lock/unlock). As a matter of fact, in most actual usecases in practice, the waiter thread is already waiting on the Wait() call when DecrementCount() is called, which makes Mutex::Unlock() take the slow path as there's a waiter thread that it might need to wake up. PiperOrigin-RevId: 373394164 -- 65c876be5eac0cd32583ff8535ede4109d39cf3f by Martijn Vels <mvels@google.com>: Move the 'sample copied cord' logic into MaybeTrackCord(), This changes move the logic for selecting if a cord should remain being sampled from Cord to CordzInfo::MaybeTrackCord, and updates the documentation for the latter method. PiperOrigin-RevId: 373363168 -- e84410bd0aada293a81dfb82656c952e209e21fb by Martijn Vels <mvels@google.com>: Add check for the first call to cordz_should_profile() for each thread. This prevents the first cord of a newly created thread to be always sampled, which is a 'bad' kind of determinism for sampling. PiperOrigin-RevId: 373229768 -- bf09c589dc099ac8f4af780bf7e609c53c27574c by Samuel Benzaquen <sbenza@google.com>: Refactor the Flags structure into an enum. This gives us more control over the representation and allows for easier merging during parsing. PiperOrigin-RevId: 373163038 -- b947b0c51083b7b6508284b5d31819596c91729e by Derek Mauro <dmauro@google.com>: Fixes warnings about shadowed variables Fixes #956 PiperOrigin-RevId: 373158133 GitOrigin-RevId: 9fc37c11b9e46287acef00ee06ed9adcba54dd13 Change-Id: I91f35699f9bf439d1a870c6493946a310afe088c
* Export of internal Abseil changesGravatar Abseil Team2021-03-30
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 6b5be2524a088d0f4e8475794dc71232a24e94d8 by Abseil Team <absl-team@google.com>: Enable ABSL_HAVE_ATTRIBUTE_WEAK for Windows with Clang >= 9.0.0 The bug (https://bugs.llvm.org/show_bug.cgi?id=37598) motivated the workaround was fixed in 9.0.0. PiperOrigin-RevId: 365682074 -- c16b7784978a370658dce6d82cb7055316a79bcc by Abseil Team <absl-team@google.com>: Add IsFlat() evaluation to GetFlatAux for RingBuffer PiperOrigin-RevId: 365666501 -- c064eb686a3c036e093e71126c45f97d3a921569 by Abseil Team <absl-team@google.com>: Implement C++11 compatible std::remove_cvref added in C++20 PiperOrigin-RevId: 365606639 -- af2e7e055172da914e63c05308aedb68e197661e by Abseil Team <absl-team@google.com>: Add IsFlat() support to CordRepRing PiperOrigin-RevId: 365562090 -- 2cfeff9280f4967c4f828812bfe153b4e9cbabb7 by Abseil Team <absl-team@google.com>: Make unit test for TryFlat on 'substring of rep' explicit PiperOrigin-RevId: 365081382 GitOrigin-RevId: 6b5be2524a088d0f4e8475794dc71232a24e94d8 Change-Id: Ibb577748176217ce237614a6fe77c05375a97003
* Export of internal Abseil changesGravatar Abseil Team2021-01-29
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- c68f1886f5e8fd90eb0c2d2e68feaf00a7cdacda by CJ Johnson <johnsoncj@google.com>: Introduce absl::Cleanup to the OSS repo PiperOrigin-RevId: 354583156 -- 17030cf388e10f7eb959e3e566326d1072ce392e by Abseil Team <absl-team@google.com>: Internal change only PiperOrigin-RevId: 354574953 -- e979d7236d4f3252e79ddda6739b67a9a326bf6d by CJ Johnson <johnsoncj@google.com>: Internal change PiperOrigin-RevId: 354545297 -- 7ea02b3783f7f49ef97d86a8f6580a19cc57df14 by Abseil Team <absl-team@google.com>: Pre-allocate memory for vectors where the size is known. PiperOrigin-RevId: 354344576 -- 9246c7cb11f1d6444f79ebe25acc69a8a9b870e0 by Matt Kulukundis <kfm@google.com>: Add support for Elbrus 2000 (e2k) Import of https://github.com/abseil/abseil-cpp/pull/889 PiperOrigin-RevId: 354344013 -- 0fc93d359cc1fb307552e917b37b7b2e7eed822f by Abseil Team <absl-team@google.com>: Integrate CordRepRing logic into cord (but do not enable it) PiperOrigin-RevId: 354312238 -- eda05622f7da71466723acb33403f783529df24b by Abseil Team <absl-team@google.com>: Protect ignore diagnostic with "__has_warning". PiperOrigin-RevId: 354112334 -- 47716c5d8fb10efa4fdd801d28bac414c6f8ec32 by Abseil Team <absl-team@google.com>: Rearrange InlinedVector copy constructor and destructor to treat a few special cases inline and then tail-call a non-inlined routine for the rest. In particular, we optimize for empty vectors in both cases. Added a couple of benchmarks that copy either an InlVec<int64> or an InlVec<InlVec<int64>>. Speed difference: ``` BM_CopyTrivial/0 0.92ns +- 0% 0.47ns +- 0% -48.91% (p=0.000 n=11+12) BM_CopyTrivial/1 0.92ns +- 0% 1.15ns +- 0% +25.00% (p=0.000 n=10+9) BM_CopyTrivial/8 8.57ns +- 0% 10.72ns +- 1% +25.16% (p=0.000 n=10+12) BM_CopyNonTrivial/0 3.21ns +- 0% 0.70ns +- 0% -78.23% (p=0.000 n=12+10) BM_CopyNonTrivial/1 5.88ns +- 1% 5.51ns +- 0% -6.28% (p=0.000 n=10+8) BM_CopyNonTrivial/8 21.5ns +- 1% 15.2ns +- 2% -29.23% (p=0.000 n=12+12) ``` Note: the slowdowns are a few cycles which is expected given the procedure call added in that case. We decided this is a good tradeoff given the code size reductions and the more significant speedups for empty vectors. Size difference (as measured by nm): ``` BM_CopyTrivial from 1048 bytes to 326 bytes. BM_CopyNonTrivial from 749 bytes to 470 bytes. ``` Code size for a large binary drops by ~500KB (from 349415719 to 348906015 348906191). All of the benchmarks that showed a significant difference: Ones that improve with this CL: ``` BM_CopyNonTrivial/0 3.21ns +- 0% 0.70ns +- 0% -78.23% (p=0.000 n=12+10) BM_InlinedVectorFillString/0 0.93ns +- 0% 0.24ns +- 0% -74.19% (p=0.000 n=12+10) BM_InlinedVectorAssignments/1 10.5ns +- 0% 4.1ns +- 0% -60.64% (p=0.000 n=11+10) BM_InlinedVectorAssignments/2 10.7ns +- 0% 4.4ns +- 0% -59.08% (p=0.000 n=11+11) BM_CopyTrivial/0 0.92ns +- 0% 0.47ns +- 0% -48.91% (p=0.000 n=11+12) BM_CopyNonTrivial/8 21.5ns +- 1% 15.2ns +- 2% -29.23% (p=0.000 n=12+12) BM_StdVectorEmpty 0.47ns +- 1% 0.35ns +- 0% -24.73% (p=0.000 n=12+12) BM_StdVectorSize 0.46ns +- 2% 0.35ns +- 0% -24.32% (p=0.000 n=12+12) BM_SwapElements<LargeCopyableOnly>/0 3.44ns +- 0% 2.76ns +- 1% -19.83% (p=0.000 n=11+11) BM_InlinedVectorFillRange/256 20.7ns +- 1% 17.8ns +- 0% -14.08% (p=0.000 n=12+9) BM_CopyNonTrivial/1 5.88ns +- 1% 5.51ns +- 0% -6.28% (p=0.000 n=10+8) BM_SwapElements<LargeCopyableMovable>/1 4.19ns +- 0% 3.95ns +- 1% -5.63% (p=0.000 n=11+12) BM_SwapElements<LargeCopyableMovableSwappable>/1 4.18ns +- 0% 3.99ns +- 0% -4.70% (p=0.000 n=9+11) BM_SwapElements<LargeCopyableMovable>/0 2.41ns +- 0% 2.31ns +- 0% -4.45% (p=0.000 n=12+12) BM_InlinedVectorFillRange/64 8.25ns +- 0% 8.04ns +- 0% -2.51% (p=0.000 n=12+11) BM_SwapElements<LargeCopyableOnly>/1 82.4ns +- 0% 81.5ns +- 0% -1.06% (p=0.000 n=12+12) ``` Ones that get worse with this CL: ``` BM_CopyTrivial/1 0.92ns +- 0% 1.15ns +- 0% +25.00% (p=0.000 n=10+9) BM_CopyTrivial/8 8.57ns +- 0% 10.72ns +- 1% +25.16% (p=0.000 n=10+12) BM_SwapElements<LargeCopyableMovableSwappable>/512 1.48ns +- 1% 1.66ns +- 1% +11.88% (p=0.000 n=12+12) BM_InlinedVectorFillString/1 11.5ns +- 0% 12.8ns +- 1% +11.62% (p=0.000 n=12+11) BM_SwapElements<LargeCopyableMovableSwappable>/64 1.48ns +- 2% 1.66ns +- 1% +11.66% (p=0.000 n=12+11) BM_SwapElements<LargeCopyableMovableSwappable>/1k 1.48ns +- 1% 1.65ns +- 2% +11.32% (p=0.000 n=12+12) BM_SwapElements<LargeCopyableMovable>/512 1.48ns +- 2% 1.58ns +- 4% +6.62% (p=0.000 n=11+12) BM_SwapElements<LargeCopyableMovable>/1k 1.49ns +- 2% 1.58ns +- 3% +6.05% (p=0.000 n=12+12) BM_SwapElements<LargeCopyableMovable>/64 1.48ns +- 2% 1.57ns +- 4% +6.04% (p=0.000 n=11+12) BM_InlinedVectorFillRange/1 4.81ns +- 0% 5.05ns +- 0% +4.83% (p=0.000 n=11+11) BM_InlinedVectorFillString/8 79.4ns +- 1% 83.1ns +- 1% +4.64% (p=0.000 n=10+12) BM_StdVectorFillString/1 16.3ns +- 0% 16.6ns +- 0% +2.13% (p=0.000 n=11+8) ``` PiperOrigin-RevId: 353906786 -- 8e26518b3cec9c598e5e9573c46c3bd1b03a67ef by Abseil Team <absl-team@google.com>: Internal change PiperOrigin-RevId: 353737330 -- f206ae0983e58c9904ed8b8f05f9caf564a446be by Matt Kulukundis <kfm@google.com>: Import of CCTZ from GitHub. PiperOrigin-RevId: 353682256 GitOrigin-RevId: c68f1886f5e8fd90eb0c2d2e68feaf00a7cdacda Change-Id: I5790c1036c4f543c701d1039848fabf7ae881ad8
* Export of internal Abseil changesGravatar Abseil Team2021-01-25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- cfd7ee2487ed9b5636d8f83d3850c02e3b4a5cb0 by Jorg Brown <jorg@google.com>: Add union padding to AsTree, to avoid issues on 32-bit MSVC 2015 compilers alignas() causes compiler errors as per https://godbolt.org/z/vaTKjn This change uses explicit padding to achieve what we want: https://godbolt.org/z/Mfjhhj PiperOrigin-RevId: 353211413 -- b1ac7430ffdefe58c01b29e9acd182cda4630e1d by Jorg Brown <jorg@google.com>: Make the casting functions flat() and ring() be static_cast, rather than reinterpret_cast. PiperOrigin-RevId: 353149543 -- c37a6761c31720317c8b0b7db62b693643a88586 by Abseil Team <absl-team@google.com>: Integrate CordRepRing logic into cord (but do not enable it) PiperOrigin-RevId: 353135656 -- 2007fd3045ed6285106795cf8f2e6d792922f5e8 by Abseil Team <absl-team@google.com>: Fix a typo in the description of ::equal_range(). The correct return is actually a half-open range [first, last). PiperOrigin-RevId: 353122213 -- 6683fa2ba7271dd1f575bd7742d97f47a034c9d2 by Abseil Team <absl-team@google.com>: Integrate CordRepRing logic into cord (but do not enable it) PiperOrigin-RevId: 353121763 GitOrigin-RevId: cfd7ee2487ed9b5636d8f83d3850c02e3b4a5cb0 Change-Id: I6635163cd634706f5462c4065aa278e6bf193a72
* Export of internal Abseil changesGravatar Abseil Team2021-01-20
-- 642ab296a2c9629c44f3f2ce6911cd2488bcf416 by Derek Mauro <dmauro@google.com>: Remove an obsolete check in CMakeLists.txt PiperOrigin-RevId: 352852564 -- ce78cb96bcfd162737dbcf35005da3d1d6a3486b by Abseil Team <absl-team@google.com>: Clarify that the calling *thread* must have locked the mutex in order to unlock it. PiperOrigin-RevId: 352801804 -- 24e1f5f72756046f5265abf618e951c341f09b8d by Derek Mauro <dmauro@google.com>: Fixes failing CMake string comparisons https://cmake.org/cmake/help/latest/policy/CMP0054.html Fixes #791 PiperOrigin-RevId: 352791054 -- 0ac10bc3f4dca2c4c4b51d7b8196a2eaee9537a1 by Abseil Team <absl-team@google.com>: Introduce CordRepRing class This change introduces the CordRepRing class that implements all the lower level / internal implementation for upcoming CordRepRing ring buffer support in cord. PiperOrigin-RevId: 352771994 -- 4bd36dda61760785844f0f29f26d90cc18046f75 by Abseil Team <absl-team@google.com>: Optimize InlineData representation for cord sampling (cordz) This CL changes InlineData to allow us to store a (future) Cordz Info pointer directly into the inline representation: - make InlineData a class that provides a public API to set the active union members (tree or chars) and safely access that data. - change 'tree' and 'profiled' bits to be the 2 least significant bits, allowing us 62 continquous bits for storing a Cordz Info pointer. PiperOrigin-RevId: 352642411 -- dc55ba71bbce0e6a83e05a453990c51ac3d68426 by Mark Barolak <mbar@google.com>: Add unit test coverage for the mutating overload of absl::AsciiStrToLower. PiperOrigin-RevId: 352626006 GitOrigin-RevId: 642ab296a2c9629c44f3f2ce6911cd2488bcf416 Change-Id: I6c5929dd830d3c630e14e7fd5387fc3e25a69100
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-07 14:53:31 +0000