强制A在C中的128位登记册中进行的比较

Question

我正在使用bsearch（数组，数组，num_arrays，16，compare_func）进行二进制搜索，并且

int compare(const void *p1, const void *p2) 
{
    return memcmp(p1, p2, 16);          // unsigned char arrays[][16]
}

由于它是16个字节，它将适合单个128位寄存器。

如何修改此C函数以强制使用128位寄存器CPU指令进行比较？应该更快。

链接的问题：比较x86--128位无签名整数的比较32组装，是什么128位至512位寄存器用于？，但没有直接回答。

Answer 1

如果数字存储在大元素顺序中，并且指针在16个字节边界上对齐，则与memcmp的比较为16个字节边界。它是否更有效将取决于编译器和优化设置。

这是一个修改后的功能：

typedef unsigned __int128 u128_t;  // works for gcc, adjust for your compiler

int compare(const void *p1, const void *p2) {
    const u128_t *v1 = p1;
    const u128_t *v2 = p2;
    return (*v1 > *v2) - (*v1 < *v2);
}

问题是您的目标系统可能使用 Little Endian 顺序（例如：x86 cpus）。如果您的目标是在数组数组中找到数组，那么只要使用相同的比较对数组进行排序，您仍然可以使用此技巧。

使用bsearch需要一个功能指针，该函数指针返回等于0对比较均等的元素的签名值，如果元素指向p1 p1 小于p2指向的一个，否则为正值。这种方法的另一个问题是类型的puning和对齐问题，这些问题产生了不确定的行为。

编写在工会数组中运行的二进制搜索功能并使用单个迭代的单个比较来定位匹配条目将更加安全，更有效。必须对此数组进行排序，并且可以使用QSort（）使用compare128（）函数对其进行排序。

以下是一个示例：

#include <stddef.h>

typedef unsigned __int128 u128_t;  // works for gcc, adjust for your compiler

typedef union {
    char c[16];
    u128_t u128;
} mytype;

/* comparison function for qsort and bsearch */
int compare128(const void *p1, const void *p2) {
    const mytype *v1 = p1;
    const mytype *v2 = p2;
    return (v1->u128 > v2->u128) - (v1->u128 < v2->u128);
}

int binarySearch128(const mytype array[], size_t n,
                    const unsigned char key[16])
{
    u128_t keyval;
    memcpy(&keyval, key, sizeof keyval);
    size_t lo = 0, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (array[mid].u128 < keyval) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    if (lo < n && array[lo].u128 == keyval) {
        return (int)lo;
    } else {
        return -1;
    }
}

在没有128位整数支持的平台上，您可以使用以下方式：

#include <stdint.h>

typedef union {
    char c[16];
    uint64_t u64[2];
} mytype;

// comparison function for qsort
int compare128(const void *p1, const void *p2) {
    const mytype *v1 = p1;
    const mytype *v2 = p2;
    int cmp = (v1->u64[0] > v2->u64[0]) - (v1->u64[0] < v2->u64[0]);
    return cmp ? cmp : (v1->u64[1] > v2->u64[1]) - (v1->u64[1] < v2->u64[1]);
}

int binarySearch128(const mytype array[], size_t n,
                    const unsigned char key[16])
{
    mytype keyval;
    memcpy(&keyval, key, sizeof keyval);
    size_t lo = 0, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (array[mid].u64[0] < keyval.u64[0]
        ||  (array[mid].u64[0] == keyval.u64[0] && array[mid].u64[1] < keyval.u64[1]) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    if (lo < n && array[lo].u64[0] == keyval.u64[0] && array[lo].u64[1] == keyval.u64[1]) {
        return (int)lo;
    } else {
        return -1;  // or 0
    }
}