Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * pg_lfind.h
4 : : * Optimized linear search routines using SIMD intrinsics where
5 : : * available.
6 : : *
7 : : * Copyright (c) 2022-2025, PostgreSQL Global Development Group
8 : : *
9 : : * IDENTIFICATION
10 : : * src/include/port/pg_lfind.h
11 : : *
12 : : *-------------------------------------------------------------------------
13 : : */
14 : : #ifndef PG_LFIND_H
15 : : #define PG_LFIND_H
16 : :
17 : : #include "port/simd.h"
18 : :
19 : : /*
20 : : * pg_lfind8
21 : : *
22 : : * Return true if there is an element in 'base' that equals 'key', otherwise
23 : : * return false.
24 : : */
25 : : static inline bool
1113 john.naylor@postgres 26 :CBC 3440339 : pg_lfind8(uint8 key, uint8 *base, uint32 nelem)
27 : : {
28 : : uint32 i;
29 : :
30 : : /* round down to multiple of vector length */
31 : 3440339 : uint32 tail_idx = nelem & ~(sizeof(Vector8) - 1);
32 : : Vector8 chunk;
33 : :
34 [ + + ]: 5569937 : for (i = 0; i < tail_idx; i += sizeof(Vector8))
35 : : {
36 : 3440379 : vector8_load(&chunk, &base[i]);
37 [ + + ]: 3440379 : if (vector8_has(chunk, key))
38 : 1310781 : return true;
39 : : }
40 : :
41 : : /* Process the remaining elements one at a time. */
42 [ + + ]: 2129611 : for (; i < nelem; i++)
43 : : {
44 [ + + ]: 60 : if (key == base[i])
45 : 7 : return true;
46 : : }
47 : :
48 : 2129551 : return false;
49 : : }
50 : :
51 : : /*
52 : : * pg_lfind8_le
53 : : *
54 : : * Return true if there is an element in 'base' that is less than or equal to
55 : : * 'key', otherwise return false.
56 : : */
57 : : static inline bool
58 : 410320 : pg_lfind8_le(uint8 key, uint8 *base, uint32 nelem)
59 : : {
60 : : uint32 i;
61 : :
62 : : /* round down to multiple of vector length */
63 : 410320 : uint32 tail_idx = nelem & ~(sizeof(Vector8) - 1);
64 : : Vector8 chunk;
65 : :
66 [ + + ]: 820667 : for (i = 0; i < tail_idx; i += sizeof(Vector8))
67 : : {
68 : 410360 : vector8_load(&chunk, &base[i]);
69 [ + + ]: 410360 : if (vector8_has_le(chunk, key))
70 : 13 : return true;
71 : : }
72 : :
73 : : /* Process the remaining elements one at a time. */
74 [ + + ]: 410354 : for (; i < nelem; i++)
75 : : {
76 [ + + ]: 60 : if (base[i] <= key)
77 : 13 : return true;
78 : : }
79 : :
80 : 410294 : return false;
81 : : }
82 : :
83 : : /*
84 : : * pg_lfind32_one_by_one_helper
85 : : *
86 : : * Searches the array of integers one-by-one. The caller is responsible for
87 : : * ensuring that there are at least "nelem" integers in the array.
88 : : */
89 : : static inline bool
528 nathan@postgresql.or 90 : 17461146 : pg_lfind32_one_by_one_helper(uint32 key, const uint32 *base, uint32 nelem)
91 : : {
92 [ + + ]: 42498811 : for (uint32 i = 0; i < nelem; i++)
93 : : {
94 [ + + ]: 25080330 : if (key == base[i])
95 : 42665 : return true;
96 : : }
97 : :
98 : 17418481 : return false;
99 : : }
100 : :
101 : : #ifndef USE_NO_SIMD
102 : : /*
103 : : * pg_lfind32_simd_helper
104 : : *
105 : : * Searches one 4-register-block of integers. The caller is responsible for
106 : : * ensuring that there are at least 4-registers-worth of integers remaining.
107 : : */
108 : : static inline bool
109 : 38 : pg_lfind32_simd_helper(const Vector32 keys, const uint32 *base)
110 : : {
529 111 : 38 : const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
112 : : Vector32 vals1,
113 : : vals2,
114 : : vals3,
115 : : vals4,
116 : : result1,
117 : : result2,
118 : : result3,
119 : : result4,
120 : : tmp1,
121 : : tmp2,
122 : : result;
123 : :
124 : : /* load the next block into 4 registers */
125 : 38 : vector32_load(&vals1, base);
126 : 38 : vector32_load(&vals2, &base[nelem_per_vector]);
127 : 38 : vector32_load(&vals3, &base[nelem_per_vector * 2]);
128 : 38 : vector32_load(&vals4, &base[nelem_per_vector * 3]);
129 : :
130 : : /* compare each value to the key */
131 : 38 : result1 = vector32_eq(keys, vals1);
132 : 38 : result2 = vector32_eq(keys, vals2);
133 : 38 : result3 = vector32_eq(keys, vals3);
134 : 38 : result4 = vector32_eq(keys, vals4);
135 : :
136 : : /* combine the results into a single variable */
137 : 38 : tmp1 = vector32_or(result1, result2);
138 : 38 : tmp2 = vector32_or(result3, result4);
139 : 38 : result = vector32_or(tmp1, tmp2);
140 : :
141 : : /* return whether there was a match */
142 : 38 : return vector32_is_highbit_set(result);
143 : : }
144 : : #endif /* ! USE_NO_SIMD */
145 : :
146 : : /*
147 : : * pg_lfind32
148 : : *
149 : : * Return true if there is an element in 'base' that equals 'key', otherwise
150 : : * return false.
151 : : */
152 : : static inline bool
528 153 : 8730576 : pg_lfind32(uint32 key, const uint32 *base, uint32 nelem)
154 : : {
155 : : #ifndef USE_NO_SIMD
156 : 8730576 : uint32 i = 0;
157 : :
158 : : /*
159 : : * For better instruction-level parallelism, each loop iteration operates
160 : : * on a block of four registers.
161 : : */
1104 john.naylor@postgres 162 : 8730576 : const Vector32 keys = vector32_broadcast(key); /* load copies of key */
163 : 8730576 : const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
164 : 8730576 : const uint32 nelem_per_iteration = 4 * nelem_per_vector;
165 : :
166 : : /* round down to multiple of elements per iteration */
167 : 8730576 : const uint32 tail_idx = nelem & ~(nelem_per_iteration - 1);
168 : :
169 : : #if defined(USE_ASSERT_CHECKING)
528 nathan@postgresql.or 170 : 8730576 : bool assert_result = pg_lfind32_one_by_one_helper(key, base, nelem);
171 : : #endif
172 : :
173 : : /*
174 : : * If there aren't enough elements for the SIMD code, use the standard
175 : : * one-by-one linear search code.
176 : : */
529 177 [ + + ]: 8730576 : if (nelem < nelem_per_iteration)
528 178 : 8730570 : return pg_lfind32_one_by_one_helper(key, base, nelem);
179 : :
180 : : /*
181 : : * Process as many elements as possible with a block of 4 registers.
182 : : */
183 : : do
184 : : {
529 185 [ + + ]: 30 : if (pg_lfind32_simd_helper(keys, &base[i]))
186 : : {
1130 john.naylor@postgres 187 [ - + ]: 2 : Assert(assert_result == true);
188 : 2 : return true;
189 : : }
190 : :
529 nathan@postgresql.or 191 : 28 : i += nelem_per_iteration;
192 : :
193 [ + + ]: 28 : } while (i < tail_idx);
194 : :
195 : : /*
196 : : * Process the last 'nelem_per_iteration' elements in the array with a
197 : : * 4-register block. This will cause us to check a subset of the elements
198 : : * more than once, but that won't affect correctness, and testing has
199 : : * demonstrated that this helps more cases than it harms.
200 : : */
201 [ - + ]: 4 : Assert(assert_result == pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]));
202 : 4 : return pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]);
203 : : #else
204 : : /* Process the elements one at a time. */
205 : : return pg_lfind32_one_by_one_helper(key, base, nelem);
206 : : #endif
207 : : }
208 : :
209 : : #endif /* PG_LFIND_H */
|
