[フレーム]

Functions

pg_lfind.h File Reference

#include "port/simd.h"

Include dependency graph for pg_lfind.h:

simd_8h.html

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}

uint32

uint32_t uint32

Definition: c.h:538

Assert

Assert(PointerIsAligned(start, uint64))

i

int i

Definition: isn.c:77

sort-test.key

key

Definition: sort-test.py:19

pg_lfind32_one_by_one_helper

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);

32 Vector8 chunk;

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}

vector8_load

static void vector8_load(Vector8 *v, const uint8 *s)

Definition: simd.h:107

Vector8

uint64 Vector8

Definition: simd.h:60

vector8_has

static bool vector8_has(const Vector8 v, const uint8 c)

Definition: simd.h:176

References 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);

64 Vector8 chunk;

65

66 for (i = 0; i < tail_idx; i += sizeof(Vector8))

67 {

68 vector8_load(&chunk, &base[i]);

69 if (vector8_has_le(chunk, key))

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}

vector8_has_le

static bool vector8_has_le(const Vector8 v, const uint8 c)

Definition: simd.h:227

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

Referenced by json_lex_string(), and test_lfind8_le_internal().