Эффективная маска массива на языке C

Question

У меня есть два трехмерных массива BOOL, и я хочу замаскировать их между собой.Я имею в виду создать третий массив: third[i][j][k] = first[i][j][k] && second[i][j][k], для каждого i, j, k.

1. Я использую язык c (может быть ассемблер)
2. Мне нужно, чтобы операция маскирования была какмаксимально быстро
3. Можно предположить, что первый и второй имеют одинаковый размер.
4. Если это может улучшить производительность, я мог бы переставить данные из массивов в другое расположение данных.

Отредактировано: каждый размер массива равен 100

Спасибо!

Answer 1

Я упоминал об этом в комментарии, но вот некоторый рабочий код (надеюсь. Я не проверял это и не передавал его через компилятор. Это только для идеи). Если у вас есть массив 100x100x100, который вы пытаетесь смоделировать как битовые маски, то вы можете сделать следующее:

// Create two bitmasks
const unsigned int BITS_PER_BYTE = 8;
const unsigned int DIM = 100;
const unsigned int BITS_PER_VALUE = BITS_PER_BYTE * sizeof(unsigned long);
const unsigned long MASK_SIZE = (DIM * DIM * DIM) / BITS_PER_VALUE;
unsigned long bitmask1[MASK_SIZE] = {0};
unsigned long bitmask2[MASK_SIZE] = {0};
unsigned long bitmask_result[MASK_SIZE];

// Set the two bitmasks, this is probably sub-optimal but you
// mention that setting bitmasks isn't supposed to be overly performant

// set bitmask1 (repeat something similar for bitmask2)
for (int i = 0; i < DIM; ++i)
  for (int j = 0; j < DIM; ++j)
    for (int k = 0; k < DIM; ++k) {
      // set bitmask[i][j][k] to 1
      unsigned int offset = DIM*DIM*i + DIM*j + k;
      unsigned int long_offset = offset / BITS_PER_VALUE;
      unsigned int bit_offset  = offset % BITS_PER_VALUE;
      // XXX SET THIS TO WHATEVER VALUE YOU HAVE, 1 FOR true and 0
      // FOR false. I'M SETTING EVERYTHING TO TRUE FOR THE SAKE OF
      // EXAMPLE
      bitmask1[long_offset] = 1 << bit_offset;
    }

// Now to actually compare:
for (int i = 0; i < MASK_SIZE; ++i) {
  bitmask_result[i] = bitmask1[i] & bitmask2[i];

// and that's it. bitmask_result will now have your answers. decompose
// the bitmask by doing the reverse of the above set loop

Answer 2

Знаете, поможет размещение данных в памяти, чтобы все вычисления могли быть выполнены в одном цикле (очень оптимизирован, SSE и т. Д.).ОДНАКО, учтите, что вы получаете доступ к большому количеству памяти, выполняя очень, очень быструю операцию, поэтому оптимизация не будет значительной.И, если вы решите переставить память, процесс аранжировки будет возможно медленнее, чем сам расчет.

Глядя на эту проблему, мне приходит в голову статья Чарльза Петцольда о книге «Красивый код»».Вы можете сгенерировать кодовые шаблоны для каждого значения каждой строки цикла (100 различных кодовых шаблонов), которые генерируют присваивание только в том случае, если соответствующее значение бита равно 1, а затем переходят к правильной реализации в зависимости от значения бита строкивы обрабатываетеВам нужно будет использовать битовые поля для разных масок.Вы преобразуете 3-вложенный цикл в 2-вложенный цикл с оптимизированным кодом для внутреннего цикла (не так уж и плохо), при этом необходимо с помощью какой-либо другой утилиты (или просто C / C ++) создать код для самогоразные значения внутреннего цикла.Вы должны прочитать главу, чтобы понять это.Действительно аккуратно.

Answer 3

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

Не оптимизируйте преждевременно.