short short int in c?

Question

我正在尝试充分利用我的内存。我有一个包含4.9999995e13个整数的矩阵，但它们只需要是真或假 - 基本上每个这些整数只需要一位存储空间。

我知道在C中没有单个比特类型（也许有人可以向我解释为什么），我也知道如果存在一个“short short int”，它将是1字节，与char相同。然而，C中的所有逻辑操作都返回整数（以及其他一些函数）。

所以我的问题是：

• 有没有办法使“short short int”存在？
• 如果我使用“char”代替，“int”强制转换会导致性能下降吗？
• 是否还有其他我不知道的方法？

如果相关的话，我正在使用GCC编译C99。

编辑我刚刚在这个维基百科页面上看到有一个_Bool类型，这实际上是标准吗？

- Griffin

---

请问可以解释一下为什么它们都必须转换为 int 类型吗？ - aardvarkk

你可以使用位域（http://codepad.org/HMz2f7OR）。在C语言中，将`char`作为位域底层类型是实现定义的（这就是为什么我没有将其发布为答案的原因，因为我现在不想为无符号整数创建32个位域），但对于GCC而言是有效的。 - Johannes Schaub - litb

这些位分别代表什么？例如，您计划如何访问bit [4264334543]的值，以及您将如何处理它？我之所以问是因为可能有一种更有效的存储数据的方式，这取决于您尚未透露的结构。 - AShelly

你的邻接矩阵是稀疏的吗？ - Jacob

只是好奇，为什么你需要6.5TB的布尔值？我在猜测可能的用例。 - Dani Barca Casafont

Answer 1

_Bool类型在最新版的C语言中已经成为标准，但这仍然不是您想要的，因为_Bool仍然至少占用一个字节（根据定义，char也是如此）。

如果您需要那么多布尔位，您需要将它们打包到位域或位数组中。在C语言中，没有标准的位域数据类型，所以您还需要编写自己的宏或函数来获取特定偏移处的位。我还希望您在64位机器上运行此程序，并且有足够的内存，否则您可能会很快耗尽内存。

- JSBձոգչ

---

谢谢，但这会对性能造成很大的影响吗？是的，目前有32GB的RAM可用。 - Griffin

@Griffin，如果数据大小像你所拥有的一样庞大，那么内存中的数据输入输出成本将超过执行成本。你没有5e13字节的内存，你的计算机上只有约3e10字节的内存，因此，任何你可能采取的使数据集适应内存的措施都将是一个胜利。 - JSBձոգչ

+1 实际上，我正在创建和分析非常大的图形。目标是获得1e7个节点（我现在询问的顺序），但即使是1e6的邻接矩阵也可能占用58GB的RAM。我最终可以将所有这些内容移植到OpenCL并在大学的超级计算机上运行，但仍然存在问题。我有很多事情要考虑。谢谢你让我有所启发！对你的回答加一！ - Griffin

@Griffin，如果你想要的是邻接矩阵，有更高效的数据结构可用，使用它们可能会将内存占用减少数个数量级。如果你正在尝试构建这样的结构，可以尝试提出一个单独的问题询问相关内容。 - JSBձոգչ

Answer 2

您有大约50TB的数据。您想一次性将它们全部放入RAM中吗？为了保留一位信息，使用超过一个比特的RAM是完全疯狂的，即使这样，您的计算机也必须达到地球上最大的超级计算机的大小。忘记位打包的性能。您需要担心完全不同的事情。

- n. m.

Answer 3

你需要的是一个位图（或者维基百科称之为位数组）。

在C语言中，不存在short short int这种类型，这只是一个char类型而已，它是C语言中最小的整数存储类。

使用这种方法可能会有一些性能开销，但不是因为隐式转换为int类型，而是由于操作位图比直接操作数组成员更加棘手。

下面是一个简单的示例：

使用普通的整型矩阵：

int mat[8*8]; // 假设按行主序排列
int is_element_set(int x, int y) { 
  return mat[y*8 + x];
}

使用位图：

unsigned char mat[8]; // assuming CHAR_BIT == 8
int is_element_set(int x, int y) { 
  return mat[y] & (1 << x);
}

- user786653

---

谢谢，我宁愿牺牲空间效率也不想影响性能，所以看起来我已经尽力了？另外，由于我的位域大约有5000000000000000个位，我应该用什么类型来存储它呢？ - Griffin

你可以将它存储在5e13/8个字符或5e13/32个整数中。无论哪种方式，都需要大约5TB的空间 - 因此我肯定会考虑空间效率 - 将数据快速地输入和输出主内存是不可能的。 - AShelly

这是非常多的比特。原则上，您可以将其存储在unsigned char mat[5000000000000000/CHAR_BIT]中，但如果您的数据是稀疏的，最好考虑使用稀疏数据结构。 - user786653

@Griffin 在许多情况下，即使您的代码需要做更多的工作，较小的空间可能会更有效率，因为较小的数据可以适应缓存，而缓存比操作主内存快一个数量级。只有通过针对您特定情况的测量才能确定。 - nos

从其他答案中可以看出，我有很多需要考虑的地方。感谢您的建议。 - Griffin

Answer 4

如果你要表示比特字段，那么你需要大约5.6 TB的存储空间。但是，处理你的问题可能会有更好的方法。

- Patrick Schlüter

Answer 5

也许你可以使用 ANSI C 中可用的位域结构体的明智实现。

像这样的东西：

typedef struct node_t_
{
    char bit0 : 1;
    char bit1 : 1;
    char bit2 : 1;
    char bit3 : 1;
    char bit4 : 1;
    char bit5 : 1;
    char bit6 : 1;
    char bit7 : 1;
} node_t;

然后，您可以编写一些快速函数（可能是宏），以获取和设置此矩阵中的元素。虽然我从未实现过类似的东西。

- Ivan Filgueiras

Answer 6

C99 stdbool.h 允许使用 bool。但是，您的问题在于 4.9999995e13/8 大约会得到 6.2500e+12（$10^9$ 是 Gbyte，$10^12$ 是 Tbyte），因此您需要超过 6 Tbytes 的实际 + 虚拟内存（要有运气）。这表明您正在做其他错误的事情。您需要将问题“缩放”为您可以使用更少内存处理的子问题。

- ShinTakezou

Answer 7

正如其他人建议的那样，你应该使用位域。

此外，如果你只是使用真/假值，并且其中一个值比另一个值少得多，考虑使用隐式编码。你可以使用映射数据结构轻松实现这一点。由于你正在处理图形，如果你的图形非常稀疏，这将节省大量内存。如果你将其与上面的位打包技术相结合，甚至可能将其全部放入RAM中。不过，你必须对索引进行相当聪明的处理。

另一件事情是，如果你不在意处理过程中的性能损失（即如果你更担心存储而不是处理），可以将结构通过块压缩算法运行。有一个针对bzip2的C库，可以在这方面节省90%或更多的空间。缺点是这需要（非常！）长时间。你可能会从像动态马尔可夫压缩（DMC）这样的位压缩器中获得可比较的性能，而且速度要快得多。

- John Doucette

Answer 8

我正在尽可能地挤出我的内存。

如果是这样，那么你不会浪费8位来存储1位数据。你会使用位域。

如果你知道矩阵的内容类型，那么你可以使用其他优化方法。例如，如果你知道大多数矩阵通常设置为零，那么你只需要存储设置为1的元素的x、y对。

如果不是这样，那么4.9999995e13将占用约6 TB的RAM！

- kirsch