面试题：C语言多维数组存储顺序优化与内存对齐

Question

假设在特定硬件平台下，内存对齐要求每个数据元素的存储地址必须是8字节对齐。现有一个四维数组`int arr[2][3][4][5];`，请描述该数组在内存中的存储顺序，分析因内存对齐可能产生的空洞情况，并提出一种优化存储的方案，使得在保持逻辑上多维数组结构不变的同时，减少内存空洞对空间的浪费。

Answer 1

1. 数组在内存中的存储顺序

在C和C++语言中，多维数组按行优先（row - major order）存储。对于int arr[2][3][4][5];，先变化最右边的维度，即：

1. 先遍历arr[0][0][0]这一“层”内的arr[0][0][0][0]到arr[0][0][0][4]。
2. 然后遍历arr[0][0][1]这一“层”内的arr[0][0][1][0]到arr[0][0][1][4]，依此类推。
3. 当arr[0][0]的所有元素遍历完后，开始遍历arr[0][1]的所有元素，直到arr[1][2][3][4]。

2. 内存对齐产生的空洞情况分析

已知每个数据元素的存储地址必须是8字节对齐，而int类型通常为4字节。

1. 对于单个int元素，由于其本身大小为4字节，小于8字节对齐要求，会在其存储后填充4字节空洞，使得下一个元素地址满足8字节对齐。
2. 以arr[0][0][0]这一“层”为例，该“层”有5个int元素，共占用5 * 4 = 20字节。但由于8字节对齐，实际占用空间为24字节（20字节数据 + 4字节空洞）。
3. 对于arr[0][0]这一“片”，包含4个上述“层”，理论数据大小为4 * 20 = 80字节，但由于每层后的空洞，实际占用空间为4 * 24 = 96字节。
4. 对于arr[0]这一“块”，包含3个上述“片”，理论数据大小为3 * 80 = 240字节，但实际占用空间为3 * 96 = 288字节。
5. 整个数组包含2个上述“块”，理论数据大小为2 * 240 = 480字节，但实际占用空间为2 * 288 = 576字节。

3. 优化存储方案

一种优化方案是使用结构体数组来模拟多维数组，并手动控制内存对齐。

#include <iostream>
#include <cstdint>

// 使用结构体数组模拟多维数组
struct IntBlock {
    int data[5];
} __attribute__((aligned(8)));

struct IntSlice {
    IntBlock blocks[4];
} __attribute__((aligned(8)));

struct IntChunk {
    IntSlice slices[3];
} __attribute__((aligned(8)));

struct IntArray {
    IntChunk chunks[2];
} __attribute__((aligned(8)));

int main() {
    IntArray arr;
    // 访问元素示例：arr.chunks[0].slices[1].blocks[2].data[3] = 10;
    return 0;
}

在这个方案中：

1. 定义IntBlock结构体，包含5个int元素，通过__attribute__((aligned(8)))保证结构体整体8字节对齐。这样每个IntBlock占用5 * 4 = 20字节，加上4字节填充达到24字节，满足8字节对齐。
2. IntSlice结构体包含4个IntBlock，整体占用4 * 24 = 96字节，自然满足8字节对齐。
3. IntChunk结构体包含3个IntSlice，整体占用3 * 96 = 288字节，也满足8字节对齐。
4. IntArray结构体包含2个IntChunk，整体占用2 * 288 = 576字节，同样满足8字节对齐。 通过这种方式，在保持逻辑上多维数组结构不变的同时，减少了不必要的内存空洞对空间的浪费。