128-битное сравнение в AIX (64 бита) для сортировки хеш-значений

Question

Мне нужно отсортировать массив структур, подобных этой, в AIX (64 бита) с помощью компилятора xlC_r:

struct digest_line {
    uint64_t first;
    uint64_t second;
};

Прямо сейчас я делаю длинный путь (сравниваю первый элемент, и если они равны, сравнивают второй элемент.) Есть ли более быстрый способ сравнить эти значения?

Редактировать: Я забыл упомянуть, что я использую функцию qsort() в AIX. Согласно справочной странице 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,077 с - много раз стандартное отклонение), а версия указателя быстрее.Так что используйте обычную основанную на указателе версию компаратора.«Нулевое» время использует функцию сравнения, которая просто возвращает 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;
}

Answer 2

Вероятно, лучший выбор на любой платформе - просто использовать memcmp.Это должно быть высоко оптимизировано (и встроено) на любой достойной архитектуре.Изучение ассемблера должно сказать вам, выполняет ли компилятор некоторую умную оптимизацию.И тогда бенчмаркинг мог бы сказать вам, какая из ваших версий лучше, так как, например, проблемы с выравниванием могут также играть роль и зависеть от типа ваших данных.

У меня нет вашей архитектуры под рукой, поэтому ябыстро проверил на моем старом i686 с gcc.Ассемблер следующей функции

int compare(struct digest* a, struct digest* b) {
  return memcmp(a, b, sizeof *a);
}

выглядит прекрасно оптимизированным.

Редактировать: Джонатан прав в своем замечании, что это не обязательно дает числовойупорядочение 128-битного шаблона.Но до тех пор, пока вы заинтересованы только в последовательном заказе, чтобы внести порядок :) в ваш дайджест, это должно работать нормально на всех платформах.Платформы AFAIR AIX с прямым порядком байтов, поэтому он должен особенно хорошо работать там.