diff --git a/CMakeLists.txt b/CMakeLists.txt index 744241e..89a3386 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt
@@ -13,7 +13,10 @@ # See the License for the specific language governing permissions and # limitations under the License. # -cmake_minimum_required(VERSION 2.8.12) + +# We require 3.0 for modern, target-based CMake. We require 3.1 for the use of +# CXX_STANDARD in our targets. +cmake_minimum_required(VERSION 3.1) project(absl) list(APPEND CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/CMake)
diff --git a/absl/base/BUILD.bazel b/absl/base/BUILD.bazel index 5c05c67..3d3c7ae 100644 --- a/absl/base/BUILD.bazel +++ b/absl/base/BUILD.bazel
@@ -102,6 +102,7 @@ cc_library( name = "base_internal", hdrs = [ + "internal/hide_ptr.h", "internal/identity.h", "internal/inline_variable.h", "internal/invoke.h",
diff --git a/absl/base/CMakeLists.txt b/absl/base/CMakeLists.txt index 4564056..303533e 100644 --- a/absl/base/CMakeLists.txt +++ b/absl/base/CMakeLists.txt
@@ -36,6 +36,7 @@ "internal/endian.h" "internal/exception_testing.h" "internal/exception_safety_testing.h" + "internal/hide_ptr.h" "internal/identity.h" "internal/invoke.h" "internal/inline_variable.h"
diff --git a/absl/base/internal/hide_ptr.h b/absl/base/internal/hide_ptr.h new file mode 100644 index 0000000..2c2e11f --- /dev/null +++ b/absl/base/internal/hide_ptr.h
@@ -0,0 +1,49 @@ +// 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 +// +// http://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. + +#ifndef ABSL_BASE_INTERNAL_HIDE_PTR_H_ +#define ABSL_BASE_INTERNAL_HIDE_PTR_H_ + +#include <cstdint> + +namespace absl { +namespace base_internal { + +// Arbitrary value with high bits set. Xor'ing with it is unlikely +// to map one valid pointer to another valid pointer. +constexpr uintptr_t HideMask() { + static_assert(sizeof(uintptr_t) == 4 || sizeof(uintptr_t) == 8, + "uintptr_t must be 32 or 64 bits"); + return sizeof(uintptr_t) == 8 ? 0xF03A5F7BF03A5F7BULL : 0xF03A5F7BUL; +} + +// Hide a pointer from the leak checker. For internal use only. +// Differs from absl::IgnoreLeak(ptr) in that absl::IgnoreLeak(ptr) causes ptr +// and all objects reachable from ptr to be ignored by the leak checker. +template <class T> +inline uintptr_t HidePtr(T* ptr) { + return reinterpret_cast<uintptr_t>(ptr) ^ HideMask(); +} + +// Return a pointer that has been hidden from the leak checker. +// For internal use only. +template <class T> +inline T* UnhidePtr(uintptr_t hidden) { + return reinterpret_cast<T*>(hidden ^ HideMask()); +} + +} // namespace base_internal +} // namespace absl + +#endif // ABSL_BASE_INTERNAL_HIDE_PTR_H_
diff --git a/absl/debugging/failure_signal_handler.cc b/absl/debugging/failure_signal_handler.cc index 46ef7b8..4c131fe 100644 --- a/absl/debugging/failure_signal_handler.cc +++ b/absl/debugging/failure_signal_handler.cc
@@ -158,6 +158,8 @@ #endif +#ifdef ABSL_HAVE_SIGACTION + // Sets up an alternate stack for signal handlers once. // Returns the appropriate flag for sig_action.sa_flags // if the system supports using an alternate stack. @@ -170,8 +172,6 @@ #endif } -#ifdef ABSL_HAVE_SIGACTION - static void InstallOneFailureHandler(FailureSignalData* data, void (*handler)(int, siginfo_t*, void*)) { struct sigaction act;
diff --git a/absl/memory/memory.h b/absl/memory/memory.h index 2220ee4..055d88e 100644 --- a/absl/memory/memory.h +++ b/absl/memory/memory.h
@@ -40,7 +40,8 @@ // ----------------------------------------------------------------------------- // // Adopts ownership from a raw pointer and transfers it to the returned -// `std::unique_ptr`, whose type is deduced. +// `std::unique_ptr`, whose type is deduced. DO NOT specify the template type T +// when calling WrapUnique. // // Example: // X* NewX(int, int);
diff --git a/absl/numeric/BUILD.bazel b/absl/numeric/BUILD.bazel index 4a24a87..0791145 100644 --- a/absl/numeric/BUILD.bazel +++ b/absl/numeric/BUILD.bazel
@@ -1,3 +1,17 @@ +# 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 +# +# http://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. + load( "//absl:copts.bzl", "ABSL_DEFAULT_COPTS",
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 1e52312..28cf2d2 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel
@@ -13,10 +13,6 @@ # See the License for the specific language governing permissions and # limitations under the License. # -# -*- mode: python; -*- -# Libraries in this low-level package may not depend on libraries in packages -# that are not low level. For more information, including how to submit -# changes to this file, see http://www/eng/howto/build-monitors.html load( "//absl:copts.bzl", @@ -173,6 +169,20 @@ ) cc_test( + name = "string_view_benchmark", + srcs = ["string_view_benchmark.cc"], + copts = ABSL_TEST_COPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":strings", + "//absl/base", + "//absl/base:core_headers", + "@com_github_google_benchmark//:benchmark", + ], +) + +cc_test( name = "string_view_test", size = "small", srcs = ["string_view_test.cc"], @@ -201,6 +211,19 @@ ) cc_test( + name = "str_replace_benchmark", + srcs = ["str_replace_benchmark.cc"], + copts = ABSL_TEST_COPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":strings", + "//absl/base", + "@com_github_google_benchmark//:benchmark", + ], +) + +cc_test( name = "str_replace_test", size = "small", srcs = ["str_replace_test.cc"], @@ -226,6 +249,19 @@ ) cc_test( + name = "str_split_benchmark", + srcs = ["str_split_benchmark.cc"], + copts = ABSL_TEST_COPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":strings", + "//absl/base", + "@com_github_google_benchmark//:benchmark", + ], +) + +cc_test( name = "ostringstream_test", size = "small", srcs = ["internal/ostringstream_test.cc"], @@ -268,6 +304,19 @@ ) cc_test( + name = "str_join_benchmark", + srcs = ["str_join_benchmark.cc"], + copts = ABSL_TEST_COPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":strings", + "//absl/memory", + "@com_github_google_benchmark//:benchmark", + ], +) + +cc_test( name = "str_cat_test", size = "small", srcs = ["str_cat_test.cc"], @@ -281,6 +330,18 @@ ) cc_test( + name = "str_cat_benchmark", + srcs = ["str_cat_benchmark.cc"], + copts = ABSL_TEST_COPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":strings", + "@com_github_google_benchmark//:benchmark", + ], +) + +cc_test( name = "numbers_test", size = "small", srcs = [
diff --git a/absl/strings/numbers.h b/absl/strings/numbers.h index adf706a..75925e6 100644 --- a/absl/strings/numbers.h +++ b/absl/strings/numbers.h
@@ -124,17 +124,11 @@ } } -} // namespace numbers_internal - -// SimpleAtoi() -// -// Converts a std::string to an integer, using `safe_strto?()` functions for actual -// parsing, returning `true` if successful. The `safe_strto?()` functions apply -// strict checking; the std::string must be a base-10 integer, optionally followed or -// preceded by ASCII whitespace, with a value in the range of the corresponding -// integer type. +// Implementation of SimpleAtoi, generalized to support arbitrary base (used +// with base different from 10 elsewhere in Abseil implementation). template <typename int_type> -ABSL_MUST_USE_RESULT bool SimpleAtoi(absl::string_view s, int_type* out) { +ABSL_MUST_USE_RESULT bool safe_strtoi_base(absl::string_view s, int_type* out, + int base) { static_assert(sizeof(*out) == 4 || sizeof(*out) == 8, "SimpleAtoi works only with 32-bit or 64-bit integers."); static_assert(!std::is_floating_point<int_type>::value, @@ -146,27 +140,41 @@ if (static_cast<int_type>(1) - 2 < 0) { // Signed if (sizeof(*out) == 64 / 8) { // 64-bit int64_t val; - parsed = numbers_internal::safe_strto64_base(s, &val, 10); + parsed = numbers_internal::safe_strto64_base(s, &val, base); *out = static_cast<int_type>(val); } else { // 32-bit int32_t val; - parsed = numbers_internal::safe_strto32_base(s, &val, 10); + parsed = numbers_internal::safe_strto32_base(s, &val, base); *out = static_cast<int_type>(val); } } else { // Unsigned if (sizeof(*out) == 64 / 8) { // 64-bit uint64_t val; - parsed = numbers_internal::safe_strtou64_base(s, &val, 10); + parsed = numbers_internal::safe_strtou64_base(s, &val, base); *out = static_cast<int_type>(val); } else { // 32-bit uint32_t val; - parsed = numbers_internal::safe_strtou32_base(s, &val, 10); + parsed = numbers_internal::safe_strtou32_base(s, &val, base); *out = static_cast<int_type>(val); } } return parsed; } +} // namespace numbers_internal + +// SimpleAtoi() +// +// Converts a std::string to an integer, using `safe_strto?()` functions for actual +// parsing, returning `true` if successful. The `safe_strto?()` functions apply +// strict checking; the std::string must be a base-10 integer, optionally followed or +// preceded by ASCII whitespace, with a value in the range of the corresponding +// integer type. +template <typename int_type> +ABSL_MUST_USE_RESULT bool SimpleAtoi(absl::string_view s, int_type* out) { + return numbers_internal::safe_strtoi_base(s, out, 10); +} + } // namespace absl #endif // ABSL_STRINGS_NUMBERS_H_
diff --git a/absl/strings/str_cat_benchmark.cc b/absl/strings/str_cat_benchmark.cc new file mode 100644 index 0000000..1791410 --- /dev/null +++ b/absl/strings/str_cat_benchmark.cc
@@ -0,0 +1,142 @@ +// 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 +// +// http://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 "absl/strings/str_cat.h" + +#include <cstdint> +#include <string> + +#include "benchmark/benchmark.h" +#include "absl/strings/substitute.h" + +namespace { + +const char kStringOne[] = "Once Upon A Time, "; +const char kStringTwo[] = "There was a std::string benchmark"; + +// We want to include negative numbers in the benchmark, so this function +// is used to count 0, 1, -1, 2, -2, 3, -3, ... +inline int IncrementAlternatingSign(int i) { + return i > 0 ? -i : 1 - i; +} + +void BM_Sum_By_StrCat(benchmark::State& state) { + int i = 0; + char foo[100]; + for (auto _ : state) { + // NOLINTNEXTLINE(runtime/printf) + strcpy(foo, absl::StrCat(kStringOne, i, kStringTwo, i * 65536ULL).c_str()); + int sum = 0; + for (char* f = &foo[0]; *f != 0; ++f) { + sum += *f; + } + benchmark::DoNotOptimize(sum); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_Sum_By_StrCat); + +void BM_StrCat_By_snprintf(benchmark::State& state) { + int i = 0; + char on_stack[1000]; + for (auto _ : state) { + snprintf(on_stack, sizeof(on_stack), "%s %s:%d", kStringOne, kStringTwo, i); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_StrCat_By_snprintf); + +void BM_StrCat_By_Strings(benchmark::State& state) { + int i = 0; + for (auto _ : state) { + std::string result = + std::string(kStringOne) + " " + kStringTwo + ":" + absl::StrCat(i); + benchmark::DoNotOptimize(result); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_StrCat_By_Strings); + +void BM_StrCat_By_StringOpPlus(benchmark::State& state) { + int i = 0; + for (auto _ : state) { + std::string result = kStringOne; + result += " "; + result += kStringTwo; + result += ":"; + result += absl::StrCat(i); + benchmark::DoNotOptimize(result); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_StrCat_By_StringOpPlus); + +void BM_StrCat_By_StrCat(benchmark::State& state) { + int i = 0; + for (auto _ : state) { + std::string result = absl::StrCat(kStringOne, " ", kStringTwo, ":", i); + benchmark::DoNotOptimize(result); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_StrCat_By_StrCat); + +void BM_HexCat_By_StrCat(benchmark::State& state) { + int i = 0; + for (auto _ : state) { + std::string result = + absl::StrCat(kStringOne, " ", absl::Hex(int64_t{i} + 0x10000000)); + benchmark::DoNotOptimize(result); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_HexCat_By_StrCat); + +void BM_HexCat_By_Substitute(benchmark::State& state) { + int i = 0; + for (auto _ : state) { + std::string result = absl::Substitute( + "$0 $1", kStringOne, reinterpret_cast<void*>(int64_t{i} + 0x10000000)); + benchmark::DoNotOptimize(result); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_HexCat_By_Substitute); + +void BM_FloatToString_By_StrCat(benchmark::State& state) { + int i = 0; + float foo = 0.0f; + for (auto _ : state) { + std::string result = absl::StrCat(foo += 1.001f, " != ", int64_t{i}); + benchmark::DoNotOptimize(result); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_FloatToString_By_StrCat); + +void BM_DoubleToString_By_SixDigits(benchmark::State& state) { + int i = 0; + double foo = 0.0; + for (auto _ : state) { + std::string result = + absl::StrCat(absl::SixDigits(foo += 1.001), " != ", int64_t{i}); + benchmark::DoNotOptimize(result); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_DoubleToString_By_SixDigits); + +} // namespace + +BENCHMARK_MAIN();
diff --git a/absl/strings/str_join_benchmark.cc b/absl/strings/str_join_benchmark.cc new file mode 100644 index 0000000..79cad5e --- /dev/null +++ b/absl/strings/str_join_benchmark.cc
@@ -0,0 +1,98 @@ +// +// 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 +// +// http://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 "absl/strings/str_join.h" + +#include <string> +#include <vector> +#include <utility> + +#include "benchmark/benchmark.h" + +namespace { + +void BM_Join2_Strings(benchmark::State& state) { + const int string_len = state.range(0); + const int num_strings = state.range(1); + const std::string s(string_len, 'x'); + const std::vector<std::string> v(num_strings, s); + for (auto _ : state) { + std::string s = absl::StrJoin(v, "-"); + benchmark::DoNotOptimize(s); + } +} +BENCHMARK(BM_Join2_Strings) + ->ArgPair(1 << 0, 1 << 3) + ->ArgPair(1 << 10, 1 << 3) + ->ArgPair(1 << 13, 1 << 3) + ->ArgPair(1 << 0, 1 << 10) + ->ArgPair(1 << 10, 1 << 10) + ->ArgPair(1 << 13, 1 << 10) + ->ArgPair(1 << 0, 1 << 13) + ->ArgPair(1 << 10, 1 << 13) + ->ArgPair(1 << 13, 1 << 13); + +void BM_Join2_Ints(benchmark::State& state) { + const int num_ints = state.range(0); + const std::vector<int> v(num_ints, 42); + for (auto _ : state) { + std::string s = absl::StrJoin(v, "-"); + benchmark::DoNotOptimize(s); + } +} +BENCHMARK(BM_Join2_Ints)->Range(0, 1 << 13); + +void BM_Join2_KeysAndValues(benchmark::State& state) { + const int string_len = state.range(0); + const int num_pairs = state.range(1); + const std::string s(string_len, 'x'); + const std::vector<std::pair<std::string, int>> v(num_pairs, std::make_pair(s, 42)); + for (auto _ : state) { + std::string s = absl::StrJoin(v, ",", absl::PairFormatter("=")); + benchmark::DoNotOptimize(s); + } +} +BENCHMARK(BM_Join2_KeysAndValues) + ->ArgPair(1 << 0, 1 << 3) + ->ArgPair(1 << 10, 1 << 3) + ->ArgPair(1 << 13, 1 << 3) + ->ArgPair(1 << 0, 1 << 10) + ->ArgPair(1 << 10, 1 << 10) + ->ArgPair(1 << 13, 1 << 10) + ->ArgPair(1 << 0, 1 << 13) + ->ArgPair(1 << 10, 1 << 13) + ->ArgPair(1 << 13, 1 << 13); + +void BM_JoinStreamable(benchmark::State& state) { + const int string_len = state.range(0); + const int num_strings = state.range(1); + const std::vector<std::string> v(num_strings, std::string(string_len, 'x')); + for (auto _ : state) { + std::string s = absl::StrJoin(v, "", absl::StreamFormatter()); + benchmark::DoNotOptimize(s); + } +} +BENCHMARK(BM_JoinStreamable) + ->ArgPair(0, 0) + ->ArgPair(16, 1) + ->ArgPair(256, 1) + ->ArgPair(16, 16) + ->ArgPair(256, 16) + ->ArgPair(16, 256) + ->ArgPair(256, 256); + +} // namespace + +BENCHMARK_MAIN();
diff --git a/absl/strings/str_replace_benchmark.cc b/absl/strings/str_replace_benchmark.cc new file mode 100644 index 0000000..9dd72eb --- /dev/null +++ b/absl/strings/str_replace_benchmark.cc
@@ -0,0 +1,124 @@ +// 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 +// +// http://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 "absl/strings/str_replace.h" + +#include <cstring> +#include <string> + +#include "benchmark/benchmark.h" +#include "absl/base/internal/raw_logging.h" + +namespace { + +std::string* big_string; +std::string* after_replacing_the; +std::string* after_replacing_many; + +struct Replacement { + const char* needle; + const char* replacement; +} replacements[] = { + {"the", "box"}, // + {"brown", "quick"}, // + {"jumped", "liquored"}, // + {"dozen", "brown"}, // + {"lazy", "pack"}, // + {"liquor", "shakes"}, // +}; + +// Here, we set up a std::string for use in global-replace benchmarks. +// We started with a million blanks, and then deterministically insert +// 10,000 copies each of two pangrams. The result is a std::string that is +// 40% blank space and 60% these words. 'the' occurs 18,247 times and +// all the substitutions together occur 49,004 times. +// +// We then create "after_replacing_the" to be a std::string that is a result of +// replacing "the" with "box" in big_string. +// +// And then we create "after_replacing_many" to be a std::string that is result +// of preferring several substitutions. +void SetUpStrings() { + if (big_string == nullptr) { + size_t r = 0; + big_string = new std::string(1000 * 1000, ' '); + for (std::string phrase : {"the quick brown fox jumped over the lazy dogs", + "pack my box with the five dozen liquor jugs"}) { + for (int i = 0; i < 10 * 1000; ++i) { + r = r * 237 + 41; // not very random. + memcpy(&(*big_string)[r % (big_string->size() - phrase.size())], + phrase.data(), phrase.size()); + } + } + // big_string->resize(50); + // OK, we've set up the std::string, now let's set up expectations - first by + // just replacing "the" with "box" + after_replacing_the = new std::string(*big_string); + for (size_t pos = 0; + (pos = after_replacing_the->find("the", pos)) != std::string::npos;) { + memcpy(&(*after_replacing_the)[pos], "box", 3); + } + // And then with all the replacements. + after_replacing_many = new std::string(*big_string); + for (size_t pos = 0;;) { + size_t next_pos = static_cast<size_t>(-1); + const char* needle_string = nullptr; + const char* replacement_string = nullptr; + for (const auto& r : replacements) { + auto needlepos = after_replacing_many->find(r.needle, pos); + if (needlepos != std::string::npos && needlepos < next_pos) { + next_pos = needlepos; + needle_string = r.needle; + replacement_string = r.replacement; + } + } + if (next_pos > after_replacing_many->size()) break; + after_replacing_many->replace(next_pos, strlen(needle_string), + replacement_string); + next_pos += strlen(replacement_string); + pos = next_pos; + } + } +} + +void BM_StrReplaceAllOneReplacement(benchmark::State& state) { + SetUpStrings(); + std::string src = *big_string; + for (auto _ : state) { + std::string dest = absl::StrReplaceAll(src, {{"the", "box"}}); + ABSL_RAW_CHECK(dest == *after_replacing_the, + "not benchmarking intended behavior"); + } +} +BENCHMARK(BM_StrReplaceAllOneReplacement); + +void BM_StrReplaceAll(benchmark::State& state) { + SetUpStrings(); + std::string src = *big_string; + for (auto _ : state) { + std::string dest = absl::StrReplaceAll(src, {{"the", "box"}, + {"brown", "quick"}, + {"jumped", "liquored"}, + {"dozen", "brown"}, + {"lazy", "pack"}, + {"liquor", "shakes"}}); + ABSL_RAW_CHECK(dest == *after_replacing_many, + "not benchmarking intended behavior"); + } +} +BENCHMARK(BM_StrReplaceAll); + +} // namespace + +BENCHMARK_MAIN();
diff --git a/absl/strings/str_split_benchmark.cc b/absl/strings/str_split_benchmark.cc new file mode 100644 index 0000000..c35787b --- /dev/null +++ b/absl/strings/str_split_benchmark.cc
@@ -0,0 +1,158 @@ +// 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 +// +// http://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 "absl/strings/str_split.h" + +#include <iterator> +#include <string> +#include <unordered_map> +#include <unordered_set> +#include <vector> + +#include "benchmark/benchmark.h" +#include "absl/base/internal/raw_logging.h" +#include "absl/strings/string_view.h" + +namespace { + +std::string MakeTestString(int desired_length) { + static const int kAverageValueLen = 25; + std::string test(desired_length * kAverageValueLen, 'x'); + for (int i = 1; i < test.size(); i += kAverageValueLen) { + test[i] = ';'; + } + return test; +} + +void BM_Split2StringPiece(benchmark::State& state) { + std::string test = MakeTestString(state.range(0)); + for (auto _ : state) { + std::vector<absl::string_view> result = absl::StrSplit(test, ';'); + benchmark::DoNotOptimize(result); + } +} +BENCHMARK_RANGE(BM_Split2StringPiece, 0, 1 << 20); + +void BM_Split2StringPieceLifted(benchmark::State& state) { + std::string test = MakeTestString(state.range(0)); + std::vector<absl::string_view> result; + for (auto _ : state) { + result = absl::StrSplit(test, ';'); + } + benchmark::DoNotOptimize(result); +} +BENCHMARK_RANGE(BM_Split2StringPieceLifted, 0, 1 << 20); + +void BM_Split2String(benchmark::State& state) { + std::string test = MakeTestString(state.range(0)); + for (auto _ : state) { + std::vector<std::string> result = absl::StrSplit(test, ';'); + benchmark::DoNotOptimize(result); + } +} +BENCHMARK_RANGE(BM_Split2String, 0, 1 << 20); + +// This benchmark is for comparing Split2 to Split1 (SplitStringUsing). In +// particular, this benchmark uses SkipEmpty() to match SplitStringUsing's +// behavior. +void BM_Split2SplitStringUsing(benchmark::State& state) { + std::string test = MakeTestString(state.range(0)); + for (auto _ : state) { + std::vector<std::string> result = absl::StrSplit(test, ';', absl::SkipEmpty()); + benchmark::DoNotOptimize(result); + } +} +BENCHMARK_RANGE(BM_Split2SplitStringUsing, 0, 1 << 20); + +void BM_SplitStringToUnorderedSet(benchmark::State& state) { + const int len = state.range(0); + std::string test(len, 'x'); + for (int i = 1; i < len; i += 2) { + test[i] = ';'; + } + for (auto _ : state) { + std::unordered_set<std::string> result = + absl::StrSplit(test, ':', absl::SkipEmpty()); + benchmark::DoNotOptimize(result); + } +} +BENCHMARK_RANGE(BM_SplitStringToUnorderedSet, 0, 1 << 20); + +void BM_SplitStringToUnorderedMap(benchmark::State& state) { + const int len = state.range(0); + std::string test(len, 'x'); + for (int i = 1; i < len; i += 2) { + test[i] = ';'; + } + for (auto _ : state) { + std::unordered_map<std::string, std::string> result = + absl::StrSplit(test, ':', absl::SkipEmpty()); + benchmark::DoNotOptimize(result); + } +} +BENCHMARK_RANGE(BM_SplitStringToUnorderedMap, 0, 1 << 20); + +void BM_SplitStringAllowEmpty(benchmark::State& state) { + const int len = state.range(0); + std::string test(len, 'x'); + for (int i = 1; i < len; i += 2) { + test[i] = ';'; + } + for (auto _ : state) { + std::vector<std::string> result = absl::StrSplit(test, ';'); + benchmark::DoNotOptimize(result); + } +} +BENCHMARK_RANGE(BM_SplitStringAllowEmpty, 0, 1 << 20); + +struct OneCharLiteral { + char operator()() const { return 'X'; } +}; + +struct OneCharStringLiteral { + const char* operator()() const { return "X"; } +}; + +template <typename DelimiterFactory> +void BM_SplitStringWithOneChar(benchmark::State& state) { + const auto delimiter = DelimiterFactory()(); + std::vector<absl::string_view> pieces; + size_t v = 0; + for (auto _ : state) { + pieces = absl::StrSplit("The quick brown fox jumps over the lazy dog", + delimiter); + v += pieces.size(); + } + ABSL_RAW_CHECK(v == state.iterations(), ""); +} +BENCHMARK_TEMPLATE(BM_SplitStringWithOneChar, OneCharLiteral); +BENCHMARK_TEMPLATE(BM_SplitStringWithOneChar, OneCharStringLiteral); + +template <typename DelimiterFactory> +void BM_SplitStringWithOneCharNoVector(benchmark::State& state) { + const auto delimiter = DelimiterFactory()(); + size_t v = 0; + for (auto _ : state) { + auto splitter = absl::StrSplit( + "The quick brown fox jumps over the lazy dog", delimiter); + v += std::distance(splitter.begin(), splitter.end()); + } + ABSL_RAW_CHECK(v == state.iterations(), ""); +} +BENCHMARK_TEMPLATE(BM_SplitStringWithOneCharNoVector, OneCharLiteral); +BENCHMARK_TEMPLATE(BM_SplitStringWithOneCharNoVector, OneCharStringLiteral); + +} // namespace + +BENCHMARK_MAIN();
diff --git a/absl/strings/string_view_benchmark.cc b/absl/strings/string_view_benchmark.cc new file mode 100644 index 0000000..c66f0fb --- /dev/null +++ b/absl/strings/string_view_benchmark.cc
@@ -0,0 +1,331 @@ +// 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 +// +// http://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 "absl/strings/string_view.h" + +#include <algorithm> +#include <cstdint> +#include <map> +#include <random> +#include <string> +#include <unordered_set> +#include <vector> + +#include "benchmark/benchmark.h" +#include "absl/base/attributes.h" +#include "absl/base/internal/raw_logging.h" +#include "absl/base/macros.h" +#include "absl/strings/str_cat.h" + +namespace { + +// Provide a forcibly out-of-line wrapper for operator== that can be used in +// benchmarks to measure the impact of inlining. +ABSL_ATTRIBUTE_NOINLINE +bool NonInlinedEq(absl::string_view a, absl::string_view b) { return a == b; } + +// We use functions that cannot be inlined to perform the comparison loops so +// that inlining of the operator== can't optimize away *everything*. +ABSL_ATTRIBUTE_NOINLINE +void DoEqualityComparisons(benchmark::State& state, absl::string_view a, + absl::string_view b) { + for (auto _ : state) { + benchmark::DoNotOptimize(a == b); + } +} + +void BM_EqualIdentical(benchmark::State& state) { + std::string x(state.range(0), 'a'); + DoEqualityComparisons(state, x, x); +} +BENCHMARK(BM_EqualIdentical)->DenseRange(0, 3)->Range(4, 1 << 10); + +void BM_EqualSame(benchmark::State& state) { + std::string x(state.range(0), 'a'); + std::string y = x; + DoEqualityComparisons(state, x, y); +} +BENCHMARK(BM_EqualSame) + ->DenseRange(0, 10) + ->Arg(20) + ->Arg(40) + ->Arg(70) + ->Arg(110) + ->Range(160, 4096); + +void BM_EqualDifferent(benchmark::State& state) { + const int len = state.range(0); + std::string x(len, 'a'); + std::string y = x; + if (len > 0) { + y[len - 1] = 'b'; + } + DoEqualityComparisons(state, x, y); +} +BENCHMARK(BM_EqualDifferent)->DenseRange(0, 3)->Range(4, 1 << 10); + +// This benchmark is intended to check that important simplifications can be +// made with absl::string_view comparisons against constant strings. The idea is +// that if constant strings cause redundant components of the comparison, the +// compiler should detect and eliminate them. Here we use 8 different strings, +// each with the same size. Provided our comparison makes the implementation +// inline-able by the compiler, it should fold all of these away into a single +// size check once per loop iteration. +ABSL_ATTRIBUTE_NOINLINE +void DoConstantSizeInlinedEqualityComparisons(benchmark::State& state, + absl::string_view a) { + for (auto _ : state) { + benchmark::DoNotOptimize(a == "aaa"); + benchmark::DoNotOptimize(a == "bbb"); + benchmark::DoNotOptimize(a == "ccc"); + benchmark::DoNotOptimize(a == "ddd"); + benchmark::DoNotOptimize(a == "eee"); + benchmark::DoNotOptimize(a == "fff"); + benchmark::DoNotOptimize(a == "ggg"); + benchmark::DoNotOptimize(a == "hhh"); + } +} +void BM_EqualConstantSizeInlined(benchmark::State& state) { + std::string x(state.range(0), 'a'); + DoConstantSizeInlinedEqualityComparisons(state, x); +} +// We only need to check for size of 3, and <> 3 as this benchmark only has to +// do with size differences. +BENCHMARK(BM_EqualConstantSizeInlined)->DenseRange(2, 4); + +// This benchmark exists purely to give context to the above timings: this is +// what they would look like if the compiler is completely unable to simplify +// between two comparisons when they are comparing against constant strings. +ABSL_ATTRIBUTE_NOINLINE +void DoConstantSizeNonInlinedEqualityComparisons(benchmark::State& state, + absl::string_view a) { + for (auto _ : state) { + // Force these out-of-line to compare with the above function. + benchmark::DoNotOptimize(NonInlinedEq(a, "aaa")); + benchmark::DoNotOptimize(NonInlinedEq(a, "bbb")); + benchmark::DoNotOptimize(NonInlinedEq(a, "ccc")); + benchmark::DoNotOptimize(NonInlinedEq(a, "ddd")); + benchmark::DoNotOptimize(NonInlinedEq(a, "eee")); + benchmark::DoNotOptimize(NonInlinedEq(a, "fff")); + benchmark::DoNotOptimize(NonInlinedEq(a, "ggg")); + benchmark::DoNotOptimize(NonInlinedEq(a, "hhh")); + } +} + +void BM_EqualConstantSizeNonInlined(benchmark::State& state) { + std::string x(state.range(0), 'a'); + DoConstantSizeNonInlinedEqualityComparisons(state, x); +} +// We only need to check for size of 3, and <> 3 as this benchmark only has to +// do with size differences. +BENCHMARK(BM_EqualConstantSizeNonInlined)->DenseRange(2, 4); + +void BM_CompareSame(benchmark::State& state) { + const int len = state.range(0); + std::string x; + for (int i = 0; i < len; i++) { + x += 'a'; + } + std::string y = x; + absl::string_view a = x; + absl::string_view b = y; + + for (auto _ : state) { + benchmark::DoNotOptimize(a.compare(b)); + } +} +BENCHMARK(BM_CompareSame)->DenseRange(0, 3)->Range(4, 1 << 10); + +void BM_find_string_view_len_one(benchmark::State& state) { + std::string haystack(state.range(0), '0'); + absl::string_view s(haystack); + for (auto _ : state) { + s.find("x"); // not present; length 1 + } +} +BENCHMARK(BM_find_string_view_len_one)->Range(1, 1 << 20); + +void BM_find_string_view_len_two(benchmark::State& state) { + std::string haystack(state.range(0), '0'); + absl::string_view s(haystack); + for (auto _ : state) { + s.find("xx"); // not present; length 2 + } +} +BENCHMARK(BM_find_string_view_len_two)->Range(1, 1 << 20); + +void BM_find_one_char(benchmark::State& state) { + std::string haystack(state.range(0), '0'); + absl::string_view s(haystack); + for (auto _ : state) { + s.find('x'); // not present + } +} +BENCHMARK(BM_find_one_char)->Range(1, 1 << 20); + +void BM_rfind_one_char(benchmark::State& state) { + std::string haystack(state.range(0), '0'); + absl::string_view s(haystack); + for (auto _ : state) { + s.rfind('x'); // not present + } +} +BENCHMARK(BM_rfind_one_char)->Range(1, 1 << 20); + +void BM_worst_case_find_first_of(benchmark::State& state, int haystack_len) { + const int needle_len = state.range(0); + std::string needle; + for (int i = 0; i < needle_len; ++i) { + needle += 'a' + i; + } + std::string haystack(haystack_len, '0'); // 1000 zeros. + + absl::string_view s(haystack); + for (auto _ : state) { + s.find_first_of(needle); + } +} + +void BM_find_first_of_short(benchmark::State& state) { + BM_worst_case_find_first_of(state, 10); +} + +void BM_find_first_of_medium(benchmark::State& state) { + BM_worst_case_find_first_of(state, 100); +} + +void BM_find_first_of_long(benchmark::State& state) { + BM_worst_case_find_first_of(state, 1000); +} + +BENCHMARK(BM_find_first_of_short)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32); +BENCHMARK(BM_find_first_of_medium)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32); +BENCHMARK(BM_find_first_of_long)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32); + +struct EasyMap : public std::map<absl::string_view, uint64_t> { + explicit EasyMap(size_t) {} +}; + +// This templated benchmark helper function is intended to stress operator== or +// operator< in a realistic test. It surely isn't entirely realistic, but it's +// a start. The test creates a map of type Map, a template arg, and populates +// it with table_size key/value pairs. Each key has WordsPerKey words. After +// creating the map, a number of lookups are done in random order. Some keys +// are used much more frequently than others in this phase of the test. +template <typename Map, int WordsPerKey> +void StringViewMapBenchmark(benchmark::State& state) { + const int table_size = state.range(0); + const double kFractionOfKeysThatAreHot = 0.2; + const int kNumLookupsOfHotKeys = 20; + const int kNumLookupsOfColdKeys = 1; + const char* words[] = {"the", "quick", "brown", "fox", "jumped", + "over", "the", "lazy", "dog", "and", + "found", "a", "large", "mushroom", "and", + "a", "couple", "crickets", "eating", "pie"}; + // Create some keys that consist of words in random order. + std::random_device r; + std::seed_seq seed({r(), r(), r(), r(), r(), r(), r(), r()}); + std::mt19937 rng(seed); + std::vector<std::string> keys(table_size); + std::vector<int> all_indices; + const int kBlockSize = 1 << 12; + std::unordered_set<std::string> t(kBlockSize); + std::uniform_int_distribution<int> uniform(0, ABSL_ARRAYSIZE(words) - 1); + for (int i = 0; i < table_size; i++) { + all_indices.push_back(i); + do { + keys[i].clear(); + for (int j = 0; j < WordsPerKey; j++) { + absl::StrAppend(&keys[i], j > 0 ? " " : "", words[uniform(rng)]); + } + } while (!t.insert(keys[i]).second); + } + + // Create a list of strings to lookup: a permutation of the array of + // keys we just created, with repeats. "Hot" keys get repeated more. + std::shuffle(all_indices.begin(), all_indices.end(), rng); + const int num_hot = table_size * kFractionOfKeysThatAreHot; + const int num_cold = table_size - num_hot; + std::vector<int> hot_indices(all_indices.begin(), + all_indices.begin() + num_hot); + std::vector<int> indices; + for (int i = 0; i < kNumLookupsOfColdKeys; i++) { + indices.insert(indices.end(), all_indices.begin(), all_indices.end()); + } + for (int i = 0; i < kNumLookupsOfHotKeys - kNumLookupsOfColdKeys; i++) { + indices.insert(indices.end(), hot_indices.begin(), hot_indices.end()); + } + std::shuffle(indices.begin(), indices.end(), rng); + ABSL_RAW_CHECK( + num_cold * kNumLookupsOfColdKeys + num_hot * kNumLookupsOfHotKeys == + indices.size(), + ""); + // After constructing the array we probe it with absl::string_views built from + // test_strings. This means operator== won't see equal pointers, so + // it'll have to check for equal lengths and equal characters. + std::vector<std::string> test_strings(indices.size()); + for (int i = 0; i < indices.size(); i++) { + test_strings[i] = keys[indices[i]]; + } + + // Run the benchmark. It includes map construction but is mostly + // map lookups. + for (auto _ : state) { + Map h(table_size); + for (int i = 0; i < table_size; i++) { + h[keys[i]] = i * 2; + } + ABSL_RAW_CHECK(h.size() == table_size, ""); + uint64_t sum = 0; + for (int i = 0; i < indices.size(); i++) { + sum += h[test_strings[i]]; + } + benchmark::DoNotOptimize(sum); + } +} + +void BM_StdMap_4(benchmark::State& state) { + StringViewMapBenchmark<EasyMap, 4>(state); +} +BENCHMARK(BM_StdMap_4)->Range(1 << 10, 1 << 16); + +void BM_StdMap_8(benchmark::State& state) { + StringViewMapBenchmark<EasyMap, 8>(state); +} +BENCHMARK(BM_StdMap_8)->Range(1 << 10, 1 << 16); + +void BM_CopyToStringNative(benchmark::State& state) { + std::string src(state.range(0), 'x'); + absl::string_view sv(src); + std::string dst; + for (auto _ : state) { + dst.assign(sv.begin(), sv.end()); + } +} +BENCHMARK(BM_CopyToStringNative)->Range(1 << 3, 1 << 12); + +void BM_AppendToStringNative(benchmark::State& state) { + std::string src(state.range(0), 'x'); + absl::string_view sv(src); + std::string dst; + for (auto _ : state) { + dst.clear(); + dst.insert(dst.end(), sv.begin(), sv.end()); + } +} +BENCHMARK(BM_AppendToStringNative)->Range(1 << 3, 1 << 12); + +} // namespace + +BENCHMARK_MAIN();
diff --git a/absl/synchronization/BUILD.bazel b/absl/synchronization/BUILD.bazel index 0537690..67ce7ff 100644 --- a/absl/synchronization/BUILD.bazel +++ b/absl/synchronization/BUILD.bazel
@@ -39,6 +39,7 @@ ], deps = [ "//absl/base", + "//absl/base:base_internal", "//absl/base:core_headers", "//absl/base:malloc_internal", ], @@ -119,6 +120,20 @@ ], ) +cc_test( + name = "graphcycles_benchmark", + srcs = ["internal/graphcycles_benchmark.cc"], + copts = ABSL_TEST_COPTS, + tags = [ + "benchmark", + ], + deps = [ + ":graphcycles_internal", + "//absl/base", + "@com_github_google_benchmark//:benchmark", + ], +) + cc_library( name = "thread_pool", testonly = 1, @@ -149,6 +164,20 @@ ) cc_test( + name = "mutex_benchmark", + srcs = ["mutex_benchmark.cc"], + copts = ABSL_TEST_COPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":synchronization", + ":thread_pool", + "//absl/base", + "@com_github_google_benchmark//:benchmark", + ], +) + +cc_test( name = "notification_test", size = "small", srcs = ["notification_test.cc"],
diff --git a/absl/synchronization/internal/graphcycles.cc b/absl/synchronization/internal/graphcycles.cc index 28ad172..ab1f3f8 100644 --- a/absl/synchronization/internal/graphcycles.cc +++ b/absl/synchronization/internal/graphcycles.cc
@@ -37,6 +37,7 @@ #include <algorithm> #include <array> +#include "absl/base/internal/hide_ptr.h" #include "absl/base/internal/raw_logging.h" #include "absl/base/internal/spinlock.h" @@ -276,18 +277,6 @@ return static_cast<uint32_t>(id.handle >> 32); } -// We need to hide Mutexes (or other deadlock detection's pointers) -// from the leak detector. Xor with an arbitrary number with high bits set. -static const uintptr_t kHideMask = static_cast<uintptr_t>(0xF03A5F7BF03A5F7Bll); - -static inline uintptr_t MaskPtr(void *ptr) { - return reinterpret_cast<uintptr_t>(ptr) ^ kHideMask; -} - -static inline void* UnmaskPtr(uintptr_t word) { - return reinterpret_cast<void*>(word ^ kHideMask); -} - struct Node { int32_t rank; // rank number assigned by Pearce-Kelly algorithm uint32_t version; // Current version number @@ -309,7 +298,7 @@ } int32_t Find(void* ptr) { - auto masked = MaskPtr(ptr); + auto masked = base_internal::HidePtr(ptr); for (int32_t i = table_[Hash(ptr)]; i != -1;) { Node* n = (*nodes_)[i]; if (n->masked_ptr == masked) return i; @@ -327,7 +316,7 @@ int32_t Remove(void* ptr) { // Advance through linked list while keeping track of the // predecessor slot that points to the current entry. - auto masked = MaskPtr(ptr); + auto masked = base_internal::HidePtr(ptr); for (int32_t* slot = &table_[Hash(ptr)]; *slot != -1; ) { int32_t index = *slot; Node* n = (*nodes_)[index]; @@ -395,7 +384,7 @@ NodeSet ranks; // Set of ranks seen so far. for (uint32_t x = 0; x < r->nodes_.size(); x++) { Node* nx = r->nodes_[x]; - void* ptr = UnmaskPtr(nx->masked_ptr); + void* ptr = base_internal::UnhidePtr<void>(nx->masked_ptr); if (ptr != nullptr && static_cast<uint32_t>(r->ptrmap_.Find(ptr)) != x) { ABSL_RAW_LOG(FATAL, "Did not find live node in hash table %u %p", x, ptr); } @@ -427,7 +416,7 @@ n->version = 1; // Avoid 0 since it is used by InvalidGraphId() n->visited = false; n->rank = rep_->nodes_.size(); - n->masked_ptr = MaskPtr(ptr); + n->masked_ptr = base_internal::HidePtr(ptr); n->nstack = 0; n->priority = 0; rep_->nodes_.push_back(n); @@ -439,7 +428,7 @@ int32_t r = rep_->free_nodes_.back(); rep_->free_nodes_.pop_back(); Node* n = rep_->nodes_[r]; - n->masked_ptr = MaskPtr(ptr); + n->masked_ptr = base_internal::HidePtr(ptr); n->nstack = 0; n->priority = 0; rep_->ptrmap_.Add(ptr, r); @@ -461,7 +450,7 @@ } x->in.clear(); x->out.clear(); - x->masked_ptr = MaskPtr(nullptr); + x->masked_ptr = base_internal::HidePtr<void>(nullptr); if (x->version == std::numeric_limits<uint32_t>::max()) { // Cannot use x any more } else { @@ -472,7 +461,8 @@ void* GraphCycles::Ptr(GraphId id) { Node* n = FindNode(rep_, id); - return n == nullptr ? nullptr : UnmaskPtr(n->masked_ptr); + return n == nullptr ? nullptr + : base_internal::UnhidePtr<void>(n->masked_ptr); } bool GraphCycles::HasNode(GraphId node) {
diff --git a/absl/synchronization/internal/graphcycles_benchmark.cc b/absl/synchronization/internal/graphcycles_benchmark.cc new file mode 100644 index 0000000..b4a1deb --- /dev/null +++ b/absl/synchronization/internal/graphcycles_benchmark.cc
@@ -0,0 +1,46 @@ +// 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 +// +// http://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 "absl/synchronization/internal/graphcycles.h" + +#include <algorithm> +#include <cstdint> +#include <vector> + +#include "benchmark/benchmark.h" +#include "absl/base/internal/raw_logging.h" + +namespace { + +void BM_StressTest(benchmark::State& state) { + const int num_nodes = state.range(0); + while (state.KeepRunningBatch(num_nodes)) { + absl::synchronization_internal::GraphCycles g; + std::vector<absl::synchronization_internal::GraphId> nodes(num_nodes); + for (int i = 0; i < num_nodes; i++) { + nodes[i] = g.GetId(reinterpret_cast<void*>(static_cast<uintptr_t>(i))); + } + for (int i = 0; i < num_nodes; i++) { + int end = std::min(num_nodes, i + 5); + for (int j = i + 1; j < end; j++) { + ABSL_RAW_CHECK(g.InsertEdge(nodes[i], nodes[j]), ""); + } + } + } +} +BENCHMARK(BM_StressTest)->Range(2048, 1048576); + +} // namespace + +BENCHMARK_MAIN();
diff --git a/absl/synchronization/mutex.cc b/absl/synchronization/mutex.cc index bd54a4d..e652504 100644 --- a/absl/synchronization/mutex.cc +++ b/absl/synchronization/mutex.cc
@@ -43,6 +43,7 @@ #include "absl/base/dynamic_annotations.h" #include "absl/base/internal/atomic_hook.h" #include "absl/base/internal/cycleclock.h" +#include "absl/base/internal/hide_ptr.h" #include "absl/base/internal/low_level_alloc.h" #include "absl/base/internal/raw_logging.h" #include "absl/base/internal/spinlock.h" @@ -272,13 +273,6 @@ // Can't be too small, as it's used for deadlock detection information. static const uint32_t kNSynchEvent = 1031; -// We need to hide Mutexes (or other deadlock detection's pointers) -// from the leak detector. -static const uintptr_t kHideMask = static_cast<uintptr_t>(0xF03A5F7BF03A5F7BLL); -static uintptr_t MaskMu(const void *mu) { - return reinterpret_cast<uintptr_t>(mu) ^ kHideMask; -} - static struct SynchEvent { // this is a trivial hash table for the events // struct is freed when refcount reaches 0 int refcount GUARDED_BY(synch_event_mu); @@ -314,7 +308,8 @@ SynchEvent *e; // first look for existing SynchEvent struct.. synch_event_mu.Lock(); - for (e = synch_event[h]; e != nullptr && e->masked_addr != MaskMu(addr); + for (e = synch_event[h]; + e != nullptr && e->masked_addr != base_internal::HidePtr(addr); e = e->next) { } if (e == nullptr) { // no SynchEvent struct found; make one. @@ -325,7 +320,7 @@ e = reinterpret_cast<SynchEvent *>( base_internal::LowLevelAlloc::Alloc(sizeof(*e) + l)); e->refcount = 2; // one for return value, one for linked list - e->masked_addr = MaskMu(addr); + e->masked_addr = base_internal::HidePtr(addr); e->invariant = nullptr; e->arg = nullptr; e->log = false; @@ -367,7 +362,8 @@ SynchEvent *e; synch_event_mu.Lock(); for (pe = &synch_event[h]; - (e = *pe) != nullptr && e->masked_addr != MaskMu(addr); pe = &e->next) { + (e = *pe) != nullptr && e->masked_addr != base_internal::HidePtr(addr); + pe = &e->next) { } bool del = false; if (e != nullptr) { @@ -388,7 +384,8 @@ uint32_t h = reinterpret_cast<intptr_t>(addr) % kNSynchEvent; SynchEvent *e; synch_event_mu.Lock(); - for (e = synch_event[h]; e != nullptr && e->masked_addr != MaskMu(addr); + for (e = synch_event[h]; + e != nullptr && e->masked_addr != base_internal::HidePtr(addr); e = e->next) { } if (e != nullptr) {
diff --git a/absl/synchronization/mutex.h b/absl/synchronization/mutex.h index 368684b..840b9d6 100644 --- a/absl/synchronization/mutex.h +++ b/absl/synchronization/mutex.h
@@ -854,7 +854,7 @@ MutexLockMaybe& operator=(MutexLockMaybe&&) = delete; }; -// ReleaseableMutexLock +// ReleasableMutexLock // // ReleasableMutexLock is like MutexLock, but permits `Release()` of its // mutex before destruction. `Release()` may be called at most once.
diff --git a/absl/synchronization/mutex_benchmark.cc b/absl/synchronization/mutex_benchmark.cc new file mode 100644 index 0000000..d91071b --- /dev/null +++ b/absl/synchronization/mutex_benchmark.cc
@@ -0,0 +1,96 @@ +// Copyright 2017 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 +// +// http://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 <vector> + +#include "benchmark/benchmark.h" +#include "absl/base/internal/sysinfo.h" +#include "absl/synchronization/blocking_counter.h" +#include "absl/synchronization/internal/thread_pool.h" +#include "absl/synchronization/mutex.h" + +namespace { + +// Measure the overhead of conditions on mutex release (when they must be +// evaluated). Mutex has (some) support for equivalence classes allowing +// Conditions with the same function/argument to potentially not be multiply +// evaluated. +// +// num_classes==0 is used for the special case of every waiter being distinct. +void BM_ConditionWaiters(benchmark::State& state) { + int num_classes = state.range(0); + int num_waiters = state.range(1); + + struct Helper { + static void Waiter(absl::BlockingCounter* init, absl::Mutex* m, int* p) { + init->DecrementCount(); + m->LockWhen(absl::Condition( + static_cast<bool (*)(int*)>([](int* v) { return *v == 0; }), p)); + m->Unlock(); + } + }; + + if (num_classes == 0) { + // No equivalence classes. + num_classes = num_waiters; + } + + absl::BlockingCounter init(num_waiters); + absl::Mutex mu; + std::vector<int> equivalence_classes(num_classes, 1); + + // Must be declared last to be destroyed first. + absl::synchronization_internal::ThreadPool pool(num_waiters); + + for (int i = 0; i < num_waiters; i++) { + // Mutex considers Conditions with the same function and argument + // to be equivalent. + pool.Schedule([&, i] { + Helper::Waiter(&init, &mu, &equivalence_classes[i % num_classes]); + }); + } + init.Wait(); + + for (auto _ : state) { + mu.Lock(); + mu.Unlock(); // Each unlock requires Condition evaluation for our waiters. + } + + mu.Lock(); + for (int i = 0; i < num_classes; i++) { + equivalence_classes[i] = 0; + } + mu.Unlock(); +} + +#ifdef THREAD_SANITIZER +// ThreadSanitizer can't handle 8192 threads. +constexpr int kMaxConditionWaiters = 2048; +#else +constexpr int kMaxConditionWaiters = 8192; +#endif +BENCHMARK(BM_ConditionWaiters)->RangePair(0, 2, 1, kMaxConditionWaiters); + +void BM_ContendedMutex(benchmark::State& state) { + static absl::Mutex* mu = new absl::Mutex; + for (auto _ : state) { + absl::MutexLock lock(mu); + } +} +BENCHMARK(BM_ContendedMutex)->Threads(1); +BENCHMARK(BM_ContendedMutex)->ThreadPerCpu(); + +} // namespace + +BENCHMARK_MAIN();