1 // Copyright 2020 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "base/substring_set_matcher/substring_set_matcher.h"
6
7 #include <limits>
8 #include <string>
9 #include <vector>
10
11 #include "base/containers/contains.h"
12 #include "base/rand_util.h"
13 #include "base/time/time.h"
14 #include "base/timer/elapsed_timer.h"
15 #include "base/trace_event/memory_usage_estimator.h" // no-presubmit-check
16 #include "testing/gtest/include/gtest/gtest.h"
17 #include "testing/perf/perf_result_reporter.h"
18
19 namespace base {
20
21 namespace {
22
23 // Returns a random string of the given length using characters from 'a' to 'z'.
GetRandomString(size_t len)24 std::string GetRandomString(size_t len) {
25 std::vector<char> random_chars;
26 random_chars.reserve(len);
27 for (size_t i = 0; i < len; i++)
28 random_chars.push_back(base::RandInt('a', 'z'));
29
30 return std::string(random_chars.begin(), random_chars.end());
31 }
32
33 // Tests performance of SubstringSetMatcher for 20000 random patterns of length
34 // 30.
TEST(SubstringSetMatcherPerfTest,RandomKeys)35 TEST(SubstringSetMatcherPerfTest, RandomKeys) {
36 std::vector<MatcherStringPattern> patterns;
37 std::set<std::string> pattern_strings;
38
39 // Create patterns.
40 const size_t kNumPatterns = 20000;
41 const size_t kPatternLen = 30;
42 for (size_t i = 0; i < kNumPatterns; i++) {
43 std::string str = GetRandomString(kPatternLen);
44
45 // Ensure we don't have any duplicate pattern strings.
46 if (base::Contains(pattern_strings, str))
47 continue;
48
49 pattern_strings.insert(str);
50 patterns.emplace_back(str, i);
51 }
52
53 base::ElapsedTimer init_timer;
54
55 // Allocate SubstringSetMatcher on the heap so that EstimateMemoryUsage below
56 // also includes its stack allocated memory.
57 auto matcher = std::make_unique<SubstringSetMatcher>();
58 ASSERT_TRUE(matcher->Build(patterns));
59 base::TimeDelta init_time = init_timer.Elapsed();
60
61 // Match patterns against a random string of 500 characters.
62 const size_t kTextLen = 500;
63 base::ElapsedTimer match_timer;
64 std::set<MatcherStringPattern::ID> matches;
65 matcher->Match(GetRandomString(kTextLen), &matches);
66 base::TimeDelta match_time = match_timer.Elapsed();
67
68 const char* kInitializationTime = ".init_time";
69 const char* kMatchTime = ".match_time";
70 const char* kMemoryUsage = ".memory_usage";
71 auto reporter =
72 perf_test::PerfResultReporter("SubstringSetMatcher", "RandomKeys");
73 reporter.RegisterImportantMetric(kInitializationTime, "us");
74 reporter.RegisterImportantMetric(kMatchTime, "us");
75 reporter.RegisterImportantMetric(kMemoryUsage, "Mb");
76
77 reporter.AddResult(kInitializationTime, init_time);
78 reporter.AddResult(kMatchTime, match_time);
79 reporter.AddResult(
80 kMemoryUsage,
81 (base::trace_event::EstimateMemoryUsage(matcher) * 1.0 / (1 << 20)));
82 }
83
84 } // namespace
85
86 } // namespace base
87