C语言中大型稀疏阵列的压缩或大小优化

Question

/* The following codes are compiled into library(test.a) */
typedef struct {
    short x[5];
} weight_t;

typedef struct {
    weight_t wgt;
    char *ptr;
} tbl_t;

/* huge static array and 70% of entries are empty/zero */
static tbl_t tbl[] ={
{ { 0x0102, 0x0102, 0x0102, 0x0102, 0x0102, }, 0 }, /* 0000 */
{ { 0x0103, 0x0103, 0x0103, 0x0103, 0x0103, }, 0 }, /* 0001 */
{ { 0x0104, 0x0104, 0x0104, 0x0104, 0x0104, }, 0 }, /* 0002 */
{ { 0x0105, 0x0105, 0x0105, 0x0105, 0x0105, }, 0 }, /* 0003 */

{ { 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, }, 0 }, /* 3134c */
{ { 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, }, 0 }, /* 3134d */
......
......
.....

}; /* more than one million entries */

由于array1包含100多万个条目（即使其中70%是空/零条目），库文件（test.a）的大小相当大。

我知道使用哈希表只包含非空条目可以减少array1的大小，但是有没有办法在不更改array1的情况下压缩或优化库文件（test.a）的大小？

在structweight\u t中，在其他库中有很多地方可以访问x的值，要更改当前的静态数组tbl实现可能需要付出巨大的努力。

    /* tbl_t obj ==> tbl_t_obj */
    val = tbl_t_obj.wgt.x[1];

Answer 1

TL： DR：以zstd/lz4/gzip格式存储非零条目加上零的基本游程长度编码，并从中初始化一个零数组。

正如你在这里提到的，以及在C语言中如何对大型静态稀疏数组进行压缩或大小优化（基本上是这个问题的重复，你忘记了链接这个现有的问题），你的主要目标似乎是减少可执行文件的大小，而不是在加载代码后减少RAM的使用。（如果没有ABI的更改，后者是不可能的），意味着重新编译所有接触这个数组的代码。这当然是你应该考虑的，例如，在你的另一个问题上使用LundIn的答案：如果“代码> char *比 短 >，请减少数组中的填充。

减少这种情况的唯一选择是不使用非零值静态初始化该数组。编译器无法为您优化此选项。（或者至少，我不知道；我猜在理论上，一个嵌入式实现必须将非零数据初始值设定项从闪存复制到RAM，无论如何都可以使用lz4或zstd.IDK压缩数据，如果任何工具链都这样做的话；这将是一个整洁的特性。）

要自己做这件事，零初始化实际数组（静态tbl_ttbl[]；），这样它就会进入BSS，不会占用. a中的空间，并在启动时调用一个初始化函数来循环使用更紧凑的数据表示。可以从文件或静态const数组。

您可以省略最初总是（？）的char*成员零，但带有uint8\u t或无符号短距离\u到下一个\u非零成员。这与运行长度编码类似。如果该成员的零运行时间过长，只需记录所有零权重和新长度。

或者它甚至可以是一个单独的二进制文件，因此在应用程序的生命周期1中更容易避免将初始化器内存分配给它。

可能是在一个使用fopen/fwrite转储文件的程序中，通过这样编译源代码生成文件。即使在构建过程中使用zstd2对初始值设定项数据进行压缩，也可以很容易地进行维护。尽管你总是可以直接将任何二进制文件转储回Cconst char initddata_zstd[]={…} 数组初始值设定项。

我假设char*成员始终为空，否则将其初始化为指向常量字符串更具挑战性。

typedef struct {
    short x[5];
    unsigned short num_zeros;
    // or  uint_least8_t num_zeros;  if you use __attribute__((packed)) for the init stuff
} weight_initializer;

脚注1:
释放init数据：像Linux这样的内核将其init数据放在一个自定义链接器部分中，因此它是连续的，并在引导结束时的某个时刻将该内存区域放在空闲列表中以供重用。在Linux下的用户空间中，您可以通过在仅包含初始值设定项数组的页面上调用munmap来执行类似操作。（使用alignas（4096）static const unsigned char initdata[]={…} 因此它从页面的开头开始。）

脚注2：
您示例中的非零初始值设定项数据看起来非常可压缩。zstd或lz4是快速解压缩的首选，如果你花足够的时间压缩，zstd可以提供良好的压缩比，我认为这不会影响解压缩速度。（你可以限制解压所需的最大内存，但以牺牲压缩效率为代价。尽管我认为这只适用于大于内存大小的输入。）

我认为LZ4速度更快，但可能不会太快。显然还有一种蜥蜴（下一代LZ5）。同样，花费大量时间压缩可以使压缩的大小更小，可能会导致更快的解压缩。

zstd的压缩或解压速度比gzip快一个数量级，IIRC，并在该速度下获得相同或更好的压缩比。（速度和压缩预设范围广泛。）如果不需要格式兼容性，zlib基本上就过时了。

如果你的数据真的是那么规律（递增模式），那么zstd比lz4要好得多。我想不会，但我很好奇，在问题中的示例中显示的模式下，压缩的效果如何。所以我写了一个循环来生成重复数据，没有零间隙成员。

typedef struct {
    short x[5];
} weight_t;

typedef struct {
    weight_t wgt;
   // char *ptr;
//    unsigned ptr;   // leave 8 or 4-byte zeros in each record or not
} tbl_t;

