如何在C中压缩或优化大型静态稀疏阵列[duplicate]

Question

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

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

/* huge static array and 70% of entries are empty/zero */
static myarray_t array1[] ={
{ { 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 millon entries */

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

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

由于array1已被其他库引用，因此对array1进行改造以使用其他实现可能不是解决我当前情况的方法。

这是对C语言中大型稀疏数组的压缩或大小优化的后续，基本上是在要求同样的事情，即在不改变内存数据结构的情况下保存文件大小。这一个被标记为编译器优化，另一个没有。（编者按：我不认为这会使它们之间的差异足以成为非重复的；除非我们澄清这个问题的区别，否则就结束这个问题。）

Answer 1

一个明显的大小优化是去掉结构填充。您可以在2x5字节数组和指针之间填充，和/或在结构末尾填充。您可能使用2x5 4=14字节或2x5 8=18字节的实际数据。如果4或8字节对齐，两者都不合适。

因此，删除结构：

static short array1 [5*n] = { ... };
static char* ptr [n] = { ... };

这将删除当前低效结构中存在的所有填充。您将为每个项目节省大约2-6个字节，这意味着一百万个项目浪费了大约2-6兆字节的空间。

gccx86_64Linux示例：

#include <stdio.h>

#define n 1000000

int main()
{
    typedef struct {
        short x[5];
    } weight_t;

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

    static myarray_t array1[n];
    printf("%zu\n", sizeof array1);

    static short array2 [5*n];
    static char* ptr [n];
    printf("%zu\n", sizeof array2 + sizeof ptr);

    return 0;
}

输出：

24000000
18000000

更改在这个特定系统上节省了600万字节。如果由于某些向后兼容性原因而被当前结构所困扰，请考虑使用一些包装宏来模拟使用SoW数组时的结构类似的访问。