1 | /* Measure memmem functions. |
2 | Copyright (C) 2013-2024 Free Software Foundation, Inc. |
3 | This file is part of the GNU C Library. |
4 | |
5 | The GNU C Library is free software; you can redistribute it and/or |
6 | modify it under the terms of the GNU Lesser General Public |
7 | License as published by the Free Software Foundation; either |
8 | version 2.1 of the License, or (at your option) any later version. |
9 | |
10 | The GNU C Library is distributed in the hope that it will be useful, |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | Lesser General Public License for more details. |
14 | |
15 | You should have received a copy of the GNU Lesser General Public |
16 | License along with the GNU C Library; if not, see |
17 | <https://www.gnu.org/licenses/>. */ |
18 | |
19 | #define TEST_MAIN |
20 | #define TEST_NAME "memmem" |
21 | #define BUF1PAGES 20 |
22 | #define ITERATIONS 100 |
23 | #include "bench-string.h" |
24 | #include "json-lib.h" |
25 | |
26 | typedef char *(*proto_t) (const void *, size_t, const void *, size_t); |
27 | |
28 | void * |
29 | basic_memmem (const void *haystack, size_t hs_len, const void *needle, |
30 | size_t ne_len) |
31 | { |
32 | const char *hs = haystack; |
33 | const char *ne = needle; |
34 | |
35 | if (ne_len == 0) |
36 | return (void *)hs; |
37 | int i; |
38 | int c = ne[0]; |
39 | const char *end = hs + hs_len - ne_len; |
40 | |
41 | for ( ; hs <= end; hs++) |
42 | { |
43 | if (hs[0] != c) |
44 | continue; |
45 | for (i = ne_len - 1; i != 0; i--) |
46 | if (hs[i] != ne[i]) |
47 | break; |
48 | if (i == 0) |
49 | return (void *)hs; |
50 | } |
51 | |
52 | return NULL; |
53 | } |
54 | |
55 | #define RETURN_TYPE void * |
56 | #define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l)) |
57 | #define FASTSEARCH(S,C,N) (void*) memchr ((void *)(S), (C), (N)) |
58 | #include "../string/str-two-way.h" |
59 | |
60 | void * |
61 | twoway_memmem (const void *haystack_start, size_t haystack_len, |
62 | const void *needle_start, size_t needle_len) |
63 | { |
64 | /* Abstract memory is considered to be an array of 'unsigned char' values, |
65 | not an array of 'char' values. See ISO C 99 section 6.2.6.1. */ |
66 | const unsigned char *haystack = (const unsigned char *) haystack_start; |
67 | const unsigned char *needle = (const unsigned char *) needle_start; |
68 | |
69 | if (needle_len == 0) |
70 | /* The first occurrence of the empty string is deemed to occur at |
71 | the beginning of the string. */ |
72 | return (void *) haystack; |
73 | |
74 | /* Sanity check, otherwise the loop might search through the whole |
75 | memory. */ |
76 | if (__glibc_unlikely (haystack_len < needle_len)) |
77 | return NULL; |
78 | |
79 | /* Use optimizations in memchr when possible, to reduce the search |
80 | size of haystack using a linear algorithm with a smaller |
81 | coefficient. However, avoid memchr for long needles, since we |
82 | can often achieve sublinear performance. */ |
83 | if (needle_len < LONG_NEEDLE_THRESHOLD) |
84 | { |
85 | haystack = memchr (haystack, *needle, haystack_len); |
86 | if (!haystack || __builtin_expect (needle_len == 1, 0)) |
87 | return (void *) haystack; |
88 | haystack_len -= haystack - (const unsigned char *) haystack_start; |
89 | if (haystack_len < needle_len) |
90 | return NULL; |
91 | /* Check whether we have a match. This improves performance since we |
92 | avoid the initialization overhead of the two-way algorithm. */ |
93 | if (memcmp (haystack, needle, needle_len) == 0) |
94 | return (void *) haystack; |
95 | return two_way_short_needle (haystack, haystack_len, needle, needle_len); |
96 | } |
97 | else |
98 | return two_way_long_needle (haystack, haystack_len, needle, needle_len); |
99 | } |
100 | |
101 | IMPL (memmem, 1) |
102 | IMPL (twoway_memmem, 0) |
103 | IMPL (basic_memmem, 0) |
104 | |
105 | static void |
106 | do_one_test (json_ctx_t *json_ctx, impl_t *impl, const void *haystack, |
107 | size_t haystack_len, const void *needle, size_t needle_len, |
108 | const void *expected) |
109 | { |
110 | size_t i, iters = INNER_LOOP_ITERS_SMALL; |
111 | timing_t start, stop, cur; |
112 | void *res; |
113 | TIMING_NOW (start); |
114 | for (i = 0; i < iters; ++i) |
115 | { |
116 | res = CALL (impl, haystack, haystack_len, needle, needle_len); |
117 | } |
118 | TIMING_NOW (stop); |
119 | |
120 | TIMING_DIFF (cur, start, stop); |
121 | |
122 | json_element_double (ctx: json_ctx, d: (double) cur / (double) iters); |
123 | |
124 | if (res != expected) |
125 | { |
126 | error (status: 0, errnum: 0, format: "Wrong result in function (%p != %p) %s(%p, %zu, %p, %zu)" , |
127 | res, expected, impl->name, haystack, haystack_len, needle, |
128 | needle_len); |
129 | ret = 1; |
130 | } |
131 | } |
132 | |
133 | static void |
134 | do_test (json_ctx_t *json_ctx, const char *str, size_t len, size_t idx) |
135 | { |
136 | char tmpbuf[len]; |
137 | |
138 | memcpy (tmpbuf, buf1 + idx, len); |
139 | memcpy (buf1 + idx, str, len); |
140 | |
141 | json_element_object_begin (ctx: json_ctx); |
142 | json_attr_uint (ctx: json_ctx, name: "len_haystack" , BUF1PAGES * page_size); |
143 | json_attr_uint (ctx: json_ctx, name: "len_needle" , d: len); |
144 | json_attr_uint (ctx: json_ctx, name: "haystack_ptr" , d: (uintptr_t) buf1); |
145 | json_attr_uint (ctx: json_ctx, name: "needle_ptr" , d: (uintptr_t) str); |
146 | json_attr_uint (ctx: json_ctx, name: "fail" , d: 0); |
147 | |
148 | json_array_begin (ctx: json_ctx, name: "timings" ); |
149 | |
150 | FOR_EACH_IMPL (impl, 0) |
151 | do_one_test (json_ctx, impl, haystack: buf1, BUF1PAGES * page_size, needle: str, needle_len: len, |
152 | expected: buf1 + idx); |
153 | |
154 | memcpy (buf1 + idx, tmpbuf, len); |
155 | |
156 | json_array_end (ctx: json_ctx); |
157 | json_element_object_end (ctx: json_ctx); |
158 | } |
159 | |
160 | static void |
161 | do_random_tests (json_ctx_t *json_ctx) |
162 | { |
163 | for (size_t n = 0; n < ITERATIONS; ++n) |
164 | { |
165 | char tmpbuf[32]; |
166 | |
167 | size_t shift = random () % 11; |
168 | size_t rel = random () % ((2 << (shift + 1)) * 64); |
169 | size_t idx = MIN ((2 << shift) * 64 + rel, BUF1PAGES * page_size - 2); |
170 | size_t len = random () % (sizeof (tmpbuf) - 1) + 1; |
171 | len = MIN (len, BUF1PAGES * page_size - idx - 1); |
172 | memcpy (tmpbuf, buf1 + idx, len); |
173 | for (size_t i = random () % len / 2 + 1; i > 0; --i) |
174 | { |
175 | size_t off = random () % len; |
176 | char ch = '0' + random () % 10; |
177 | |
178 | buf1[idx + off] = ch; |
179 | } |
180 | |
181 | json_element_object_begin (ctx: json_ctx); |
182 | json_attr_uint (ctx: json_ctx, name: "len_haystack" , BUF1PAGES * page_size); |
183 | json_attr_uint (ctx: json_ctx, name: "len_needle" , d: len); |
184 | json_attr_uint (ctx: json_ctx, name: "haystack_ptr" , d: (uintptr_t) buf1); |
185 | json_attr_uint (ctx: json_ctx, name: "needle_ptr" , d: (uintptr_t) (buf1 + idx)); |
186 | json_attr_uint (ctx: json_ctx, name: "fail" , d: 0); |
187 | |
188 | json_array_begin (ctx: json_ctx, name: "timings" ); |
189 | |
190 | FOR_EACH_IMPL (impl, 0) |
191 | do_one_test (json_ctx, impl, haystack: buf1, BUF1PAGES * page_size, needle: buf1 + idx, |
192 | needle_len: len, expected: buf1 + idx); |
193 | |
194 | json_array_end (ctx: json_ctx); |
195 | json_element_object_end (ctx: json_ctx); |
196 | |
197 | memcpy (buf1 + idx, tmpbuf, len); |
198 | } |
199 | } |
200 | |
201 | static const char *const strs[] = |
202 | { |
203 | "00000" , "00112233" , "0123456789" , "0000111100001111" , |
204 | "00000111110000022222" , "012345678901234567890" , |
205 | "abc0" , "aaaa0" , "abcabc0" |
206 | }; |
207 | |
208 | int |
209 | test_main (void) |
210 | { |
211 | json_ctx_t json_ctx; |
212 | size_t i; |
213 | |
214 | test_init (); |
215 | json_init (ctx: &json_ctx, indent_level: 0, stdout); |
216 | |
217 | json_document_begin (ctx: &json_ctx); |
218 | json_attr_string (ctx: &json_ctx, name: "timing_type" , TIMING_TYPE); |
219 | |
220 | json_attr_object_begin (ctx: &json_ctx, name: "functions" ); |
221 | json_attr_object_begin (ctx: &json_ctx, TEST_NAME); |
222 | json_attr_string (ctx: &json_ctx, name: "bench-variant" , s: "" ); |
223 | |
224 | json_array_begin (ctx: &json_ctx, name: "ifuncs" ); |
225 | FOR_EACH_IMPL (impl, 0) |
226 | json_element_string (ctx: &json_ctx, s: impl->name); |
227 | json_array_end (ctx: &json_ctx); |
228 | |
229 | json_array_begin (ctx: &json_ctx, name: "results" ); |
230 | |
231 | for (i = 0; i < BUF1PAGES * page_size; ++i) |
232 | buf1[i] = 60 + random () % 32; |
233 | |
234 | for (i = 0; i < sizeof (strs) / sizeof (strs[0]); ++i) |
235 | for (size_t j = 0; j < 120; j += 7) |
236 | { |
237 | size_t len = strlen (strs[i]); |
238 | |
239 | do_test (json_ctx: &json_ctx, str: strs[i], len, idx: j); |
240 | } |
241 | |
242 | do_random_tests (json_ctx: &json_ctx); |
243 | |
244 | json_array_end (ctx: &json_ctx); |
245 | json_attr_object_end (ctx: &json_ctx); |
246 | json_attr_object_end (ctx: &json_ctx); |
247 | json_document_end (ctx: &json_ctx); |
248 | return ret; |
249 | } |
250 | |
251 | #include <support/test-driver.c> |
252 | |