Каков самый быстрый способ вернуть позиции всех заданных битов в 64-битное целое число?

Ответ 1

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

Судя по вашему образцу кода и предыдущему запросу SO, вы перечисляете все слова с установленными по порядку битами K и извлекаете из них битовые индексы. Это значительно упрощает дело.

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

Что-то в этом роде:

// Walk through all len-bit words with num-bits set in order
void enumerate(size_t num, size_t len) {
    size_t i;
    unsigned int bitpos[64 + 1];

    // Seed with the lowest word plus a sentinel
    for(i = 0; i < num; ++i)
        bitpos[i] = i;
    bitpos[i] = 0;

    // Here goes the main loop
    do {
        // Do something with the resulting data
        process(bitpos, num);

        // Increment the least-significant series of consecutive bits
        for(i = 0; bitpos[i + 1] == bitpos[i] + 1; ++i)
            bitpos[i] = i;
    // Stop on reaching the top
    } while(++bitpos[i] != len);
}

// Test function
void process(const unsigned int *bits, size_t num) {
    do
        printf("%d ", bits[--num]);
    while(num);
    putchar('\n');
}

Не особенно оптимизирован, но вы получаете общую идею.

Ответ 2

Здесь что-то очень простое, что может быть быстрее - невозможно узнать без тестирования. Многое будет зависеть от количества бит, установленного по сравнению с номером unset. Вы можете развернуть это, чтобы полностью удалить ветвление, но с сегодняшними процессорами я не знаю, будет ли это ускоряться вообще.

unsigned char idx[K+1]; // need one extra for overwrite protection
unsigned char *dst=idx;
for (unsigned char i = 0; i < 50; i++)
{
    *dst = i;
    dst += x & 1;
    x >>= 1;
}

P.S. ваш образец вывода в вопросе неверен, см. http://ideone.com/2o032E

Ответ 3

Как минимальная модификация:

int64_t x;            
char idx[K+1];
char *dst=idx;
const int BITS = 8;
for (int i = 0 ; i < 64+BITS; i += BITS) {
  int y = (x & ((1<<BITS)-1));
  char* end = strcat(dst, tab[y]); // tab[y] is a _string_
  for (; dst != end; ++dst)
  {
    *dst += (i - 1); // tab[] is null-terminated so bit positions are 1 to BITS.
  }
  x >>= BITS;
}

Выбор BITS определяет размер таблицы. 8, 13 и 16 являются логическим выбором. Каждая запись представляет собой строку с нулевым завершением и содержит позиции бит с 1 смещением. То есть вкладка [5] равна "\x03\x01". Внутренний цикл фиксирует это смещение.

Чуть более эффективный: замените strcat и внутренний цикл на

char const* ptr = tab[y];
while (*ptr)
{
   *dst++ = *ptr++ + (i-1);
}

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

Одна вещь, которую я рассматриваю, заключается в том, что tab[y] представляет собой массив указателей на строки. Они очень похожи: "\x1" является суффиксом "\x3\x1". Фактически, каждая строка, которая не начинается с "\x8", является суффиксом строки, которая делает. Мне интересно, сколько уникальных строк вам нужно, и в какой степени tab[y] на самом деле требуется. Например. по логике выше, tab[128+x] == tab[x]-1.

[править]

Nevermind, вам определенно требуется 128 вкладок, начиная с "\x8", так как они никогда не являются суффиксом другой строки. Тем не менее, правило tab[128+x] == tab[x]-1 означает, что вы можете сохранить половину записей, но за счет двух дополнительных инструкций: char const* ptr = tab[x & 0x7F] - ((x>>7) & 1). (Настройте tab[] на точку после \x8)

Ответ 4

Использование char не поможет вам увеличить скорость, но на самом деле часто требуется больше ANDing и sign/zero, распространяющихся при вычислении. Только в случае очень больших массивов, которые должны входить в кеш, следует использовать меньшие типы int

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

