d原位数组扩展优化

原文
我注意到D运行时的原位数组扩展优化仅适合特定内存对齐的数组数据.
除了重复向数组加元素之外,使用以下程序来测试,
-version=neither不会删除元素(这也是"好")
-version=bad丢弃前面元素(移动窗口为1)
-'version=good'仅当元素数据达到某个对齐值时,才会删除元素.这是期望的吗?

import std.stdio;
import std.range;

// 请取消一个注释.
// version = bad;    // 无原位扩展
// version = good;   // 有原位扩展
// version = neither;// 有原位扩展

mixin assertSingleVersionOf!("bad", "good", "neither");

void main() {
  struct S {
    ubyte[4] data;  // 不同的合理尺寸
                    // 如5,是不行的.
  }

  S[] arr;

  foreach (i; 0 .. 100_000) {
    const oldCap = arr.capacity;
    const oldPtr = arr.ptr;

    arr ~= S.init;

    if (arr.capacity != oldCap) {
      // 需要扩展数组.
      if (arr.ptr == oldPtr) {
        // ... 但是指针不变
        writefln!"原位扩展元素: %,s  容量: %,s -> %,s  指针: %s"(
          i, oldCap, arr.capacity, arr.ptr);
      }
    }

    version (neither) {
      // 不删,仅扩展
    }

    version (bad) {
      // 删1元素,其余禁止
      arr = arr[1..$];

      // 这样也没用
      arr.assumeSafeAppend();
    }

    version (good) {
      // 删除等于 2048 字节的前端元素有效
      // 可能是GC相关数.

      enum magic = 2048;
      enum elementsPerPage = magic / S.sizeof;

      if (arr.length == elementsPerPage) {
        arr = arr[elementsPerPage..$];
      }
    }
  }
}

// 有用模板
mixin template assertSingleVersionOf(args...) {
  import std.format : format;

  static assert (1 >= {
    size_t count = 0;
    static foreach (arg; args) {
      static assert (is (typeof(arg) == string));
      mixin (format!q{
        version (%s) {
          ++count;
        }
      }(arg));
    }
    return count;
  }(), format!"取<=1的%(%s, %)"([args]));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

不,它基于两个因素:它是比页大小更大的块?后面有释放页吗?
较小的块存储在页面大小池中,且不能组合在一起.如,你不能合并2个16字节的块起来形成32字节的块.
bad版本失败原因:必须重新分配时,它仍然只分配1个元素.
现在一个页面一般是4096字节.为什么2048数有效呢?因为为了存储一个2048字节的数组,你需要2048字节和(如用于析构和追加容量的typeinfo的)元数据.这需要一整页.
请注意,一旦达到页面大小,即使只是附加到尾切片,就会优化.如,当容量小于元素的"神奇"数量时,保存该数量元素.然后"每个循环删除一个元素"应该使用优化.

如16字节的相同块仍有空间.为什么不使用剩余部分?
这是更简单的测试,结果好于期望.c数组是我想要做的.在该测试中可工作,甚至不必调用assumeSafeAppend()(这必须是你所说的"尾切片").

import std.stdio;

void main() {
  ubyte[] a;
  a ~= 0;
  a.length = 0;
  a.assumeSafeAppend();         // 需要
  assert(a.capacity == 15);

  // 同上
  ubyte[] b;
  b ~= 0;
  b = b[0..0];
  b.assumeSafeAppend();        // 需要
  assert(b.capacity == 15);

  ubyte[] c;
  c ~= 0;
  c = c[1..$];
  // c.assumeSafeAppend();
  assert(c.capacity == 14);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

它总共有16个字节(64位):void*+size_t,我打印.ptr时我看到了该:变化总是0x10.

void increaseCapacityWithoutAllocating(T)(ref T[] arr) {
  // ...
}//不分配增加容量.
1
2
3

可以在运行时调用类似在object.d中调用_d_arrayshrinkfit()的assumeSafeAppend()方法吗?

不,是现有块长度.
内存分配器中的所有内容都以页为单位.池是一堆页.大块是多页,小块是分成相同大小块的页.
想分配块时,如果它小于半页,则它会进入小池,你不能粘贴2个块在一起.
如果它大于半页,则它需要多页大小块.他们太大了,不能不管,所以分配器只是抓住一些有足够空闲页面池,然后返回它.这些块可按需缝合在一起.一旦释放,也可把它们分成页面.在此,容量可不复制就增长.

它会,直到它不能.然后需要重新分配.
请注意,如果删除头元素,则指向数组的切片.
A表示被当前切片使用,x是已分配,但未被数组引用..是块的一部分但未使用(但可供使用)“.M是"元数据”.

auto arr = new ubyte[10];      
// AAAA AAAA AA.. ...M
arr = arr[1 .. $];             
// xAAA AAAA AA.. ...M
arr ~= 0;                      
// xAAA AAAA AAA. ...M
arr ~= 0;                      
// xAAA AAAA AAAA ...M
arr = arr[3 .. $];             
// xxxx AAAA AAAA ...M
arr ~= cast(ubyte[])[1, 2, 3]; 
// xxxx AAAA AAAA AAAM // 满了!
arr ~= 1;                      
// AAAA AAAA AAAA ...M //分配后,改了.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

请注意,在最后实例中,它现在已移动到不同的16字节块中,原始块仍然完好无损,只是未指向它.最终被垃集.
但是,可看到它只分配了可容纳切片已包含内容+新元素的空间.
是的,数组切片的"可附加性"取决于它是否在"已用"空间的末尾.否则,如果更早结束,附加会占用可能在其他地方引用的内存.如果稍后结束,则你在代码中做错了,现在已被破坏了.

并不总是存储元数据.另外,它针对块大小优化了.如,256字节或更小的块只需要一个字节来存储"已用"空间.
仅在需要时存储析构数组元素所需的TypeInfo(如,int数组,就不需要).