c - AIX下128位比较(64位)对hash值排序

Question

我需要在 AIX(64 位)下使用 xlC_r 编译器对像这样的结构数组进行排序:

struct digest_line {
    uint64_t first;
    uint64_t second;
};

现在我正在做很长的路要走(比较第一个元素，如果它们相等，则比较第二个元素。)有没有更快的方法来比较这些值？

编辑:我忘了说我正在使用 AIX 的 qsort() 函数。根据 qsort 的手册页，比较函数定义如下

int  (*ComparisonPointer)(const void*, const void*);

这(对我而言)意味着我不能只返回一个 int64_t 值，而是像这样:

int compare_digests(const void *a, const void *b)
{
        struct digest_line *aa = (struct digest_line *) a;
        struct digest_line *bb = (struct digest_line *) b;

        int64_t ret = aa->first - bb->first;
        if (!ret) {
                ret = aa->second - bb->second;
        }
        return (ret == 0) ? 0 : (ret > 0) ? 1 : -1;
}

这看起来……不对。我一直认为一定有更好的方法。

Answer 1

您的代码有问题，因为您正在对未签名的数据进行签名比较。使用以下替代方法之一:

更正统

这明显更快。

int compare_digests(const void *a, const void *b)
{
        const struct digest_line *aa = (const struct digest_line *) a;
        const struct digest_line *bb = (const struct digest_line *) b;

        if (aa->first > bb->first)
            return +1;
        else if (aa->first < bb->first)
            return -1;
        else if (aa->second > bb->second)
            return +1;
        else if (aa->second < bb->second)
            return -1;
        else
            return 0;
}

不太正统

这明显较慢；不要使用它。

int compare_digests(const void *a, const void *b)
{
        struct digest_line aa = *(struct digest_line *) a;
        struct digest_line bb = *(struct digest_line *) b;

        if (aa.first > bb.first)
            return +1;
        else if (aa.first < bb.first)
            return -1;
        else if (aa.second > bb.second)
            return +1;
        else if (aa.second < bb.second)
            return -1;
        else
            return 0;
}

时机

经过一些测量，很明显‘不太正统’的方法也比较慢。超过 20 次运行(每次运行 100,000,000 次迭代，每次迭代中比较不同的一对值)，我得到了平均时间和标准偏差(以秒为单位):

            Mean        Standard Deviation
Value       0.732914    0.005000
Pointer     0.655853    0.003895
Null        0.353649    0.003448

值和指针版本之间的差异是显着的(0.077s 是标准偏差的许多倍)，指针版本更快。所以使用传统的基于指针的比较器版本。 “Null”时间使用比较器函数，该函数只返回 0，根本不进行任何比较。

代表性输出行:

Value:   0.730634 (less =  51517909, more =  48482090, equl =         1)
Pointer: 0.684107 (less =  51517909, more =  48482090, equl =         1)
Null:    0.351807 (less =         0, more =         0, equl = 100000000)

测试代码

两个比较器被重命名为 compare_digests_val() 用于比较值，而 compare_digests_ptr() 用于比较指针。 Clock 类型和 clk_* 函数是在我测试的平台上使用 gettimeofday() 的高分辨率计时器包。显然，在增量循环和累积统计信息中存在相当大的开销，但这仅意味着比较器中的差异更为显着。

static int compare_digests_nul(const void *a, const void *b)
{
    return 0;
}

static void time_comparisons(const char *tag, int (*compare)(const void *, const void *))
{
    struct digest_line a = { 0, 0 };
    struct digest_line b = { 0, 0 };
    int less = 0;
    int more = 0;
    int equl = 0;
    Clock clk;
    char buffer[32];
    clk_init(&clk);
    clk_start(&clk);
    for (int i = 0; i < 100000000; i++)
    {
        int j = (*compare)(&a, &b);
        if (j < 0)
            less++;
        else if (j > 0)
            more++;
        else
            equl++;
        a.first  += 1234567890123ULL;
        a.second += 2345678901234ULL;
        b.first  += 7654321098765ULL;
        b.second += 8765432109876ULL;
    }
    clk_stop(&clk);
    printf("%-8s %s (less = %9d, more = %9d, equl = %9d)\n", tag,
           clk_elapsed_us(&clk, buffer, sizeof(buffer)),
           less, more, equl);
}

int main(void)
{
    for (int i = 0; i < 20; i++)
    {
        time_comparisons("Value:",   compare_digests_val);
        time_comparisons("Pointer:", compare_digests_ptr);
        time_comparisons("Null:",    compare_digests_nul);
    }
    return 0;
}