Эффективное сравнение малых целых векторов

Question

У меня есть небольшие векторы. Каждый из них состоит из 10 целых чисел, которые находятся между 0 и 15. Это означает, что каждый элемент в векторе может быть записан с использованием 4 бит. Поэтому я могу конкатенировать элементы вектора и хранить весь вектор в одном long (в C, C++, java ...)

Вектор v1 доминирует над вектором v2, если для каждого i в 0, ..., 9, v1 [i]> = v2 [i]

Я хочу написать метод compare(long v1, long v2), который будет возвращать 0, если не векторы доминируют над другим, 1, если первый доминирует, а -1, если второй доминирует.

Есть ли эффективный способ реализовать сравнение, отличное от того, чтобы получить каждый компонент i и выполнить в 10 раз обычное целочисленное сравнение?

EDIT

если v1 точно так же, как и v2 возвращение 1 или -1 оба прекрасно

Answer 1

Это можно сделать с помощью манипуляции бит. Пронумеруйте свои значения так, чтобы каждый из них занимал 5 бит, с 4 битами для значения и пустым 0 в наиболее значимой позиции как своего рода бит расстояния.

Размещение промежуточного бита между каждым значением прекращает перенос/перенос от распространения между смежными значениями и означает, что вы можете выполнять определенные арифметические операции SIMD в векторе, просто используя регулярное целочисленное сложение или вычитание. Мы можем использовать вычитание для векторного сравнения.

Для выполнения теста вы можете установить все биты расстояния в 1 в одном из векторов, а затем вычесть второй. Если значение в 4 битах ниже бит интервала больше во втором, то оно будет переносить бит из бита интервала и установить его в ноль в результате, если не тогда, то оно останется одним (первое значение больше чем или равна второй). Если первый вектор доминирует над вторым, тогда все биты расстояния будут одно после вычитания.

Простая демонстрация с использованием Интс:

#define SPACING_BITS ((1<<4)|(1<<9)|(1<<14)|(1<<19)) 
int createVector(int v0, int v1, int v2, int v3) 
{ 
    return v0 | (v1 << 5) | (v2 << 10) | (v3 << 15); 
} 

int vectorDominates(int vectorA, int vectorB) 
{ 
    // returns 1 if vectorA dominates vectorB: 
    return (((vectorA | SPACING_BITS) - vectorB) & SPACING_BITS) == SPACING_BITS; 
} 

int compare(int vectorA, int vectorB) 
{ 
    if(vectorDominates(vectorA, vectorB)) 
     return 1; 
    else if(vectorDominates(vectorB, vectorA)) 
     return -1; 
    return 0; 
} 

Вы можете продлить его использовать 64-битные значения, используя 50 бит для хранения 10 значений. Вы также можете подключить вызовы к vectorDominates в функции сравнения.

Demo

Answer 2

Ну, в C вы можете, вероятно, рычаги векторизации, чтобы сделать это. Я не думаю, что напрямую можно сравнивать на 4-битных операндах, поэтому вам придется перекомпоновать (либо на лету, либо просто сохранить ваши данные в более подходящем формате) до 8 бит, прежде чем делать сравнение. Поскольку 10 * 8 = 80, что больше, чем 64, вам понадобятся 128-битные векторные инструкции.

Не уверен, что Java VM поддерживают это еще, но this question suggests that JNI is the answer, т. Е. Вызывают код C из Java.