посещение всех бесплатных слотов в битфилде

Question

У меня есть массив uint64, и для всех неустановленных битов (0 с) я делаю некоторые оценки.

Оценки не очень дороги, но очень мало битов не установлено. Профилирование говорит, что я трачу много времени на логику «найти следующий неустановленный бит».

Есть ли более быстрый способ (на Core2duo)?

Мой текущий код может пропустить много старших 1:

for(int y=0; y<height; y++) {
  uint64_t xbits = ~board[y];
  int x = 0;
  while(xbits) {
    if(xbits & 1) {
      ... with x and y
    }
    x++;
    xbits >>= 1;
  }
}

(И любая дискуссия о том, как / если SIMD / CUDA-ise это будет интригующей касательной!)

Answer 1

Восхищение Хакера предлагает бинарный поиск с развернутым циклом. Не красиво, но быстро для редких неустановленных битов, потому что пропускает dwords / bytes / nibbles / etc. с каждым установленным битом.

Если вы можете получить Phenom с SSE4a (не с Core2 Duo, к сожалению), вы можете использовать POPCNT, чтобы написать быструю функцию количества установленных битов. Затем вы можете получить индекс следующего неустановленного бита с помощью:

pop(x & (~x-1))

x & (~x-1) очищает установленные биты выше следующего нулевого бита; тогда вам просто нужно посчитать оставшиеся биты с помощью POPCNT.

Вот рабочий пример с байтом:

    01101111 x
    10010000 ~x
    10001111 ~x-1
    00001111 x & ~x-1
pop(00001111) => 4

Answer 2

Если вы хотите использовать сборку, BSF (Bit Scan Forward) будет операцией для использования. Он находит 1 битов, поэтому вам придется инвертировать свою битовую маску. IIRC, XOR установит нулевой флаг, если результат равен 0, так что вы можете проверить этот флаг, прежде чем пытаться BSF. На x86 BSF работает с 32-битными регистрами, поэтому вам придется разделить ваше значение. (Но тогда я бы сказал, что вы должны использовать 32-разрядные целые числа).

Answer 3

