是否可以在运行时在 D 中创建一个连续的多维数组？

Question

我想在运行时创建一个矩形多维数组，以便将整个数组存储在一个连续的内存块中。数组在初始创建后无需调整大小。实际上，我想在运行时创建一个静态数组，但我会接受一种满足规定条件的方法，即使该数组在技术上属于不同类型。

更正式地说，我想使用两个 ulongs nr 和 nc，并在运行时创建一个数组 arr，这样 arr[r][c]等同于 *(arr.ptr + r * nc + c)，无论是就其评估的内容还是评估的效率而言。（*(arr.ptr + c * nr + r) 也将是 acceptable，尽管我不认为 D 会使用列优先顺序。）

有没有办法在 D 中做到这一点？

我得到的最接近的是：

import std.stdio, core.memory;

void main() {
    ulong nr = 3, nc = 4;
    auto p = cast(int*)GC.malloc(nr * nc * int.sizeof);
    auto p1 = cast(int[3][4])p[0..12];
}

但是如果我将 cast(int[3][4]) 更改为 cast(int[nr][nc])，编译将失败。

答案比较

为了比较所提供的不同答案，我运行在 10,000,000 x 20 的双精度数组上使用以下函数（根据需要调整索引表达式）。

auto busywork(T)(T p) {
    foreach (r; 0..nr) {
        foreach (c; 0..nc) {
            p[r][c] = r + log(1.0 + c);
        }
    }
    double result = 1.0;
    foreach (t; 0..1) {
        foreach (r; 0..nr) {
            foreach (c; 0..nc) {
                result += log(1.0 + pow(p[r][c], 3));
            }
        }
    }
    return result;
}

baseline 是使用p[r * nc + c]手动索引的一维数组。
baseline_dynamic为二维动态数组
chunks_array是Bearded Beaver的做法
chunks 是 Bearded Beaver 的方法，没有 .array
array2D 是 Jack Applegame 的 (2D) 方法，从 opIndex 中删除了边界检查。

运行时间

table 报告了五次运行的平均运行时间（以毫秒为单位）。

	dmd -O	gdc -O3	gdc -Os	ldc -O3
baseline	13592 +/- 1758	20978 +/- 434	15452 +/- 1178	20778 +/- 1017
baseline_dynamic	13481 +/- 339	20782 +/- 501	13476 +/- 209	20632 +/- 156
chunks	15800 +/- 144	21014 +/- 176	13676 +/- 118	21203 +/- 212
chunksarray	12903 +/- 649	19648 +/- 1080	12895 +/- 519	19770 +/- 816
array2d	*12606 +/- 606*	19844 +/- 1042	12640 +/- 540	19724 +/- 953

内存使用

chunks 和 array2d 都比基线有零内存开销。
chunksarray 对所有编译器有 9% 的开销。
baseline_dynamic 在 dmd 下有 18% 的开销，在 gcc 和 ldc 下有 41% 的开销。

当然，相对开销因数组维度和类型而异。

结论

-O3 和 -Os 之间的巨大差异，以及 array2d 在 dmd -O 下的表现比更好某些运行中的基线（尽管对（较短程序的）生成的程序集的检查表明 opIndex 没有被 dmd 内联）表明缓存未命中的数量是主要因素，至少当array 占用了相当一部分系统 RAM。（设置 -boundscheck=off 使基线的 dmd -O 版本与 array2d 性能一致，所以这显然是为什么 array2d 有时做得更好的原因。）

chunksarray 的优点是代码更短并且使用与动态数组相同的语法，并且在 nc and/or T.sizeof 足够大以至于相对内存开销变得不那么重要，但 array2d 似乎是一般情况下的最佳选择。

Answer 1

D 中的静态和动态数组在内存中的布局不同。

动态数组是引用类型，静态数组是值类型。

因此，无法将内存块转换为多维动态数组。

相反，您必须使用重载的索引运算符创建您自己的类型。

基本示例：

import std.stdio : writeln;

void main() {
    auto arr = Array2D!int(3, 4);
    arr[2, 3] = 23;
    // arr[3, 3] = 33; // range violation
    writeln(arr[2, 3]);
    writeln(arr.data[0..12]);
}

struct Array2D(T) {
    import core.memory : GC;
    import std.exception : enforce;
    import core.exception : RangeError;
    
    size_t nr, nc;
    T* data;
    this(size_t nr, size_t nc) {
        this.nr = nr;
        this.nc = nc;
        auto ds = nr * nc;
        data = cast(T*) GC.malloc(T.sizeof * ds);
        data[0..ds] = 0;
    }
    
    ref T opIndex(size_t r, size_t c) {
        enforce!RangeError(r >= 0 && r < nr);
        enforce!RangeError(c >= 0 && c < nc);
        return data[c * nr + r];
    }
}

基本通用示例：

import std.stdio : writeln;

void main() {
    auto arr = makeArrayMD!int(2, 3, 4);
    arr[1, 2, 3] = 123;
    // arr[2, 2, 3] = 223; // range violation
    writeln(arr[1, 2, 3]);
    writeln(arr.data[0..24]);
}

struct ArrayMD(T, size_t dims) {
    import core.memory : GC;
    import std.algorithm : fold;
    import std.exception : enforce;
    import core.exception : RangeError;
    
    size_t[dims] sizes;
    T* data;
    this(Sizes...)(Sizes szs) if(Sizes.length == dims) {
        sizes = [szs];
        auto ds = sizes.fold!"a * b";
        data = cast(T*) GC.malloc(T.sizeof * ds);
        data[0..ds] = 0;
    }
    
    ref T opIndex(Sizes...)(Sizes szs) {
        size_t idx = 0;
        size_t rs = 1;
        static foreach(i, s; szs) {
            enforce!RangeError(s >= 0 && s < sizes[i]);
            static if(i > 0) rs *= sizes[i - 1];
            idx += s * rs;
        }
        return data[idx];
    }
}

auto makeArrayMD(T, DS...)(DS dims) {
    return ArrayMD!(T, DS.length)(dims);
}

Answer 2

我用chunks创建了一个二维数组，一块块存在内存中

auto p = new int[](nr * nc);
auto p1 = p.chunks(nc).array;

// now you can set and get values as in usual 2D array
p1[i][j] = 42;

更多信息在这里：https://dlang.org/library/std/range/chunks.html#1

是否可以在运行时在 D 中创建一个连续的多维数组？

Is it possible to create a contiguous multidimensional array at runtime in D?

arrays

d

memory-layout

答案比较

运行时间

内存使用

结论