Большой массив из 26-битных целых чисел без знака - PullRequest
0 голосов
/ 10 января 2012

Мне нужно работать с большим массивом 26-битных переменных в оперативной памяти. Использование 32-битных int s слишком дорого. Доступ должен быть максимально быстрым (особенно операция чтения).

Я пришел к следующей схеме: каждое 26-битное значение разделяется на три 8-битных значения и одно 2-битное значение.

#define N 500000000
uint8 arr1[N], arr2[N], arr3[N];
uint8 arr4[N / 4];

int read_value(int index)
{
  int a1 = arr1[index];                                   // bits 0..7
  int a2 = arr2[index];                                   // bits 8..15
  int a3 = arr3[index];                                   // bits 16..23
  int a4 = (arr4[index / 4] >> (2 * (index % 4))) & 3;    // bits 24..25
  return a1 | (a2 << 8) | (a3 << 16) | (a4 << 24);
}

Есть ли лучшая техника для этого? Или, может быть, есть хороший способ работы с 27/28/29/30-битными целыми числами?

Ответы [ 2 ]

0 голосов
/ 01 августа 2013

Загрузка памяти стоит намного больше, чем простые арифметические инструкции в CPU, поэтому вы не должны использовать массивы uint8, как это. Читать каждый элемент будет стоить вам много нагрузки. По крайней мере, используйте массив uint16, так как на один груз меньше

uint16 arr1[N];     // byte 0-15
uint8  arr2[N];     // byte 16-23
uint8  arr3[N / 4]; // byte 25-26

Но это все еще медленно. Быстрое решение - прочитать все 13 uint32 (или uint64, если вы используете 64-битную машину) одновременно в цикле, а затем извлечь их в 16 26-битную int с, Есть много способов сохранить эти 26-битные int с в 13 unint32 с. Например, хранить каждый 26-битный int s непрерывно.

A 0 A 1 ... A 15

Или сохраняя первые 32 байта для бита 16-15 элементов, следующие 16 байтов для бита каждого элемента 16-23, последние байты будут использоваться для бита 24-25. Карта памяти будет такой

B00: A₀₀[00..07]
B01: A₀₀[08..15]
B02: A₀₁[00..07]
B03: A₀₁[08..15]
...
B30: A₁₅[00..07]
B31: A₁₅[08..15]
B32: A₀₀[16..23]
B33: A₀₁[16..23]
...
B47: A₁₅[16..23]
B48: A₀₀[24..25]A₀₁[24..25]A₀₂[24..25]A₀₃[24..25]
B49: A₀₄[24..25]A₀₅[24..25]A₀₆[24..25]A₀₇[24..25]
B50: A₀₈[24..25]A₀₉[24..25]A₁₀[24..25]A₁₁[24..25]
B51: A₁₂[24..25]A₁₃[24..25]A₁₄[24..25]A₁₅[24..25]

Это обычно используется в графических форматах с нечетным числом битов на канал . Например, для 10 бит на формат канала каждый пиксель будет сохранен в 5 байтах, первые четыре сохранят старшие 8 бит каждого пикселя, а младшие 2 бита каждого пикселя будут упакованы в оставшийся байт

Вам следует протестировать и выбрать самый быстрый в вашем случае.

0 голосов
/ 10 января 2012

Когда вы говорите, что «слишком дорого» использовать 32-битные целочисленные значения, вы имеете в виду пространство?

Предполагая, что вы это делаете, я не совсем уверен, как вам там помочь.Тем не менее, с точки зрения скорости чтения, массив в C / C ++ предоставляет вам постоянный доступ к элементам массива в постоянном времени (это предполагает, что память уже находится в кеше ЦП; если это не так, это займетбольше).Следовательно, считывающий элемент 0 занимает столько же времени, сколько считывающий элемент 10000;код, который у вас есть, может сделать это медленнее, но я не могу сказать это наверняка.

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...