c - 26 位无符号整数大数组

Question

我需要使用 RAM 中的大量 26 位变量。使用 32 位 int 的成本太高了。访问应该尽可能快(尤其是读操作)。

我采用了以下方案:每个 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 位整数的好方法？

Answer 1

内存负载的成本远高于 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 位ints。有很多方法可以将这些 26 位 int 存储在 13 个 unint32 中。例如，连续存储每个 26 位 int。

A₀ A₁... A₁₅

或者存储前 32 个字节用于 16 个元素的位 0-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]

这通常用于每个 channel 具有奇数位数的图像格式。例如，对于每 channel 10 位格式，则每个像素将存储在 5 个字节中，前 4 位存储每个像素的高 8 位，每个像素的低 2 位将打包到剩余的字节中

您应该测试并选择适合您情况的最快的。