c - 在字节数组中存储记录与使用结构数组

Question

我有 2 亿条记录，其中一些具有可变大小的字段(字符串、可变长度数组等)。我需要对它们执行一些过滤器、聚合等(面向分析的查询)。

我只想将它们全部放在内存中(足以装进一个大盒子)，然后对它们进行线性扫描。我可以采用两种方法，我想听听您对哪种方法更好以最大化速度的意见:

1. 使用char* 和int* 等结构数组来处理变长字段
2. 使用大字节数组，像二进制流一样扫描字节数组，然后解析记录

您会推荐哪种方法？

更新:使用 C。

Answer 1

不幸的是，“这取决于您未提供的详细信息”，这虽然是真的，但并不是特别有用。解决此类问题的一般建议是从最简单/最明显的设计开始，然后根据需要对其进行分析和优化。如果它真的很重要，您可以使用您的确切数据和用例对一些设计进行一些非常基本的基准测试，以更准确地了解您应该采取的方向。

总体上看一些特定的设计及其一般优缺点:

一个大缓冲区

 char* pBuffer = malloc(200000000);

• 假设您的数据可以一次全部装入内存。
• 对所有文本(或主要是文本)数据效果更好。
• 对于大数据，它不是我的首选，因为它只是镜像磁盘上的数据。最好只使用硬件/软件文件缓存/预读并直接从驱动器读取数据，或者在需要时映射它。
• 对于线性扫描，这是一种很好的格式，但如果它需要复杂的解析(尤其是当您必须进行多次扫描时)，您会损失一点。
• 假定您可以一个接一个地打包结构，则开销可能最少。

静态结构

 typedef struct {
     char  Data1[32];
     int   Data2[10];
 } myStruct;

 myStruct *pData = malloc(sizeof(myStruct)*200000000);

• 最简单的设计，可能是以内存为代价的最佳速度潜力(无需实际分析)。
• 如果您的可变长度数组的大小范围很广，您将浪费大量内存。由于您有 2 亿条记录，因此您可能没有足够的内存来使用此方法。
• 对于线性扫描，由于内存缓存/预取，这可能是最好的内存结构。

动态结构

 typedef struct {
     char* pData1;
     int*  pData2;
 } myStruct2;

 myStruct2 *pData = malloc(sizeof(myStruct2)*200000000);

• 对于 2 亿条记录，这将需要大量动态内存分配，这很可能会对速度产生重大影响。
• 如果您的动态数组的大小范围很广(请参阅下一点)，则有可能提高内存效率。
• 注意指针大小的开销。在 32 位系统上，此结构需要 8 个字节(忽略填充)来存储指针，对于 2 亿条记录，仅 1.6 GB!如果您的动态数组通常很小(或为空)，您可能会在开销上花费比实际数据更多的内存。
• 对于数据的线性扫描，这种类型的结构可能会表现不佳，因为您以非线性方式访问内存，预取器无法预测。

串流

• 如果您只需要对数据进行一次扫描，那么我会考虑一种流式解决方案，您可以一次从文件中读取一小部分数据。
• 适用于无法放入内存的超大数据集。
• 这里的主要限制是磁盘读取速度和解析的复杂程度。
• 即使您必须对文件缓存进行多次传递，这在速度上也可能与其他方法相当。

其中哪一个是“最佳”实际上取决于您的具体情况……我可以想到每种方法都是首选方法的情况。