algorithm - 在 DWORD 数组中查找最重要的 DWORD

Question

我想在 DWORD 数组中找到不等于 0 的最重要的 DWORD。该算法应该针对最大 128 字节的数据大小进行优化。

我做了三个不同的函数，它们都返回特定 DWORD 的索引。

unsigned long msb_msvc(long* dw, std::intptr_t n)
{
    while( --n )
    {
        if( dw[n] )
            break;
    }
    return n;
}

static inline unsigned long msb_386(long* dw, std::intptr_t n)
{
    __asm 
    {
        mov ecx, [dw]
        mov eax, [n]

__loop: sub eax, 1
        jz  SHORT __exit
        cmp DWORD PTR [ecx + eax * 4], 0
        jz  SHORT __loop
__exit:
    }
}

static inline unsigned long msb_sse2(long* dw, std::intptr_t n)
{
    __asm 
    {
        mov  ecx, [dw]
        mov  eax, [n]
        test ecx, 0x0f
        jnz  SHORT __128_unaligned

__128_aligned:
        cmp      eax, 4
        jb       SHORT __64
        sub      eax, 4
        movdqa   xmm0, XMMWORD PTR [ecx + eax * 4]
        pxor     xmm1, xmm1
        pcmpeqd  xmm0, xmm1
        pmovmskb edx, xmm0
        not      edx
        and      edx, 0xffff
        jz       SHORT __128_aligned
        jmp      SHORT __exit

__128_unaligned:
        cmp      eax, 4
        jb       SHORT __64
        sub      eax, 4
        movdqu   xmm0, XMMWORD PTR [ecx + eax * 4]
        pxor     xmm1, xmm1
        pcmpeqd  xmm0, xmm1
        pmovmskb edx, xmm0
        not      edx
        and      edx, 0xffff
        jz       SHORT __128_unaligned
        jmp      SHORT __exit

__64:
        cmp      eax, 2
        jb       __32
        sub      eax, 2
        movq     mm0, MMWORD PTR [ecx + eax * 4]
        pxor     mm1, mm1
        pcmpeqd  mm0, mm1
        pmovmskb edx, mm0
        not      edx
        and      edx, 0xff
        emms
        jz       SHORT __64
        jmp      SHORT __exit

__32:
        test eax, eax
        jz   SHORT __exit
        xor  eax, eax
        jmp  __leave ; retn

__exit:
        bsr      edx, edx
        shr      edx, 2
        add eax, edx

__leave:
    }
}

应该使用这些功能来预选将相互比较的数据。因此，它需要高性能。

有人知道更好的算法吗？

Answer 1

我认为您只是在寻找给定数组中的第一个非零词。我肯定会选择用 C 语言编写的简单循环。如果有某种原因说明这是 super 性能关键，我建议您查看程序的更大上下文并询问例如为什么您需要从数组中找到非零对象以及为什么您不知道它的位置的问题。