1 // Copyright 2024 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include "pw_allocator/benchmarks/benchmark.h"
16
17 #include "public/pw_allocator/benchmarks/measurements.h"
18 #include "pw_allocator/benchmarks/measurements.h"
19 #include "pw_allocator/fragmentation.h"
20 #include "pw_allocator/test_harness.h"
21 #include "pw_allocator/testing.h"
22 #include "pw_random/xor_shift.h"
23 #include "pw_unit_test/framework.h"
24
25 namespace {
26
27 constexpr size_t kCapacity = 65536;
28 constexpr size_t kMaxSize = 64;
29
30 using AllocatorForTest = ::pw::allocator::test::AllocatorForTest<kCapacity>;
31 using Benchmark =
32 ::pw::allocator::DefaultBlockAllocatorBenchmark<AllocatorForTest>;
33 using ::pw::allocator::CalculateFragmentation;
34 using ::pw::allocator::Measurement;
35 using ::pw::allocator::Measurements;
36 using ::pw::allocator::test::AllocationRequest;
37 using ::pw::allocator::test::kToken;
38 using ::pw::allocator::test::Request;
39
40 template <typename GetByKey>
IsChanged(Benchmark & benchmark,GetByKey get_by_key)41 bool IsChanged(Benchmark& benchmark, GetByKey get_by_key) {
42 return get_by_key(benchmark.measurements()).count() != 0;
43 }
44
ByCountChanged(Benchmark & benchmark,size_t count)45 bool ByCountChanged(Benchmark& benchmark, size_t count) {
46 return IsChanged(benchmark, [count](Measurements& m) -> Measurement<size_t>& {
47 return m.GetByCount(count);
48 });
49 }
50
TEST(BenchmarkTest,ByCount)51 TEST(BenchmarkTest, ByCount) {
52 AllocatorForTest allocator;
53 Benchmark benchmark(kToken, allocator);
54 benchmark.set_prng_seed(1);
55 benchmark.set_available(kCapacity);
56
57 EXPECT_FALSE(ByCountChanged(benchmark, 0));
58
59 benchmark.GenerateRequest(kMaxSize);
60 EXPECT_TRUE(ByCountChanged(benchmark, 0));
61
62 while (benchmark.num_allocations() < 9) {
63 benchmark.GenerateRequest(kMaxSize);
64 }
65 EXPECT_FALSE(ByCountChanged(benchmark, 10));
66
67 while (benchmark.num_allocations() < 10) {
68 benchmark.GenerateRequest(kMaxSize);
69 }
70 EXPECT_TRUE(ByCountChanged(benchmark, 10));
71
72 while (benchmark.num_allocations() < 99) {
73 benchmark.GenerateRequest(kMaxSize);
74 }
75 EXPECT_FALSE(ByCountChanged(benchmark, 100));
76
77 while (benchmark.num_allocations() < 100) {
78 benchmark.GenerateRequest(kMaxSize);
79 }
80 EXPECT_TRUE(ByCountChanged(benchmark, 100));
81
82 while (benchmark.num_allocations() < 999) {
83 benchmark.GenerateRequest(kMaxSize);
84 }
85 EXPECT_FALSE(ByCountChanged(benchmark, 1000));
86
87 while (benchmark.num_allocations() < 1000) {
88 benchmark.GenerateRequest(kMaxSize);
89 }
90 EXPECT_TRUE(ByCountChanged(benchmark, 1000));
91 }
92
ByFragmentationChanged(Benchmark & benchmark,float fragmentation)93 size_t ByFragmentationChanged(Benchmark& benchmark, float fragmentation) {
94 return IsChanged(benchmark,
95 [fragmentation](Measurements& m) -> Measurement<float>& {
96 return m.GetByFragmentation(fragmentation);
97 });
98 }
99
TEST(BenchmarkTest,ByFragmentation)100 TEST(BenchmarkTest, ByFragmentation) {
101 AllocatorForTest allocator;
102 Benchmark benchmark(kToken, allocator);
103 benchmark.set_prng_seed(1);
104 benchmark.set_available(kCapacity);
105
106 EXPECT_FALSE(ByFragmentationChanged(benchmark, 0.2f));
107
108 while (CalculateFragmentation(allocator.MeasureFragmentation()) < 0.2f) {
109 benchmark.GenerateRequest(kMaxSize);
110 }
111 EXPECT_TRUE(ByFragmentationChanged(benchmark, 0.2f));
112
113 while (CalculateFragmentation(allocator.MeasureFragmentation()) < 0.4f) {
114 benchmark.GenerateRequest(kMaxSize);
115 }
116 EXPECT_TRUE(ByFragmentationChanged(benchmark, 0.4f));
117
118 while (CalculateFragmentation(allocator.MeasureFragmentation()) < 0.6f) {
119 benchmark.GenerateRequest(kMaxSize);
120 }
121 EXPECT_TRUE(ByFragmentationChanged(benchmark, 0.6f));
122
123 while (CalculateFragmentation(allocator.MeasureFragmentation()) < 0.8f) {
124 benchmark.GenerateRequest(kMaxSize);
125 }
126 EXPECT_TRUE(ByFragmentationChanged(benchmark, 0.8f));
127 }
128
BySizeChanged(Benchmark & benchmark,size_t size)129 bool BySizeChanged(Benchmark& benchmark, size_t size) {
130 return IsChanged(benchmark, [size](Measurements& m) -> Measurement<size_t>& {
131 return m.GetBySize(size);
132 });
133 }
134
TEST(BenchmarkTest,BySize)135 TEST(BenchmarkTest, BySize) {
136 AllocatorForTest allocator;
137 Benchmark benchmark(kToken, allocator);
138 benchmark.set_prng_seed(1);
139 benchmark.set_available(kCapacity);
140 AllocationRequest request;
141
142 EXPECT_FALSE(BySizeChanged(benchmark, 4096));
143 request.size = 8192;
144 EXPECT_TRUE(benchmark.HandleRequest(request));
145 EXPECT_TRUE(BySizeChanged(benchmark, 4096));
146 EXPECT_FALSE(BySizeChanged(benchmark, 4095));
147
148 EXPECT_FALSE(BySizeChanged(benchmark, 1024));
149 request.size = 4095;
150 EXPECT_TRUE(benchmark.HandleRequest(request));
151 EXPECT_TRUE(BySizeChanged(benchmark, 1024));
152 EXPECT_FALSE(BySizeChanged(benchmark, 1023));
153
154 EXPECT_FALSE(BySizeChanged(benchmark, 256));
155 request.size = 256;
156 EXPECT_TRUE(benchmark.HandleRequest(request));
157 EXPECT_TRUE(BySizeChanged(benchmark, 256));
158 EXPECT_FALSE(BySizeChanged(benchmark, 255));
159
160 EXPECT_FALSE(BySizeChanged(benchmark, 64));
161 request.size = 96;
162 EXPECT_TRUE(benchmark.HandleRequest(request));
163 EXPECT_TRUE(BySizeChanged(benchmark, 64));
164 EXPECT_FALSE(BySizeChanged(benchmark, 63));
165
166 EXPECT_FALSE(BySizeChanged(benchmark, 16));
167 request.size = 63;
168 EXPECT_TRUE(benchmark.HandleRequest(request));
169 EXPECT_TRUE(BySizeChanged(benchmark, 16));
170 EXPECT_FALSE(BySizeChanged(benchmark, 15));
171 }
172
173 } // namespace
174