]>
Commit | Line | Data |
---|---|---|
97020474 | 1 | /* Measure memmem functions. |
04277e02 | 2 | Copyright (C) 2013-2019 Free Software Foundation, Inc. |
97020474 SP |
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 | <http://www.gnu.org/licenses/>. */ | |
18 | ||
19 | #define TEST_MAIN | |
20 | #define TEST_NAME "memmem" | |
21 | #define BUF1PAGES 20 | |
a173d09f | 22 | #define ITERATIONS 100 |
97020474 SP |
23 | #include "bench-string.h" |
24 | ||
25 | typedef char *(*proto_t) (const void *, size_t, const void *, size_t); | |
97020474 | 26 | |
a173d09f WD |
27 | void * |
28 | basic_memmem (const void *haystack, size_t hs_len, const void *needle, | |
29 | size_t ne_len) | |
30 | { | |
31 | const char *hs = haystack; | |
32 | const char *ne = needle; | |
33 | ||
34 | if (ne_len == 0) | |
35 | return (void *)hs; | |
36 | int i; | |
37 | int c = ne[0]; | |
38 | const char *end = hs + hs_len - ne_len; | |
39 | ||
40 | for ( ; hs <= end; hs++) | |
41 | { | |
42 | if (hs[0] != c) | |
43 | continue; | |
44 | for (i = ne_len - 1; i != 0; i--) | |
45 | if (hs[i] != ne[i]) | |
46 | break; | |
47 | if (i == 0) | |
48 | return (void *)hs; | |
49 | } | |
50 | ||
51 | return NULL; | |
52 | } | |
53 | ||
54 | #define RETURN_TYPE void * | |
55 | #define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l)) | |
56 | #define FASTSEARCH(S,C,N) (void*) memchr ((void *)(S), (C), (N)) | |
57 | #include "../string/str-two-way.h" | |
97020474 SP |
58 | |
59 | void * | |
a173d09f WD |
60 | twoway_memmem (const void *haystack_start, size_t haystack_len, |
61 | const void *needle_start, size_t needle_len) | |
97020474 | 62 | { |
a173d09f WD |
63 | /* Abstract memory is considered to be an array of 'unsigned char' values, |
64 | not an array of 'char' values. See ISO C 99 section 6.2.6.1. */ | |
65 | const unsigned char *haystack = (const unsigned char *) haystack_start; | |
66 | const unsigned char *needle = (const unsigned char *) needle_start; | |
97020474 SP |
67 | |
68 | if (needle_len == 0) | |
69 | /* The first occurrence of the empty string is deemed to occur at | |
70 | the beginning of the string. */ | |
71 | return (void *) haystack; | |
72 | ||
73 | /* Sanity check, otherwise the loop might search through the whole | |
74 | memory. */ | |
a1ffb40e | 75 | if (__glibc_unlikely (haystack_len < needle_len)) |
97020474 SP |
76 | return NULL; |
77 | ||
a173d09f WD |
78 | /* Use optimizations in memchr when possible, to reduce the search |
79 | size of haystack using a linear algorithm with a smaller | |
80 | coefficient. However, avoid memchr for long needles, since we | |
81 | can often achieve sublinear performance. */ | |
82 | if (needle_len < LONG_NEEDLE_THRESHOLD) | |
83 | { | |
84 | haystack = memchr (haystack, *needle, haystack_len); | |
85 | if (!haystack || __builtin_expect (needle_len == 1, 0)) | |
86 | return (void *) haystack; | |
87 | haystack_len -= haystack - (const unsigned char *) haystack_start; | |
88 | if (haystack_len < needle_len) | |
89 | return NULL; | |
90 | /* Check whether we have a match. This improves performance since we | |
91 | avoid the initialization overhead of the two-way algorithm. */ | |
92 | if (memcmp (haystack, needle, needle_len) == 0) | |
93 | return (void *) haystack; | |
94 | return two_way_short_needle (haystack, haystack_len, needle, needle_len); | |
95 | } | |
96 | else | |
97 | return two_way_long_needle (haystack, haystack_len, needle, needle_len); | |
97020474 SP |
98 | } |
99 | ||
a173d09f WD |
100 | IMPL (memmem, 1) |
101 | IMPL (twoway_memmem, 0) | |
102 | IMPL (basic_memmem, 0) | |
103 | ||
97020474 SP |
104 | static void |
105 | do_one_test (impl_t *impl, const void *haystack, size_t haystack_len, | |
106 | const void *needle, size_t needle_len, const void *expected) | |
107 | { | |
46ae0732 | 108 | size_t i, iters = INNER_LOOP_ITERS_SMALL; |
44558701 WN |
109 | timing_t start, stop, cur; |
110 | ||
111 | TIMING_NOW (start); | |
112 | for (i = 0; i < iters; ++i) | |
97020474 | 113 | { |
44558701 WN |
114 | CALL (impl, haystack, haystack_len, needle, needle_len); |
115 | } | |
116 | TIMING_NOW (stop); | |
97020474 | 117 | |
44558701 | 118 | TIMING_DIFF (cur, start, stop); |
97020474 | 119 | |
44558701 | 120 | TIMING_PRINT_MEAN ((double) cur, (double) iters); |
97020474 SP |
121 | } |
122 | ||
123 | static void | |
124 | do_test (const char *str, size_t len, size_t idx) | |
125 | { | |
126 | char tmpbuf[len]; | |
127 | ||
128 | memcpy (tmpbuf, buf1 + idx, len); | |
129 | memcpy (buf1 + idx, str, len); | |
130 | ||
44558701 | 131 | printf ("String %s, offset %zd:", str, idx); |
97020474 SP |
132 | |
133 | FOR_EACH_IMPL (impl, 0) | |
134 | do_one_test (impl, buf1, BUF1PAGES * page_size, str, len, buf1 + idx); | |
135 | ||
136 | memcpy (buf1 + idx, tmpbuf, len); | |
137 | ||
44558701 | 138 | putchar ('\n'); |
97020474 SP |
139 | } |
140 | ||
141 | static void | |
142 | do_random_tests (void) | |
143 | { | |
144 | for (size_t n = 0; n < ITERATIONS; ++n) | |
145 | { | |
146 | char tmpbuf[32]; | |
147 | ||
148 | size_t shift = random () % 11; | |
149 | size_t rel = random () % ((2 << (shift + 1)) * 64); | |
150 | size_t idx = MIN ((2 << shift) * 64 + rel, BUF1PAGES * page_size - 2); | |
151 | size_t len = random () % (sizeof (tmpbuf) - 1) + 1; | |
152 | len = MIN (len, BUF1PAGES * page_size - idx - 1); | |
153 | memcpy (tmpbuf, buf1 + idx, len); | |
154 | for (size_t i = random () % len / 2 + 1; i > 0; --i) | |
155 | { | |
156 | size_t off = random () % len; | |
157 | char ch = '0' + random () % 10; | |
158 | ||
159 | buf1[idx + off] = ch; | |
160 | } | |
161 | ||
44558701 | 162 | printf ("String %.*s, offset %zd:", (int) len, buf1 + idx, idx); |
97020474 SP |
163 | |
164 | FOR_EACH_IMPL (impl, 0) | |
165 | do_one_test (impl, buf1, BUF1PAGES * page_size, buf1 + idx, len, | |
166 | buf1 + idx); | |
167 | ||
44558701 | 168 | putchar ('\n'); |
97020474 SP |
169 | |
170 | memcpy (buf1 + idx, tmpbuf, len); | |
171 | } | |
172 | } | |
173 | ||
174 | static const char *const strs[] = | |
175 | { | |
176 | "00000", "00112233", "0123456789", "0000111100001111", | |
177 | "00000111110000022222", "012345678901234567890", | |
178 | "abc0", "aaaa0", "abcabc0" | |
179 | }; | |
180 | ||
181 | ||
182 | int | |
183 | test_main (void) | |
184 | { | |
185 | size_t i; | |
186 | ||
187 | test_init (); | |
188 | ||
189 | printf ("%23s", ""); | |
190 | FOR_EACH_IMPL (impl, 0) | |
191 | printf ("\t%s", impl->name); | |
192 | putchar ('\n'); | |
193 | ||
194 | for (i = 0; i < BUF1PAGES * page_size; ++i) | |
195 | buf1[i] = 60 + random () % 32; | |
196 | ||
197 | for (i = 0; i < sizeof (strs) / sizeof (strs[0]); ++i) | |
198 | for (size_t j = 0; j < 120; j += 7) | |
199 | { | |
200 | size_t len = strlen (strs[i]); | |
201 | ||
202 | do_test (strs[i], len, j); | |
203 | } | |
204 | ||
205 | do_random_tests (); | |
206 | return ret; | |
207 | } | |
208 | ||
b598e134 | 209 | #include <support/test-driver.c> |