如何在ARM NEON的uint8x8_t寄存器中查找最小值及位置？求改进建议

Hey there! Let's figure out how to efficiently find both the minimum value and its position in a uint8x8_t ARM NEON register. I'll walk through optimized approaches and share improvements for your existing solution.

First, let's recap the scalar code you provided for reference—it's straightforward but doesn't leverage NEON's parallelism:

uint8_t v[8] = { ... }; 
int ret = 256; 
int ret_pos = -1; 
for (int i=0; i<8; ++i) { 
    if (v[i] < ret) { 
        ret = v[i]; 
        ret_pos = i; 
    } 
}

While vminv_u8 gives us the minimum value in a uint8x8_t with a single instruction, it doesn't track the position. Let's cover two robust approaches, plus improvements for your existing solution.

Approach 1: Find Min First, Then Locate Its Position #

This is the most concise and often most efficient method, especially with modern compilers. Here's how it works:

1. Use vminv_u8 to get the scalar minimum value.
2. Create a vector filled with this minimum value.
3. Compare the original vector to this min vector to generate a mask (1s where elements equal the min, 0s otherwise).
4. Find the position of the first (or last) 1 in the mask using scalar built-in functions.

Example Code #

#include <arm_neon.h>

void find_min_and_pos(uint8x8_t data, uint8_t* out_min, int* out_pos) {
    // Step 1: Get the minimum value
    *out_min = vminv_u8(data);
    
    // Step 2: Create a vector of the minimum value
    uint8x8_t min_vec = vdup_n_u8(*out_min);
    
    // Step 3: Generate mask where elements equal the min
    uint8x8_t mask = vceq_u8(data, min_vec);
    
    // Step 4: Convert mask to 64-bit integer and find the first set bit
    uint64_t mask_64 = vget_lane_u64(vreinterpret_u64_u8(mask), 0);
    // __builtin_ctzll finds trailing zeros (gives first min position)
    *out_pos = __builtin_ctzll(mask_64) / 8;
}

Improvements for This Method #

• Handle Multiple Minima: If you want the rightmost minimum instead of the leftmost, replace __builtin_ctzll with 63 - __builtin_clzll(mask_64) (then divide by 8). __builtin_clzll counts leading zeros, so this gives the highest set bit position.
• Compiler Compatibility: For ARM Compiler (ARMCC), use __clzll instead of __builtin_clzll, or use inline assembly for bit-counting if needed.
• Avoid Overhead: Modern compilers optimize the mask-to-64bit conversion and bit-counting into efficient NEON/ARM instructions (like RBIT + CLZ), so you don't need hand-written assembly here.

Approach 2: Track Position During Pairwise Min Comparisons #

If you prefer to track the position alongside the minimum value through each pairwise comparison (your original approach direction), here's an optimized version using NEON's comparison and selection instructions:

Example Code #

#include <arm_neon.h>

void find_min_and_pos_pairwise(uint8x8_t data, uint8_t* out_min, int* out_pos) {
    // Initialize position vector (0-7)
    static const uint8_t pos_arr[8] = {0,1,2,3,4,5,6,7};
    uint8x8_t pos_vec = vld1_u8(pos_arr);
    
    // First pairwise min: compare adjacent elements, select position of smaller value
    uint8x8_t min_data = vpmin_u8(data, data);
    uint8x8_t min_pos = vbsl_u8(vclt_u8(data, vext_u8(data, data, 1)), pos_vec, vext_u8(pos_vec, pos_vec, 1));
    
    // Narrow to 4 elements (only even lanes are valid from vpmin)
    uint8x4_t min4_data = vpmin_u8(vget_low_u8(min_data), vget_low_u8(min_data));
    uint8x4_t min4_pos = vbsl_u8(vclt_u8(vget_low_u8(min_data), vext_u8(vget_low_u8(min_data), vget_low_u8(min_data), 1)),
                                 vget_low_u8(min_pos), vext_u8(vget_low_u8(min_pos), vget_low_u8(min_pos), 1));
    
    // Narrow to 2 elements
    uint8x2_t min2_data = vpmin_u8(vget_low_u8(min4_data), vget_low_u8(min4_data));
    uint8x2_t min2_pos = vbsl_u8(vclt_u8(vget_low_u8(min4_data), vext_u8(vget_low_u8(min4_data), vget_low_u8(min4_data), 1)),
                                 vget_low_u8(min4_pos), vext_u8(vget_low_u8(min4_pos), vget_low_u8(min4_pos), 1));
    
    // Final min comparison
    uint8x1_t final_min = vmin_u8(vget_low_u8(min2_data), vget_high_u8(min2_data));
    uint8x1_t final_pos = vbsl_u8(vclt_u8(vget_low_u8(min2_data), vget_high_u8(min2_data)),
                                  vget_low_u8(min2_pos), vget_high_u8(min2_pos));
    
    *out_min = vget_lane_u8(final_min, 0);
    *out_pos = vget_lane_u8(final_pos, 0);
}

Improvements for Pairwise Tracking #

• Eliminate Memory Load for Positions: Instead of loading from an array, construct the position vector at compile time:

  uint8x8_t pos_vec = vcreate_u8(0x0001020304050607);
  

  Just ensure your target uses little-endian (standard for ARM) so each byte maps to the correct index 0-7.
• Simplify Instruction Flow: Use vpmin_u8 to handle pairwise minima in a single instruction, instead of manually splitting the vector into low/high halves. This reduces clutter and improves pipeline efficiency.
• Clarify Comparison Logic: The vbsl_u8 uses vclt_u8 (compare less than) to pick the position of the smaller element. Adjust to vcgt_u8 if you want to prioritize the right element when values are equal.

Key Takeaways for Your Solution #

• Prefer Approach 1 for most cases: It's shorter, easier to maintain, and compiles to fewer instructions. The bit-counting step is highly optimized by modern compilers.
• If You Stick to Pairwise Tracking: Use vpmin_u8 and vext_u8 to reduce manual vector manipulation, and avoid unnecessary memory loads for the position vector by using compile-time constants.
• Be Explicit About Minima Handling: Decide whether you want the first or last occurrence of the minimum, and adjust your position-finding logic accordingly.

内容的提问来源于stack exchange，提问作者Pavel P