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

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