diff options
| -rw-r--r-- | absl/base/config.h | 28 | ||||
| -rw-r--r-- | absl/container/BUILD.bazel | 26 | ||||
| -rw-r--r-- | absl/container/btree_benchmark.cc | 707 | ||||
| -rw-r--r-- | absl/container/internal/raw_hash_set.h | 15 | ||||
| -rw-r--r-- | absl/flags/marshalling.h | 6 | ||||
| -rw-r--r-- | absl/strings/internal/str_format/extension.h | 3 | ||||
| -rw-r--r-- | absl/strings/numbers.cc | 52 | ||||
| -rw-r--r-- | absl/time/internal/cctz/src/zone_info_source.cc | 40 | ||||
| -rw-r--r-- | absl/time/time.h | 76 | ||||
| -rw-r--r-- | absl/types/compare.h | 40 | ||||
| -rw-r--r-- | absl/types/compare_test.cc | 92 |
11 files changed, 1025 insertions, 60 deletions
diff --git a/absl/base/config.h b/absl/base/config.h index edbf22468ec5..c4e8dce403bb 100644 --- a/absl/base/config.h +++ b/absl/base/config.h @@ -66,6 +66,10 @@ #include "absl/base/options.h" #include "absl/base/policy_checks.h" +// Helper macro to convert a CPP variable to a string literal. +#define ABSL_INTERNAL_DO_TOKEN_STR(x) #x +#define ABSL_INTERNAL_TOKEN_STR(x) ABSL_INTERNAL_DO_TOKEN_STR(x) + // ----------------------------------------------------------------------------- // Abseil namespace annotations // ----------------------------------------------------------------------------- @@ -98,8 +102,6 @@ // Check that ABSL_OPTION_INLINE_NAMESPACE_NAME is neither "head" nor "" #if defined(__cplusplus) && ABSL_OPTION_USE_INLINE_NAMESPACE == 1 -#define ABSL_INTERNAL_DO_TOKEN_STR(x) #x -#define ABSL_INTERNAL_TOKEN_STR(x) ABSL_INTERNAL_DO_TOKEN_STR(x) #define ABSL_INTERNAL_INLINE_NAMESPACE_STR \ ABSL_INTERNAL_TOKEN_STR(ABSL_OPTION_INLINE_NAMESPACE_NAME) @@ -617,6 +619,28 @@ static_assert(ABSL_INTERNAL_INLINE_NAMESPACE_STR[0] != 'h' || #define ABSL_INTERNAL_MSVC_2017_DBG_MODE #endif +// ABSL_INTERNAL_MANGLED_NS +// ABSL_INTERNAL_MANGLED_BACKREFERENCE +// +// Internal macros for building up mangled names in our internal fork of CCTZ. +// This implementation detail is only needed and provided for the MSVC build. +// +// These macros both expand to string literals. ABSL_INTERNAL_MANGLED_NS is +// the mangled spelling of the `absl` namespace, and +// ABSL_INTERNAL_MANGLED_BACKREFERENCE is a back-reference integer representing +// the proper count to skip past the CCTZ fork namespace names. (This number +// is one larger when there is an inline namespace name to skip.) +#if defined(_MSC_VER) +#if ABSL_OPTION_USE_INLINE_NAMESPACE == 0 +#define ABSL_INTERNAL_MANGLED_NS "absl" +#define ABSL_INTERNAL_MANGLED_BACKREFERENCE "5" +#else +#define ABSL_INTERNAL_MANGLED_NS \ + ABSL_INTERNAL_TOKEN_STR(ABSL_OPTION_INLINE_NAMESPACE_NAME) "@absl" +#define ABSL_INTERNAL_MANGLED_BACKREFERENCE "6" +#endif +#endif + #undef ABSL_INTERNAL_HAS_KEYWORD #endif // ABSL_BASE_CONFIG_H_ diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 1f7abe07ff07..f221714027ac 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel @@ -874,3 +874,29 @@ cc_test( "@com_google_googletest//:gtest_main", ], ) + +cc_binary( + name = "btree_benchmark", + testonly = 1, + srcs = [ + "btree_benchmark.cc", + ], + copts = ABSL_TEST_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":btree", + ":btree_test_common", + ":flat_hash_map", + ":flat_hash_set", + ":hashtable_debug", + "//absl/base:raw_logging_internal", + "//absl/flags:flag", + "//absl/hash", + "//absl/memory", + "//absl/strings:str_format", + "//absl/time", + "@com_github_google_benchmark//:benchmark_main", + ], +) diff --git a/absl/container/btree_benchmark.cc b/absl/container/btree_benchmark.cc new file mode 100644 index 000000000000..4af92f9fd888 --- /dev/null +++ b/absl/container/btree_benchmark.cc @@ -0,0 +1,707 @@ +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include <stdint.h> + +#include <algorithm> +#include <functional> +#include <map> +#include <numeric> +#include <random> +#include <set> +#include <string> +#include <type_traits> +#include <unordered_map> +#include <unordered_set> +#include <vector> + +#include "absl/base/internal/raw_logging.h" +#include "absl/container/btree_map.h" +#include "absl/container/btree_set.h" +#include "absl/container/btree_test.h" +#include "absl/container/flat_hash_map.h" +#include "absl/container/flat_hash_set.h" +#include "absl/container/internal/hashtable_debug.h" +#include "absl/flags/flag.h" +#include "absl/hash/hash.h" +#include "absl/memory/memory.h" +#include "absl/strings/str_format.h" +#include "absl/time/time.h" +#include "benchmark/benchmark.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace container_internal { +namespace { + +constexpr size_t kBenchmarkValues = 1 << 20; + +// How many times we add and remove sub-batches in one batch of *AddRem +// benchmarks. +constexpr size_t kAddRemBatchSize = 1 << 2; + +// Generates n values in the range [0, 4 * n]. +template <typename V> +std::vector<V> GenerateValues(int n) { + constexpr int kSeed = 23; + return GenerateValuesWithSeed<V>(n, 4 * n, kSeed); +} + +// Benchmark insertion of values into a container. +template <typename T> +void BM_InsertImpl(benchmark::State& state, bool sorted) { + using V = typename remove_pair_const<typename T::value_type>::type; + typename KeyOfValue<typename T::key_type, V>::type key_of_value; + + std::vector<V> values = GenerateValues<V>(kBenchmarkValues); + if (sorted) { + std::sort(values.begin(), values.end()); + } + T container(values.begin(), values.end()); + + // Remove and re-insert 10% of the keys per batch. + const int batch_size = (kBenchmarkValues + 9) / 10; + while (state.KeepRunningBatch(batch_size)) { + state.PauseTiming(); + const auto i = static_cast<int>(state.iterations()); + + for (int j = i; j < i + batch_size; j++) { + int x = j % kBenchmarkValues; + container.erase(key_of_value(values[x])); + } + + state.ResumeTiming(); + + for (int j = i; j < i + batch_size; j++) { + int x = j % kBenchmarkValues; + container.insert(values[x]); + } + } +} + +template <typename T> +void BM_Insert(benchmark::State& state) { + BM_InsertImpl<T>(state, false); +} + +template <typename T> +void BM_InsertSorted(benchmark::State& state) { + BM_InsertImpl<T>(state, true); +} + +// container::insert sometimes returns a pair<iterator, bool> and sometimes +// returns an iterator (for multi- containers). +template <typename Iter> +Iter GetIterFromInsert(const std::pair<Iter, bool>& pair) { + return pair.first; +} +template <typename Iter> +Iter GetIterFromInsert(const Iter iter) { + return iter; +} + +// Benchmark insertion of values into a container at the end. +template <typename T> +void BM_InsertEnd(benchmark::State& state) { + using V = typename remove_pair_const<typename T::value_type>::type; + typename KeyOfValue<typename T::key_type, V>::type key_of_value; + + T container; + const int kSize = 10000; + for (int i = 0; i < kSize; ++i) { + container.insert(Generator<V>(kSize)(i)); + } + V v = Generator<V>(kSize)(kSize - 1); + typename T::key_type k = key_of_value(v); + + auto it = container.find(k); + while (state.KeepRunning()) { + // Repeatedly removing then adding v. + container.erase(it); + it = GetIterFromInsert(container.insert(v)); + } +} + +template <typename T> +void BM_LookupImpl(benchmark::State& state, bool sorted) { + using V = typename remove_pair_const<typename T::value_type>::type; + typename KeyOfValue<typename T::key_type, V>::type key_of_value; + + std::vector<V> values = GenerateValues<V>(kBenchmarkValues); + if (sorted) { + std::sort(values.begin(), values.end()); + } + T container(values.begin(), values.end()); + + while (state.KeepRunning()) { + int idx = state.iterations() % kBenchmarkValues; + benchmark::DoNotOptimize(container.find(key_of_value(values[idx]))); + } +} + +// Benchmark lookup of values in a container. +template <typename T> +void BM_Lookup(benchmark::State& state) { + BM_LookupImpl<T>(state, false); +} + +// Benchmark lookup of values in a full container, meaning that values +// are inserted in-order to take advantage of biased insertion, which +// yields a full tree. +template <typename T> +void BM_FullLookup(benchmark::State& state) { + BM_LookupImpl<T>(state, true); +} + +// Benchmark deletion of values from a container. +template <typename T> +void BM_Delete(benchmark::State& state) { + using V = typename remove_pair_const<typename T::value_type>::type; + typename KeyOfValue<typename T::key_type, V>::type key_of_value; + std::vector<V> values = GenerateValues<V>(kBenchmarkValues); + T container(values.begin(), values.end()); + + // Remove and re-insert 10% of the keys per batch. + const int batch_size = (kBenchmarkValues + 9) / 10; + while (state.KeepRunningBatch(batch_size)) { + const int i = state.iterations(); + + for (int j = i; j < i + batch_size; j++) { + int x = j % kBenchmarkValues; + container.erase(key_of_value(values[x])); + } + + state.PauseTiming(); + for (int j = i; j < i + batch_size; j++) { + int x = j % kBenchmarkValues; + container.insert(values[x]); + } + state.ResumeTiming(); + } +} + +// Benchmark deletion of multiple values from a container. +template <typename T> +void BM_DeleteRange(benchmark::State& state) { + using V = typename remove_pair_const<typename T::value_type>::type; + typename KeyOfValue<typename T::key_type, V>::type key_of_value; + std::vector<V> values = GenerateValues<V>(kBenchmarkValues); + T container(values.begin(), values.end()); + + // Remove and re-insert 10% of the keys per batch. + const int batch_size = (kBenchmarkValues + 9) / 10; + while (state.KeepRunningBatch(batch_size)) { + const int i = state.iterations(); + + const int start_index = i % kBenchmarkValues; + + state.PauseTiming(); + { + std::vector<V> removed; + removed.reserve(batch_size); + auto itr = container.find(key_of_value(values[start_index])); + auto start = itr; + for (int j = 0; j < batch_size; j++) { + if (itr == container.end()) { + state.ResumeTiming(); + container.erase(start, itr); + state.PauseTiming(); + itr = container.begin(); + start = itr; + } + removed.push_back(*itr++); + } + + state.ResumeTiming(); + container.erase(start, itr); + state.PauseTiming(); + + container.insert(removed.begin(), removed.end()); + } + state.ResumeTiming(); + } +} + +// Benchmark steady-state insert (into first half of range) and remove (from +// second half of range), treating the container approximately like a queue with +// log-time access for all elements. This benchmark does not test the case where +// insertion and removal happen in the same region of the tree. This benchmark +// counts two value constructors. +template <typename T> +void BM_QueueAddRem(benchmark::State& state) { + using V = typename remove_pair_const<typename T::value_type>::type; + typename KeyOfValue<typename T::key_type, V>::type key_of_value; + + ABSL_RAW_CHECK(kBenchmarkValues % 2 == 0, "for performance"); + + T container; + + const size_t half = kBenchmarkValues / 2; + std::vector<int> remove_keys(half); + std::vector<int> add_keys(half); + + // We want to do the exact same work repeatedly, and the benchmark can end + // after a different number of iterations depending on the speed of the + // individual run so we use a large batch size here and ensure that we do + // deterministic work every batch. + while (state.KeepRunningBatch(half * kAddRemBatchSize)) { + state.PauseTiming(); + + container.clear(); + + for (size_t i = 0; i < half; ++i) { + remove_keys[i] = i; + add_keys[i] = i; + } + constexpr int kSeed = 5; + std::mt19937_64 rand(kSeed); + std::shuffle(remove_keys.begin(), remove_keys.end(), rand); + std::shuffle(add_keys.begin(), add_keys.end(), rand); + + // Note needs lazy generation of values. + Generator<V> g(kBenchmarkValues * kAddRemBatchSize); + + for (size_t i = 0; i < half; ++i) { + container.insert(g(add_keys[i])); + container.insert(g(half + remove_keys[i])); + } + + // There are three parts each of size "half": + // 1 is being deleted from [offset - half, offset) + // 2 is standing [offset, offset + half) + // 3 is being inserted into [offset + half, offset + 2 * half) + size_t offset = 0; + + for (size_t i = 0; i < kAddRemBatchSize; ++i) { + std::shuffle(remove_keys.begin(), remove_keys.end(), rand); + std::shuffle(add_keys.begin(), add_keys.end(), rand); + offset += half; + + state.ResumeTiming(); + for (size_t idx = 0; idx < half; ++idx) { + container.erase(key_of_value(g(offset - half + remove_keys[idx]))); + container.insert(g(offset + half + add_keys[idx])); + } + state.PauseTiming(); + } + state.ResumeTiming(); + } +} + +// Mixed insertion and deletion in the same range using pre-constructed values. +template <typename T> +void BM_MixedAddRem(benchmark::State& state) { + using V = typename remove_pair_const<typename T::value_type>::type; + typename KeyOfValue<typename T::key_type, V>::type key_of_value; + + ABSL_RAW_CHECK(kBenchmarkValues % 2 == 0, "for performance"); + + T container; + + // Create two random shuffles + std::vector<int> remove_keys(kBenchmarkValues); + std::vector<int> add_keys(kBenchmarkValues); + + // We want to do the exact same work repeatedly, and the benchmark can end + // after a different number of iterations depending on the speed of the + // individual run so we use a large batch size here and ensure that we do + // deterministic work every batch. + while (state.KeepRunningBatch(kBenchmarkValues * kAddRemBatchSize)) { + state.PauseTiming(); + + container.clear(); + + constexpr int kSeed = 7; + std::mt19937_64 rand(kSeed); + + std::vector<V> values = GenerateValues<V>(kBenchmarkValues * 2); + + // Insert the first half of the values (already in random order) + container.insert(values.begin(), values.begin() + kBenchmarkValues); + + // Insert the first half of the values (already in random order) + for (size_t i = 0; i < kBenchmarkValues; ++i) { + // remove_keys and add_keys will be swapped before each round, + // therefore fill add_keys here w/ the keys being inserted, so + // they'll be the first to be removed. + remove_keys[i] = i + kBenchmarkValues; + add_keys[i] = i; + } + + for (size_t i = 0; i < kAddRemBatchSize; ++i) { + remove_keys.swap(add_keys); + std::shuffle(remove_keys.begin(), remove_keys.end(), rand); + std::shuffle(add_keys.begin(), add_keys.end(), rand); + + state.ResumeTiming(); + for (size_t idx = 0; idx < kBenchmarkValues; ++idx) { + container.erase(key_of_value(values[remove_keys[idx]])); + container.insert(values[add_keys[idx]]); + } + state.PauseTiming(); + } + state.ResumeTiming(); + } +} + +// Insertion at end, removal from the beginning. This benchmark +// counts two value constructors. +// TODO(ezb): we could add a GenerateNext version of generator that could reduce +// noise for string-like types. +template <typename T> +void BM_Fifo(benchmark::State& state) { + using V = typename remove_pair_const<typename T::value_type>::type; + + T container; + // Need lazy generation of values as state.max_iterations is large. + Generator<V> g(kBenchmarkValues + state.max_iterations); + + for (int i = 0; i < kBenchmarkValues; i++) { + container.insert(g(i)); + } + + while (state.KeepRunning()) { + container.erase(container.begin()); + container.insert(container.end(), g(state.iterations() + kBenchmarkValues)); + } +} + +// Iteration (forward) through the tree +template <typename T> +void BM_FwdIter(benchmark::State& state) { + using V = typename remove_pair_const<typename T::value_type>::type; + using R = typename T::value_type const*; + + std::vector<V> values = GenerateValues<V>(kBenchmarkValues); + T container(values.begin(), values.end()); + + auto iter = container.end(); + + R r = nullptr; + + while (state.KeepRunning()) { + if (iter == container.end()) iter = container.begin(); + r = &(*iter); + ++iter; + } + + benchmark::DoNotOptimize(r); +} + +// Benchmark random range-construction of a container. +template <typename T> +void BM_RangeConstructionImpl(benchmark::State& state, bool sorted) { + using V = typename remove_pair_const<typename T::value_type>::type; + + std::vector<V> values = GenerateValues<V>(kBenchmarkValues); + if (sorted) { + std::sort(values.begin(), values.end()); + } + { + T container(values.begin(), values.end()); + } + + while (state.KeepRunning()) { + T container(values.begin(), values.end()); + benchmark::DoNotOptimize(container); + } +} + +template <typename T> +void BM_InsertRangeRandom(benchmark::State& state) { + BM_RangeConstructionImpl<T>(state, false); +} + +template <typename T> +void BM_InsertRangeSorted(benchmark::State& state) { + BM_RangeConstructionImpl<T>(state, true); +} + +#define STL_ORDERED_TYPES(value) \ + using stl_set_##value = std::set<value>; \ + using stl_map_##value = std::map<value, intptr_t>; \ + using stl_multiset_##value = std::multiset<value>; \ + using stl_multimap_##value = std::multimap<value, intptr_t> + +using StdString = std::string; +STL_ORDERED_TYPES(int32_t); +STL_ORDERED_TYPES(int64_t); +STL_ORDERED_TYPES(StdString); +STL_ORDERED_TYPES(Time); + +#define STL_UNORDERED_TYPES(value) \ + using stl_unordered_set_##value = std::unordered_set<value>; \ + using stl_unordered_map_##value = std::unordered_map<value, intptr_t>; \ + using flat_hash_set_##value = flat_hash_set<value>; \ + using flat_hash_map_##value = flat_hash_map<value, intptr_t>; \ + using stl_unordered_multiset_##value = std::unordered_multiset<value>; \ + using stl_unordered_multimap_##value = \ + std::unordered_multimap<value, intptr_t> + +#define STL_UNORDERED_TYPES_CUSTOM_HASH(value, hash) \ + using stl_unordered_set_##value = std::unordered_set<value, hash>; \ + using stl_unordered_map_##value = std::unordered_map<value, intptr_t, hash>; \ + using flat_hash_set_##value = flat_hash_set<value, hash>; \ + using flat_hash_map_##value = flat_hash_map<value, intptr_t, hash>; \ + using stl_unordered_multiset_##value = std::unordered_multiset<value, hash>; \ + using stl_unordered_multimap_##value = \ + std::unordered_multimap<value, intptr_t, hash> + +STL_UNORDERED_TYPES(int32_t); +STL_UNORDERED_TYPES(int64_t); +STL_UNORDERED_TYPES(StdString); +STL_UNORDERED_TYPES_CUSTOM_HASH(Time, absl::Hash<absl::Time>); + +#define BTREE_TYPES(value) \ + using btree_256_set_##value = \ + btree_set<value, std::less<value>, std::allocator<value>>; \ + using btree_256_map_##value = \ + btree_map<value, intptr_t, std::less<value>, \ + std::allocator<std::pair<const value, intptr_t>>>; \ + using btree_256_multiset_##value = \ + btree_multiset<value, std::less<value>, std::allocator<value>>; \ + using btree_256_multimap_##value = \ + btree_multimap<value, intptr_t, std::less<value>, \ + std::allocator<std::pair<const value, intptr_t>>> + +BTREE_TYPES(int32_t); +BTREE_TYPES(int64_t); +BTREE_TYPES(StdString); +BTREE_TYPES(Time); + +#define MY_BENCHMARK4(type, func) \ + void BM_##type##_##func(benchmark::State& state) { BM_##func<type>(state); } \ + BENCHMARK(BM_##type##_##func) + +#define MY_BENCHMARK3(type) \ + MY_BENCHMARK4(type, Insert); \ + MY_BENCHMARK4(type, InsertSorted); \ + MY_BENCHMARK4(type, InsertEnd); \ + MY_BENCHMARK4(type, Lookup); \ + MY_BENCHMARK4(type, FullLookup); \ + MY_BENCHMARK4(type, Delete); \ + MY_BENCHMARK4(type, DeleteRange); \ + MY_BENCHMARK4(type, QueueAddRem); \ + MY_BENCHMARK4(type, MixedAddRem); \ + MY_BENCHMARK4(type, Fifo); \ + MY_BENCHMARK4(type, FwdIter); \ + MY_BENCHMARK4(type, InsertRangeRandom); \ + MY_BENCHMARK4(type, InsertRangeSorted) + +#define MY_BENCHMARK2_SUPPORTS_MULTI_ONLY(type) \ + MY_BENCHMARK3(stl_##type); \ + MY_BENCHMARK3(stl_unordered_##type); \ + MY_BENCHMARK3(btree_256_##type) + +#define MY_BENCHMARK2(type) \ + MY_BENCHMARK2_SUPPORTS_MULTI_ONLY(type); \ + MY_BENCHMARK3(flat_hash_##type) + +// Define MULTI_TESTING to see benchmarks for multi-containers also. +// +// You can use --copt=-DMULTI_TESTING. +#ifdef MULTI_TESTING +#define MY_BENCHMARK(type) \ + MY_BENCHMARK2(set_##type); \ + MY_BENCHMARK2(map_##type); \ + MY_BENCHMARK2_SUPPORTS_MULTI_ONLY(multiset_##type); \ + MY_BENCHMARK2_SUPPORTS_MULTI_ONLY(multimap_##type) +#else +#define MY_BENCHMARK(type) \ + MY_BENCHMARK2(set_##type); \ + MY_BENCHMARK2(map_##type) +#endif + +MY_BENCHMARK(int32_t); +MY_BENCHMARK(int64_t); +MY_BENCHMARK(StdString); +MY_BENCHMARK(Time); + +// Define a type whose size and cost of moving are independently customizable. +// When sizeof(value_type) increases, we expect btree to no longer have as much +// cache-locality advantage over STL. When cost of moving increases, we expect +// btree to actually do more work than STL because it has to move values around +// and STL doesn't have to. +template <int Size, int Copies> +struct BigType { + BigType() : BigType(0) {} + explicit BigType(int x) { std::iota(values.begin(), values.end(), x); } + + void Copy(const BigType& x) { + for (int i = 0; i < Size && i < Copies; ++i) values[i] = x.values[i]; + // If Copies > Size, do extra copies. + for (int i = Size, idx = 0; i < Copies; ++i) { + int64_t tmp = x.values[idx]; + benchmark::DoNotOptimize(tmp); + idx = idx + 1 == Size ? 0 : idx + 1; + } + } + + BigType(const BigType& x) { Copy(x); } + BigType& operator=(const BigType& x) { + Copy(x); + return *this; + } + + // Compare only the first Copies elements if Copies is less than Size. + bool operator<(const BigType& other) const { + return std::lexicographical_compare( + values.begin(), values.begin() + std::min(Size, Copies), + other.values.begin(), other.values.begin() + std::min(Size, Copies)); + } + bool operator==(const BigType& other) const { + return std::equal(values.begin(), values.begin() + std::min(Size, Copies), + other.values.begin()); + } + + // Support absl::Hash. + template <typename State> + friend State AbslHashValue(State h, const BigType& b) { + for (int i = 0; i < Size && i < Copies; ++i) + h = State::combine(std::move(h), b.values[i]); + return h; + } + + std::array<int64_t, Size> values; +}; + +#define BIG_TYPE_BENCHMARKS(SIZE, COPIES) \ + using stl_set_size##SIZE##copies##COPIES = std::set<BigType<SIZE, COPIES>>; \ + using stl_map_size##SIZE##copies##COPIES = \ + std::map<BigType<SIZE, COPIES>, intptr_t>; \ + using stl_multiset_size##SIZE##copies##COPIES = \ + std::multiset<BigType<SIZE, COPIES>>; \ + using stl_multimap_size##SIZE##copies##COPIES = \ + std::multimap<BigType<SIZE, COPIES>, intptr_t>; \ + using stl_unordered_set_size##SIZE##copies##COPIES = \ + std::unordered_set<BigType<SIZE, COPIES>, \ + absl::Hash<BigType<SIZE, COPIES>>>; \ + using stl_unordered_map_size##SIZE##copies##COPIES = \ + std::unordered_map<BigType<SIZE, COPIES>, intptr_t, \ + absl::Hash<BigType<SIZE, COPIES>>>; \ + using flat_hash_set_size##SIZE##copies##COPIES = \ + flat_hash_set<BigType<SIZE, COPIES>>; \ + using flat_hash_map_size##SIZE##copies##COPIES = \ + flat_hash_map<BigType<SIZE, COPIES>, intptr_t>; \ + using stl_unordered_multiset_size##SIZE##copies##COPIES = \ + std::unordered_multiset<BigType<SIZE, COPIES>, \ + absl::Hash<BigType<SIZE, COPIES>>>; \ + using stl_unordered_multimap_size##SIZE##copies##COPIES = \ + std::unordered_multimap<BigType<SIZE, COPIES>, intptr_t, \ + absl::Hash<BigType<SIZE, COPIES>>>; \ + using btree_256_set_size##SIZE##copies##COPIES = \ + btree_set<BigType<SIZE, COPIES>>; \ + using btree_256_map_size##SIZE##copies##COPIES = \ + btree_map<BigType<SIZE, COPIES>, intptr_t>; \ + using btree_256_multiset_size##SIZE##copies##COPIES = \ + btree_multiset<BigType<SIZE, COPIES>>; \ + using btree_256_multimap_size##SIZE##copies##COPIES = \ + btree_multimap<BigType<SIZE, COPIES>, intptr_t>; \ + MY_BENCHMARK(size##SIZE##copies##COPIES) + +// Define BIG_TYPE_TESTING to see benchmarks for more big types. +// +// You can use --copt=-DBIG_TYPE_TESTING. +#ifndef NODESIZE_TESTING +#ifdef BIG_TYPE_TESTING +BIG_TYPE_BENCHMARKS(1, 4); +BIG_TYPE_BENCHMARKS(4, 1); +BIG_TYPE_BENCHMARKS(4, 4); +BIG_TYPE_BENCHMARKS(1, 8); +BIG_TYPE_BENCHMARKS(8, 1); +BIG_TYPE_BENCHMARKS(8, 8); +BIG_TYPE_BENCHMARKS(1, 16); +BIG_TYPE_BENCHMARKS(16, 1); +BIG_TYPE_BENCHMARKS(16, 16); +BIG_TYPE_BENCHMARKS(1, 32); +BIG_TYPE_BENCHMARKS(32, 1); +BIG_TYPE_BENCHMARKS(32, 32); +#else +BIG_TYPE_BENCHMARKS(32, 32); +#endif +#endif + +// Benchmark using unique_ptrs to large value types. In order to be able to use +// the same benchmark code as the other types, use a type that holds a +// unique_ptr and has a copy constructor. +template <int Size> +struct BigTypePtr { + BigTypePtr() : BigTypePtr(0) {} + explicit BigTypePtr(int x) { + ptr = absl::make_unique<BigType<Size, Size>>(x); + } + BigTypePtr(const BigTypePtr& x) { + ptr = absl::make_unique<BigType<Size, Size>>(*x.ptr); + } + BigTypePtr(BigTypePtr&& x) noexcept = default; + BigTypePtr& operator=(const BigTypePtr& x) { + ptr = absl::make_unique<BigType<Size, Size>>(*x.ptr); + } + BigTypePtr& operator=(BigTypePtr&& x) noexcept = default; + + bool operator<(const BigTypePtr& other) const { return *ptr < *other.ptr; } + bool operator==(const BigTypePtr& other) const { return *ptr == *other.ptr; } + + std::unique_ptr<BigType<Size, Size>> ptr; +}; + +template <int Size> +double ContainerInfo(const btree_set<BigTypePtr<Size>>& b) { + const double bytes_used = + b.bytes_used() + b.size() * sizeof(BigType<Size, Size>); + const double bytes_per_value = bytes_used / b.size(); + BtreeContainerInfoLog(b, bytes_used, bytes_per_value); + return bytes_per_value; +} +template <int Size> +double ContainerInfo(const btree_map<int, BigTypePtr<Size>>& b) { + const double bytes_used = + b.bytes_used() + b.size() * sizeof(BigType<Size, Size>); + const double bytes_per_value = bytes_used / b.size(); + BtreeContainerInfoLog(b, bytes_used, bytes_per_value); + return bytes_per_value; +} + +#define BIG_TYPE_PTR_BENCHMARKS(SIZE) \ + using stl_set_size##SIZE##copies##SIZE##ptr = std::set<BigType<SIZE, SIZE>>; \ + using stl_map_size##SIZE##copies##SIZE##ptr = \ + std::map<int, BigType<SIZE, SIZE>>; \ + using stl_unordered_set_size##SIZE##copies##SIZE##ptr = \ + std::unordered_set<BigType<SIZE, SIZE>, \ + absl::Hash<BigType<SIZE, SIZE>>>; \ + using stl_unordered_map_size##SIZE##copies##SIZE##ptr = \ + std::unordered_map<int, BigType<SIZE, SIZE>>; \ + using flat_hash_set_size##SIZE##copies##SIZE##ptr = \ + flat_hash_set<BigType<SIZE, SIZE>>; \ + using flat_hash_map_size##SIZE##copies##SIZE##ptr = \ + flat_hash_map<int, BigTypePtr<SIZE>>; \ + using btree_256_set_size##SIZE##copies##SIZE##ptr = \ + btree_set<BigTypePtr<SIZE>>; \ + using btree_256_map_size##SIZE##copies##SIZE##ptr = \ + btree_map<int, BigTypePtr<SIZE>>; \ + MY_BENCHMARK3(stl_set_size##SIZE##copies##SIZE##ptr); \ + MY_BENCHMARK3(stl_unordered_set_size##SIZE##copies##SIZE##ptr); \ + MY_BENCHMARK3(flat_hash_set_size##SIZE##copies##SIZE##ptr); \ + MY_BENCHMARK3(btree_256_set_size##SIZE##copies##SIZE##ptr); \ + MY_BENCHMARK3(stl_map_size##SIZE##copies##SIZE##ptr); \ + MY_BENCHMARK3(stl_unordered_map_size##SIZE##copies##SIZE##ptr); \ + MY_BENCHMARK3(flat_hash_map_size##SIZE##copies##SIZE##ptr); \ + MY_BENCHMARK3(btree_256_map_size##SIZE##copies##SIZE##ptr) + +BIG_TYPE_PTR_BENCHMARKS(32); + +} // namespace +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index b1c686edf28c..0d3d604ca50f 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -625,7 +625,7 @@ class raw_hash_set { // PRECONDITION: not an end() iterator. iterator& operator++() { - /* To be enabled: assert_is_full(); */ + assert_is_full(); ++ctrl_; ++slot_; skip_empty_or_deleted(); @@ -1084,10 +1084,15 @@ class raw_hash_set { // Extension API: support for lazy emplace. // // Looks up key in the table. If found, returns the iterator to the element. - // Otherwise calls f with one argument of type raw_hash_set::constructor. f - // MUST call raw_hash_set::constructor with arguments as if a - // raw_hash_set::value_type is constructed, otherwise the behavior is - // undefined. + // Otherwise calls `f` with one argument of type `raw_hash_set::constructor`. + // + // `f` must abide by several restrictions: + // - it MUST call `raw_hash_set::constructor` with arguments as if a + // `raw_hash_set::value_type` is constructed, + // - it MUST NOT access the container before the call to + // `raw_hash_set::constructor`, and + // - it MUST NOT erase the lazily emplaced element. + // Doing any of these is undefined behavior. // // For example: // diff --git a/absl/flags/marshalling.h b/absl/flags/marshalling.h index 1f3dc2dcb9dd..0b5033547e97 100644 --- a/absl/flags/marshalling.h +++ b/absl/flags/marshalling.h @@ -33,16 +33,16 @@ // * `double` // * `std::string` // * `std::vector<std::string>` -// * `absl::LogSeverity` (provided here due to dependency ordering) +// * `absl::LogSeverity` (provided natively for layering reasons) // // Note that support for integral types is implemented using overloads for // variable-width fundamental types (`short`, `int`, `long`, etc.). However, // you should prefer the fixed-width integral types (`int32_t`, `uint64_t`, // etc.) we've noted above within flag definitions. - // // In addition, several Abseil libraries provide their own custom support for -// Abseil flags. +// Abseil flags. Documentation for these formats is provided in the type's +// `AbslParseFlag()` definition. // // The Abseil time library provides the following support for civil time values: // diff --git a/absl/strings/internal/str_format/extension.h b/absl/strings/internal/str_format/extension.h index 5726ea5c100b..51d7dd6fcf2b 100644 --- a/absl/strings/internal/str_format/extension.h +++ b/absl/strings/internal/str_format/extension.h @@ -27,9 +27,6 @@ namespace absl { ABSL_NAMESPACE_BEGIN - -class Cord; - namespace str_format_internal { class FormatRawSinkImpl { diff --git a/absl/strings/numbers.cc b/absl/strings/numbers.cc index caab463161eb..a0e5a7fd4e7d 100644 --- a/absl/strings/numbers.cc +++ b/absl/strings/numbers.cc @@ -30,6 +30,7 @@ #include <memory> #include <utility> +#include "absl/base/attributes.h" #include "absl/base/internal/bits.h" #include "absl/base/internal/raw_logging.h" #include "absl/strings/ascii.h" @@ -719,8 +720,8 @@ inline bool safe_parse_sign_and_base(absl::string_view* text /*inout*/, // commonly used bases. template <typename IntType> struct LookupTables { - static const IntType kVmaxOverBase[]; - static const IntType kVminOverBase[]; + ABSL_CONST_INIT static const IntType kVmaxOverBase[]; + ABSL_CONST_INIT static const IntType kVminOverBase[]; }; // An array initializer macro for X/base where base in [0, 36]. @@ -735,6 +736,49 @@ struct LookupTables { X / 35, X / 36, \ } +// uint128& operator/=(uint128) is not constexpr, so hardcode the resulting +// array to avoid a static initializer. +template <> +const uint128 LookupTables<uint128>::kVmaxOverBase[] = { + 0, + 0, + MakeUint128(9223372036854775807u, 18446744073709551615u), + MakeUint128(6148914691236517205u, 6148914691236517205u), + MakeUint128(4611686018427387903u, 18446744073709551615u), + MakeUint128(3689348814741910323u, 3689348814741910323u), + MakeUint128(3074457345618258602u, 12297829382473034410u), + MakeUint128(2635249153387078802u, 5270498306774157604u), + MakeUint128(2305843009213693951u, 18446744073709551615u), + MakeUint128(2049638230412172401u, 14347467612885206812u), + MakeUint128(1844674407370955161u, 11068046444225730969u), + MakeUint128(1676976733973595601u, 8384883669867978007u), + MakeUint128(1537228672809129301u, 6148914691236517205u), + MakeUint128(1418980313362273201u, 4256940940086819603u), + MakeUint128(1317624576693539401u, 2635249153387078802u), + MakeUint128(1229782938247303441u, 1229782938247303441u), + MakeUint128(1152921504606846975u, 18446744073709551615u), + MakeUint128(1085102592571150095u, 1085102592571150095u), + MakeUint128(1024819115206086200u, 16397105843297379214u), + MakeUint128(970881267037344821u, 16504981539634861972u), + MakeUint128(922337203685477580u, 14757395258967641292u), + MakeUint128(878416384462359600u, 14054662151397753612u), + MakeUint128(838488366986797800u, 13415813871788764811u), + MakeUint128(802032351030850070u, 4812194106185100421u), + MakeUint128(768614336404564650u, 12297829382473034410u), + MakeUint128(737869762948382064u, 11805916207174113034u), + MakeUint128(709490156681136600u, 11351842506898185609u), + MakeUint128(683212743470724133u, 17080318586768103348u), + MakeUint128(658812288346769700u, 10540996613548315209u), + MakeUint128(636094623231363848u, 15266270957552732371u), + MakeUint128(614891469123651720u, 9838263505978427528u), + MakeUint128(595056260442243600u, 9520900167075897608u), + MakeUint128(576460752303423487u, 18446744073709551615u), + MakeUint128(558992244657865200u, 8943875914525843207u), + MakeUint128(542551296285575047u, 9765923333140350855u), + MakeUint128(527049830677415760u, 8432797290838652167u), + MakeUint128(512409557603043100u, 8198552921648689607u), +}; + template <typename IntType> const IntType LookupTables<IntType>::kVmaxOverBase[] = X_OVER_BASE_INITIALIZER(std::numeric_limits<IntType>::max()); @@ -754,6 +798,8 @@ inline bool safe_parse_positive_int(absl::string_view text, int base, assert(base >= 0); assert(vmax >= static_cast<IntType>(base)); const IntType vmax_over_base = LookupTables<IntType>::kVmaxOverBase[base]; + assert(base < 2 || + std::numeric_limits<IntType>::max() / base == vmax_over_base); const char* start = text.data(); const char* end = start + text.size(); // loop over digits @@ -787,6 +833,8 @@ inline bool safe_parse_negative_int(absl::string_view text, int base, assert(vmin < 0); assert(vmin <= 0 - base); IntType vmin_over_base = LookupTables<IntType>::kVminOverBase[base]; + assert(base < 2 || + std::numeric_limits<IntType>::min() / base == vmin_over_base); // 2003 c++ standard [expr.mul] // "... the sign of the remainder is implementation-defined." // Although (vmin/base)*base + vmin%base is always vmin. diff --git a/absl/time/internal/cctz/src/zone_info_source.cc b/absl/time/internal/cctz/src/zone_info_source.cc index 619ac1fbd0b8..98ea16126782 100644 --- a/absl/time/internal/cctz/src/zone_info_source.cc +++ b/absl/time/internal/cctz/src/zone_info_source.cc @@ -66,13 +66,41 @@ extern ZoneInfoSourceFactory zone_info_source_factory; extern ZoneInfoSourceFactory default_factory; ZoneInfoSourceFactory default_factory = DefaultFactory; #if defined(_M_IX86) -#pragma comment( \ - linker, \ - "/alternatename:?zone_info_source_factory@cctz_extension@time_internal@absl@@3P6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@absl@@U?$default_delete@VZoneInfoSource@cctz@time_internal@absl@@@std@@@std@@ABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@5@ABV?$function@$$A6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@absl@@U?$default_delete@VZoneInfoSource@cctz@time_internal@absl@@@std@@@std@@ABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@2@@Z@5@@ZA=?default_factory@cctz_extension@time_internal@absl@@3P6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@absl@@U?$default_delete@VZoneInfoSource@cctz@time_internal@absl@@@std@@@std@@ABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@5@ABV?$function@$$A6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@absl@@U?$default_delete@VZoneInfoSource@cctz@time_internal@absl@@@std@@@std@@ABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@2@@Z@5@@ZA") +#pragma comment( \ + linker, \ + "/alternatename:?zone_info_source_factory@cctz_extension@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@3P6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@U?$default_delete@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@@std@@@std@@ABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@" ABSL_INTERNAL_MANGLED_BACKREFERENCE \ + "@ABV?$function@$$A6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@U?$default_delete@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@@std@@@std@@ABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@2@@Z@" ABSL_INTERNAL_MANGLED_BACKREFERENCE \ + "@@ZA=?default_factory@cctz_extension@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@3P6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@U?$default_delete@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@@std@@@std@@ABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@" ABSL_INTERNAL_MANGLED_BACKREFERENCE \ + "@ABV?$function@$$A6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@U?$default_delete@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@@std@@@std@@ABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@2@@Z@" ABSL_INTERNAL_MANGLED_BACKREFERENCE \ + "@@ZA") #elif defined(_M_IA_64) || defined(_M_AMD64) || defined(_M_ARM64) -#pragma comment( \ - linker, \ - "/alternatename:?zone_info_source_factory@cctz_extension@time_internal@absl@@3P6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@absl@@U?$default_delete@VZoneInfoSource@cctz@time_internal@absl@@@std@@@std@@AEBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@5@AEBV?$function@$$A6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@absl@@U?$default_delete@VZoneInfoSource@cctz@time_internal@absl@@@std@@@std@@AEBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@2@@Z@5@@ZEA=?default_factory@cctz_extension@time_internal@absl@@3P6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@absl@@U?$default_delete@VZoneInfoSource@cctz@time_internal@absl@@@std@@@std@@AEBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@5@AEBV?$function@$$A6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@absl@@U?$default_delete@VZoneInfoSource@cctz@time_internal@absl@@@std@@@std@@AEBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@2@@Z@5@@ZEA") +#pragma comment( \ + linker, \ + "/alternatename:?zone_info_source_factory@cctz_extension@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@3P6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@U?$default_delete@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@@std@@@std@@AEBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@" ABSL_INTERNAL_MANGLED_BACKREFERENCE \ + "@AEBV?$function@$$A6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@U?$default_delete@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@@std@@@std@@AEBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@2@@Z@" ABSL_INTERNAL_MANGLED_BACKREFERENCE \ + "@@ZEA=?default_factory@cctz_extension@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@3P6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@U?$default_delete@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@@std@@@std@@AEBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@" ABSL_INTERNAL_MANGLED_BACKREFERENCE \ + "@AEBV?$function@$$A6A?AV?$unique_ptr@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@U?$default_delete@VZoneInfoSource@cctz@time_internal@" ABSL_INTERNAL_MANGLED_NS \ + "@@@std@@@std@@AEBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@2@@Z@" ABSL_INTERNAL_MANGLED_BACKREFERENCE \ + "@@ZEA") #else #error Unsupported MSVC platform #endif // _M_<PLATFORM> diff --git a/absl/time/time.h b/absl/time/time.h index 7507b0cd4080..1be5727c0dbc 100644 --- a/absl/time/time.h +++ b/absl/time/time.h @@ -527,30 +527,59 @@ std::chrono::seconds ToChronoSeconds(Duration d); std::chrono::minutes ToChronoMinutes(Duration d); std::chrono::hours ToChronoHours(Duration d); + // FormatDuration() // -// Returns a string representing the duration in the form "72h3m0.5s". -// Returns "inf" or "-inf" for +/- `InfiniteDuration()`. +// Returns a string represention of the duration in a format consisting of a +// possibly-signed prefix and a sequence of decimal numbers, each with an +// optional fractional part and a unit suffix. +// +// Valid unit suffixes are "ns", "us" "ms", "s", "m", and "h". +// +// Simple examples include "300ms", "-1.5h", and "2h45m". Returns "inf" or +// "-inf" for +/- `InfiniteDuration()` values and "0" for `ZeroDuration()` +// values. +// +// This string format is used both as an input for parsing (when handling +// command-line flags of type `absl::Duration`) and as an output in +// `FormatDuration()` std::string FormatDuration(Duration d); -// Output stream operator. -inline std::ostream& operator<<(std::ostream& os, Duration d) { - return os << FormatDuration(d); -} - // ParseDuration() // -// Parses a duration string consisting of a possibly signed sequence of -// decimal numbers, each with an optional fractional part and a unit -// suffix. The valid suffixes are "ns", "us" "ms", "s", "m", and "h". -// Simple examples include "300ms", "-1.5h", and "2h45m". Parses "0" as -// `ZeroDuration()`. Parses "inf" and "-inf" as +/- `InfiniteDuration()`. +// Parses a `dur_string` of the format noted above into an `absl::Duration` +// value. +// +// Parses "0" as a zero-length duration value. Parses "-inf" or "+inf" as +// infinite durations values. bool ParseDuration(const std::string& dur_string, Duration* d); -// Support for flag values of type Duration. Duration flags must be specified -// in a format that is valid input for absl::ParseDuration(). +// AbslParseFlag() +// +// Parses the command-line flag string representation `text` (using the format +// noted above) into an `absl::Duration` destination, setting `error` on +// failure. +// +// Example: +// +// --timeout=6h30m +// --timeout=inf // Equivalent to `InfiniteDuration()` +// --timeout=0 // Equivalent to `ZeroDuration()` bool AbslParseFlag(absl::string_view text, Duration* dst, std::string* error); + +// AbslUnparseFlag() +// +// Unparses an `absl::Duration` into a command-line string representation using +// the format noted above. std::string AbslUnparseFlag(Duration d); + +// operator<<() +// +// Output stream operator, returning a stream in the format noted above. +inline std::ostream& operator<<(std::ostream& os, Duration d) { + return os << FormatDuration(d); +} + ABSL_DEPRECATED("Use AbslParseFlag() instead.") bool ParseFlag(const std::string& text, Duration* dst, std::string* error); ABSL_DEPRECATED("Use AbslUnparseFlag() instead.") @@ -813,18 +842,29 @@ Time FromChrono(const std::chrono::system_clock::time_point& tp); // // tp == std::chrono::system_clock::from_time_t(123); std::chrono::system_clock::time_point ToChronoTime(Time); -// Support for flag values of type Time. Time flags must be specified in a -// format that matches absl::RFC3339_full. For example: +// AbslParseFlag() +// +// Parses the command-line flag string representation `text` into an +// `absl::Time` destination, setting `error` on failure. Time flag string +// representations must be specified in a format that matches +// `absl::RFC3339_full`. +// +// Example: // // --start_time=2016-01-02T03:04:05.678+08:00 // // Note: A UTC offset (or 'Z' indicating a zero-offset from UTC) is required. // // Additionally, if you'd like to specify a time as a count of -// seconds/milliseconds/etc from the Unix epoch, use an absl::Duration flag -// and add that duration to absl::UnixEpoch() to get an absl::Time. +// seconds/milliseconds/etc from the Unix epoch, use an `absl::Duration` flag +// and add that duration to `absl::UnixEpoch()` to get an `absl::Time`. bool AbslParseFlag(absl::string_view text, Time* t, std::string* error); + +// AbslUnparseFlag() +// +// Unparses an `absl::Time` into a command-line string format as noted above. std::string AbslUnparseFlag(Time t); + ABSL_DEPRECATED("Use AbslParseFlag() instead.") bool ParseFlag(const std::string& text, Time* t, std::string* error); ABSL_DEPRECATED("Use AbslUnparseFlag() instead.") diff --git a/absl/types/compare.h b/absl/types/compare.h index c29ced5273a2..62ca70f9a704 100644 --- a/absl/types/compare.h +++ b/absl/types/compare.h @@ -176,6 +176,14 @@ class weak_equality weak_equality v) noexcept { return 0 != v.value_; } + friend constexpr bool operator==(weak_equality v1, + weak_equality v2) noexcept { + return v1.value_ == v2.value_; + } + friend constexpr bool operator!=(weak_equality v1, + weak_equality v2) noexcept { + return v1.value_ != v2.value_; + } private: compare_internal::value_type value_; @@ -219,6 +227,14 @@ class strong_equality strong_equality v) noexcept { return 0 != v.value_; } + friend constexpr bool operator==(strong_equality v1, + strong_equality v2) noexcept { + return v1.value_ == v2.value_; + } + friend constexpr bool operator!=(strong_equality v1, + strong_equality v2) noexcept { + return v1.value_ != v2.value_; + } private: compare_internal::value_type value_; @@ -306,6 +322,14 @@ class partial_ordering partial_ordering v) noexcept { return v.is_ordered() && 0 >= v.value_; } + friend constexpr bool operator==(partial_ordering v1, + partial_ordering v2) noexcept { + return v1.value_ == v2.value_; + } + friend constexpr bool operator!=(partial_ordering v1, + partial_ordering v2) noexcept { + return v1.value_ != v2.value_; + } private: compare_internal::value_type value_; @@ -390,6 +414,14 @@ class weak_ordering weak_ordering v) noexcept { return 0 >= v.value_; } + friend constexpr bool operator==(weak_ordering v1, + weak_ordering v2) noexcept { + return v1.value_ == v2.value_; + } + friend constexpr bool operator!=(weak_ordering v1, + weak_ordering v2) noexcept { + return v1.value_ != v2.value_; + } private: compare_internal::value_type value_; @@ -481,6 +513,14 @@ class strong_ordering strong_ordering v) noexcept { return 0 >= v.value_; } + friend constexpr bool operator==(strong_ordering v1, + strong_ordering v2) noexcept { + return v1.value_ == v2.value_; + } + friend constexpr bool operator!=(strong_ordering v1, + strong_ordering v2) noexcept { + return v1.value_ != v2.value_; + } private: compare_internal::value_type value_; diff --git a/absl/types/compare_test.cc b/absl/types/compare_test.cc index 955844b529bb..8095baf9569f 100644 --- a/absl/types/compare_test.cc +++ b/absl/types/compare_test.cc @@ -31,6 +31,15 @@ TEST(Compare, WeakEquality) { EXPECT_TRUE(Identity(0 == weak_equality::equivalent)); EXPECT_TRUE(Identity(weak_equality::nonequivalent != 0)); EXPECT_TRUE(Identity(0 != weak_equality::nonequivalent)); + const weak_equality values[] = {weak_equality::equivalent, + weak_equality::nonequivalent}; + for (const auto& lhs : values) { + for (const auto& rhs : values) { + const bool are_equal = &lhs == &rhs; + EXPECT_EQ(lhs == rhs, are_equal); + EXPECT_EQ(lhs != rhs, !are_equal); + } + } } TEST(Compare, StrongEquality) { @@ -42,6 +51,18 @@ TEST(Compare, StrongEquality) { EXPECT_TRUE(Identity(0 == strong_equality::equivalent)); EXPECT_TRUE(Identity(strong_equality::nonequivalent != 0)); EXPECT_TRUE(Identity(0 != strong_equality::nonequivalent)); + const strong_equality values[] = {strong_equality::equal, + strong_equality::nonequal}; + for (const auto& lhs : values) { + for (const auto& rhs : values) { + const bool are_equal = &lhs == &rhs; + EXPECT_EQ(lhs == rhs, are_equal); + EXPECT_EQ(lhs != rhs, !are_equal); + } + } + EXPECT_TRUE(Identity(strong_equality::equivalent == strong_equality::equal)); + EXPECT_TRUE( + Identity(strong_equality::nonequivalent == strong_equality::nonequal)); } TEST(Compare, PartialOrdering) { @@ -65,6 +86,16 @@ TEST(Compare, PartialOrdering) { EXPECT_FALSE(Identity(0 > partial_ordering::unordered)); EXPECT_FALSE(Identity(partial_ordering::unordered >= 0)); EXPECT_FALSE(Identity(0 >= partial_ordering::unordered)); + const partial_ordering values[] = { + partial_ordering::less, partial_ordering::equivalent, + partial_ordering::greater, partial_ordering::unordered}; + for (const auto& lhs : values) { + for (const auto& rhs : values) { + const bool are_equal = &lhs == &rhs; + EXPECT_EQ(lhs == rhs, are_equal); + EXPECT_EQ(lhs != rhs, !are_equal); + } + } } TEST(Compare, WeakOrdering) { @@ -78,6 +109,15 @@ TEST(Compare, WeakOrdering) { EXPECT_TRUE(Identity(0 < weak_ordering::greater)); EXPECT_TRUE(Identity(weak_ordering::greater >= 0)); EXPECT_TRUE(Identity(0 <= weak_ordering::greater)); + const weak_ordering values[] = { + weak_ordering::less, weak_ordering::equivalent, weak_ordering::greater}; + for (const auto& lhs : values) { + for (const auto& rhs : values) { + const bool are_equal = &lhs == &rhs; + EXPECT_EQ(lhs == rhs, are_equal); + EXPECT_EQ(lhs != rhs, !are_equal); + } + } } TEST(Compare, StrongOrdering) { @@ -93,6 +133,16 @@ TEST(Compare, StrongOrdering) { EXPECT_TRUE(Identity(0 < strong_ordering::greater)); EXPECT_TRUE(Identity(strong_ordering::greater >= 0)); EXPECT_TRUE(Identity(0 <= strong_ordering::greater)); + const strong_ordering values[] = { + strong_ordering::less, strong_ordering::equal, strong_ordering::greater}; + for (const auto& lhs : values) { + for (const auto& rhs : values) { + const bool are_equal = &lhs == &rhs; + EXPECT_EQ(lhs == rhs, are_equal); + EXPECT_EQ(lhs != rhs, !are_equal); + } + } + EXPECT_TRUE(Identity(strong_ordering::equivalent == strong_ordering::equal)); } TEST(Compare, Conversions) { @@ -190,7 +240,7 @@ TEST(Compare, Conversions) { struct WeakOrderingLess { template <typename T> - absl::weak_ordering operator()(const T &a, const T &b) const { + absl::weak_ordering operator()(const T& a, const T& b) const { return a < b ? absl::weak_ordering::less : a == b ? absl::weak_ordering::equivalent : absl::weak_ordering::greater; @@ -224,10 +274,10 @@ TEST(DoLessThanComparison, SanityTest) { } TEST(CompareResultAsOrdering, SanityTest) { - EXPECT_TRUE(Identity( - absl::compare_internal::compare_result_as_ordering(-1) < 0)); - EXPECT_FALSE(Identity( - absl::compare_internal::compare_result_as_ordering(-1) == 0)); + EXPECT_TRUE( + Identity(absl::compare_internal::compare_result_as_ordering(-1) < 0)); + EXPECT_FALSE( + Identity(absl::compare_internal::compare_result_as_ordering(-1) == 0)); EXPECT_FALSE( Identity(absl::compare_internal::compare_result_as_ordering(-1) > 0)); EXPECT_TRUE(Identity(absl::compare_internal::compare_result_as_ordering( @@ -237,31 +287,31 @@ TEST(CompareResultAsOrdering, SanityTest) { EXPECT_FALSE(Identity(absl::compare_internal::compare_result_as_ordering( weak_ordering::less) > 0)); - EXPECT_FALSE(Identity( - absl::compare_internal::compare_result_as_ordering(0) < 0)); - EXPECT_TRUE(Identity( - absl::compare_internal::compare_result_as_ordering(0) == 0)); - EXPECT_FALSE(Identity( - absl::compare_internal::compare_result_as_ordering(0) > 0)); + EXPECT_FALSE( + Identity(absl::compare_internal::compare_result_as_ordering(0) < 0)); + EXPECT_TRUE( + Identity(absl::compare_internal::compare_result_as_ordering(0) == 0)); + EXPECT_FALSE( + Identity(absl::compare_internal::compare_result_as_ordering(0) > 0)); EXPECT_FALSE(Identity(absl::compare_internal::compare_result_as_ordering( - weak_ordering::equivalent) < 0)); + weak_ordering::equivalent) < 0)); EXPECT_TRUE(Identity(absl::compare_internal::compare_result_as_ordering( - weak_ordering::equivalent) == 0)); + weak_ordering::equivalent) == 0)); EXPECT_FALSE(Identity(absl::compare_internal::compare_result_as_ordering( weak_ordering::equivalent) > 0)); - EXPECT_FALSE(Identity( - absl::compare_internal::compare_result_as_ordering(1) < 0)); - EXPECT_FALSE(Identity( - absl::compare_internal::compare_result_as_ordering(1) == 0)); - EXPECT_TRUE(Identity( - absl::compare_internal::compare_result_as_ordering(1) > 0)); + EXPECT_FALSE( + Identity(absl::compare_internal::compare_result_as_ordering(1) < 0)); + EXPECT_FALSE( + Identity(absl::compare_internal::compare_result_as_ordering(1) == 0)); + EXPECT_TRUE( + Identity(absl::compare_internal::compare_result_as_ordering(1) > 0)); EXPECT_FALSE(Identity(absl::compare_internal::compare_result_as_ordering( - weak_ordering::greater) < 0)); + weak_ordering::greater) < 0)); EXPECT_FALSE(Identity(absl::compare_internal::compare_result_as_ordering( weak_ordering::greater) == 0)); EXPECT_TRUE(Identity(absl::compare_internal::compare_result_as_ordering( - weak_ordering::greater) > 0)); + weak_ordering::greater) > 0)); } TEST(DoThreeWayComparison, SanityTest) { |