From 1918ad2ae38aa32c74b558b322479a8efdd76363 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Fri, 11 Dec 2020 14:49:17 -0800 Subject: Export of internal Abseil changes MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit -- 0bfa836596a9c787a2f0bdc283011dd1f6810c6e by Benjamin Barenblat : Ignore missing CPU frequency on more architectures Linux on MIPS, PA-RISC, RISC-V, and SystemZ doesn’t expose the nominal CPU frequency via /sys, so don’t worry if `NominalCPUFrequency` returns 1.0 on those platforms. Some POWER machines expose the CPU frequency; others do not. Since we can’t predict which type of machine the tests will run on, simply disable testing for `NominalCPUFrequency` on POWER. PiperOrigin-RevId: 347079873 -- 492b6834ed4a07cbc3abccd846f7e37d8c556ee5 by Benjamin Barenblat : Use ABSL_HAVE_THREAD_LOCAL macro instead of copying code Reduce code duplication by checking the ABSL_HAVE_THREAD_LOCAL macro instead of copying code from base/config.h. PiperOrigin-RevId: 347079561 -- 8d656efce4da9cb032094377e58493d98427a536 by Abseil Team : Rollback PiperOrigin-RevId: 347078779 -- 221bc69ec6dd7e2777ffcff6942584f979ef6382 by Abseil Team : Add flag for 'shallow subcord' feature for experimental ring buffer rollout There is a potential trade-off of CPU cost vs over-sharing cord data for subcord of large cords. This flag allows making subcords shallow for ringbuffers (with a potential larger waste of referenced source cords), which allows us to make subcord fast for this apps that do no persist (unmodified / plain copied) sub cords. This change also introduces constants for the default settings, intended to keep the internal cord settings concistent with external flags. PiperOrigin-RevId: 347053271 -- 00a56c24293566734009f6bf2169a83fb37a35ba by Abseil Team : Revert the usage of variant<> in Cord iterator and reader. The introduction of the variant may lead to some missed compiler optimizations. PiperOrigin-RevId: 347053041 -- c7b7b5ed7e3ab46b1e75b80f1a7de0bda26c8f70 by Chris Kennelly : Release library for integer power-of-2 functions and bit counting. PiperOrigin-RevId: 347035065 -- 5a035c0d9840b251967f9e7039fc6a4e01dd52f3 by Abseil Team : Restructure Cord::ChunkIterator for future ring buffer support. PiperOrigin-RevId: 346890054 GitOrigin-RevId: 0bfa836596a9c787a2f0bdc283011dd1f6810c6e Change-Id: I3a58e2a44cb4c6f2116c43e2a4ccbc319d3ccecf --- absl/strings/CMakeLists.txt | 4 +-- absl/strings/cord.cc | 45 ++++++++++++++++++++-------------- absl/strings/cord.h | 30 ++++++++++++++++++++--- absl/strings/internal/cord_internal.cc | 5 +++- absl/strings/internal/cord_internal.h | 11 +++++++++ 5 files changed, 70 insertions(+), 25 deletions(-) (limited to 'absl/strings') diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index 54c10151..6cdab257 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt @@ -56,7 +56,7 @@ absl_cc_library( DEPS absl::strings_internal absl::base - absl::bits + absl::internal_bits absl::config absl::core_headers absl::endian @@ -406,7 +406,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS - absl::bits + absl::internal_bits absl::strings absl::config absl::core_headers diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc index f475042c..f87f4882 100644 --- a/absl/strings/cord.cc +++ b/absl/strings/cord.cc @@ -1298,26 +1298,23 @@ void Cord::CopyToArraySlowPath(char* dst) const { } } -Cord::ChunkIterator& Cord::ChunkIterator::operator++() { - ABSL_HARDENING_ASSERT(bytes_remaining_ > 0 && - "Attempted to iterate past `end()`"); - assert(bytes_remaining_ >= current_chunk_.size()); - bytes_remaining_ -= current_chunk_.size(); - - if (stack_of_right_children_.empty()) { +Cord::ChunkIterator& Cord::ChunkIterator::AdvanceStack() { + assert(absl::holds_alternative(context_)); + auto& stack_of_right_children = absl::get(context_); + if (stack_of_right_children.empty()) { assert(!current_chunk_.empty()); // Called on invalid iterator. // We have reached the end of the Cord. return *this; } // Process the next node on the stack. - CordRep* node = stack_of_right_children_.back(); - stack_of_right_children_.pop_back(); + CordRep* node = stack_of_right_children.back(); + stack_of_right_children.pop_back(); // Walk down the left branches until we hit a non-CONCAT node. Save the // right children to the stack for subsequent traversal. while (node->tag == CONCAT) { - stack_of_right_children_.push_back(node->concat()->right); + stack_of_right_children.push_back(node->concat()->right); node = node->concat()->left; } @@ -1360,6 +1357,8 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { } return subcord; } + assert(absl::holds_alternative(context_)); + auto& stack_of_right_children = absl::get(context_); if (n < current_chunk_.size()) { // Range to read is a proper subrange of the current chunk. assert(current_leaf_ != nullptr); @@ -1388,13 +1387,13 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { // Process the next node(s) on the stack, reading whole subtrees depending on // their length and how many bytes we are advancing. CordRep* node = nullptr; - while (!stack_of_right_children_.empty()) { - node = stack_of_right_children_.back(); - stack_of_right_children_.pop_back(); + while (!stack_of_right_children.empty()) { + node = stack_of_right_children.back(); + stack_of_right_children.pop_back(); if (node->length > n) break; // TODO(qrczak): This might unnecessarily recreate existing concat nodes. // Avoiding that would need pretty complicated logic (instead of - // current_leaf_, keep current_subtree_ which points to the highest node + // current_leaf, keep current_subtree_ which points to the highest node // such that the current leaf can be found on the path of left children // starting from current_subtree_; delay creating subnode while node is // below current_subtree_; find the proper node along the path of left @@ -1419,7 +1418,7 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { while (node->tag == CONCAT) { if (node->concat()->left->length > n) { // Push right, descend left. - stack_of_right_children_.push_back(node->concat()->right); + stack_of_right_children.push_back(node->concat()->right); node = node->concat()->left; } else { // Read left, descend right. @@ -1462,12 +1461,20 @@ void Cord::ChunkIterator::AdvanceBytesSlowPath(size_t n) { n -= current_chunk_.size(); bytes_remaining_ -= current_chunk_.size(); + if (!absl::holds_alternative(context_)) { + // We have reached the end of the Cord. + assert(bytes_remaining_ == 0); + return; + } + // Process the next node(s) on the stack, skipping whole subtrees depending on // their length and how many bytes we are advancing. CordRep* node = nullptr; - while (!stack_of_right_children_.empty()) { - node = stack_of_right_children_.back(); - stack_of_right_children_.pop_back(); + assert(absl::holds_alternative(context_)); + auto& stack_of_right_children = absl::get(context_); + while (!stack_of_right_children.empty()) { + node = stack_of_right_children.back(); + stack_of_right_children.pop_back(); if (node->length > n) break; n -= node->length; bytes_remaining_ -= node->length; @@ -1485,7 +1492,7 @@ void Cord::ChunkIterator::AdvanceBytesSlowPath(size_t n) { while (node->tag == CONCAT) { if (node->concat()->left->length > n) { // Push right, descend left. - stack_of_right_children_.push_back(node->concat()->right); + stack_of_right_children.push_back(node->concat()->right); node = node->concat()->left; } else { // Skip left, descend right. diff --git a/absl/strings/cord.h b/absl/strings/cord.h index b9cdc435..5fc61a73 100644 --- a/absl/strings/cord.h +++ b/absl/strings/cord.h @@ -362,6 +362,8 @@ class Cord { friend class CharIterator; private: + using Stack = absl::InlinedVector; + // Constructs a `begin()` iterator from `cord`. explicit ChunkIterator(const Cord* cord); @@ -370,6 +372,10 @@ class Cord { void RemoveChunkPrefix(size_t n); Cord AdvanceAndReadBytes(size_t n); void AdvanceBytes(size_t n); + + // Stack specific operator++ + ChunkIterator& AdvanceStack(); + // Iterates `n` bytes, where `n` is expected to be greater than or equal to // `current_chunk_.size()`. void AdvanceBytesSlowPath(size_t n); @@ -383,8 +389,10 @@ class Cord { absl::cord_internal::CordRep* current_leaf_ = nullptr; // The number of bytes left in the `Cord` over which we are iterating. size_t bytes_remaining_ = 0; - absl::InlinedVector - stack_of_right_children_; + // Context of this chunk iterator, can be one of: + // - monostate: iterator holds only one chunk or is empty. + // - Stack : iterator holds a concat / substring tree + absl::variant context_; }; // Cord::ChunkIterator::chunk_begin() @@ -1100,13 +1108,29 @@ inline Cord::ChunkIterator::ChunkIterator(const Cord* cord) : bytes_remaining_(cord->size()) { if (cord->empty()) return; if (cord->contents_.is_tree()) { - stack_of_right_children_.push_back(cord->contents_.tree()); + Stack& stack_of_right_children = context_.emplace(); + stack_of_right_children.push_back(cord->contents_.tree()); operator++(); } else { current_chunk_ = absl::string_view(cord->contents_.data(), cord->size()); } } +inline Cord::ChunkIterator& Cord::ChunkIterator::operator++() { + ABSL_HARDENING_ASSERT(bytes_remaining_ > 0 && + "Attempted to iterate past `end()`"); + assert(bytes_remaining_ >= current_chunk_.size()); + bytes_remaining_ -= current_chunk_.size(); + if (bytes_remaining_ > 0) { + if (absl::holds_alternative(context_)) { + return AdvanceStack(); + } + } else { + current_chunk_ = {}; + } + return *this; +} + inline Cord::ChunkIterator Cord::ChunkIterator::operator++(int) { ChunkIterator tmp(*this); operator++(); diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc index 35f4d235..59f2e4d9 100644 --- a/absl/strings/internal/cord_internal.cc +++ b/absl/strings/internal/cord_internal.cc @@ -24,7 +24,10 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace cord_internal { -ABSL_CONST_INIT std::atomic cord_ring_buffer_enabled(false); +ABSL_CONST_INIT std::atomic cord_ring_buffer_enabled( + kCordEnableRingBufferDefault); +ABSL_CONST_INIT std::atomic shallow_subcords_enabled( + kCordShallowSubcordsDefault); void CordRep::Destroy(CordRep* rep) { assert(rep != nullptr); diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h index f1af8e6e..57e7046a 100644 --- a/absl/strings/internal/cord_internal.h +++ b/absl/strings/internal/cord_internal.h @@ -31,12 +31,23 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace cord_internal { +// Default feature enable states for cord ring buffers +enum CordFeatureDefaults { + kCordEnableRingBufferDefault = false, + kCordShallowSubcordsDefault = false +}; + extern std::atomic cord_ring_buffer_enabled; +extern std::atomic shallow_subcords_enabled; inline void enable_cord_ring_buffer(bool enable) { cord_ring_buffer_enabled.store(enable, std::memory_order_relaxed); } +inline void enable_shallow_subcords(bool enable) { + shallow_subcords_enabled.store(enable, std::memory_order_relaxed); +} + enum Constants { // The inlined size to use with absl::InlinedVector. // -- cgit v1.2.3