LCOV - code coverage report
Current view: top level - src/include/port - pg_lfind.h (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 52 52 100.0 %
Date: 2024-03-28 11:11:48 Functions: 5 5 100.0 %
Legend: Lines: hit not hit

          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-2024, 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
      26     4571300 : pg_lfind8(uint8 key, uint8 *base, uint32 nelem)
      27             : {
      28             :     uint32      i;
      29             : 
      30             :     /* round down to multiple of vector length */
      31     4571300 :     uint32      tail_idx = nelem & ~(sizeof(Vector8) - 1);
      32             :     Vector8     chunk;
      33             : 
      34     7323956 :     for (i = 0; i < tail_idx; i += sizeof(Vector8))
      35             :     {
      36     4571380 :         vector8_load(&chunk, &base[i]);
      37     4571380 :         if (vector8_has(chunk, key))
      38     1818724 :             return true;
      39             :     }
      40             : 
      41             :     /* Process the remaining elements one at a time. */
      42     2752682 :     for (; i < nelem; i++)
      43             :     {
      44         120 :         if (key == base[i])
      45          14 :             return true;
      46             :     }
      47             : 
      48     2752562 :     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      467226 : pg_lfind8_le(uint8 key, uint8 *base, uint32 nelem)
      59             : {
      60             :     uint32      i;
      61             : 
      62             :     /* round down to multiple of vector length */
      63      467226 :     uint32      tail_idx = nelem & ~(sizeof(Vector8) - 1);
      64             :     Vector8     chunk;
      65             : 
      66      934506 :     for (i = 0; i < tail_idx; i += sizeof(Vector8))
      67             :     {
      68      467306 :         vector8_load(&chunk, &base[i]);
      69      467306 :         if (vector8_has_le(chunk, key))
      70          26 :             return true;
      71             :     }
      72             : 
      73             :     /* Process the remaining elements one at a time. */
      74      467294 :     for (; i < nelem; i++)
      75             :     {
      76         120 :         if (base[i] <= key)
      77          26 :             return true;
      78             :     }
      79             : 
      80      467174 :     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
      90    10045882 : pg_lfind32_one_by_one_helper(uint32 key, const uint32 *base, uint32 nelem)
      91             : {
      92    19869296 :     for (uint32 i = 0; i < nelem; i++)
      93             :     {
      94     9832648 :         if (key == base[i])
      95        9234 :             return true;
      96             :     }
      97             : 
      98    10036648 :     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          68 : pg_lfind32_simd_helper(const Vector32 keys, const uint32 *base)
     110             : {
     111          68 :     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          68 :     vector32_load(&vals1, base);
     126          68 :     vector32_load(&vals2, &base[nelem_per_vector]);
     127          68 :     vector32_load(&vals3, &base[nelem_per_vector * 2]);
     128          68 :     vector32_load(&vals4, &base[nelem_per_vector * 3]);
     129             : 
     130             :     /* compare each value to the key */
     131          68 :     result1 = vector32_eq(keys, vals1);
     132          68 :     result2 = vector32_eq(keys, vals2);
     133          68 :     result3 = vector32_eq(keys, vals3);
     134          68 :     result4 = vector32_eq(keys, vals4);
     135             : 
     136             :     /* combine the results into a single variable */
     137          68 :     tmp1 = vector32_or(result1, result2);
     138          68 :     tmp2 = vector32_or(result3, result4);
     139          68 :     result = vector32_or(tmp1, tmp2);
     140             : 
     141             :     /* return whether there was a match */
     142          68 :     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
     153    10045894 : pg_lfind32(uint32 key, const uint32 *base, uint32 nelem)
     154             : {
     155             : #ifndef USE_NO_SIMD
     156    10045894 :     uint32      i = 0;
     157             : 
     158             :     /*
     159             :      * For better instruction-level parallelism, each loop iteration operates
     160             :      * on a block of four registers.
     161             :      */
     162    10045894 :     const Vector32 keys = vector32_broadcast(key);  /* load copies of key */
     163    10045894 :     const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
     164    10045894 :     const uint32 nelem_per_iteration = 4 * nelem_per_vector;
     165             : 
     166             :     /* round down to multiple of elements per iteration */
     167    10045894 :     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    10045894 :     if (nelem < nelem_per_iteration)
     178    10045882 :         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          60 :         if (pg_lfind32_simd_helper(keys, &base[i]))
     186             :         {
     187             :             Assert(assert_result == true);
     188           4 :             return true;
     189             :         }
     190             : 
     191          56 :         i += nelem_per_iteration;
     192             : 
     193          56 :     } 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           8 :     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 */

Generated by: LCOV version 1.14