diff options
author | 2023-08-14 23:44:27 -0700 | |
---|---|---|
committer | 2023-08-14 23:45:21 -0700 | |
commit | 32f414f4f781b55faede067f1d996f5e8dc885aa (patch) | |
tree | c25d1eefc36ecd1efb8fc46cfebc7c4cc6867d76 | |
parent | 71910654b4452f13f543f7c7f433fb3c6d932c33 (diff) |
Benchmark FNMatch, and use the greedy algorithm with better time and space complexity and no recursion (from 233 to 53.8 ns).
PiperOrigin-RevId: 557032497
Change-Id: I7a92feb3d79fa3dc1b7aa5b1097e53a9dae17c81
-rw-r--r-- | absl/log/BUILD.bazel | 4 | ||||
-rw-r--r-- | absl/log/internal/BUILD.bazel | 12 | ||||
-rw-r--r-- | absl/log/internal/fnmatch.cc | 48 | ||||
-rw-r--r-- | absl/log/internal/fnmatch_benchmark.cc | 29 |
4 files changed, 77 insertions, 16 deletions
diff --git a/absl/log/BUILD.bazel b/absl/log/BUILD.bazel index e1410637..2f393554 100644 --- a/absl/log/BUILD.bazel +++ b/absl/log/BUILD.bazel @@ -573,9 +573,9 @@ cc_test( ], ) -cc_binary( +cc_test( name = "log_benchmark", - testonly = 1, + size = "small", srcs = ["log_benchmark.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, diff --git a/absl/log/internal/BUILD.bazel b/absl/log/internal/BUILD.bazel index b8077a77..d7a30c9e 100644 --- a/absl/log/internal/BUILD.bazel +++ b/absl/log/internal/BUILD.bazel @@ -404,3 +404,15 @@ cc_test( "@com_google_googletest//:gtest_main", ], ) + +cc_test( + name = "fnmatch_benchmark", + srcs = ["fnmatch_benchmark.cc"], + copts = ABSL_TEST_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + tags = ["benchmark"], + deps = [ + ":fnmatch", + "@com_github_google_benchmark//:benchmark_main", + ], +) diff --git a/absl/log/internal/fnmatch.cc b/absl/log/internal/fnmatch.cc index be4e4b1c..26e1e57f 100644 --- a/absl/log/internal/fnmatch.cc +++ b/absl/log/internal/fnmatch.cc @@ -14,6 +14,8 @@ #include "absl/log/internal/fnmatch.h" +#include <cstddef> + #include "absl/base/config.h" #include "absl/strings/string_view.h" @@ -21,31 +23,49 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace log_internal { bool FNMatch(absl::string_view pattern, absl::string_view str) { + bool in_wildcard_match = false; while (true) { if (pattern.empty()) { // `pattern` is exhausted; succeed if all of `str` was consumed matching // it. - return str.empty(); + return in_wildcard_match || str.empty(); } if (str.empty()) { // `str` is exhausted; succeed if `pattern` is empty or all '*'s. return pattern.find_first_not_of('*') == pattern.npos; } - if (pattern.front() == '*') { - pattern.remove_prefix(1); - if (pattern.empty()) return true; - do { - if (FNMatch(pattern, str)) return true; + switch (pattern.front()) { + case '*': + pattern.remove_prefix(1); + in_wildcard_match = true; + break; + case '?': + pattern.remove_prefix(1); str.remove_prefix(1); - } while (!str.empty()); - return false; - } - if (pattern.front() == '?' || pattern.front() == str.front()) { - pattern.remove_prefix(1); - str.remove_prefix(1); - continue; + break; + default: + if (in_wildcard_match) { + absl::string_view fixed_portion = pattern; + const size_t end = fixed_portion.find_first_of("*?"); + if (end != fixed_portion.npos) { + fixed_portion = fixed_portion.substr(0, end); + } + const size_t match = str.find(fixed_portion); + if (match == str.npos) { + return false; + } + pattern.remove_prefix(fixed_portion.size()); + str.remove_prefix(match + fixed_portion.size()); + in_wildcard_match = false; + } else { + if (pattern.front() != str.front()) { + return false; + } + pattern.remove_prefix(1); + str.remove_prefix(1); + } + break; } - return false; } } } // namespace log_internal diff --git a/absl/log/internal/fnmatch_benchmark.cc b/absl/log/internal/fnmatch_benchmark.cc new file mode 100644 index 00000000..f062ba20 --- /dev/null +++ b/absl/log/internal/fnmatch_benchmark.cc @@ -0,0 +1,29 @@ +// Copyright 2023 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/log/internal/fnmatch.h" +#include "benchmark/benchmark.h" + +namespace { +void BM_FNMatch(benchmark::State& state) { + while (state.KeepRunning()) { + bool ret = + absl::log_internal::FNMatch("*?*asdf*?*we???asdf**asdf*we", + "QWERFASVWERASDFWEDFASDasdfQWERGFWASDERREWF" + "weHOOasdf@#$%TW#ZSERasdfQW#REGTZSERERwe"); + benchmark::DoNotOptimize(ret); + } +} +BENCHMARK(BM_FNMatch); +} // namespace |