PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
pg_lfind.h File Reference
#include "port/simd.h"
Include dependency graph for pg_lfind.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

static bool pg_lfind8 (uint8 key, uint8 *base, uint32 nelem)
 
static bool pg_lfind8_le (uint8 key, uint8 *base, uint32 nelem)
 
static bool pg_lfind32_one_by_one_helper (uint32 key, const uint32 *base, uint32 nelem)
 
static bool pg_lfind32 (uint32 key, const uint32 *base, uint32 nelem)
 

Function Documentation

◆ pg_lfind32()

static bool pg_lfind32 ( uint32  key,
const uint32 base,
uint32  nelem 
)
inlinestatic

Definition at line 153 of file pg_lfind.h.

154{
155#ifndef USE_NO_SIMD
156 uint32 i = 0;
157
158 /*
159 * For better instruction-level parallelism, each loop iteration operates
160 * on a block of four registers.
161 */
162 const Vector32 keys = vector32_broadcast(key); /* load copies of key */
163 const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
164 const uint32 nelem_per_iteration = 4 * nelem_per_vector;
165
166 /* round down to multiple of elements per iteration */
167 const uint32 tail_idx = nelem & ~(nelem_per_iteration - 1);
168
169#if defined(USE_ASSERT_CHECKING)
170 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 */
177 if (nelem < nelem_per_iteration)
178 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 {
185 if (pg_lfind32_simd_helper(keys, &base[i]))
186 {
187 Assert(assert_result == true);
188 return true;
189 }
190
191 i += nelem_per_iteration;
192
193 } 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 Assert(assert_result == pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]));
202 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}
#define Assert(condition)
Definition: c.h:812
uint32_t uint32
Definition: c.h:485
int i
Definition: isn.c:72
static bool pg_lfind32_one_by_one_helper(uint32 key, const uint32 *base, uint32 nelem)
Definition: pg_lfind.h:90

References Assert, i, sort-test::key, and pg_lfind32_one_by_one_helper().

Referenced by test_lfind32(), TransactionIdIsInProgress(), XidInMVCCSnapshot(), and XidIsConcurrent().

◆ pg_lfind32_one_by_one_helper()

static bool pg_lfind32_one_by_one_helper ( uint32  key,
const uint32 base,
uint32  nelem 
)
inlinestatic

Definition at line 90 of file pg_lfind.h.

91{
92 for (uint32 i = 0; i < nelem; i++)
93 {
94 if (key == base[i])
95 return true;
96 }
97
98 return false;
99}

References i, and sort-test::key.

Referenced by pg_lfind32().

◆ pg_lfind8()

static bool pg_lfind8 ( uint8  key,
uint8 base,
uint32  nelem 
)
inlinestatic

Definition at line 26 of file pg_lfind.h.

27{
28 uint32 i;
29
30 /* round down to multiple of vector length */
31 uint32 tail_idx = nelem & ~(sizeof(Vector8) - 1);
33
34 for (i = 0; i < tail_idx; i += sizeof(Vector8))
35 {
36 vector8_load(&chunk, &base[i]);
37 if (vector8_has(chunk, key))
38 return true;
39 }
40
41 /* Process the remaining elements one at a time. */
42 for (; i < nelem; i++)
43 {
44 if (key == base[i])
45 return true;
46 }
47
48 return false;
49}
uint64 chunk
static void vector8_load(Vector8 *v, const uint8 *s)
Definition: simd.h:108
uint64 Vector8
Definition: simd.h:60
static bool vector8_has(const Vector8 v, const uint8 c)
Definition: simd.h:162

References chunk, i, sort-test::key, vector8_has(), and vector8_load().

Referenced by json_lex_string(), and test_lfind8_internal().

◆ pg_lfind8_le()

static bool pg_lfind8_le ( uint8  key,
uint8 base,
uint32  nelem 
)
inlinestatic

Definition at line 58 of file pg_lfind.h.

59{
60 uint32 i;
61
62 /* round down to multiple of vector length */
63 uint32 tail_idx = nelem & ~(sizeof(Vector8) - 1);
65
66 for (i = 0; i < tail_idx; i += sizeof(Vector8))
67 {
68 vector8_load(&chunk, &base[i]);
70 return true;
71 }
72
73 /* Process the remaining elements one at a time. */
74 for (; i < nelem; i++)
75 {
76 if (base[i] <= key)
77 return true;
78 }
79
80 return false;
81}
static bool vector8_has_le(const Vector8 v, const uint8 c)
Definition: simd.h:213

References chunk, i, sort-test::key, vector8_has_le(), and vector8_load().

Referenced by json_lex_string(), and test_lfind8_le_internal().