From 5aa5d282eac56a21e74611c1cdbaa97bb5db2dca Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Tue, 8 Feb 2022 02:05:36 +0300 Subject: chore(3p/abseil_cpp): unvendor abseil_cpp we weren't actually using these sources anymore, okay? Change-Id: If701571d9716de308d3512e1eb22c35db0877a66 Reviewed-on: https://cl.tvl.fyi/c/depot/+/5248 Tested-by: BuildkiteCI Reviewed-by: grfn Autosubmit: tazjin --- third_party/abseil_cpp/absl/random/BUILD.bazel | 509 --------- third_party/abseil_cpp/absl/random/CMakeLists.txt | 1207 -------------------- third_party/abseil_cpp/absl/random/benchmarks.cc | 383 ------- .../absl/random/bernoulli_distribution.h | 200 ---- .../absl/random/bernoulli_distribution_test.cc | 217 ---- .../abseil_cpp/absl/random/beta_distribution.h | 427 ------- .../absl/random/beta_distribution_test.cc | 619 ---------- third_party/abseil_cpp/absl/random/bit_gen_ref.h | 181 --- .../abseil_cpp/absl/random/bit_gen_ref_test.cc | 102 -- .../absl/random/discrete_distribution.cc | 98 -- .../abseil_cpp/absl/random/discrete_distribution.h | 247 ---- .../absl/random/discrete_distribution_test.cc | 250 ---- third_party/abseil_cpp/absl/random/distributions.h | 452 -------- .../abseil_cpp/absl/random/distributions_test.cc | 455 -------- .../abseil_cpp/absl/random/examples_test.cc | 99 -- .../absl/random/exponential_distribution.h | 165 --- .../absl/random/exponential_distribution_test.cc | 430 ------- .../absl/random/gaussian_distribution.cc | 104 -- .../abseil_cpp/absl/random/gaussian_distribution.h | 275 ----- .../absl/random/gaussian_distribution_test.cc | 579 ---------- .../abseil_cpp/absl/random/generators_test.cc | 179 --- .../abseil_cpp/absl/random/internal/BUILD.bazel | 730 ------------ .../abseil_cpp/absl/random/internal/chi_square.cc | 232 ---- .../abseil_cpp/absl/random/internal/chi_square.h | 89 -- .../absl/random/internal/chi_square_test.cc | 365 ------ .../absl/random/internal/distribution_caller.h | 92 -- .../absl/random/internal/distribution_test_util.cc | 418 ------- .../absl/random/internal/distribution_test_util.h | 113 -- .../random/internal/distribution_test_util_test.cc | 193 ---- .../absl/random/internal/explicit_seed_seq.h | 91 -- .../absl/random/internal/explicit_seed_seq_test.cc | 204 ---- .../absl/random/internal/fast_uniform_bits.h | 268 ----- .../absl/random/internal/fast_uniform_bits_test.cc | 336 ------ .../abseil_cpp/absl/random/internal/fastmath.h | 74 -- .../absl/random/internal/fastmath_test.cc | 110 -- .../internal/gaussian_distribution_gentables.cc | 143 --- .../absl/random/internal/generate_real.h | 146 --- .../absl/random/internal/generate_real_test.cc | 497 -------- .../absl/random/internal/iostream_state_saver.h | 245 ---- .../random/internal/iostream_state_saver_test.cc | 371 ------ .../abseil_cpp/absl/random/internal/mock_helpers.h | 127 -- .../absl/random/internal/mock_overload_set.h | 97 -- .../absl/random/internal/nanobenchmark.cc | 804 ------------- .../absl/random/internal/nanobenchmark.h | 172 --- .../absl/random/internal/nanobenchmark_test.cc | 77 -- .../absl/random/internal/nonsecure_base.h | 150 --- .../absl/random/internal/nonsecure_base_test.cc | 245 ---- .../abseil_cpp/absl/random/internal/pcg_engine.h | 307 ----- .../absl/random/internal/pcg_engine_test.cc | 638 ----------- .../abseil_cpp/absl/random/internal/platform.h | 171 --- .../abseil_cpp/absl/random/internal/pool_urbg.cc | 254 ---- .../abseil_cpp/absl/random/internal/pool_urbg.h | 131 --- .../absl/random/internal/pool_urbg_test.cc | 182 --- .../abseil_cpp/absl/random/internal/randen.cc | 91 -- .../abseil_cpp/absl/random/internal/randen.h | 102 -- .../absl/random/internal/randen_benchmarks.cc | 174 --- .../absl/random/internal/randen_detect.cc | 221 ---- .../absl/random/internal/randen_detect.h | 33 - .../absl/random/internal/randen_engine.h | 230 ---- .../absl/random/internal/randen_engine_test.cc | 656 ----------- .../absl/random/internal/randen_hwaes.cc | 573 ---------- .../abseil_cpp/absl/random/internal/randen_hwaes.h | 50 - .../absl/random/internal/randen_hwaes_test.cc | 104 -- .../absl/random/internal/randen_round_keys.cc | 462 -------- .../abseil_cpp/absl/random/internal/randen_slow.cc | 457 -------- .../abseil_cpp/absl/random/internal/randen_slow.h | 40 - .../absl/random/internal/randen_slow_test.cc | 63 - .../abseil_cpp/absl/random/internal/randen_test.cc | 70 -- .../absl/random/internal/randen_traits.h | 88 -- .../absl/random/internal/salted_seed_seq.h | 167 --- .../absl/random/internal/salted_seed_seq_test.cc | 168 --- .../absl/random/internal/seed_material.cc | 219 ---- .../absl/random/internal/seed_material.h | 104 -- .../absl/random/internal/seed_material_test.cc | 202 ---- .../absl/random/internal/sequence_urbg.h | 60 - .../abseil_cpp/absl/random/internal/traits.h | 101 -- .../abseil_cpp/absl/random/internal/traits_test.cc | 126 -- .../absl/random/internal/uniform_helper.h | 244 ---- .../absl/random/internal/uniform_helper_test.cc | 279 ----- .../absl/random/internal/wide_multiply.h | 111 -- .../absl/random/internal/wide_multiply_test.cc | 66 -- .../absl/random/log_uniform_int_distribution.h | 254 ---- .../random/log_uniform_int_distribution_test.cc | 280 ----- .../abseil_cpp/absl/random/mock_distributions.h | 266 ----- .../absl/random/mock_distributions_test.cc | 72 -- .../abseil_cpp/absl/random/mocking_bit_gen.h | 228 ---- .../abseil_cpp/absl/random/mocking_bit_gen_test.cc | 347 ------ .../abseil_cpp/absl/random/poisson_distribution.h | 258 ----- .../absl/random/poisson_distribution_test.cc | 573 ---------- third_party/abseil_cpp/absl/random/random.h | 189 --- .../abseil_cpp/absl/random/seed_gen_exception.cc | 46 - .../abseil_cpp/absl/random/seed_gen_exception.h | 55 - .../abseil_cpp/absl/random/seed_sequences.cc | 29 - .../abseil_cpp/absl/random/seed_sequences.h | 110 -- .../abseil_cpp/absl/random/seed_sequences_test.cc | 126 -- .../absl/random/uniform_int_distribution.h | 275 ----- .../absl/random/uniform_int_distribution_test.cc | 259 ----- .../absl/random/uniform_real_distribution.h | 202 ---- .../absl/random/uniform_real_distribution_test.cc | 343 ------ .../abseil_cpp/absl/random/zipf_distribution.h | 271 ----- .../absl/random/zipf_distribution_test.cc | 427 ------- 101 files changed, 25121 deletions(-) delete mode 100644 third_party/abseil_cpp/absl/random/BUILD.bazel delete mode 100644 third_party/abseil_cpp/absl/random/CMakeLists.txt delete mode 100644 third_party/abseil_cpp/absl/random/benchmarks.cc delete mode 100644 third_party/abseil_cpp/absl/random/bernoulli_distribution.h delete mode 100644 third_party/abseil_cpp/absl/random/bernoulli_distribution_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/beta_distribution.h delete mode 100644 third_party/abseil_cpp/absl/random/beta_distribution_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/bit_gen_ref.h delete mode 100644 third_party/abseil_cpp/absl/random/bit_gen_ref_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/discrete_distribution.cc delete mode 100644 third_party/abseil_cpp/absl/random/discrete_distribution.h delete mode 100644 third_party/abseil_cpp/absl/random/discrete_distribution_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/distributions.h delete mode 100644 third_party/abseil_cpp/absl/random/distributions_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/examples_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/exponential_distribution.h delete mode 100644 third_party/abseil_cpp/absl/random/exponential_distribution_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/gaussian_distribution.cc delete mode 100644 third_party/abseil_cpp/absl/random/gaussian_distribution.h delete mode 100644 third_party/abseil_cpp/absl/random/gaussian_distribution_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/generators_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/BUILD.bazel delete mode 100644 third_party/abseil_cpp/absl/random/internal/chi_square.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/chi_square.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/chi_square_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/distribution_caller.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/distribution_test_util.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/distribution_test_util.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/distribution_test_util_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/explicit_seed_seq.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/explicit_seed_seq_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/fast_uniform_bits.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/fast_uniform_bits_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/fastmath.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/fastmath_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/gaussian_distribution_gentables.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/generate_real.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/generate_real_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/iostream_state_saver.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/iostream_state_saver_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/mock_helpers.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/mock_overload_set.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/nanobenchmark.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/nanobenchmark.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/nanobenchmark_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/nonsecure_base.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/nonsecure_base_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/pcg_engine.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/pcg_engine_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/platform.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/pool_urbg.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/pool_urbg.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/pool_urbg_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen_benchmarks.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen_detect.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen_detect.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen_engine.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen_engine_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen_hwaes.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen_hwaes.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen_hwaes_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen_round_keys.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen_slow.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen_slow.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen_slow_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/randen_traits.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/salted_seed_seq.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/salted_seed_seq_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/seed_material.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/seed_material.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/seed_material_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/sequence_urbg.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/traits.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/traits_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/uniform_helper.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/uniform_helper_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/internal/wide_multiply.h delete mode 100644 third_party/abseil_cpp/absl/random/internal/wide_multiply_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/log_uniform_int_distribution.h delete mode 100644 third_party/abseil_cpp/absl/random/log_uniform_int_distribution_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/mock_distributions.h delete mode 100644 third_party/abseil_cpp/absl/random/mock_distributions_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/mocking_bit_gen.h delete mode 100644 third_party/abseil_cpp/absl/random/mocking_bit_gen_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/poisson_distribution.h delete mode 100644 third_party/abseil_cpp/absl/random/poisson_distribution_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/random.h delete mode 100644 third_party/abseil_cpp/absl/random/seed_gen_exception.cc delete mode 100644 third_party/abseil_cpp/absl/random/seed_gen_exception.h delete mode 100644 third_party/abseil_cpp/absl/random/seed_sequences.cc delete mode 100644 third_party/abseil_cpp/absl/random/seed_sequences.h delete mode 100644 third_party/abseil_cpp/absl/random/seed_sequences_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/uniform_int_distribution.h delete mode 100644 third_party/abseil_cpp/absl/random/uniform_int_distribution_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/uniform_real_distribution.h delete mode 100644 third_party/abseil_cpp/absl/random/uniform_real_distribution_test.cc delete mode 100644 third_party/abseil_cpp/absl/random/zipf_distribution.h delete mode 100644 third_party/abseil_cpp/absl/random/zipf_distribution_test.cc (limited to 'third_party/abseil_cpp/absl/random') diff --git a/third_party/abseil_cpp/absl/random/BUILD.bazel b/third_party/abseil_cpp/absl/random/BUILD.bazel deleted file mode 100644 index 81e150e62e..0000000000 --- a/third_party/abseil_cpp/absl/random/BUILD.bazel +++ /dev/null @@ -1,509 +0,0 @@ -# -# Copyright 2019 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. -# - -# ABSL random-number generation libraries. - -load("@rules_cc//cc:defs.bzl", "cc_binary", "cc_library", "cc_test") -load( - "//absl:copts/configure_copts.bzl", - "ABSL_DEFAULT_COPTS", - "ABSL_DEFAULT_LINKOPTS", - "ABSL_TEST_COPTS", -) - -package(default_visibility = ["//visibility:public"]) - -licenses(["notice"]) - -cc_library( - name = "random", - hdrs = ["random.h"], - copts = ABSL_DEFAULT_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":distributions", - ":seed_sequences", - "//absl/random/internal:nonsecure_base", - "//absl/random/internal:pcg_engine", - "//absl/random/internal:pool_urbg", - "//absl/random/internal:randen_engine", - ], -) - -cc_library( - name = "distributions", - srcs = [ - "discrete_distribution.cc", - "gaussian_distribution.cc", - ], - hdrs = [ - "bernoulli_distribution.h", - "beta_distribution.h", - "discrete_distribution.h", - "distributions.h", - "exponential_distribution.h", - "gaussian_distribution.h", - "log_uniform_int_distribution.h", - "poisson_distribution.h", - "uniform_int_distribution.h", - "uniform_real_distribution.h", - "zipf_distribution.h", - ], - copts = ABSL_DEFAULT_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - "//absl/base:base_internal", - "//absl/base:config", - "//absl/base:core_headers", - "//absl/meta:type_traits", - "//absl/random/internal:distribution_caller", - "//absl/random/internal:fast_uniform_bits", - "//absl/random/internal:fastmath", - "//absl/random/internal:generate_real", - "//absl/random/internal:iostream_state_saver", - "//absl/random/internal:traits", - "//absl/random/internal:uniform_helper", - "//absl/random/internal:wide_multiply", - "//absl/strings", - ], -) - -cc_library( - name = "seed_gen_exception", - srcs = ["seed_gen_exception.cc"], - hdrs = ["seed_gen_exception.h"], - copts = ABSL_DEFAULT_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = ["//absl/base:config"], -) - -cc_library( - name = "seed_sequences", - srcs = ["seed_sequences.cc"], - hdrs = [ - "seed_sequences.h", - ], - copts = ABSL_DEFAULT_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":seed_gen_exception", - "//absl/container:inlined_vector", - "//absl/random/internal:nonsecure_base", - "//absl/random/internal:pool_urbg", - "//absl/random/internal:salted_seed_seq", - "//absl/random/internal:seed_material", - "//absl/types:span", - ], -) - -cc_library( - name = "bit_gen_ref", - hdrs = ["bit_gen_ref.h"], - copts = ABSL_DEFAULT_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":random", - "//absl/base:core_headers", - "//absl/base:fast_type_id", - "//absl/meta:type_traits", - "//absl/random/internal:distribution_caller", - "//absl/random/internal:fast_uniform_bits", - ], -) - -cc_library( - name = "mock_distributions", - testonly = 1, - hdrs = ["mock_distributions.h"], - deps = [ - ":distributions", - ":mocking_bit_gen", - "//absl/meta:type_traits", - "//absl/random/internal:mock_overload_set", - "@com_google_googletest//:gtest", - ], -) - -cc_library( - name = "mocking_bit_gen", - testonly = 1, - hdrs = [ - "mocking_bit_gen.h", - ], - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":distributions", - ":random", - "//absl/base:fast_type_id", - "//absl/container:flat_hash_map", - "//absl/meta:type_traits", - "//absl/random/internal:distribution_caller", - "//absl/strings", - "//absl/types:span", - "//absl/types:variant", - "//absl/utility", - "@com_google_googletest//:gtest", - ], -) - -cc_test( - name = "bernoulli_distribution_test", - size = "small", - timeout = "eternal", # Android can take a very long time - srcs = ["bernoulli_distribution_test.cc"], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":distributions", - ":random", - "//absl/random/internal:pcg_engine", - "//absl/random/internal:sequence_urbg", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "beta_distribution_test", - size = "small", - timeout = "eternal", # Android can take a very long time - srcs = ["beta_distribution_test.cc"], - copts = ABSL_TEST_COPTS, - flaky = 1, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":distributions", - ":random", - "//absl/base:raw_logging_internal", - "//absl/random/internal:distribution_test_util", - "//absl/random/internal:pcg_engine", - "//absl/random/internal:sequence_urbg", - "//absl/strings", - "//absl/strings:str_format", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "distributions_test", - size = "small", - timeout = "moderate", - srcs = [ - "distributions_test.cc", - ], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":distributions", - ":random", - "//absl/random/internal:distribution_test_util", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "generators_test", - size = "small", - srcs = ["generators_test.cc"], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":distributions", - ":random", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "log_uniform_int_distribution_test", - size = "medium", - srcs = [ - "log_uniform_int_distribution_test.cc", - ], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":distributions", - ":random", - "//absl/base:raw_logging_internal", - "//absl/random/internal:distribution_test_util", - "//absl/random/internal:pcg_engine", - "//absl/random/internal:sequence_urbg", - "//absl/strings", - "//absl/strings:str_format", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "discrete_distribution_test", - size = "medium", - srcs = [ - "discrete_distribution_test.cc", - ], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":distributions", - ":random", - "//absl/base:raw_logging_internal", - "//absl/random/internal:distribution_test_util", - "//absl/random/internal:pcg_engine", - "//absl/random/internal:sequence_urbg", - "//absl/strings", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "poisson_distribution_test", - size = "small", - timeout = "eternal", # Android can take a very long time - srcs = [ - "poisson_distribution_test.cc", - ], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - tags = [ - # Too Slow. - "no_test_android_arm", - "no_test_loonix", - ], - deps = [ - ":distributions", - ":random", - "//absl/base:core_headers", - "//absl/base:raw_logging_internal", - "//absl/container:flat_hash_map", - "//absl/random/internal:distribution_test_util", - "//absl/random/internal:pcg_engine", - "//absl/random/internal:sequence_urbg", - "//absl/strings", - "//absl/strings:str_format", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "exponential_distribution_test", - size = "small", - srcs = ["exponential_distribution_test.cc"], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":distributions", - ":random", - "//absl/base:core_headers", - "//absl/base:raw_logging_internal", - "//absl/random/internal:distribution_test_util", - "//absl/random/internal:pcg_engine", - "//absl/random/internal:sequence_urbg", - "//absl/strings", - "//absl/strings:str_format", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "gaussian_distribution_test", - size = "small", - timeout = "eternal", # Android can take a very long time - srcs = [ - "gaussian_distribution_test.cc", - ], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":distributions", - ":random", - "//absl/base:core_headers", - "//absl/base:raw_logging_internal", - "//absl/random/internal:distribution_test_util", - "//absl/random/internal:sequence_urbg", - "//absl/strings", - "//absl/strings:str_format", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "uniform_int_distribution_test", - size = "medium", - timeout = "long", - srcs = [ - "uniform_int_distribution_test.cc", - ], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":distributions", - ":random", - "//absl/base:raw_logging_internal", - "//absl/random/internal:distribution_test_util", - "//absl/random/internal:pcg_engine", - "//absl/random/internal:sequence_urbg", - "//absl/strings", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "uniform_real_distribution_test", - size = "medium", - srcs = [ - "uniform_real_distribution_test.cc", - ], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - tags = [ - "no_test_android_arm", - "no_test_android_arm64", - "no_test_android_x86", - ], - deps = [ - ":distributions", - ":random", - "//absl/base:raw_logging_internal", - "//absl/random/internal:distribution_test_util", - "//absl/random/internal:pcg_engine", - "//absl/random/internal:sequence_urbg", - "//absl/strings", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "zipf_distribution_test", - size = "medium", - srcs = [ - "zipf_distribution_test.cc", - ], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":distributions", - ":random", - "//absl/base:raw_logging_internal", - "//absl/random/internal:distribution_test_util", - "//absl/random/internal:pcg_engine", - "//absl/random/internal:sequence_urbg", - "//absl/strings", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "bit_gen_ref_test", - size = "small", - srcs = ["bit_gen_ref_test.cc"], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":bit_gen_ref", - ":random", - "//absl/base:fast_type_id", - "//absl/random/internal:sequence_urbg", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "mocking_bit_gen_test", - size = "small", - srcs = ["mocking_bit_gen_test.cc"], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":bit_gen_ref", - ":mock_distributions", - ":mocking_bit_gen", - ":random", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "mock_distributions_test", - size = "small", - srcs = ["mock_distributions_test.cc"], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":mock_distributions", - ":mocking_bit_gen", - ":random", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "examples_test", - size = "small", - srcs = ["examples_test.cc"], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":random", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "seed_sequences_test", - size = "small", - srcs = ["seed_sequences_test.cc"], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":random", - ":seed_sequences", - "//absl/random/internal:nonsecure_base", - "@com_google_googletest//:gtest_main", - ], -) - -BENCHMARK_TAGS = [ - "benchmark", - "no_test_android_arm", - "no_test_android_arm64", - "no_test_android_x86", - "no_test_darwin_x86_64", - "no_test_ios_x86_64", - "no_test_loonix", - "no_test_msvc_x64", - "no_test_wasm", -] - -# Benchmarks for various methods / test utilities -cc_binary( - name = "benchmarks", - testonly = 1, - srcs = [ - "benchmarks.cc", - ], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - tags = BENCHMARK_TAGS, - deps = [ - ":distributions", - ":random", - ":seed_sequences", - "//absl/base:core_headers", - "//absl/meta:type_traits", - "//absl/random/internal:fast_uniform_bits", - "//absl/random/internal:randen_engine", - "@com_github_google_benchmark//:benchmark_main", - ], -) diff --git a/third_party/abseil_cpp/absl/random/CMakeLists.txt b/third_party/abseil_cpp/absl/random/CMakeLists.txt deleted file mode 100644 index 7d7bec83d9..0000000000 --- a/third_party/abseil_cpp/absl/random/CMakeLists.txt +++ /dev/null @@ -1,1207 +0,0 @@ -# -# Copyright 2019 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. -# - -absl_cc_library( - NAME - random_random - HDRS - "random.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_distributions - absl::random_internal_nonsecure_base - absl::random_internal_pcg_engine - absl::random_internal_pool_urbg - absl::random_internal_randen_engine - absl::random_seed_sequences -) - -absl_cc_library( - NAME - random_bit_gen_ref - HDRS - "bit_gen_ref.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::core_headers - absl::random_internal_distribution_caller - absl::random_internal_fast_uniform_bits - absl::type_traits -) - -absl_cc_test( - NAME - random_bit_gen_ref_test - SRCS - "bit_gen_ref_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_bit_gen_ref - absl::random_random - absl::random_internal_sequence_urbg - absl::fast_type_id - gmock - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_mock_helpers - HDRS - "internal/mock_helpers.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::fast_type_id - absl::optional -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_mock_overload_set - HDRS - "internal/mock_overload_set.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_mocking_bit_gen - absl::random_internal_mock_helpers - TESTONLY -) - -absl_cc_library( - NAME - random_mocking_bit_gen - HDRS - "mock_distributions.h" - "mocking_bit_gen.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::flat_hash_map - absl::raw_logging_internal - absl::random_distributions - absl::random_internal_distribution_caller - absl::random_internal_mock_overload_set - absl::random_random - absl::strings - absl::span - absl::type_traits - absl::utility - absl::variant - gmock - gtest - TESTONLY -) - -absl_cc_test( - NAME - random_mock_distributions_test - SRCS - "mock_distributions_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_mocking_bit_gen - absl::random_random - gmock - gtest_main -) - -absl_cc_test( - NAME - random_mocking_bit_gen_test - SRCS - "mocking_bit_gen_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_bit_gen_ref - absl::random_mocking_bit_gen - absl::random_random - gmock - gtest_main -) - -absl_cc_library( - NAME - random_distributions - SRCS - "discrete_distribution.cc" - "gaussian_distribution.cc" - HDRS - "bernoulli_distribution.h" - "beta_distribution.h" - "discrete_distribution.h" - "distributions.h" - "exponential_distribution.h" - "gaussian_distribution.h" - "log_uniform_int_distribution.h" - "poisson_distribution.h" - "uniform_int_distribution.h" - "uniform_real_distribution.h" - "zipf_distribution.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::base_internal - absl::config - absl::core_headers - absl::random_internal_generate_real - absl::random_internal_distribution_caller - absl::random_internal_fast_uniform_bits - absl::random_internal_fastmath - absl::random_internal_iostream_state_saver - absl::random_internal_traits - absl::random_internal_uniform_helper - absl::random_internal_wide_multiply - absl::strings - absl::type_traits -) - -absl_cc_library( - NAME - random_seed_gen_exception - SRCS - "seed_gen_exception.cc" - HDRS - "seed_gen_exception.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::config -) - -absl_cc_library( - NAME - random_seed_sequences - SRCS - "seed_sequences.cc" - HDRS - "seed_sequences.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::inlined_vector - absl::random_internal_nonsecure_base - absl::random_internal_pool_urbg - absl::random_internal_salted_seed_seq - absl::random_internal_seed_material - absl::random_seed_gen_exception - absl::span -) - -absl_cc_test( - NAME - random_bernoulli_distribution_test - SRCS - "bernoulli_distribution_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_distributions - absl::random_random - absl::random_internal_sequence_urbg - absl::random_internal_pcg_engine - gmock - gtest_main -) - -absl_cc_test( - NAME - random_beta_distribution_test - SRCS - "beta_distribution_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_distributions - absl::random_random - absl::random_internal_distribution_test_util - absl::random_internal_sequence_urbg - absl::random_internal_pcg_engine - absl::raw_logging_internal - absl::strings - absl::str_format - gmock - gtest_main -) - -absl_cc_test( - NAME - random_distributions_test - SRCS - "distributions_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_distributions - absl::random_random - absl::random_internal_distribution_test_util - gmock - gtest_main -) - -absl_cc_test( - NAME - random_generators_test - SRCS - "generators_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - absl::random_distributions - absl::random_random - absl::raw_logging_internal - gmock - gtest_main -) - -absl_cc_test( - NAME - random_log_uniform_int_distribution_test - SRCS - "log_uniform_int_distribution_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - absl::random_distributions - absl::random_internal_distribution_test_util - absl::random_internal_pcg_engine - absl::random_internal_sequence_urbg - absl::random_random - absl::raw_logging_internal - absl::strings - absl::str_format - gmock - gtest_main -) - -absl_cc_test( - NAME - random_discrete_distribution_test - SRCS - "discrete_distribution_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_distributions - absl::random_internal_distribution_test_util - absl::random_internal_pcg_engine - absl::random_internal_sequence_urbg - absl::random_random - absl::raw_logging_internal - absl::strings - gmock - gtest_main -) - -absl_cc_test( - NAME - random_poisson_distribution_test - SRCS - "poisson_distribution_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_distributions - absl::random_random - absl::core_headers - absl::flat_hash_map - absl::random_internal_distribution_test_util - absl::random_internal_pcg_engine - absl::random_internal_sequence_urbg - absl::raw_logging_internal - absl::strings - absl::str_format - gmock - gtest_main -) - -absl_cc_test( - NAME - random_exponential_distribution_test - SRCS - "exponential_distribution_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::core_headers - absl::random_distributions - absl::random_internal_distribution_test_util - absl::random_internal_pcg_engine - absl::random_internal_sequence_urbg - absl::random_random - absl::raw_logging_internal - absl::strings - absl::str_format - gmock - gtest_main -) - -absl_cc_test( - NAME - random_gaussian_distribution_test - SRCS - "gaussian_distribution_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::core_headers - absl::random_distributions - absl::random_internal_distribution_test_util - absl::random_internal_sequence_urbg - absl::random_random - absl::raw_logging_internal - absl::strings - absl::str_format - gmock - gtest_main -) - -absl_cc_test( - NAME - random_uniform_int_distribution_test - SRCS - "uniform_int_distribution_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_distributions - absl::random_internal_distribution_test_util - absl::random_internal_pcg_engine - absl::random_internal_sequence_urbg - absl::random_random - absl::raw_logging_internal - absl::strings - gmock - gtest_main -) - -absl_cc_test( - NAME - random_uniform_real_distribution_test - SRCS - "uniform_real_distribution_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_distributions - absl::random_internal_distribution_test_util - absl::random_internal_pcg_engine - absl::random_internal_sequence_urbg - absl::random_random - absl::strings - gmock - gtest_main -) - -absl_cc_test( - NAME - random_zipf_distribution_test - SRCS - "zipf_distribution_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_distributions - absl::random_internal_distribution_test_util - absl::random_internal_pcg_engine - absl::random_internal_sequence_urbg - absl::random_random - absl::raw_logging_internal - absl::strings - gmock - gtest_main -) - -absl_cc_test( - NAME - random_examples_test - SRCS - "examples_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_random - gtest_main -) - -absl_cc_test( - NAME - random_seed_sequences_test - SRCS - "seed_sequences_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_seed_sequences - absl::random_internal_nonsecure_base - absl::random_random - gmock - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_traits - HDRS - "internal/traits.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::config -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_distribution_caller - HDRS - "internal/distribution_caller.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::config - absl::utility - absl::fast_type_id -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_fast_uniform_bits - HDRS - "internal/fast_uniform_bits.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::config -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_seed_material - SRCS - "internal/seed_material.cc" - HDRS - "internal/seed_material.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - $<$:"bcrypt"> - DEPS - absl::core_headers - absl::optional - absl::random_internal_fast_uniform_bits - absl::raw_logging_internal - absl::span - absl::strings -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_pool_urbg - SRCS - "internal/pool_urbg.cc" - HDRS - "internal/pool_urbg.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::base - absl::config - absl::core_headers - absl::endian - absl::random_internal_randen - absl::random_internal_seed_material - absl::random_internal_traits - absl::random_seed_gen_exception - absl::raw_logging_internal - absl::span -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_explicit_seed_seq - HDRS - "internal/random_internal_explicit_seed_seq.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::config - TESTONLY -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_sequence_urbg - HDRS - "internal/sequence_urbg.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::config - TESTONLY -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_salted_seed_seq - HDRS - "internal/salted_seed_seq.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::inlined_vector - absl::optional - absl::span - absl::random_internal_seed_material - absl::type_traits -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_iostream_state_saver - HDRS - "internal/iostream_state_saver.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::int128 - absl::type_traits -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_generate_real - HDRS - "internal/generate_real.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::bits - absl::random_internal_fastmath - absl::random_internal_traits - absl::type_traits -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_wide_multiply - HDRS - "internal/wide_multiply.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::bits - absl::config - absl::int128 -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_fastmath - HDRS - "internal/fastmath.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::bits -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_nonsecure_base - HDRS - "internal/nonsecure_base.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::core_headers - absl::optional - absl::random_internal_pool_urbg - absl::random_internal_salted_seed_seq - absl::random_internal_seed_material - absl::span - absl::type_traits -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_pcg_engine - HDRS - "internal/pcg_engine.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::config - absl::int128 - absl::random_internal_fastmath - absl::random_internal_iostream_state_saver - absl::type_traits -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_randen_engine - HDRS - "internal/randen_engine.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_iostream_state_saver - absl::random_internal_randen - absl::raw_logging_internal - absl::type_traits -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_platform - HDRS - "internal/randen_traits.h" - "internal/platform.h" - SRCS - "internal/randen_round_keys.cc" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::config -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_randen - SRCS - "internal/randen.cc" - HDRS - "internal/randen.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_platform - absl::random_internal_randen_hwaes - absl::random_internal_randen_slow -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_randen_slow - SRCS - "internal/randen_slow.cc" - HDRS - "internal/randen_slow.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_platform - absl::config -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_randen_hwaes - SRCS - "internal/randen_detect.cc" - HDRS - "internal/randen_detect.h" - "internal/randen_hwaes.h" - COPTS - ${ABSL_DEFAULT_COPTS} - ${ABSL_RANDOM_RANDEN_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_platform - absl::random_internal_randen_hwaes_impl - absl::config -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_randen_hwaes_impl - SRCS - "internal/randen_hwaes.cc" - "internal/randen_hwaes.h" - COPTS - ${ABSL_DEFAULT_COPTS} - ${ABSL_RANDOM_RANDEN_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_platform - absl::config -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_distribution_test_util - SRCS - "internal/chi_square.cc" - "internal/distribution_test_util.cc" - HDRS - "internal/chi_square.h" - "internal/distribution_test_util.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::config - absl::core_headers - absl::raw_logging_internal - absl::strings - absl::str_format - absl::span -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_traits_test - SRCS - "internal/traits_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_traits - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_generate_real_test - SRCS - "internal/generate_real_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::bits - absl::flags - absl::random_internal_generate_real - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_distribution_test_util_test - SRCS - "internal/distribution_test_util_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_distribution_test_util - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_fastmath_test - SRCS - "internal/fastmath_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_fastmath - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_explicit_seed_seq_test - SRCS - "internal/explicit_seed_seq_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_explicit_seed_seq - absl::random_seed_sequences - gmock - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_salted_seed_seq_test - SRCS - "internal/salted_seed_seq_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_salted_seed_seq - gmock - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_chi_square_test - SRCS - "internal/chi_square_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::core_headers - absl::random_internal_distribution_test_util - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_fast_uniform_bits_test - SRCS - "internal/fast_uniform_bits_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_fast_uniform_bits - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_nonsecure_base_test - SRCS - "internal/nonsecure_base_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_nonsecure_base - absl::random_random - absl::random_distributions - absl::random_seed_sequences - absl::strings - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_seed_material_test - SRCS - "internal/seed_material_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_seed_material - gmock - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_pool_urbg_test - SRCS - "internal/pool_urbg_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_pool_urbg - absl::span - absl::type_traits - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_pcg_engine_test - SRCS - "internal/pcg_engine_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_explicit_seed_seq - absl::random_internal_pcg_engine - absl::time - gmock - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_randen_engine_test - SRCS - "internal/randen_engine_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_explicit_seed_seq - absl::random_internal_randen_engine - absl::raw_logging_internal - absl::strings - absl::time - gmock - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_randen_test - SRCS - "internal/randen_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_randen - absl::type_traits - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_randen_slow_test - SRCS - "internal/randen_slow_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_randen_slow - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_randen_hwaes_test - SRCS - "internal/randen_hwaes_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_platform - absl::random_internal_randen_hwaes - absl::random_internal_randen_hwaes_impl - absl::raw_logging_internal - absl::str_format - gmock - gtest -) - -# Internal-only target, do not depend on directly. -absl_cc_library( - NAME - random_internal_uniform_helper - HDRS - "internal/uniform_helper.h" - COPTS - ${ABSL_DEFAULT_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::config - absl::random_internal_traits - absl::type_traits -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_uniform_helper_test - SRCS - "internal/uniform_helper_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_uniform_helper - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_iostream_state_saver_test - SRCS - "internal/iostream_state_saver_test.cc" - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_iostream_state_saver - gtest_main -) - -# Internal-only target, do not depend on directly. -absl_cc_test( - NAME - random_internal_wide_multiply_test - SRCS - internal/wide_multiply_test.cc - COPTS - ${ABSL_TEST_COPTS} - LINKOPTS - ${ABSL_DEFAULT_LINKOPTS} - DEPS - absl::random_internal_wide_multiply - absl::bits - absl::int128 - gtest_main -) diff --git a/third_party/abseil_cpp/absl/random/benchmarks.cc b/third_party/abseil_cpp/absl/random/benchmarks.cc deleted file mode 100644 index 87bbb9810a..0000000000 --- a/third_party/abseil_cpp/absl/random/benchmarks.cc +++ /dev/null @@ -1,383 +0,0 @@ -// 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 -// -// 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. - -// Benchmarks for absl random distributions as well as a selection of the -// C++ standard library random distributions. - -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include "absl/base/macros.h" -#include "absl/meta/type_traits.h" -#include "absl/random/bernoulli_distribution.h" -#include "absl/random/beta_distribution.h" -#include "absl/random/exponential_distribution.h" -#include "absl/random/gaussian_distribution.h" -#include "absl/random/internal/fast_uniform_bits.h" -#include "absl/random/internal/randen_engine.h" -#include "absl/random/log_uniform_int_distribution.h" -#include "absl/random/poisson_distribution.h" -#include "absl/random/random.h" -#include "absl/random/uniform_int_distribution.h" -#include "absl/random/uniform_real_distribution.h" -#include "absl/random/zipf_distribution.h" -#include "benchmark/benchmark.h" - -namespace { - -// Seed data to avoid reading random_device() for benchmarks. -uint32_t kSeedData[] = { - 0x1B510052, 0x9A532915, 0xD60F573F, 0xBC9BC6E4, 0x2B60A476, 0x81E67400, - 0x08BA6FB5, 0x571BE91F, 0xF296EC6B, 0x2A0DD915, 0xB6636521, 0xE7B9F9B6, - 0xFF34052E, 0xC5855664, 0x53B02D5D, 0xA99F8FA1, 0x08BA4799, 0x6E85076A, - 0x4B7A70E9, 0xB5B32944, 0xDB75092E, 0xC4192623, 0xAD6EA6B0, 0x49A7DF7D, - 0x9CEE60B8, 0x8FEDB266, 0xECAA8C71, 0x699A18FF, 0x5664526C, 0xC2B19EE1, - 0x193602A5, 0x75094C29, 0xA0591340, 0xE4183A3E, 0x3F54989A, 0x5B429D65, - 0x6B8FE4D6, 0x99F73FD6, 0xA1D29C07, 0xEFE830F5, 0x4D2D38E6, 0xF0255DC1, - 0x4CDD2086, 0x8470EB26, 0x6382E9C6, 0x021ECC5E, 0x09686B3F, 0x3EBAEFC9, - 0x3C971814, 0x6B6A70A1, 0x687F3584, 0x52A0E286, 0x13198A2E, 0x03707344, -}; - -// PrecompiledSeedSeq provides kSeedData to a conforming -// random engine to speed initialization in the benchmarks. -class PrecompiledSeedSeq { - public: - using result_type = uint32_t; - - PrecompiledSeedSeq() {} - - template - PrecompiledSeedSeq(Iterator begin, Iterator end) {} - - template - PrecompiledSeedSeq(std::initializer_list il) {} - - template - void generate(OutIterator begin, OutIterator end) { - static size_t idx = 0; - for (; begin != end; begin++) { - *begin = kSeedData[idx++]; - if (idx >= ABSL_ARRAYSIZE(kSeedData)) { - idx = 0; - } - } - } - - size_t size() const { return ABSL_ARRAYSIZE(kSeedData); } - - template - void param(OutIterator out) const { - std::copy(std::begin(kSeedData), std::end(kSeedData), out); - } -}; - -// use_default_initialization indicates whether the random engine -// T must be default initialized, or whether we may initialize it using -// a seed sequence. This is used because some engines do not accept seed -// sequence-based initialization. -template -using use_default_initialization = std::false_type; - -// make_engine returns a random_engine which is initialized, -// either via the default constructor, when use_default_initialization -// is true, or via the indicated seed sequence, SSeq. -template -typename absl::enable_if_t::value, Engine> -make_engine() { - // Initialize the random engine using the seed sequence SSeq, which - // is constructed from the precompiled seed data. - SSeq seq(std::begin(kSeedData), std::end(kSeedData)); - return Engine(seq); -} - -template -typename absl::enable_if_t::value, Engine> -make_engine() { - // Initialize the random engine using the default constructor. - return Engine(); -} - -template -void BM_Construct(benchmark::State& state) { - for (auto _ : state) { - auto rng = make_engine(); - benchmark::DoNotOptimize(rng()); - } -} - -template -void BM_Direct(benchmark::State& state) { - using value_type = typename Engine::result_type; - // Direct use of the URBG. - auto rng = make_engine(); - for (auto _ : state) { - benchmark::DoNotOptimize(rng()); - } - state.SetBytesProcessed(sizeof(value_type) * state.iterations()); -} - -template -void BM_Generate(benchmark::State& state) { - // std::generate makes a copy of the RNG; thus this tests the - // copy-constructor efficiency. - using value_type = typename Engine::result_type; - std::vector v(64); - auto rng = make_engine(); - while (state.KeepRunningBatch(64)) { - std::generate(std::begin(v), std::end(v), rng); - } -} - -template -void BM_Shuffle(benchmark::State& state) { - // Direct use of the Engine. - std::vector v(elems); - while (state.KeepRunningBatch(elems)) { - auto rng = make_engine(); - std::shuffle(std::begin(v), std::end(v), rng); - } -} - -template -void BM_ShuffleReuse(benchmark::State& state) { - // Direct use of the Engine. - std::vector v(elems); - auto rng = make_engine(); - while (state.KeepRunningBatch(elems)) { - std::shuffle(std::begin(v), std::end(v), rng); - } -} - -template -void BM_Dist(benchmark::State& state, Args&&... args) { - using value_type = typename Dist::result_type; - auto rng = make_engine(); - Dist dis{std::forward(args)...}; - // Compare the following loop performance: - for (auto _ : state) { - benchmark::DoNotOptimize(dis(rng)); - } - state.SetBytesProcessed(sizeof(value_type) * state.iterations()); -} - -template -void BM_Large(benchmark::State& state) { - using value_type = typename Dist::result_type; - volatile value_type kMin = 0; - volatile value_type kMax = std::numeric_limits::max() / 2 + 1; - BM_Dist(state, kMin, kMax); -} - -template -void BM_Small(benchmark::State& state) { - using value_type = typename Dist::result_type; - volatile value_type kMin = 0; - volatile value_type kMax = std::numeric_limits::max() / 64 + 1; - BM_Dist(state, kMin, kMax); -} - -template -void BM_Bernoulli(benchmark::State& state) { - volatile double a = static_cast(A) / 1000000; - BM_Dist(state, a); -} - -template -void BM_Beta(benchmark::State& state) { - using value_type = typename Dist::result_type; - volatile value_type a = static_cast(A) / 100; - volatile value_type b = static_cast(B) / 100; - BM_Dist(state, a, b); -} - -template -void BM_Gamma(benchmark::State& state) { - using value_type = typename Dist::result_type; - volatile value_type a = static_cast(A) / 100; - BM_Dist(state, a); -} - -template -void BM_Poisson(benchmark::State& state) { - volatile double a = static_cast(A) / 100; - BM_Dist(state, a); -} - -template -void BM_Zipf(benchmark::State& state) { - using value_type = typename Dist::result_type; - volatile double q = Q; - volatile double v = V; - BM_Dist(state, std::numeric_limits::max(), q, v); -} - -template -void BM_Thread(benchmark::State& state) { - using value_type = typename Dist::result_type; - auto rng = make_engine(); - Dist dis{}; - for (auto _ : state) { - benchmark::DoNotOptimize(dis(rng)); - } - state.SetBytesProcessed(sizeof(value_type) * state.iterations()); -} - -// NOTES: -// -// std::geometric_distribution is similar to the zipf distributions. -// The algorithm for the geometric_distribution is, basically, -// floor(log(1-X) / log(1-p)) - -// Normal benchmark suite -#define BM_BASIC(Engine) \ - BENCHMARK_TEMPLATE(BM_Construct, Engine, PrecompiledSeedSeq); \ - BENCHMARK_TEMPLATE(BM_Construct, Engine, std::seed_seq); \ - BENCHMARK_TEMPLATE(BM_Direct, Engine); \ - BENCHMARK_TEMPLATE(BM_Shuffle, Engine, 10); \ - BENCHMARK_TEMPLATE(BM_Shuffle, Engine, 100); \ - BENCHMARK_TEMPLATE(BM_Shuffle, Engine, 1000); \ - BENCHMARK_TEMPLATE(BM_ShuffleReuse, Engine, 100); \ - BENCHMARK_TEMPLATE(BM_ShuffleReuse, Engine, 1000); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, \ - absl::random_internal::FastUniformBits); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, \ - absl::random_internal::FastUniformBits); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, std::uniform_int_distribution); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, std::uniform_int_distribution); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, \ - absl::uniform_int_distribution); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, \ - absl::uniform_int_distribution); \ - BENCHMARK_TEMPLATE(BM_Large, Engine, \ - std::uniform_int_distribution); \ - BENCHMARK_TEMPLATE(BM_Large, Engine, \ - std::uniform_int_distribution); \ - BENCHMARK_TEMPLATE(BM_Large, Engine, \ - absl::uniform_int_distribution); \ - BENCHMARK_TEMPLATE(BM_Large, Engine, \ - absl::uniform_int_distribution); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, std::uniform_real_distribution); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, std::uniform_real_distribution); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, absl::uniform_real_distribution); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, absl::uniform_real_distribution) - -#define BM_COPY(Engine) BENCHMARK_TEMPLATE(BM_Generate, Engine) - -#define BM_THREAD(Engine) \ - BENCHMARK_TEMPLATE(BM_Thread, Engine, \ - absl::uniform_int_distribution) \ - ->ThreadPerCpu(); \ - BENCHMARK_TEMPLATE(BM_Thread, Engine, \ - absl::uniform_real_distribution) \ - ->ThreadPerCpu(); \ - BENCHMARK_TEMPLATE(BM_Shuffle, Engine, 100)->ThreadPerCpu(); \ - BENCHMARK_TEMPLATE(BM_Shuffle, Engine, 1000)->ThreadPerCpu(); \ - BENCHMARK_TEMPLATE(BM_ShuffleReuse, Engine, 100)->ThreadPerCpu(); \ - BENCHMARK_TEMPLATE(BM_ShuffleReuse, Engine, 1000)->ThreadPerCpu(); - -#define BM_EXTENDED(Engine) \ - /* -------------- Extended Uniform -----------------------*/ \ - BENCHMARK_TEMPLATE(BM_Small, Engine, \ - std::uniform_int_distribution); \ - BENCHMARK_TEMPLATE(BM_Small, Engine, \ - std::uniform_int_distribution); \ - BENCHMARK_TEMPLATE(BM_Small, Engine, \ - absl::uniform_int_distribution); \ - BENCHMARK_TEMPLATE(BM_Small, Engine, \ - absl::uniform_int_distribution); \ - BENCHMARK_TEMPLATE(BM_Small, Engine, std::uniform_real_distribution); \ - BENCHMARK_TEMPLATE(BM_Small, Engine, \ - std::uniform_real_distribution); \ - BENCHMARK_TEMPLATE(BM_Small, Engine, \ - absl::uniform_real_distribution); \ - BENCHMARK_TEMPLATE(BM_Small, Engine, \ - absl::uniform_real_distribution); \ - /* -------------- Other -----------------------*/ \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, std::normal_distribution); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, absl::gaussian_distribution); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, std::exponential_distribution); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, absl::exponential_distribution); \ - BENCHMARK_TEMPLATE(BM_Poisson, Engine, std::poisson_distribution, \ - 100); \ - BENCHMARK_TEMPLATE(BM_Poisson, Engine, absl::poisson_distribution, \ - 100); \ - BENCHMARK_TEMPLATE(BM_Poisson, Engine, std::poisson_distribution, \ - 10 * 100); \ - BENCHMARK_TEMPLATE(BM_Poisson, Engine, absl::poisson_distribution, \ - 10 * 100); \ - BENCHMARK_TEMPLATE(BM_Poisson, Engine, std::poisson_distribution, \ - 13 * 100); \ - BENCHMARK_TEMPLATE(BM_Poisson, Engine, absl::poisson_distribution, \ - 13 * 100); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, \ - absl::log_uniform_int_distribution); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, \ - absl::log_uniform_int_distribution); \ - BENCHMARK_TEMPLATE(BM_Dist, Engine, std::geometric_distribution); \ - BENCHMARK_TEMPLATE(BM_Zipf, Engine, absl::zipf_distribution); \ - BENCHMARK_TEMPLATE(BM_Zipf, Engine, absl::zipf_distribution, 2, \ - 3); \ - BENCHMARK_TEMPLATE(BM_Bernoulli, Engine, std::bernoulli_distribution, \ - 257305); \ - BENCHMARK_TEMPLATE(BM_Bernoulli, Engine, absl::bernoulli_distribution, \ - 257305); \ - BENCHMARK_TEMPLATE(BM_Beta, Engine, absl::beta_distribution, 65, \ - 41); \ - BENCHMARK_TEMPLATE(BM_Beta, Engine, absl::beta_distribution, 99, \ - 330); \ - BENCHMARK_TEMPLATE(BM_Beta, Engine, absl::beta_distribution, 150, \ - 150); \ - BENCHMARK_TEMPLATE(BM_Beta, Engine, absl::beta_distribution, 410, \ - 580); \ - BENCHMARK_TEMPLATE(BM_Beta, Engine, absl::beta_distribution, 65, 41); \ - BENCHMARK_TEMPLATE(BM_Beta, Engine, absl::beta_distribution, 99, \ - 330); \ - BENCHMARK_TEMPLATE(BM_Beta, Engine, absl::beta_distribution, 150, \ - 150); \ - BENCHMARK_TEMPLATE(BM_Beta, Engine, absl::beta_distribution, 410, \ - 580); \ - BENCHMARK_TEMPLATE(BM_Gamma, Engine, std::gamma_distribution, 199); \ - BENCHMARK_TEMPLATE(BM_Gamma, Engine, std::gamma_distribution, 199); - -// ABSL Recommended interfaces. -BM_BASIC(absl::InsecureBitGen); // === pcg64_2018_engine -BM_BASIC(absl::BitGen); // === randen_engine. -BM_THREAD(absl::BitGen); -BM_EXTENDED(absl::BitGen); - -// Instantiate benchmarks for multiple engines. -using randen_engine_64 = absl::random_internal::randen_engine; -using randen_engine_32 = absl::random_internal::randen_engine; - -// Comparison interfaces. -BM_BASIC(std::mt19937_64); -BM_COPY(std::mt19937_64); -BM_EXTENDED(std::mt19937_64); -BM_BASIC(randen_engine_64); -BM_COPY(randen_engine_64); -BM_EXTENDED(randen_engine_64); - -BM_BASIC(std::mt19937); -BM_COPY(std::mt19937); -BM_BASIC(randen_engine_32); -BM_COPY(randen_engine_32); - -} // namespace diff --git a/third_party/abseil_cpp/absl/random/bernoulli_distribution.h b/third_party/abseil_cpp/absl/random/bernoulli_distribution.h deleted file mode 100644 index 25bd0d5ca4..0000000000 --- a/third_party/abseil_cpp/absl/random/bernoulli_distribution.h +++ /dev/null @@ -1,200 +0,0 @@ -// 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 -// -// 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. - -#ifndef ABSL_RANDOM_BERNOULLI_DISTRIBUTION_H_ -#define ABSL_RANDOM_BERNOULLI_DISTRIBUTION_H_ - -#include -#include -#include - -#include "absl/base/optimization.h" -#include "absl/random/internal/fast_uniform_bits.h" -#include "absl/random/internal/iostream_state_saver.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN - -// absl::bernoulli_distribution is a drop in replacement for -// std::bernoulli_distribution. It guarantees that (given a perfect -// UniformRandomBitGenerator) the acceptance probability is *exactly* equal to -// the given double. -// -// The implementation assumes that double is IEEE754 -class bernoulli_distribution { - public: - using result_type = bool; - - class param_type { - public: - using distribution_type = bernoulli_distribution; - - explicit param_type(double p = 0.5) : prob_(p) { - assert(p >= 0.0 && p <= 1.0); - } - - double p() const { return prob_; } - - friend bool operator==(const param_type& p1, const param_type& p2) { - return p1.p() == p2.p(); - } - friend bool operator!=(const param_type& p1, const param_type& p2) { - return p1.p() != p2.p(); - } - - private: - double prob_; - }; - - bernoulli_distribution() : bernoulli_distribution(0.5) {} - - explicit bernoulli_distribution(double p) : param_(p) {} - - explicit bernoulli_distribution(param_type p) : param_(p) {} - - // no-op - void reset() {} - - template - bool operator()(URBG& g) { // NOLINT(runtime/references) - return Generate(param_.p(), g); - } - - template - bool operator()(URBG& g, // NOLINT(runtime/references) - const param_type& param) { - return Generate(param.p(), g); - } - - param_type param() const { return param_; } - void param(const param_type& param) { param_ = param; } - - double p() const { return param_.p(); } - - result_type(min)() const { return false; } - result_type(max)() const { return true; } - - friend bool operator==(const bernoulli_distribution& d1, - const bernoulli_distribution& d2) { - return d1.param_ == d2.param_; - } - - friend bool operator!=(const bernoulli_distribution& d1, - const bernoulli_distribution& d2) { - return d1.param_ != d2.param_; - } - - private: - static constexpr uint64_t kP32 = static_cast(1) << 32; - - template - static bool Generate(double p, URBG& g); // NOLINT(runtime/references) - - param_type param_; -}; - -template -std::basic_ostream& operator<<( - std::basic_ostream& os, // NOLINT(runtime/references) - const bernoulli_distribution& x) { - auto saver = random_internal::make_ostream_state_saver(os); - os.precision(random_internal::stream_precision_helper::kPrecision); - os << x.p(); - return os; -} - -template -std::basic_istream& operator>>( - std::basic_istream& is, // NOLINT(runtime/references) - bernoulli_distribution& x) { // NOLINT(runtime/references) - auto saver = random_internal::make_istream_state_saver(is); - auto p = random_internal::read_floating_point(is); - if (!is.fail()) { - x.param(bernoulli_distribution::param_type(p)); - } - return is; -} - -template -bool bernoulli_distribution::Generate(double p, - URBG& g) { // NOLINT(runtime/references) - random_internal::FastUniformBits fast_u32; - - while (true) { - // There are two aspects of the definition of `c` below that are worth - // commenting on. First, because `p` is in the range [0, 1], `c` is in the - // range [0, 2^32] which does not fit in a uint32_t and therefore requires - // 64 bits. - // - // Second, `c` is constructed by first casting explicitly to a signed - // integer and then converting implicitly to an unsigned integer of the same - // size. This is done because the hardware conversion instructions produce - // signed integers from double; if taken as a uint64_t the conversion would - // be wrong for doubles greater than 2^63 (not relevant in this use-case). - // If converted directly to an unsigned integer, the compiler would end up - // emitting code to handle such large values that are not relevant due to - // the known bounds on `c`. To avoid these extra instructions this - // implementation converts first to the signed type and then use the - // implicit conversion to unsigned (which is a no-op). - const uint64_t c = static_cast(p * kP32); - const uint32_t v = fast_u32(g); - // FAST PATH: this path fails with probability 1/2^32. Note that simply - // returning v <= c would approximate P very well (up to an absolute error - // of 1/2^32); the slow path (taken in that range of possible error, in the - // case of equality) eliminates the remaining error. - if (ABSL_PREDICT_TRUE(v != c)) return v < c; - - // It is guaranteed that `q` is strictly less than 1, because if `q` were - // greater than or equal to 1, the same would be true for `p`. Certainly `p` - // cannot be greater than 1, and if `p == 1`, then the fast path would - // necessary have been taken already. - const double q = static_cast(c) / kP32; - - // The probability of acceptance on the fast path is `q` and so the - // probability of acceptance here should be `p - q`. - // - // Note that `q` is obtained from `p` via some shifts and conversions, the - // upshot of which is that `q` is simply `p` with some of the - // least-significant bits of its mantissa set to zero. This means that the - // difference `p - q` will not have any rounding errors. To see why, pretend - // that double has 10 bits of resolution and q is obtained from `p` in such - // a way that the 4 least-significant bits of its mantissa are set to zero. - // For example: - // p = 1.1100111011 * 2^-1 - // q = 1.1100110000 * 2^-1 - // p - q = 1.011 * 2^-8 - // The difference `p - q` has exactly the nonzero mantissa bits that were - // "lost" in `q` producing a number which is certainly representable in a - // double. - const double left = p - q; - - // By construction, the probability of being on this slow path is 1/2^32, so - // P(accept in slow path) = P(accept| in slow path) * P(slow path), - // which means the probability of acceptance here is `1 / (left * kP32)`: - const double here = left * kP32; - - // The simplest way to compute the result of this trial is to repeat the - // whole algorithm with the new probability. This terminates because even - // given arbitrarily unfriendly "random" bits, each iteration either - // multiplies a tiny probability by 2^32 (if c == 0) or strips off some - // number of nonzero mantissa bits. That process is bounded. - if (here == 0) return false; - p = here; - } -} - -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_RANDOM_BERNOULLI_DISTRIBUTION_H_ diff --git a/third_party/abseil_cpp/absl/random/bernoulli_distribution_test.cc b/third_party/abseil_cpp/absl/random/bernoulli_distribution_test.cc deleted file mode 100644 index b250f8787c..0000000000 --- a/third_party/abseil_cpp/absl/random/bernoulli_distribution_test.cc +++ /dev/null @@ -1,217 +0,0 @@ -// 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 -// -// 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 "absl/random/bernoulli_distribution.h" - -#include -#include -#include -#include -#include - -#include "gtest/gtest.h" -#include "absl/random/internal/pcg_engine.h" -#include "absl/random/internal/sequence_urbg.h" -#include "absl/random/random.h" - -namespace { - -class BernoulliTest : public testing::TestWithParam> { -}; - -TEST_P(BernoulliTest, Serialize) { - const double d = GetParam().first; - absl::bernoulli_distribution before(d); - - { - absl::bernoulli_distribution via_param{ - absl::bernoulli_distribution::param_type(d)}; - EXPECT_EQ(via_param, before); - } - - std::stringstream ss; - ss << before; - absl::bernoulli_distribution after(0.6789); - - EXPECT_NE(before.p(), after.p()); - EXPECT_NE(before.param(), after.param()); - EXPECT_NE(before, after); - - ss >> after; - - EXPECT_EQ(before.p(), after.p()); - EXPECT_EQ(before.param(), after.param()); - EXPECT_EQ(before, after); -} - -TEST_P(BernoulliTest, Accuracy) { - // Sadly, the claim to fame for this implementation is precise accuracy, which - // is very, very hard to measure, the improvements come as trials approach the - // limit of double accuracy; thus the outcome differs from the - // std::bernoulli_distribution with a probability of approximately 1 in 2^-53. - const std::pair para = GetParam(); - size_t trials = para.second; - double p = para.first; - - // We use a fixed bit generator for distribution accuracy tests. This allows - // these tests to be deterministic, while still testing the qualify of the - // implementation. - absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6); - - size_t yes = 0; - absl::bernoulli_distribution dist(p); - for (size_t i = 0; i < trials; ++i) { - if (dist(rng)) yes++; - } - - // Compute the distribution parameters for a binomial test, using a normal - // approximation for the confidence interval, as there are a sufficiently - // large number of trials that the central limit theorem applies. - const double stddev_p = std::sqrt((p * (1.0 - p)) / trials); - const double expected = trials * p; - const double stddev = trials * stddev_p; - - // 5 sigma, approved by Richard Feynman - EXPECT_NEAR(yes, expected, 5 * stddev) - << "@" << p << ", " - << std::abs(static_cast(yes) - expected) / stddev << " stddev"; -} - -// There must be many more trials to make the mean approximately normal for `p` -// closes to 0 or 1. -INSTANTIATE_TEST_SUITE_P( - All, BernoulliTest, - ::testing::Values( - // Typical values. - std::make_pair(0, 30000), std::make_pair(1e-3, 30000000), - std::make_pair(0.1, 3000000), std::make_pair(0.5, 3000000), - std::make_pair(0.9, 30000000), std::make_pair(0.999, 30000000), - std::make_pair(1, 30000), - // Boundary cases. - std::make_pair(std::nextafter(1.0, 0.0), 1), // ~1 - epsilon - std::make_pair(std::numeric_limits::epsilon(), 1), - std::make_pair(std::nextafter(std::numeric_limits::min(), - 1.0), // min + epsilon - 1), - std::make_pair(std::numeric_limits::min(), // smallest normal - 1), - std::make_pair( - std::numeric_limits::denorm_min(), // smallest denorm - 1), - std::make_pair(std::numeric_limits::min() / 2, 1), // denorm - std::make_pair(std::nextafter(std::numeric_limits::min(), - 0.0), // denorm_max - 1))); - -// NOTE: absl::bernoulli_distribution is not guaranteed to be stable. -TEST(BernoulliTest, StabilityTest) { - // absl::bernoulli_distribution stability relies on FastUniformBits and - // integer arithmetic. - absl::random_internal::sequence_urbg urbg({ - 0x0003eb76f6f7f755ull, 0xFFCEA50FDB2F953Bull, 0xC332DDEFBE6C5AA5ull, - 0x6558218568AB9702ull, 0x2AEF7DAD5B6E2F84ull, 0x1521B62829076170ull, - 0xECDD4775619F1510ull, 0x13CCA830EB61BD96ull, 0x0334FE1EAA0363CFull, - 0xB5735C904C70A239ull, 0xD59E9E0BCBAADE14ull, 0xEECC86BC60622CA7ull, - 0x4864f22c059bf29eull, 0x247856d8b862665cull, 0xe46e86e9a1337e10ull, - 0xd8c8541f3519b133ull, 0xe75b5162c567b9e4ull, 0xf732e5ded7009c5bull, - 0xb170b98353121eacull, 0x1ec2e8986d2362caull, 0x814c8e35fe9a961aull, - 0x0c3cd59c9b638a02ull, 0xcb3bb6478a07715cull, 0x1224e62c978bbc7full, - 0x671ef2cb04e81f6eull, 0x3c1cbd811eaf1808ull, 0x1bbc23cfa8fac721ull, - 0xa4c2cda65e596a51ull, 0xb77216fad37adf91ull, 0x836d794457c08849ull, - 0xe083df03475f49d7ull, 0xbc9feb512e6b0d6cull, 0xb12d74fdd718c8c5ull, - 0x12ff09653bfbe4caull, 0x8dd03a105bc4ee7eull, 0x5738341045ba0d85ull, - 0xe3fd722dc65ad09eull, 0x5a14fd21ea2a5705ull, 0x14e6ea4d6edb0c73ull, - 0x275b0dc7e0a18acfull, 0x36cebe0d2653682eull, 0x0361e9b23861596bull, - }); - - // Generate a string of '0' and '1' for the distribution output. - auto generate = [&urbg](absl::bernoulli_distribution& dist) { - std::string output; - output.reserve(36); - urbg.reset(); - for (int i = 0; i < 35; i++) { - output.append(dist(urbg) ? "1" : "0"); - } - return output; - }; - - const double kP = 0.0331289862362; - { - absl::bernoulli_distribution dist(kP); - auto v = generate(dist); - EXPECT_EQ(35, urbg.invocations()); - EXPECT_EQ(v, "00000000000010000000000010000000000") << dist; - } - { - absl::bernoulli_distribution dist(kP * 10.0); - auto v = generate(dist); - EXPECT_EQ(35, urbg.invocations()); - EXPECT_EQ(v, "00000100010010010010000011000011010") << dist; - } - { - absl::bernoulli_distribution dist(kP * 20.0); - auto v = generate(dist); - EXPECT_EQ(35, urbg.invocations()); - EXPECT_EQ(v, "00011110010110110011011111110111011") << dist; - } - { - absl::bernoulli_distribution dist(1.0 - kP); - auto v = generate(dist); - EXPECT_EQ(35, urbg.invocations()); - EXPECT_EQ(v, "11111111111111111111011111111111111") << dist; - } -} - -TEST(BernoulliTest, StabilityTest2) { - absl::random_internal::sequence_urbg urbg( - {0x0003eb76f6f7f755ull, 0xFFCEA50FDB2F953Bull, 0xC332DDEFBE6C5AA5ull, - 0x6558218568AB9702ull, 0x2AEF7DAD5B6E2F84ull, 0x1521B62829076170ull, - 0xECDD4775619F1510ull, 0x13CCA830EB61BD96ull, 0x0334FE1EAA0363CFull, - 0xB5735C904C70A239ull, 0xD59E9E0BCBAADE14ull, 0xEECC86BC60622CA7ull}); - - // Generate a string of '0' and '1' for the distribution output. - auto generate = [&urbg](absl::bernoulli_distribution& dist) { - std::string output; - output.reserve(13); - urbg.reset(); - for (int i = 0; i < 12; i++) { - output.append(dist(urbg) ? "1" : "0"); - } - return output; - }; - - constexpr double b0 = 1.0 / 13.0 / 0.2; - constexpr double b1 = 2.0 / 13.0 / 0.2; - constexpr double b3 = (5.0 / 13.0 / 0.2) - ((1 - b0) + (1 - b1) + (1 - b1)); - { - absl::bernoulli_distribution dist(b0); - auto v = generate(dist); - EXPECT_EQ(12, urbg.invocations()); - EXPECT_EQ(v, "000011100101") << dist; - } - { - absl::bernoulli_distribution dist(b1); - auto v = generate(dist); - EXPECT_EQ(12, urbg.invocations()); - EXPECT_EQ(v, "001111101101") << dist; - } - { - absl::bernoulli_distribution dist(b3); - auto v = generate(dist); - EXPECT_EQ(12, urbg.invocations()); - EXPECT_EQ(v, "001111101111") << dist; - } -} - -} // namespace diff --git a/third_party/abseil_cpp/absl/random/beta_distribution.h b/third_party/abseil_cpp/absl/random/beta_distribution.h deleted file mode 100644 index c154066fb8..0000000000 --- a/third_party/abseil_cpp/absl/random/beta_distribution.h +++ /dev/null @@ -1,427 +0,0 @@ -// 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 -// -// 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. - -#ifndef ABSL_RANDOM_BETA_DISTRIBUTION_H_ -#define ABSL_RANDOM_BETA_DISTRIBUTION_H_ - -#include -#include -#include -#include -#include -#include - -#include "absl/meta/type_traits.h" -#include "absl/random/internal/fast_uniform_bits.h" -#include "absl/random/internal/fastmath.h" -#include "absl/random/internal/generate_real.h" -#include "absl/random/internal/iostream_state_saver.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN - -// absl::beta_distribution: -// Generate a floating-point variate conforming to a Beta distribution: -// pdf(x) \propto x^(alpha-1) * (1-x)^(beta-1), -// where the params alpha and beta are both strictly positive real values. -// -// The support is the open interval (0, 1), but the return value might be equal -// to 0 or 1, due to numerical errors when alpha and beta are very different. -// -// Usage note: One usage is that alpha and beta are counts of number of -// successes and failures. When the total number of trials are large, consider -// approximating a beta distribution with a Gaussian distribution with the same -// mean and variance. One could use the skewness, which depends only on the -// smaller of alpha and beta when the number of trials are sufficiently large, -// to quantify how far a beta distribution is from the normal distribution. -template -class beta_distribution { - public: - using result_type = RealType; - - class param_type { - public: - using distribution_type = beta_distribution; - - explicit param_type(result_type alpha, result_type beta) - : alpha_(alpha), beta_(beta) { - assert(alpha >= 0); - assert(beta >= 0); - assert(alpha <= (std::numeric_limits::max)()); - assert(beta <= (std::numeric_limits::max)()); - if (alpha == 0 || beta == 0) { - method_ = DEGENERATE_SMALL; - x_ = (alpha >= beta) ? 1 : 0; - return; - } - // a_ = min(beta, alpha), b_ = max(beta, alpha). - if (beta < alpha) { - inverted_ = true; - a_ = beta; - b_ = alpha; - } else { - inverted_ = false; - a_ = alpha; - b_ = beta; - } - if (a_ <= 1 && b_ >= ThresholdForLargeA()) { - method_ = DEGENERATE_SMALL; - x_ = inverted_ ? result_type(1) : result_type(0); - return; - } - // For threshold values, see also: - // Evaluation of Beta Generation Algorithms, Ying-Chao Hung, et. al. - // February, 2009. - if ((b_ < 1.0 && a_ + b_ <= 1.2) || a_ <= ThresholdForSmallA()) { - // Choose Joehnk over Cheng when it's faster or when Cheng encounters - // numerical issues. - method_ = JOEHNK; - a_ = result_type(1) / alpha_; - b_ = result_type(1) / beta_; - if (std::isinf(a_) || std::isinf(b_)) { - method_ = DEGENERATE_SMALL; - x_ = inverted_ ? result_type(1) : result_type(0); - } - return; - } - if (a_ >= ThresholdForLargeA()) { - method_ = DEGENERATE_LARGE; - // Note: on PPC for long double, evaluating - // `std::numeric_limits::max() / ThresholdForLargeA` results in NaN. - result_type r = a_ / b_; - x_ = (inverted_ ? result_type(1) : r) / (1 + r); - return; - } - x_ = a_ + b_; - log_x_ = std::log(x_); - if (a_ <= 1) { - method_ = CHENG_BA; - y_ = result_type(1) / a_; - gamma_ = a_ + a_; - return; - } - method_ = CHENG_BB; - result_type r = (a_ - 1) / (b_ - 1); - y_ = std::sqrt((1 + r) / (b_ * r * 2 - r + 1)); - gamma_ = a_ + result_type(1) / y_; - } - - result_type alpha() const { return alpha_; } - result_type beta() const { return beta_; } - - friend bool operator==(const param_type& a, const param_type& b) { - return a.alpha_ == b.alpha_ && a.beta_ == b.beta_; - } - - friend bool operator!=(const param_type& a, const param_type& b) { - return !(a == b); - } - - private: - friend class beta_distribution; - -#ifdef _MSC_VER - // MSVC does not have constexpr implementations for std::log and std::exp - // so they are computed at runtime. -#define ABSL_RANDOM_INTERNAL_LOG_EXP_CONSTEXPR -#else -#define ABSL_RANDOM_INTERNAL_LOG_EXP_CONSTEXPR constexpr -#endif - - // The threshold for whether std::exp(1/a) is finite. - // Note that this value is quite large, and a smaller a_ is NOT abnormal. - static ABSL_RANDOM_INTERNAL_LOG_EXP_CONSTEXPR result_type - ThresholdForSmallA() { - return result_type(1) / - std::log((std::numeric_limits::max)()); - } - - // The threshold for whether a * std::log(a) is finite. - static ABSL_RANDOM_INTERNAL_LOG_EXP_CONSTEXPR result_type - ThresholdForLargeA() { - return std::exp( - std::log((std::numeric_limits::max)()) - - std::log(std::log((std::numeric_limits::max)())) - - ThresholdPadding()); - } - -#undef ABSL_RANDOM_INTERNAL_LOG_EXP_CONSTEXPR - - // Pad the threshold for large A for long double on PPC. This is done via a - // template specialization below. - static constexpr result_type ThresholdPadding() { return 0; } - - enum Method { - JOEHNK, // Uses algorithm Joehnk - CHENG_BA, // Uses algorithm BA in Cheng - CHENG_BB, // Uses algorithm BB in Cheng - - // Note: See also: - // Hung et al. Evaluation of beta generation algorithms. Communications - // in Statistics-Simulation and Computation 38.4 (2009): 750-770. - // especially: - // Zechner, Heinz, and Ernst Stadlober. Generating beta variates via - // patchwork rejection. Computing 50.1 (1993): 1-18. - - DEGENERATE_SMALL, // a_ is abnormally small. - DEGENERATE_LARGE, // a_ is abnormally large. - }; - - result_type alpha_; - result_type beta_; - - result_type a_; // the smaller of {alpha, beta}, or 1.0/alpha_ in JOEHNK - result_type b_; // the larger of {alpha, beta}, or 1.0/beta_ in JOEHNK - result_type x_; // alpha + beta, or the result in degenerate cases - result_type log_x_; // log(x_) - result_type y_; // "beta" in Cheng - result_type gamma_; // "gamma" in Cheng - - Method method_; - - // Placing this last for optimal alignment. - // Whether alpha_ != a_, i.e. true iff alpha_ > beta_. - bool inverted_; - - static_assert(std::is_floating_point::value, - "Class-template absl::beta_distribution<> must be " - "parameterized using a floating-point type."); - }; - - beta_distribution() : beta_distribution(1) {} - - explicit beta_distribution(result_type alpha, result_type beta = 1) - : param_(alpha, beta) {} - - explicit beta_distribution(const param_type& p) : param_(p) {} - - void reset() {} - - // Generating functions - template - result_type operator()(URBG& g) { // NOLINT(runtime/references) - return (*this)(g, param_); - } - - template - result_type operator()(URBG& g, // NOLINT(runtime/references) - const param_type& p); - - param_type param() const { return param_; } - void param(const param_type& p) { param_ = p; } - - result_type(min)() const { return 0; } - result_type(max)() const { return 1; } - - result_type alpha() const { return param_.alpha(); } - result_type beta() const { return param_.beta(); } - - friend bool operator==(const beta_distribution& a, - const beta_distribution& b) { - return a.param_ == b.param_; - } - friend bool operator!=(const beta_distribution& a, - const beta_distribution& b) { - return a.param_ != b.param_; - } - - private: - template - result_type AlgorithmJoehnk(URBG& g, // NOLINT(runtime/references) - const param_type& p); - - template - result_type AlgorithmCheng(URBG& g, // NOLINT(runtime/references) - const param_type& p); - - template - result_type DegenerateCase(URBG& g, // NOLINT(runtime/references) - const param_type& p) { - if (p.method_ == param_type::DEGENERATE_SMALL && p.alpha_ == p.beta_) { - // Returns 0 or 1 with equal probability. - random_internal::FastUniformBits fast_u8; - return static_cast((fast_u8(g) & 0x10) != - 0); // pick any single bit. - } - return p.x_; - } - - param_type param_; - random_internal::FastUniformBits fast_u64_; -}; - -#if defined(__powerpc64__) || defined(__PPC64__) || defined(__powerpc__) || \ - defined(__ppc__) || defined(__PPC__) -// PPC needs a more stringent boundary for long double. -template <> -constexpr long double -beta_distribution::param_type::ThresholdPadding() { - return 10; -} -#endif - -template -template -typename beta_distribution::result_type -beta_distribution::AlgorithmJoehnk( - URBG& g, // NOLINT(runtime/references) - const param_type& p) { - using random_internal::GeneratePositiveTag; - using random_internal::GenerateRealFromBits; - using real_type = - absl::conditional_t::value, float, double>; - - // Based on Joehnk, M. D. Erzeugung von betaverteilten und gammaverteilten - // Zufallszahlen. Metrika 8.1 (1964): 5-15. - // This method is described in Knuth, Vol 2 (Third Edition), pp 134. - - result_type u, v, x, y, z; - for (;;) { - u = GenerateRealFromBits( - fast_u64_(g)); - v = GenerateRealFromBits( - fast_u64_(g)); - - // Direct method. std::pow is slow for float, so rely on the optimizer to - // remove the std::pow() path for that case. - if (!std::is_same::value) { - x = std::pow(u, p.a_); - y = std::pow(v, p.b_); - z = x + y; - if (z > 1) { - // Reject if and only if `x + y > 1.0` - continue; - } - if (z > 0) { - // When both alpha and beta are small, x and y are both close to 0, so - // divide by (x+y) directly may result in nan. - return x / z; - } - } - - // Log transform. - // x = log( pow(u, p.a_) ), y = log( pow(v, p.b_) ) - // since u, v <= 1.0, x, y < 0. - x = std::log(u) * p.a_; - y = std::log(v) * p.b_; - if (!std::isfinite(x) || !std::isfinite(y)) { - continue; - } - // z = log( pow(u, a) + pow(v, b) ) - z = x > y ? (x + std::log(1 + std::exp(y - x))) - : (y + std::log(1 + std::exp(x - y))); - // Reject iff log(x+y) > 0. - if (z > 0) { - continue; - } - return std::exp(x - z); - } -} - -template -template -typename beta_distribution::result_type -beta_distribution::AlgorithmCheng( - URBG& g, // NOLINT(runtime/references) - const param_type& p) { - using random_internal::GeneratePositiveTag; - using random_internal::GenerateRealFromBits; - using real_type = - absl::conditional_t::value, float, double>; - - // Based on Cheng, Russell CH. Generating beta variates with nonintegral - // shape parameters. Communications of the ACM 21.4 (1978): 317-322. - // (https://dl.acm.org/citation.cfm?id=359482). - static constexpr result_type kLogFour = - result_type(1.3862943611198906188344642429163531361); // log(4) - static constexpr result_type kS = - result_type(2.6094379124341003746007593332261876); // 1+log(5) - - const bool use_algorithm_ba = (p.method_ == param_type::CHENG_BA); - result_type u1, u2, v, w, z, r, s, t, bw_inv, lhs; - for (;;) { - u1 = GenerateRealFromBits( - fast_u64_(g)); - u2 = GenerateRealFromBits( - fast_u64_(g)); - v = p.y_ * std::log(u1 / (1 - u1)); - w = p.a_ * std::exp(v); - bw_inv = result_type(1) / (p.b_ + w); - r = p.gamma_ * v - kLogFour; - s = p.a_ + r - w; - z = u1 * u1 * u2; - if (!use_algorithm_ba && s + kS >= 5 * z) { - break; - } - t = std::log(z); - if (!use_algorithm_ba && s >= t) { - break; - } - lhs = p.x_ * (p.log_x_ + std::log(bw_inv)) + r; - if (lhs >= t) { - break; - } - } - return p.inverted_ ? (1 - w * bw_inv) : w * bw_inv; -} - -template -template -typename beta_distribution::result_type -beta_distribution::operator()(URBG& g, // NOLINT(runtime/references) - const param_type& p) { - switch (p.method_) { - case param_type::JOEHNK: - return AlgorithmJoehnk(g, p); - case param_type::CHENG_BA: - ABSL_FALLTHROUGH_INTENDED; - case param_type::CHENG_BB: - return AlgorithmCheng(g, p); - default: - return DegenerateCase(g, p); - } -} - -template -std::basic_ostream& operator<<( - std::basic_ostream& os, // NOLINT(runtime/references) - const beta_distribution& x) { - auto saver = random_internal::make_ostream_state_saver(os); - os.precision(random_internal::stream_precision_helper::kPrecision); - os << x.alpha() << os.fill() << x.beta(); - return os; -} - -template -std::basic_istream& operator>>( - std::basic_istream& is, // NOLINT(runtime/references) - beta_distribution& x) { // NOLINT(runtime/references) - using result_type = typename beta_distribution::result_type; - using param_type = typename beta_distribution::param_type; - result_type alpha, beta; - - auto saver = random_internal::make_istream_state_saver(is); - alpha = random_internal::read_floating_point(is); - if (is.fail()) return is; - beta = random_internal::read_floating_point(is); - if (!is.fail()) { - x.param(param_type(alpha, beta)); - } - return is; -} - -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_RANDOM_BETA_DISTRIBUTION_H_ diff --git a/third_party/abseil_cpp/absl/random/beta_distribution_test.cc b/third_party/abseil_cpp/absl/random/beta_distribution_test.cc deleted file mode 100644 index 277e4dc6ee..0000000000 --- a/third_party/abseil_cpp/absl/random/beta_distribution_test.cc +++ /dev/null @@ -1,619 +0,0 @@ -// 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 -// -// 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 "absl/random/beta_distribution.h" - -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include "gmock/gmock.h" -#include "gtest/gtest.h" -#include "absl/base/internal/raw_logging.h" -#include "absl/random/internal/chi_square.h" -#include "absl/random/internal/distribution_test_util.h" -#include "absl/random/internal/pcg_engine.h" -#include "absl/random/internal/sequence_urbg.h" -#include "absl/random/random.h" -#include "absl/strings/str_cat.h" -#include "absl/strings/str_format.h" -#include "absl/strings/str_replace.h" -#include "absl/strings/strip.h" - -namespace { - -template -class BetaDistributionInterfaceTest : public ::testing::Test {}; - -using RealTypes = ::testing::Types; -TYPED_TEST_CASE(BetaDistributionInterfaceTest, RealTypes); - -TYPED_TEST(BetaDistributionInterfaceTest, SerializeTest) { - // The threshold for whether std::exp(1/a) is finite. - const TypeParam kSmallA = - 1.0f / std::log((std::numeric_limits::max)()); - // The threshold for whether a * std::log(a) is finite. - const TypeParam kLargeA = - std::exp(std::log((std::numeric_limits::max)()) - - std::log(std::log((std::numeric_limits::max)()))); - const TypeParam kLargeAPPC = std::exp( - std::log((std::numeric_limits::max)()) - - std::log(std::log((std::numeric_limits::max)())) - 10.0f); - using param_type = typename absl::beta_distribution::param_type; - - constexpr int kCount = 1000; - absl::InsecureBitGen gen; - const TypeParam kValues[] = { - TypeParam(1e-20), TypeParam(1e-12), TypeParam(1e-8), TypeParam(1e-4), - TypeParam(1e-3), TypeParam(0.1), TypeParam(0.25), - std::nextafter(TypeParam(0.5), TypeParam(0)), // 0.5 - epsilon - std::nextafter(TypeParam(0.5), TypeParam(1)), // 0.5 + epsilon - TypeParam(0.5), TypeParam(1.0), // - std::nextafter(TypeParam(1), TypeParam(0)), // 1 - epsilon - std::nextafter(TypeParam(1), TypeParam(2)), // 1 + epsilon - TypeParam(12.5), TypeParam(1e2), TypeParam(1e8), TypeParam(1e12), - TypeParam(1e20), // - kSmallA, // - std::nextafter(kSmallA, TypeParam(0)), // - std::nextafter(kSmallA, TypeParam(1)), // - kLargeA, // - std::nextafter(kLargeA, TypeParam(0)), // - std::nextafter(kLargeA, std::numeric_limits::max()), - kLargeAPPC, // - std::nextafter(kLargeAPPC, TypeParam(0)), - std::nextafter(kLargeAPPC, std::numeric_limits::max()), - // Boundary cases. - std::numeric_limits::max(), - std::numeric_limits::epsilon(), - std::nextafter(std::numeric_limits::min(), - TypeParam(1)), // min + epsilon - std::numeric_limits::min(), // smallest normal - std::numeric_limits::denorm_min(), // smallest denorm - std::numeric_limits::min() / 2, // denorm - std::nextafter(std::numeric_limits::min(), - TypeParam(0)), // denorm_max - }; - for (TypeParam alpha : kValues) { - for (TypeParam beta : kValues) { - ABSL_INTERNAL_LOG( - INFO, absl::StrFormat("Smoke test for Beta(%a, %a)", alpha, beta)); - - param_type param(alpha, beta); - absl::beta_distribution before(alpha, beta); - EXPECT_EQ(before.alpha(), param.alpha()); - EXPECT_EQ(before.beta(), param.beta()); - - { - absl::beta_distribution via_param(param); - EXPECT_EQ(via_param, before); - EXPECT_EQ(via_param.param(), before.param()); - } - - // Smoke test. - for (int i = 0; i < kCount; ++i) { - auto sample = before(gen); - EXPECT_TRUE(std::isfinite(sample)); - EXPECT_GE(sample, before.min()); - EXPECT_LE(sample, before.max()); - } - - // Validate stream serialization. - std::stringstream ss; - ss << before; - absl::beta_distribution after(3.8f, 1.43f); - EXPECT_NE(before.alpha(), after.alpha()); - EXPECT_NE(before.beta(), after.beta()); - EXPECT_NE(before.param(), after.param()); - EXPECT_NE(before, after); - - ss >> after; - -#if defined(__powerpc64__) || defined(__PPC64__) || defined(__powerpc__) || \ - defined(__ppc__) || defined(__PPC__) - if (std::is_same::value) { - // Roundtripping floating point values requires sufficient precision - // to reconstruct the exact value. It turns out that long double - // has some errors doing this on ppc. - if (alpha <= std::numeric_limits::max() && - alpha >= std::numeric_limits::lowest()) { - EXPECT_EQ(static_cast(before.alpha()), - static_cast(after.alpha())) - << ss.str(); - } - if (beta <= std::numeric_limits::max() && - beta >= std::numeric_limits::lowest()) { - EXPECT_EQ(static_cast(before.beta()), - static_cast(after.beta())) - << ss.str(); - } - continue; - } -#endif - - EXPECT_EQ(before.alpha(), after.alpha()); - EXPECT_EQ(before.beta(), after.beta()); - EXPECT_EQ(before, after) // - << ss.str() << " " // - << (ss.good() ? "good " : "") // - << (ss.bad() ? "bad " : "") // - << (ss.eof() ? "eof " : "") // - << (ss.fail() ? "fail " : ""); - } - } -} - -TYPED_TEST(BetaDistributionInterfaceTest, DegenerateCases) { - // We use a fixed bit generator for distribution accuracy tests. This allows - // these tests to be deterministic, while still testing the qualify of the - // implementation. - absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6); - - // Extreme cases when the params are abnormal. - constexpr int kCount = 1000; - const TypeParam kSmallValues[] = { - std::numeric_limits::min(), - std::numeric_limits::denorm_min(), - std::nextafter(std::numeric_limits::min(), - TypeParam(0)), // denorm_max - std::numeric_limits::epsilon(), - }; - const TypeParam kLargeValues[] = { - std::numeric_limits::max() * static_cast(0.9999), - std::numeric_limits::max() - 1, - std::numeric_limits::max(), - }; - { - // Small alpha and beta. - // Useful WolframAlpha plots: - // * plot InverseBetaRegularized[x, 0.0001, 0.0001] from 0.495 to 0.505 - // * Beta[1.0, 0.0000001, 0.0000001] - // * Beta[0.9999, 0.0000001, 0.0000001] - for (TypeParam alpha : kSmallValues) { - for (TypeParam beta : kSmallValues) { - int zeros = 0; - int ones = 0; - absl::beta_distribution d(alpha, beta); - for (int i = 0; i < kCount; ++i) { - TypeParam x = d(rng); - if (x == 0.0) { - zeros++; - } else if (x == 1.0) { - ones++; - } - } - EXPECT_EQ(ones + zeros, kCount); - if (alpha == beta) { - EXPECT_NE(ones, 0); - EXPECT_NE(zeros, 0); - } - } - } - } - { - // Small alpha, large beta. - // Useful WolframAlpha plots: - // * plot InverseBetaRegularized[x, 0.0001, 10000] from 0.995 to 1 - // * Beta[0, 0.0000001, 1000000] - // * Beta[0.001, 0.0000001, 1000000] - // * Beta[1, 0.0000001, 1000000] - for (TypeParam alpha : kSmallValues) { - for (TypeParam beta : kLargeValues) { - absl::beta_distribution d(alpha, beta); - for (int i = 0; i < kCount; ++i) { - EXPECT_EQ(d(rng), 0.0); - } - } - } - } - { - // Large alpha, small beta. - // Useful WolframAlpha plots: - // * plot InverseBetaRegularized[x, 10000, 0.0001] from 0 to 0.001 - // * Beta[0.99, 1000000, 0.0000001] - // * Beta[1, 1000000, 0.0000001] - for (TypeParam alpha : kLargeValues) { - for (TypeParam beta : kSmallValues) { - absl::beta_distribution d(alpha, beta); - for (int i = 0; i < kCount; ++i) { - EXPECT_EQ(d(rng), 1.0); - } - } - } - } - { - // Large alpha and beta. - absl::beta_distribution d(std::numeric_limits::max(), - std::numeric_limits::max()); - for (int i = 0; i < kCount; ++i) { - EXPECT_EQ(d(rng), 0.5); - } - } - { - // Large alpha and beta but unequal. - absl::beta_distribution d( - std::numeric_limits::max(), - std::numeric_limits::max() * 0.9999); - for (int i = 0; i < kCount; ++i) { - TypeParam x = d(rng); - EXPECT_NE(x, 0.5f); - EXPECT_FLOAT_EQ(x, 0.500025f); - } - } -} - -class BetaDistributionModel { - public: - explicit BetaDistributionModel(::testing::tuple p) - : alpha_(::testing::get<0>(p)), beta_(::testing::get<1>(p)) {} - - double Mean() const { return alpha_ / (alpha_ + beta_); } - - double Variance() const { - return alpha_ * beta_ / (alpha_ + beta_ + 1) / (alpha_ + beta_) / - (alpha_ + beta_); - } - - double Kurtosis() const { - return 3 + 6 * - ((alpha_ - beta_) * (alpha_ - beta_) * (alpha_ + beta_ + 1) - - alpha_ * beta_ * (2 + alpha_ + beta_)) / - alpha_ / beta_ / (alpha_ + beta_ + 2) / (alpha_ + beta_ + 3); - } - - protected: - const double alpha_; - const double beta_; -}; - -class BetaDistributionTest - : public ::testing::TestWithParam<::testing::tuple>, - public BetaDistributionModel { - public: - BetaDistributionTest() : BetaDistributionModel(GetParam()) {} - - protected: - template - bool SingleZTestOnMeanAndVariance(double p, size_t samples); - - template - bool SingleChiSquaredTest(double p, size_t samples, size_t buckets); - - absl::InsecureBitGen rng_; -}; - -template -bool BetaDistributionTest::SingleZTestOnMeanAndVariance(double p, - size_t samples) { - D dis(alpha_, beta_); - - std::vector data; - data.reserve(samples); - for (size_t i = 0; i < samples; i++) { - const double variate = dis(rng_); - EXPECT_FALSE(std::isnan(variate)); - // Note that equality is allowed on both sides. - EXPECT_GE(variate, 0.0); - EXPECT_LE(variate, 1.0); - data.push_back(variate); - } - - // We validate that the sample mean and sample variance are indeed from a - // Beta distribution with the given shape parameters. - const auto m = absl::random_internal::ComputeDistributionMoments(data); - - // The variance of the sample mean is variance / n. - const double mean_stddev = std::sqrt(Variance() / static_cast(m.n)); - - // The variance of the sample variance is (approximately): - // (kurtosis - 1) * variance^2 / n - const double variance_stddev = std::sqrt( - (Kurtosis() - 1) * Variance() * Variance() / static_cast(m.n)); - // z score for the sample variance. - const double z_variance = (m.variance - Variance()) / variance_stddev; - - const double max_err = absl::random_internal::MaxErrorTolerance(p); - const double z_mean = absl::random_internal::ZScore(Mean(), m); - const bool pass = - absl::random_internal::Near("z", z_mean, 0.0, max_err) && - absl::random_internal::Near("z_variance", z_variance, 0.0, max_err); - if (!pass) { - ABSL_INTERNAL_LOG( - INFO, - absl::StrFormat( - "Beta(%f, %f), " - "mean: sample %f, expect %f, which is %f stddevs away, " - "variance: sample %f, expect %f, which is %f stddevs away.", - alpha_, beta_, m.mean, Mean(), - std::abs(m.mean - Mean()) / mean_stddev, m.variance, Variance(), - std::abs(m.variance - Variance()) / variance_stddev)); - } - return pass; -} - -template -bool BetaDistributionTest::SingleChiSquaredTest(double p, size_t samples, - size_t buckets) { - constexpr double kErr = 1e-7; - std::vector cutoffs, expected; - const double bucket_width = 1.0 / static_cast(buckets); - int i = 1; - int unmerged_buckets = 0; - for (; i < buckets; ++i) { - const double p = bucket_width * static_cast(i); - const double boundary = - absl::random_internal::BetaIncompleteInv(alpha_, beta_, p); - // The intention is to add `boundary` to the list of `cutoffs`. It becomes - // problematic, however, when the boundary values are not monotone, due to - // numerical issues when computing the inverse regularized incomplete - // Beta function. In these cases, we merge that bucket with its previous - // neighbor and merge their expected counts. - if ((cutoffs.empty() && boundary < kErr) || - (!cutoffs.empty() && boundary <= cutoffs.back())) { - unmerged_buckets++; - continue; - } - if (boundary >= 1.0 - 1e-10) { - break; - } - cutoffs.push_back(boundary); - expected.push_back(static_cast(1 + unmerged_buckets) * - bucket_width * static_cast(samples)); - unmerged_buckets = 0; - } - cutoffs.push_back(std::numeric_limits::infinity()); - // Merge all remaining buckets. - expected.push_back(static_cast(buckets - i + 1) * bucket_width * - static_cast(samples)); - // Make sure that we don't merge all the buckets, making this test - // meaningless. - EXPECT_GE(cutoffs.size(), 3) << alpha_ << ", " << beta_; - - D dis(alpha_, beta_); - - std::vector counts(cutoffs.size(), 0); - for (int i = 0; i < samples; i++) { - const double x = dis(rng_); - auto it = std::upper_bound(cutoffs.begin(), cutoffs.end(), x); - counts[std::distance(cutoffs.begin(), it)]++; - } - - // Null-hypothesis is that the distribution is beta distributed with the - // provided alpha, beta params (not estimated from the data). - const int dof = cutoffs.size() - 1; - - const double chi_square = absl::random_internal::ChiSquare( - counts.begin(), counts.end(), expected.begin(), expected.end()); - const bool pass = - (absl::random_internal::ChiSquarePValue(chi_square, dof) >= p); - if (!pass) { - for (int i = 0; i < cutoffs.size(); i++) { - ABSL_INTERNAL_LOG( - INFO, absl::StrFormat("cutoff[%d] = %f, actual count %d, expected %d", - i, cutoffs[i], counts[i], - static_cast(expected[i]))); - } - - ABSL_INTERNAL_LOG( - INFO, absl::StrFormat( - "Beta(%f, %f) %s %f, p = %f", alpha_, beta_, - absl::random_internal::kChiSquared, chi_square, - absl::random_internal::ChiSquarePValue(chi_square, dof))); - } - return pass; -} - -TEST_P(BetaDistributionTest, TestSampleStatistics) { - static constexpr int kRuns = 20; - static constexpr double kPFail = 0.02; - const double p = - absl::random_internal::RequiredSuccessProbability(kPFail, kRuns); - static constexpr int kSampleCount = 10000; - static constexpr int kBucketCount = 100; - int failed = 0; - for (int i = 0; i < kRuns; ++i) { - if (!SingleZTestOnMeanAndVariance>( - p, kSampleCount)) { - failed++; - } - if (!SingleChiSquaredTest>( - 0.005, kSampleCount, kBucketCount)) { - failed++; - } - } - // Set so that the test is not flaky at --runs_per_test=10000 - EXPECT_LE(failed, 5); -} - -std::string ParamName( - const ::testing::TestParamInfo<::testing::tuple>& info) { - std::string name = absl::StrCat("alpha_", ::testing::get<0>(info.param), - "__beta_", ::testing::get<1>(info.param)); - return absl::StrReplaceAll(name, {{"+", "_"}, {"-", "_"}, {".", "_"}}); -} - -INSTANTIATE_TEST_CASE_P( - TestSampleStatisticsCombinations, BetaDistributionTest, - ::testing::Combine(::testing::Values(0.1, 0.2, 0.9, 1.1, 2.5, 10.0, 123.4), - ::testing::Values(0.1, 0.2, 0.9, 1.1, 2.5, 10.0, 123.4)), - ParamName); - -INSTANTIATE_TEST_CASE_P( - TestSampleStatistics_SelectedPairs, BetaDistributionTest, - ::testing::Values(std::make_pair(0.5, 1000), std::make_pair(1000, 0.5), - std::make_pair(900, 1000), std::make_pair(10000, 20000), - std::make_pair(4e5, 2e7), std::make_pair(1e7, 1e5)), - ParamName); - -// NOTE: absl::beta_distribution is not guaranteed to be stable. -TEST(BetaDistributionTest, StabilityTest) { - // absl::beta_distribution stability relies on the stability of - // absl::random_interna::RandU64ToDouble, std::exp, std::log, std::pow, - // and std::sqrt. - // - // This test also depends on the stability of std::frexp. - using testing::ElementsAre; - absl::random_internal::sequence_urbg urbg({ - 0xffff00000000e6c8ull, 0xffff0000000006c8ull, 0x800003766295CFA9ull, - 0x11C819684E734A41ull, 0x832603766295CFA9ull, 0x7fbe76c8b4395800ull, - 0xB3472DCA7B14A94Aull, 0x0003eb76f6f7f755ull, 0xFFCEA50FDB2F953Bull, - 0x13CCA830EB61BD96ull, 0x0334FE1EAA0363CFull, 0x00035C904C70A239ull, - 0x00009E0BCBAADE14ull, 0x0000000000622CA7ull, 0x4864f22c059bf29eull, - 0x247856d8b862665cull, 0xe46e86e9a1337e10ull, 0xd8c8541f3519b133ull, - 0xffe75b52c567b9e4ull, 0xfffff732e5709c5bull, 0xff1f7f0b983532acull, - 0x1ec2e8986d2362caull, 0xC332DDEFBE6C5AA5ull, 0x6558218568AB9702ull, - 0x2AEF7DAD5B6E2F84ull, 0x1521B62829076170ull, 0xECDD4775619F1510ull, - 0x814c8e35fe9a961aull, 0x0c3cd59c9b638a02ull, 0xcb3bb6478a07715cull, - 0x1224e62c978bbc7full, 0x671ef2cb04e81f6eull, 0x3c1cbd811eaf1808ull, - 0x1bbc23cfa8fac721ull, 0xa4c2cda65e596a51ull, 0xb77216fad37adf91ull, - 0x836d794457c08849ull, 0xe083df03475f49d7ull, 0xbc9feb512e6b0d6cull, - 0xb12d74fdd718c8c5ull, 0x12ff09653bfbe4caull, 0x8dd03a105bc4ee7eull, - 0x5738341045ba0d85ull, 0xf3fd722dc65ad09eull, 0xfa14fd21ea2a5705ull, - 0xffe6ea4d6edb0c73ull, 0xD07E9EFE2BF11FB4ull, 0x95DBDA4DAE909198ull, - 0xEAAD8E716B93D5A0ull, 0xD08ED1D0AFC725E0ull, 0x8E3C5B2F8E7594B7ull, - 0x8FF6E2FBF2122B64ull, 0x8888B812900DF01Cull, 0x4FAD5EA0688FC31Cull, - 0xD1CFF191B3A8C1ADull, 0x2F2F2218BE0E1777ull, 0xEA752DFE8B021FA1ull, - }); - - // Convert the real-valued result into a unit64 where we compare - // 5 (float) or 10 (double) decimal digits plus the base-2 exponent. - auto float_to_u64 = [](float d) { - int exp = 0; - auto f = std::frexp(d, &exp); - return (static_cast(1e5 * f) * 10000) + std::abs(exp); - }; - auto double_to_u64 = [](double d) { - int exp = 0; - auto f = std::frexp(d, &exp); - return (static_cast(1e10 * f) * 10000) + std::abs(exp); - }; - - std::vector output(20); - { - // Algorithm Joehnk (float) - absl::beta_distribution dist(0.1f, 0.2f); - std::generate(std::begin(output), std::end(output), - [&] { return float_to_u64(dist(urbg)); }); - EXPECT_EQ(44, urbg.invocations()); - EXPECT_THAT(output, // - testing::ElementsAre( - 998340000, 619030004, 500000001, 999990000, 996280000, - 500000001, 844740004, 847210001, 999970000, 872320000, - 585480007, 933280000, 869080042, 647670031, 528240004, - 969980004, 626050008, 915930002, 833440033, 878040015)); - } - - urbg.reset(); - { - // Algorithm Joehnk (double) - absl::beta_distribution dist(0.1, 0.2); - std::generate(std::begin(output), std::end(output), - [&] { return double_to_u64(dist(urbg)); }); - EXPECT_EQ(44, urbg.invocations()); - EXPECT_THAT( - output, // - testing::ElementsAre( - 99834713000000, 61903356870004, 50000000000001, 99999721170000, - 99628374770000, 99999999990000, 84474397860004, 84721276240001, - 99997407490000, 87232528120000, 58548364780007, 93328932910000, - 86908237770042, 64767917930031, 52824581970004, 96998544140004, - 62605946270008, 91593604380002, 83345031740033, 87804397230015)); - } - - urbg.reset(); - { - // Algorithm Cheng 1 - absl::beta_distribution dist(0.9, 2.0); - std::generate(std::begin(output), std::end(output), - [&] { return double_to_u64(dist(urbg)); }); - EXPECT_EQ(62, urbg.invocations()); - EXPECT_THAT( - output, // - testing::ElementsAre( - 62069004780001, 64433204450001, 53607416560000, 89644295430008, - 61434586310019, 55172615890002, 62187161490000, 56433684810003, - 80454622050005, 86418558710003, 92920514700001, 64645184680001, - 58549183380000, 84881283650005, 71078728590002, 69949694970000, - 73157461710001, 68592191300001, 70747623900000, 78584696930005)); - } - - urbg.reset(); - { - // Algorithm Cheng 2 - absl::beta_distribution dist(1.5, 2.5); - std::generate(std::begin(output), std::end(output), - [&] { return double_to_u64(dist(urbg)); }); - EXPECT_EQ(54, urbg.invocations()); - EXPECT_THAT( - output, // - testing::ElementsAre( - 75000029250001, 76751482860001, 53264575220000, 69193133650005, - 78028324470013, 91573587560002, 59167523770000, 60658618560002, - 80075870540000, 94141320460004, 63196592770003, 78883906300002, - 96797992590001, 76907587800001, 56645167560000, 65408302280003, - 53401156320001, 64731238570000, 83065573750001, 79788333820001)); - } -} - -// This is an implementation-specific test. If any part of the implementation -// changes, then it is likely that this test will change as well. Also, if -// dependencies of the distribution change, such as RandU64ToDouble, then this -// is also likely to change. -TEST(BetaDistributionTest, AlgorithmBounds) { - { - absl::random_internal::sequence_urbg urbg( - {0x7fbe76c8b4395800ull, 0x8000000000000000ull}); - // u=0.499, v=0.5 - absl::beta_distribution dist(1e-4, 1e-4); - double a = dist(urbg); - EXPECT_EQ(a, 2.0202860861567108529e-09); - EXPECT_EQ(2, urbg.invocations()); - } - - // Test that both the float & double algorithms appropriately reject the - // initial draw. - { - // 1/alpha = 1/beta = 2. - absl::beta_distribution dist(0.5, 0.5); - - // first two outputs are close to 1.0 - epsilon, - // thus: (u ^ 2 + v ^ 2) > 1.0 - absl::random_internal::sequence_urbg urbg( - {0xffff00000006e6c8ull, 0xffff00000007c7c8ull, 0x800003766295CFA9ull, - 0x11C819684E734A41ull}); - { - double y = absl::beta_distribution(0.5, 0.5)(urbg); - EXPECT_EQ(4, urbg.invocations()); - EXPECT_EQ(y, 0.9810668952633862) << y; - } - - // ...and: log(u) * a ~= log(v) * b ~= -0.02 - // thus z ~= -0.02 + log(1 + e(~0)) - // ~= -0.02 + 0.69 - // thus z > 0 - urbg.reset(); - { - float x = absl::beta_distribution(0.5, 0.5)(urbg); - EXPECT_EQ(4, urbg.invocations()); - EXPECT_NEAR(0.98106688261032104, x, 0.0000005) << x << "f"; - } - } -} - -} // namespace diff --git a/third_party/abseil_cpp/absl/random/bit_gen_ref.h b/third_party/abseil_cpp/absl/random/bit_gen_ref.h deleted file mode 100644 index 9555460fd4..0000000000 --- a/third_party/abseil_cpp/absl/random/bit_gen_ref.h +++ /dev/null @@ -1,181 +0,0 @@ -// -// 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. -// -// ----------------------------------------------------------------------------- -// File: bit_gen_ref.h -// ----------------------------------------------------------------------------- -// -// This header defines a bit generator "reference" class, for use in interfaces -// that take both Abseil (e.g. `absl::BitGen`) and standard library (e.g. -// `std::mt19937`) bit generators. - -#ifndef ABSL_RANDOM_BIT_GEN_REF_H_ -#define ABSL_RANDOM_BIT_GEN_REF_H_ - -#include "absl/base/internal/fast_type_id.h" -#include "absl/base/macros.h" -#include "absl/meta/type_traits.h" -#include "absl/random/internal/distribution_caller.h" -#include "absl/random/internal/fast_uniform_bits.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace random_internal { - -template -struct is_urbg : std::false_type {}; - -template -struct is_urbg< - URBG, - absl::enable_if_t::type>::value>, - absl::enable_if_t::type>::value>, - absl::enable_if_t()())>::type>::value>> - : std::true_type {}; - -template -struct DistributionCaller; -class MockHelpers; - -} // namespace random_internal - -// ----------------------------------------------------------------------------- -// absl::BitGenRef -// ----------------------------------------------------------------------------- -// -// `absl::BitGenRef` is a type-erasing class that provides a generator-agnostic -// non-owning "reference" interface for use in place of any specific uniform -// random bit generator (URBG). This class may be used for both Abseil -// (e.g. `absl::BitGen`, `absl::InsecureBitGen`) and Standard library (e.g -// `std::mt19937`, `std::minstd_rand`) bit generators. -// -// Like other reference classes, `absl::BitGenRef` does not own the -// underlying bit generator, and the underlying instance must outlive the -// `absl::BitGenRef`. -// -// `absl::BitGenRef` is particularly useful when used with an -// `absl::MockingBitGen` to test specific paths in functions which use random -// values. -// -// Example: -// void TakesBitGenRef(absl::BitGenRef gen) { -// int x = absl::Uniform(gen, 0, 1000); -// } -// -class BitGenRef { - // SFINAE to detect whether the URBG type includes a member matching - // bool InvokeMock(base_internal::FastTypeIdType, void*, void*). - // - // These live inside BitGenRef so that they have friend access - // to MockingBitGen. (see similar methods in DistributionCaller). - template