#define SIZE (1<<20)
static tbl_t tbl[SIZE] ={ };

#include <stdio.h>

int main(){
        unsigned short x = 0x0102;
        for(int i=0 ; i<SIZE ; i++){
                tbl[i].wgt = (weight_t){x,x,x,x,x};
                x++;
        }
        fwrite(tbl, sizeof(tbl[0]), SIZE, stdout);
}

所以它在2^16次迭代后环绕；zstd可能看到了这一点，并利用了更长距离的冗余。

$ gcc -O3 foo.c
$ ./a.out > initdata.bin
$ lz4 -k --best --favor-decSpeed initdata.bin initdata.bin.fastdec.lz4
Compressed 10485760 bytes into 9789946 bytes ==> 93.36%
$ lz4 -k --best  initdata.bin 
Compressed 10485760 bytes into 4092881 bytes ==> 39.03%                        
$ gzip -v -k --best  initdata.bin
initdata.bin:    85.4% -- created initdata.bin.gz
$ zstd -v -k -19  initdata.bin 
initdata.bin         :  0.65%   (  10.0 MiB =>   66.7 KiB, initdata.bin.zst)   .00% 
$ xz -v -k --best initdata.bin       # rather slow to decompress, you prob. don't want it
initdata.bin (1/1)
  100 %         27.2 KiB / 10.0 MiB = 0.003                                    
$ ll -S initdata.bin*
-rw-r--r-- 1 peter peter  10M Apr 20 20:28 initdata.bin
-rw-r--r-- 1 peter peter 9.4M Apr 20 20:28 initdata.bin.fastdec.lz4
-rw-r--r-- 1 peter peter 4.0M Apr 20 20:28 initdata.bin.lz4
-rw-r--r-- 1 peter peter 1.5M Apr 20 20:28 initdata.bin.gz
-rw-r--r-- 1 peter peter  67K Apr 20 20:28 initdata.bin.zst
-rw-r--r-- 1 peter peter  28K Apr 20 20:28 initdata.bin.xz

zstd与默认的-3压缩级别仍然得到它的原始大小的1.67%，171 KiB。

xz使用LZMA，就像7-zip一样。压缩慢，但压缩高。解压缩速度还可以（远不如压缩慢），但不如zstd快。

所以LZ4似乎做得不太好；如果你的真实数据表现得像这个简单化的测试，那么即使解压代码稍微大一些，zstd的压缩优势也能自食其果。通过zstd，真实数据的可压缩性可能要小得多，但如果大多数权重仅使用16位中的9位，即使它们在其他方面非常随机，也应该获得一些增益。

Answer 2

因为数组tbl[]包含75%的空/零条目

首先，介绍getter和setter。将索引和值存储在动态分配的数组中。只在你真正需要分配的时候分配。对于其余的，只需返回零。

// stores index and the table
// sorted on indexes, so we can use bsearch
struct maybetbl_s {
   uint32_t index;
   tbl_t tbl;
};

// dynamic memory
static struct maybetbl_s *tblidx = NULL;
static uint32_t tblidxcnt = 0;

// all zeros
const tbl_t zeros = {0};

// check if we have index idx
// if we have, return a pointer to it
tbl_t *_tbl_has(size_t idx) {
   return bsearch(&idx, tblidx, ...);
}

// memmove + realloc to remove an element     
void _tbl_remove(tbl_t *ret) {
    tbl_t *end = tblidx + tblidxcnt;
    if (ret + 1 != end) {
        memmove(ret, ret + 1, end - ret - 1); // or smth like that
    }
    tblidx = realloc(tblidx, tblidxcnt * sizeof(*tblidx));
    tblidxcnt -= 1;
}

int _tbl_allocate(size_t idx) {
   void *pnt = realloc(tblidx, tblidxcnt * sizeof(*tblidx));
   if (!pnt) return -ENOMEM;
   tblidx = pnt;
   tblidx[tblidxcnt].index = idx;
   tblidxcnt += 1;
   qsort(tblidx, ...); // so we can use bsearch
   return 0;
}

// public api --------------------------------

// if idx exists, return the value
// if it doesn't, return zeros
tbl_t tbl_get(size_t idx) {
   tbl_t *ret = _tbl_has(idx);
   return ret ? ret : zeros;
}    
 
// set specific idx to the value
// note - can allocate memory, returns 0 on success
int tbl_set(size_t idx, tbl_t value) {
   tbl_t *ret = _tbl_has(idx);
   // if we are storing zeros, just clear the element
   if (memcpy(value, zeros, sizeof(value)) {
       if (ret) {
          _tbl_remove(ret);
       }
       return 0;
   }
   // allocate the element for index if not exists
   if (!ret) {
       int err = _tbl_allocate(idx);
       if (err) err;
       ret = _tbl_has(idx);
       assert(ret);
   }
   // store the value and return success
   *ret = value;
   return 0;
}

Answer 3

在不改变当前实现的情况下压缩或优化二进制文件大小的任何方法

要减小可执行文件的大小，请遵循@user3386109的想法：通过外部文件加载表。虽然可执行文件更小，但可执行文件加上外部文件的总大小并没有减少。

代码可以压缩外部文件，然后在可执行文件运行的早期将其作为tbl[]赋值的一部分进行解压缩。根据压缩时间的不同，这可能会使外部文件缩小10倍。