inline COPY(unsigned char *dst, unsigned char *src, int n)
{
switch(n) { // remember to align dst and src when declaring
case 8:
    *((int64_t*)dst) = *((int64_t*)src);
    break;
case 7:
    *((int32_t*)dst) = *((int32_t*)src);
    *((int16_t*)(dst + 4)) = *((int32_t*)(src + 4));
    dst[6] = src[6];
    break;
case 6:
    *((int32_t*)dst) = *((int32_t*)src);
    *((int16_t*)(dst + 4)) = *((int32_t*)(src + 4));
    break;
case 5:
    *((int32_t*)dst) = *((int32_t*)src);
    dst[4] = src[4];
    break;
case 4:
    *((int32_t*)dst) = *((int32_t*)src);
    break;
case 3:
    *((int16_t*)dst) = *((int16_t*)src);
    dst[2] = src[2];
    break;
case 2:
    *((int16_t*)dst) = *((int16_t*)src);
    break;
case 1:
    dst[0] = src[0];
    break;
case 0:
    break;
}

Кроме того, поскольку tabofs [x] и n [x] часто имеют доступ друг к другу, попробуйте поместить его в память, чтобы убедиться, что они всегда находятся в кеше в то же время

typedef struct TAB_N
{
    int16_t n, tabofs;
} tab_n[256];

src=tab0+tab_n[b0].tabofs; COPY(dst, src, tab_n[b0].n);
src=tab0+tab_n[b1].tabofs; COPY(dst, src, tab_n[b1].n);
src=tab0+tab_n[b2].tabofs; COPY(dst, src, tab_n[b2].n);
src=tab0+tab_n[b3].tabofs; COPY(dst, src, tab_n[b3].n);
src=tab0+tab_n[b4].tabofs; COPY(dst, src, tab_n[b4].n);
src=tab0+tab_n[b5].tabofs; COPY(dst, src, tab_n[b5].n);

И последнее, но не менее важное: gettimeofday не для подсчета производительности. Используйте QueryPerformanceCounter, гораздо точнее

Ответ 5

В вашем коде используется индексная таблица с 1 байтом (256 записей). Вы можете ускорить его в 2 раза, если вы используете таблицу с 2 байтами (65536 записей).

К сожалению, вы, вероятно, не можете продлить это в дальнейшем - для 3-байтного размера таблицы будет 16 МБ, вряд ли вместиться в локальный кеш процессора, и это будет только замедлять работу.

Ответ 6

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

Вот наивный пример битового итератора, который я написал в Smalltalk:

LargePositiveInteger>>bitsDo: aBlock
| mask offset |
1 to: self digitLength do: [:iByte |
    offset := (iByte - 1) << 3.
    mask := (self digitAt: iByte).
    [mask = 0]
        whileFalse:
            [aBlock value: mask lowBit + offset.
            mask := mask bitAnd: mask - 1]]

A LargePositiveInteger - целое число произвольной длины, состоящее из цифр байта. LowBit отвечает на ранжирование младшего разряда и реализуется как таблица поиска с 256 элементами.

В С++ 2011 вы можете легко пройти закрытие, поэтому его нужно легко перевести.

uint64_t x;
unsigned int mask;
void (*process_bit_position)(unsigned int);
unsigned char offset = 0;
unsigned char lowBitTable[16] = {0,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0}; // 0-based, first entry is unused
while( x )
{
    mask = x & 0xFUL;
    while (mask)
    {
        process_bit_position( lowBitTable[mask]+offset );
        mask &= mask - 1;
    }
    offset += 4;
    x >>= 4;
}

Пример демонстрируется с 4-битной таблицей, но вы можете легко расширить его до 13 бит или более, если он подходит в кеш.

Для предсказания ветвлений внутренний цикл можно переписать как for(i=0;i<nbit;i++) с дополнительной таблицей nbit=numBitTable[mask], а затем развернут с помощью переключателя (компилятор мог бы это сделать?), но я даю вам возможность оценить, как он работает в первую очередь..

Ответ 7

Было ли это слишком медленным?
Мало и грубо, но все это в кэше и регистры процессора;

void mybits(uint64_t x, unsigned char *idx)
{
  unsigned char n = 0;
  do {
    if (x & 1) *(idx++) = n;
    n++;
  } while (x >>= 1);          // If x is signed this will never end
  *idx = (unsigned char) 255; // List Terminator
}

Это еще 3 раза быстрее, чтобы развернуть цикл и создать массив из 64 значений true/false (что совсем не так)

void mybits_3_2(uint64_t x, idx_type idx[])
{
#define SET(i) (idx[i] = (x & (1UL<<i)))
  SET( 0);
  SET( 1);
  SET( 2);
  SET( 3);
  ...
  SET(63);
}

Ответ 8

Вот некоторый жесткий код, написанный для 1-байтового (8 бит), но он должен легко, очевидно, расширяться до 64 бит.

int main(void)
{
    int x = 187;

    int ans[8] = {-1,-1,-1,-1,-1,-1,-1,-1};
    int idx = 0;

    while (x)
    {
        switch (x & ~(x-1))
        {
        case 0x01: ans[idx++] = 0; break;
        case 0x02: ans[idx++] = 1; break;
        case 0x04: ans[idx++] = 2; break;
        case 0x08: ans[idx++] = 3; break;
        case 0x10: ans[idx++] = 4; break;
        case 0x20: ans[idx++] = 5; break;
        case 0x40: ans[idx++] = 6; break;
        case 0x80: ans[idx++] = 7; break;
        }

        x &= x-1;
    }

   getchar();
   return 0;
}

Выходной массив должен быть:

ans = {0,1,3,4,5,7,-1,-1};

Ответ 9

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

Я понимаю, что это несколько недель назад, однако, и из любопытства, я помню, как я возвращался в свои дни сборки с CBM64 и Amiga, используя арифметический сдвиг, а затем изучал флаг переноса - если он установил, сдвинутый бит был 1, если он чист, то он равен нулю

например. для арифметического сдвига влево (проверка с бита 64 на бит 0)....

pseudo code (ignore instruction mix etc errors and oversimplification...been a while):

    move #64+1, counter
    loop. ASL 64bitinteger       
    BCS carryset
    decctr. dec counter
    bne loop
    exit

    carryset. 
    //store #counter-1 (i.e. bit position) in datastruct indexed by counter
    jmp decctr

... Надеюсь, у вас есть идея.

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

Если это возможно, я бы предположил, что это довольно быстро.

Ответ 10

Предполагая разреженность в количестве заданных битов,

int count = 0;
unsigned int tmp_bitmap = x;        
while (tmp_bitmap > 0) {
    int next_psn = __builtin_ffs(tmp_bitmap) - 1;
    tmp_bitmap &= (tmp_bitmap-1);
    id[count++] = next_psn;
}