битовая нарезка: поиск минимального значения - PullRequest
Новая
       84

битовая нарезка: поиск минимального значения

1 голос
/ 28 мая 2020

Краткая версия

Мне нужно найти минимальное значение 64 uint8_t переменных, закодированных как битовые срезы.

т.е. каждый бит переменных кодируется в восемь отдельных uint64_t: 

//Normal layout:
uint8_t values[64]; // This is what you normally use. 
                    // Finding minimum would be a simple 
                    // matter of a for loop

/***********************/

// BITSLICE layout:
uint64_t slices[8]; // This is what I have, due to performance 
                    // reasons in other parts of the code (not shown here)

slice[0]; //LSB: Least signignificant bit (for all 64 values)
slice[7]; //MSB: Most significant bit (for all 64 values)

Теперь, как мне узнать их минимальное значение? (меня не волнует его позиция, а только его значение)

Еще контекст:

На самом деле у меня есть гораздо более длинный массив (чем 64) значений внутри алгоритма, который уже использует битовое нарезание по соображениям производительности.

Итак, то, что у меня есть, на самом деле больше похоже (вопрос выше было упрощено): 

uint64_t slices[8][100];

Итак, что мне действительно нужно, так это минимальное значение из всех 100 * 64 значений. Но я полагаю, что это можно сделать в обычном режиме для l oop, применив ответ на упрощенный вопрос выше.

EDIT: очевидно, мой вопрос не был таким ясным, как я думал, поэтому он обновлен

Ответы [ 3 ]

4 голосов
/ 28 мая 2020

Я могу придумать как минимум два способа сделать это. Самый простой - это просто перебрать его: восстановить каждое из 64 целых чисел по одному с помощью соответствующей поразрядной арифметики c и отслеживать минимальный результат. Что-то вроде этих строк: 

uint8_t min = 0xff;

// iterate over the collection of values
for (uint64_t which = 1; which; which <<= 1) {
    // reconstitute one value in 'test'
    uint8_t test = 0;

    for (int bit = 0; bit < 8; bit++) {
        // verify this decoding -- your bit order may be different:
        test += (!!(slices[bit] & which)) << bit;
    }

    // track the minimum
    if (test < min) {
        min = test;
    }
}

С другой стороны, также должно быть возможно сделать это быстрее, сканируя всего один раз через slices и напрямую накапливая минимум. У меня нет времени проверять это, но он должен передать общую идею: 

uint8_t min = 0xff;
uint64_t mask = ~(uint64_t)0;  // a mask of candidate positions; all bits initially set

for (int i = 7; i >= 0; i--) {  // assumes slice 7 is most significant
    // which of the remaining candidates have this bit set:
    uint64_t bits_set = slice[i] & mask;

    // If at least one of the remaining candidates does not have this bit set
    if (bits_set != mask) {
        min ^= (1 << i);   // turn off this bit in the result
        mask ^= bits_set;  // remove the candidates that do have this bit set
    }
}

Последнее похоже на сортировку по основанию.

1 голос
/ 29 мая 2020

Вот простые и эффективные функции, которые вычисляют минимальные и максимальные значения набора из 64 байтовых значений, закодированных как 8 uint64_t пакетов, каждая из которых хранит 1 бит каждого из 64 значений: 

#include <stdint.h>

uint8_t maxslice(const uint64_t s[8]) {
    uint8_t max = 0, bit = 0x80;
    uint64_t mask = ~0ULL;
    for (int i = 8; i-- > 0; bit >>= 1) {
        uint64_t x = s[i] & mask;
        if (x) {
            max |= bit;
            mask &= x;
        }
    }
    return max;
}

uint8_t minslice(const uint64_t s[8]) {
    uint8_t min = 0, bit = 0x80;
    uint64_t mask = ~0ULL;
    for (int i = 8; i-- > 0; bit >>= 1) {
        uint64_t x = ~s[i] & mask;
        if (x) {
            min |= bit;
            mask &= x;
        }
    }
    return ~min;
}

Как можно проверить на Godbolt's Compiler Explorer , clang генерирует автономный код для обеих функций.

Для вашей расширенной цели вычисления минимума из большего набора значений, организованных таким образом, uint64_t slices[8][100], вы можете просто выполнить итерацию этого кода в массиве и постепенно вычислить минимум. Возможно, стоит проверить на каждом шаге этого l oop, был ли уже найден абсолютный минимум 0. Сложность состоит в том, как организован массив:

