// An optimised method for finding all row ids within the column encoding
// where the row contains the provided encoded id.
//
// This approach uses SIMD intrinsics to compare two registers with eight
// lanes in parallel using a single CPU instruction. One register is packed
// with the `encoded_id` we are looking for. The other register contains
// eight consecutive values from the column we're searching. The comparioson
// produces an 8 lane register (256 bits) where every 32 bit lane will be
// `0` if the comparison was not equal.
//
// The fast path for this type of column encoding would be that most rows
// will not match the provided encoded_id so it is efficient to check that
// this 256-bit register is all zero and move onto the next eight rows in the
// column.
//
// For cases where one or more of the eight values does match the encoded
// id the exact matching row(s) is/are determined by examining the register.
An optimised method for finding all row ids within the column encoding
where the row contains the provided encoded id.

This approach uses SIMD intrinsics to compare two registers with eight
lanes in parallel using a single CPU instruction. One register is packed
with the `encoded_id` we are looking for. The other register contains
eight consecutive values from the column we're searching. The comparioson
produces an 8 lane register (256 bits) where every 32 bit lane will be
`0` if the comparison was not equal.

The fast path for this type of column encoding would be that most rows
will not match the provided encoded_id so it is efficient to check that
this 256-bit register is all zero and move onto the next eight rows in the
column.

For cases where one or more of the eight values does match the encoded
id the exact matching row(s) is/are determined by examining the register.
An optimised method for finding all row ids within the column encoding where the row contains the provided encoded id . This approach uses SIMD intrinsics to compare two registers with eight lanes in parallel using a single CPU instruction . One register is packed with the ` encoded_id ` we are looking for . The other register contains eight consecutive values from the column we ' re searching . The comparioson produces an 8 lane register ( 256 bits ) where every 32 bit lane will be ` 0 ` if the comparison was not equal . The fast path for this type of column encoding would be that most rows will not match the provided encoded_id so it is efficient to check that this 256 - bit register is all zero and move onto the next eight rows in the column . For cases where one or more of the eight values does match the encoded id the exact matching row ( s ) is / are determined by examining the register .
fn row_ids_equal_simd(&self, encoded_id: u32, mut dst: RowIDs) -> RowIDs {
        unsafe {
            // Pack an 8-lane register containing the encoded id we want to find.
            let id_register = _mm256_set1_epi32(encoded_id as i32);
            let mut i = 0_u32; // Track the total index.
            self.encoded_data.chunks_exact(8).for_each(|chunk| {
                // Load the entries we want to compare against into a SIMD register.
                let entries = _mm256_loadu_si256(chunk.as_ptr() as *const __m256i);
                // Compares the 32-bit packed values and returns a register
                // with the comparison results.
                let res = _mm256_cmpeq_epi32(entries, id_register);
                // Since we only care about determining if every result is 0
                // we can just unpack into two 128-bit integers and check they're
                // both zero.
                let (a, b) = std::mem::transmute::<_, (u128, u128)>(res);
                if a != 0 || b != 0 {
                    // slow path
                    // One or more of the rows checked contains the encoded id.
                    for (j, v) in chunk.iter().enumerate() {
                        if v == &encoded_id {
                            dst.add(i + j as u32);
                        }
                    }
                }
                i += 8;
            });
            // If encoded_data.len() % 8 != 0 then there will be remaining rows
            // to check.
            let rem = self.encoded_data.len() % 8;
            let all_rows = self.num_rows() as usize;
            for i in (all_rows - rem)..all_rows {
                if self.encoded_data[i] == encoded_id {
                    dst.add(i as u32);
                }
            }
        }
        dst
    }
fn row_ids_equal_simd ( & self , encoded_id : u32 , mut dst : RowIDs ) -> RowIDs { unsafe { // Pack an 8-lane register containing the encoded id we want to find. let id_register = _mm256_set1_epi32 ( encoded_id as i32 ) ; let mut i = 0_u32 ; // Track the total index. self . encoded_data . chunks_exact ( 8 ) . for_each ( | chunk | { // Load the entries we want to compare against into a SIMD register. let entries = _mm256_loadu_si256 ( chunk . as_ptr ( ) as * const __m256i ) ; // Compares the 32-bit packed values and returns a register // with the comparison results. let res = _mm256_cmpeq_epi32 ( entries , id_register ) ; // Since we only care about determining if every result is 0 // we can just unpack into two 128-bit integers and check they're // both zero. let ( a , b ) = std :: mem :: transmute :: < _ , ( u128 , u128 ) > ( res ) ; if a != 0 || b != 0 { // slow path // One or more of the rows checked contains the encoded id. for ( j , v ) in chunk . iter ( ) . enumerate ( ) { if v == & encoded_id { dst . add ( i + j as u32 ) ; } } } i += 8 ; } ) ; // If encoded_data.len() % 8 != 0 then there will be remaining rows // to check. let rem = self . encoded_data . len ( ) % 8 ; let all_rows = self . num_rows ( ) as usize ; for i in ( all_rows - rem ) .. all_rows { if self . encoded_data [ i ] == encoded_id { dst . add ( i as u32 ) ; } } } dst }
An optimised method for finding all row ids within the column encoding
where the row contains the provided encoded id.
An optimised method for finding all row ids within the column encoding where the row contains the provided encoded id .
&self
encoded_id
u32
dst
RowIDs