Рассматривали ли вы таблицу, которая позволила бы вам обрабатывать каждый байт одновременно. По сути, с помощью одной операции индексации вы получите список значений «x», которые не заданы в байте (к которым вы добавите 8 * byte-Within-uint64, чтобы получить ваше истинное «x».

Используя один байт для хранения одного числового значения от 1 до 8 бит (мы могли бы упаковать его немного, но тогда преимущество использования хорошего значения будет несколько утрачено), и предполагая, что у нас будет максимум 4 0-значных битов (байтовые значения с большим количеством 0 битов могут быть закодированы с помощью escape-кода, который будет запускать некоторую обычную битовую логику, которая была бы приемлемой тогда, учитывая низкую вероятность таких событий), нам нужна таблица 256 * 4 байта = 1 КБ.

Answer 4

Другие ответы хороши. Вот мой вклад:

Вы можете инвертировать слово, а затем создать цикл поиска младшего разряда 1-бит:

int x = something;

int lsb = x ^ ((x-1) & x);

i.e. if   x = 100100
a = (x - 1) = 100011 // these two steps turn off the lsb
b = (a & x) = 100000
c = (x ^ b) = 000100 // this step detects the lsb
lsb = c

Затем, чтобы сказать, что вы сделали, выполните x ^= lsb и проверьте на ноль.

Если вы хотите превратить этот lsb (который является действительным битом) в число битов, то именно здесь вам может понадобиться таблица поиска или развернутый двоичный поиск.

Это то, что вы хотели?

Answer 5

Один подход - разделить на полубайты, а затем использовать переключатель для выбора битов на полубайте. Используйте шаблоны, чтобы выбранный бит был известен во время компиляции, и чтобы помочь раскрутить код.

template < int i, int x >
struct process_bit {
    inline static void apply ( int y ) { };
};

template < int x >
struct process_bit < 1, x > {
    inline static void apply ( int y ) {
        evaluate ( x, y );
    }
};

template < int x, int n >
inline void process_nibble_bits ( int y ) {
    process_bit < x & 1, n >::apply( y );
    process_bit < ( x >> 1 ) & 1, n + 1 > ::apply( y );
    process_bit < ( x >> 2 ) & 1, n + 2 > ::apply( y );
    process_bit < ( x >> 3 ) & 1, n + 3 > ::apply( y );
}


template < int n >
inline void process_nibble ( uint64_t xbits, int y ) {
    uint64_t nibble = ( xbits >> n ) & 0xf;
    if ( nibble ) {
        switch ( nibble ) {
            case 0:
            process_nibble_bits < 0, n > ( y );
            break;
            case 1:
            process_nibble_bits < 1, n > ( y );
            break;
            case 2:
            process_nibble_bits < 2, n > ( y );
            break;
            case 3:
            process_nibble_bits < 3, n > ( y );
            break;
            case 4:
            process_nibble_bits < 4, n > ( y );
            break;
            case 5:
            process_nibble_bits < 5, n > ( y );
            break;
            case 6:
            process_nibble_bits < 6, n > ( y );
            break;
            case 7:
            process_nibble_bits < 7, n > ( y );
            break;
            case 8:
            process_nibble_bits < 8, n > ( y );
            break;
            case 9:
            process_nibble_bits < 9, n > ( y );
            break;
            case 10:
            process_nibble_bits < 10, n > ( y );
            break;
            case 11:
            process_nibble_bits < 11, n > ( y );
            break;
            case 12:
            process_nibble_bits < 12, n > ( y );
            break;
            case 13:
            process_nibble_bits < 13, n > ( y );
            break;
            case 14:
            process_nibble_bits < 14, n > ( y );
            break;
            case 15:
            process_nibble_bits < 15, n > ( y );
            break;
        }
    }
}

template < int i, int n >
struct bit_tree {
    inline static void apply ( uint64_t xbits, int y ) {
        // each call to here represents scan of bits in [ n, n + 2i )
        bit_tree < i >> 1, n > ::apply(xbits, y);
        bit_tree < i >> 1, n + i > ::apply(xbits, y);
    };
};


template < int i, int n >
struct bit_tree_with_guard {
    inline static void apply ( uint64_t xbits, int y ) {
        // each call to here represents scan of bits in [ n, n + 2i )
        // so this branch to execute if any in [ n, n + i ) are set

        if ( xbits & ( ( ( ( ( uint64_t ) 1LL ) << i ) - 1 ) << n ) )
            bit_tree < i >> 1, n > ::apply(xbits, y);

        if ( xbits & ( ( ( ( ( uint64_t ) 1LL ) << i ) - 1 ) << ( n + i) ) )
            bit_tree < i >> 1, n + i > ::apply(xbits, y);
    };
};

// put guards on 8 and 16 bit blocks ( for some reason using inheritance is slower ) 
template < int n >
struct bit_tree < 8, n > {
    inline static void apply ( uint64_t xbits, int y ) {
        bit_tree_with_guard < 8, n > ::apply ( xbits, y );
    }
};
template < int n >
struct bit_tree < 16, n > {
    inline static void apply ( uint64_t xbits, int y ) {
        bit_tree_with_guard < 16, n > ::apply ( xbits, y );
    }
};


template < int n >
struct bit_tree < 2, n > {
    inline static void apply ( uint64_t xbits, int y ) {
        process_nibble < n > ( xbits, y );
    }
};


void template_nibbles(int height) {
    for (int y = 0; y < height; y++) {
        uint64_t xbits = ~board[y];
        bit_tree< 32, 0>::apply ( xbits, y );
    }
}

Запуск не такой быстрый, как у версии ffs, но на ощупь лучше, чем у других портативных, и, похоже, соответствует им в результатах:

$ bin\bit_twiddle_micro_opt.exe                                               
testing will_while()... 3375000 usecs (check 1539404233,1539597930)           
testing will_ffs()... 2890625 usecs (check 675191567,1001386403)              
testing alphaneo_unrolled_8()... 3296875 usecs (check 1539404233,1539597930)  
testing template_nibbles()... 3046875 usecs (check 1539404233,1539597930)     

Использование дерева полностью не дает никакой выгоды; не использовать переключатель для клев медленнее. Кто-нибудь знает способ не писать 16 дел вручную, используя только C ++?

Answer 6

Я могу подумать о нескольких точках оптимизации, таких как разматывание петли, в которых вы можете попробовать что-то вроде

for(int y=0; y < height; y++) {

    uint64_t xbits = ~board[y];
    int x = 0;

    while(xbits) {
        if(xbits & (1 << 0)) {
          ... with x and y
        }
        if(xbits & (1 << 1)) {
          ... with x and y
        }
        if(xbits & (1 << 2)) {
          ... with x and y
        }
        if(xbits & (1 << 3)) {
          ... with x and y
        }
        if(xbits & (1 << 4)) {
          ... with x and y
        }
        if(xbits & (1 << 5)) {
          ... with x and y
        }
        if(xbits & (1 << 6)) {
          ... with x and y
        }
        if(xbits & (1 << 7)) {
          ... with x and y
        }
        x+=8;
        xbits >>= 8;
    }
}

Это удалит 7 проверок цикла, 7 сложений, 7 сдвигов для 8 вычислений ...

Другой способ, которым я могу придумать, это просто игнорировать последовательные 1, если они установлены, например,

while (xbits) {

    if (xbits & 0xF) {

          // Process for the four bits !!!
    }

    xbits >>= 4;
} 

Предупреждение: Если биты разбросаны слишком сильно, то вышеописанный метод может замедлить работу: - (

Answer 7

Если у вас очень мало неустановленных битов, тогда вообще не используйте битовое поле, используйте разреженное представление. Под этим я подразумеваю сохранить массив целых чисел, содержащий индекс каждого неустановленного бита. Итерация по неустановленным битам - это просто итерация по массиву. Установка и очистка битов усложняется, но если поиск неустановленного бита является вашей самой дорогой операцией, использование разреженного представления, вероятно, будет выигрышным.

Answer 8

Указывает ли ваше профилирование, что вы в основном проводите время во внутреннем цикле while, или вы проводите большую часть времени, выполняя вычисление ~ board [y] и затем увеличивая y сразу?

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

Какое распределение битов установлено в вашем растровом изображении?

Answer 9

Вот быстрый микро-тест; пожалуйста, запустите его, если вы можете получить статистику для вашей системы, и, пожалуйста, добавьте свои собственные алгоритмы!

Командная строка:

g++ -o bit_twiddle_mirco_opt bit_twiddle_mirco_opt.cpp -O9 -fomit-frame-pointer -DNDEBUG -march=native

И код:

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <stdint.h>

static unsigned long get_usecs() {
    struct timeval tv;
    gettimeofday(&tv,NULL);
    return tv.tv_sec*1000000+tv.tv_usec;
}

enum { MAX_HEIGHT = 64 };
uint64_t board[MAX_HEIGHT];
int xsum, ysum;

void evaluate(int x,int y) {
    xsum += x;
    ysum += y;
}

void alphaneo_unrolled_8(int height) {
    for(int y=0; y < height; y++) {
        uint64_t xbits = ~board[y];
        int x = 0;      
        while(xbits) {
            if(xbits & (1 << 0))
                evaluate(x,y);
            if(xbits & (1 << 1))
                evaluate(x+1,y);
            if(xbits & (1 << 2))
                evaluate(x+2,y);
            if(xbits & (1 << 3))
                evaluate(x+3,y);
            if(xbits & (1 << 4))
                evaluate(x+4,y);
            if(xbits & (1 << 5))
                evaluate(x+5,y);
            if(xbits & (1 << 6))
                evaluate(x+6,y);
            if(xbits & (1 << 7))
                evaluate(x+7,y);
            x+=8;
            xbits >>= 8;
        }
    }
}

void will_while(int height) {
    for(int y=0; y<height; y++) {
        uint64_t xbits = ~board[y];
        int x = 0;
        while(xbits) {
            if(xbits & 1)
                evaluate(x,y);
            xbits >>= 1;
            x++;
        }
    }
}

void will_ffs(int height) {
    for(int y=0; y<height; y++) {
        uint64_t xbits = ~board[y];
        int x = __builtin_ffsl(xbits);
        while(x) {
            evaluate(x-1,y);
            xbits >>= x;
            xbits <<= x;
            x = __builtin_ffsl(xbits);
        }
    }
}

void rnd_board(int dim) {
    for(int y=0; y<dim; y++) {
        board[y] = ~(((uint64_t)1 << dim)-1);
        for(int x=0; x<dim; x++)
            if(random() & 1)
                board[y] |= (uint64_t)1 << x;
    }
}

void test(const char* name,void(*func)(int)) {
    srandom(0);
    printf("testing %s... ",name);
    xsum = ysum = 0;
    const unsigned long start = get_usecs();
    for(int i=0; i<100000; i++) {
        const int dim = (random() % MAX_HEIGHT) + 1;
        rnd_board(dim);
        func(dim);
    }
    const unsigned long stop = get_usecs();
    printf("%lu usecs (check %d,%d)\n",stop-start,xsum,ysum);
}

int main() {
    test("will_while()",will_while);
    test("will_ffs()",will_ffs);
    test("alphaneo_unrolled_8()",alphaneo_unrolled_8);
    return 0;
}

Answer 10

Я бы предложил использовать какую-то таблицу поиска (на байт или короткую, в зависимости от доступных ресурсов), которая бы указала, какие биты очищаются при определенном значении.