uint64_t slices[8][100] определяет массив из 8 массивов по 100 uint64_t. Другими словами, макет в памяти состоит из 6400 младших битов, затем 6400 битов порядка 2, ..., наконец, 6400 битов веса 128. 

uint8_t minarray(const uint64_t s[8][100]) {
    uint8_t all_max = 0;
    for (int j = 0; j < 100; j++) {
        uint8_t max = 0, bit = 0x80;
        uint64_t mask = ~0ULL;
        for (int i = 8; i-- > 0; bit >>= 1) {
            uint64_t x = ~s[i][j] & mask;
            if (x) {
                max |= bit;
                mask &= x;
            }
        }
        if (all_max < max) {
            all_max = max;
            if (all_max == 255)
                break;
        }
    }
    return ~all_max;
}

Чтобы векторизовать этот код, мы можем транспонировать циклы: вычисление с x и mask в виде массивов 100 uint64_t даст тот же результат, но позволит компилятору векторизовать некоторые из внутренних циклов: 

uint8_t minarray1(const uint64_t s[8][100]) {
    uint8_t max = 0, bit = 0x80;
    uint64_t mask[100] = {
        ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL,
        ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL,
        ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL,
        ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL,
        ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL,
        ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL,
        ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL,
        ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL,
        ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL,
        ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL, ~0ULL,
    };
    for (int i = 8; i-- > 0; bit >>= 1) {
        uint64_t x[100];
        uint64_t xall = 0;
        for (int j = 0; j < 100; j++) {
            x[j] = ~s[i][j] & mask[j];
            xall |= x[j];
        }
        if (xall) {
            max |= bit;
            for (int j = 0; j < 100; j++) {
                mask[j] &= x[j];
            }
        }
    }
    return ~max;
}

Снова clang генерирует развернутый векторизованный код . Бенчмаркинг покажет, дает ли этот подход лучшую производительность, чем предыдущий.

0 голосов
/ 28 мая 2020

Используйте объединение: 

#include <stdio.h>
#include <inttypes.h>

int main()
  {
  union
    {
    uint64_t slices[8];
    uint8_t  bits[64];
    } a_union;

  int     i;
  uint8_t min;

  for(i = 0 ; i < sizeof(a_union.slices)/sizeof(a_union.slices[0]) ; ++i)
    {
    a_union.slices[i] = (i+1) * 0x1122334455667788;
    printf("a_union.slices[%d] = 0x%"PRIX64"\n", i, a_union.slices[i]);
    }

  for(i = 0, min = 255 ; i < sizeof(a_union.bits) ; ++i)
    if(a_union.bits[i] < min)
      min = a_union.bits[i];

  printf("min = %u (0x%X)\n", min, min);
  }

здесь тест onlinegdb

EDIT

Еще лучше - используйте устройство Даффа . 

#include <stdio.h>
#include <inttypes.h>
#include <limits.h>
#include <stdlib.h>

uint8_t min_in_mem_block(uint8_t *p, size_t len)
  {
  /* Find the minimum byte value in the block of memory of length len pointed to by p */

  size_t  n   = (len + 7) / 8;
  uint8_t min = UINT8_MAX;

  switch (len % 8) 
    {
    case 0: do { min = *p < min ? *p : min; p++;
    case 7:      min = *p < min ? *p : min; p++;
    case 6:      min = *p < min ? *p : min; p++;
    case 5:      min = *p < min ? *p : min; p++;
    case 4:      min = *p < min ? *p : min; p++;
    case 3:      min = *p < min ? *p : min; p++;
    case 2:      min = *p < min ? *p : min; p++;
    case 1:      min = *p < min ? *p : min; p++;
               } while (--n > 0);
    }

  return min;
  }

int main()
  {
  uint64_t block[8];

  for(size_t i = 0 ; i < sizeof(block)/sizeof(block[0]) ; ++i)
    {
    block[i] = ((i+1) * 0x1122334455667788u) | 0x0101010101010101;
    printf("block[%zu] = 0x%"PRIX64"\n", i, block[i]);
    }

  uint8_t min = min_in_mem_block((uint8_t *)block, sizeof(block));

  printf("min = %" PRIX8 "\n", min);
  }

онлайн-тест gdb здесь

...