rust基础入门[12] - Data Implementation

2023-01-12

rust

learning

本章覆盖有：

  • 如何知道栈空间分配的各种类型的对象的字节数
  • 如何在外部模块缩减声明函数访问的路径
  • 原生对象类型存储了多少个bit
  • 什么时候一个对象会被存储在内存
  • 为什么填充(padding)会增加某些对象的大小
  • Vector是如何实现的

Discovering the Size of Objects

给定一个源文件，以及源代码按照Rust语言规范，Rust编译器任意将其生成目标机器码。

因此，对于一个变量，它没有定义会使用多少bit内存，也没有定义在内存哪个位置分配。编译器甚至将变量从内存中移除，只要它不再被使用，或被驻留在寄存器中。

下面看一个典型的Rust程序长度的实现。

Rust有一些可用特性：

1
2
print!("{} ", std::mem::size_of::<i32>());
print!("{} ", std::mem::size_of_val(&12));

结果将输出： “4 4”。

第一条语句，编译器引入了标准库模块std，然后跟着子模块mem(“memory”的缩写)，接着使用它的泛型函数size_of。

该泛型函数接受了类型参数i32，然后编译成对应的具体函数。该函数返回类型占用的字节数(也说“十进制的bit”)。该函数在行内调用，因此生成的代码仅是一个常数。实际上，一个32位占4个字节。

第二条语句，编译器进入同样的类库模块，以及访问了泛型函数size_of_val(顾名思义，值的大小)。这里类型参数由具体调用的参数推断确定。

当具体的生成的函数size_of_val被调用，会传递一个不可变的对象引用参数。然后返回对象字节大小。

The use Directive

在一段代码中如果要多处指定标准库函数，可以方便地使用use指令导入到当前范围。

上一段例子可以复写为：

1
2
3
use std::mem;
print!("{} ", mem::size_of::<i32>());
print!("{} ", mem::size_of_val(&12));

或写成这样：

1
2
3
4
use std::mem::size_of;
use std::mem::size_of_val;
print!("{} ", size_of::<i32>());
print!("{} ", size_of_val(&12));

Rust关键字use的用法和C++的using关键字类似。

1
2
3
use std::mem::*;
print!("{} ", size_of::<i32>());
print!("{} ", size_of_val(&12));

星号这里作为一个统配导入处理。

The Sizes of the Primitive Types

现在可以想象下原生类型对象的大小：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
use std::mem::*;
print!("{} {} {} {} {} {} {} {} {} {} {} {}",
	size_of::<i8>(),
	size_of::<u8>(),
	size_of::<i16>(),
	size_of::<u16>(),
	size_of::<i32>(),
	size_of::<u32>(),
	size_of::<i64>(),
	size_of::<u64>(),
	size_of::<f32>(),
	size_of::<f64>(),
	size_of::<bool>(),
	size_of::<char>());

在任何计算机，会打印输出：1 1 2 2 4 4 8 8 4 8 1 4。

某些其它类型数据的大小，由编译器所在的硬件设备平台所决定：

1
2
3
4
5
6
use std::mem::*;
print!("{} {} {} {}",
	size_of::<isize>(),
	size_of::<usize>(),
	size_of::<&i8>(),
	size_of::<&u32>());

在一个64位系统，打印输出：8 8 8 8，而在32位系统，打印：4 4 4 4。

后两个打印的是一个引用值。独立于所引用的对象，一个引用(又名“指针”)拥有内存地址大小。

The Representation of Primitive Types

Rust不鼓励访问内部对象的表述，同时也难于做到。但有一个技巧可以做到这点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fn as_bytes<T>(o: &T) -> &[u8] {
	unsafe {
		std::slice::from_raw_parts(
			o as *const _ as * const u8,
			std::mem::size_of::<T>())
	}
}
println!("{:?}", as_bytes(&1i8));
println!("{:?}", as_bytes(&2i16));
println!("{:?}", as_bytes(&3i32));
println!("{:?}", as_bytes(&(4i64 + 5 * 256 + 6 * 256 * 256)));
println!("{:?}", as_bytes(&'A'));
println!("{:?}", as_bytes(&true));
println!("{:?}", as_bytes(&&1i8));

在x86_64架构系统中，可能会打印：

1
2
3
4
5
6
7
[1]
[2, 0]
[3, 0, 0, 0]
[4, 5, 6, 0, 0, 0, 0, 0]
[65, 0, 0, 0]
[1]
[129, 165, 54, 102, 23, 86, 0, 0]

泛型函数as_bytes使用了某些我们没见过的Rust结构，这里不解析，目前的知识还不足以理解它的用法。简单来说，它接受一个任意类型的参数引用，并返回该所引用的对象的字节序列表述。打印任意对象的字节序列后发现，这些对象序列被存储在内存中。

首先，一个i8的值1存储一个字节，在其他任何硬件架构也是一样。

然后，一个i16的值2存储两个字节，第一个字节是2，第二个字节是0。除目前任何32位或64位处理器都一样，但仅限于“低位优先(little-endian)”硬件架构，会将多字节的数放在低位。相反，“大头优先(big-endian)”的存储顺序方式的硬件架构会打印[0, 2]。

类似地行为出现在接下来的打印行。

注意，一个char作为32位数字存储，包含Unicode码。bool作为单个字节存储，即1位true，0位false。

最后，最后一条语句打印一个i8数字的地址。在64位处理器，该地址包含8个字节。

Location of Bytes in Memory

你也可以发现任何对象的虚拟内存的位置，即它的地址：

1
2
3
4
5
6
7
let b1 = true;
let b2 = true;
let b3 = false;
print!("{} {} {}",
	&b1 as *const bool as usize,
	&b2 as *const bool as usize,
	&b3 as *const bool as usize)

在64位系统，将会输出三个巨大的数，像140727116566237 140727116566238 140727116566239。相反，在32位系统，输出三个小于5百万的数。

下面是这三个对象的地址表述：

Absolute address Binary value Variable name Type
140727116566237 0000_0000 b3 bool
140727116566238 0000_0001 b2 bool
140727116566239 0000_0001 b1 bool

三个对象中每个对象仅占一个字节。最先打印的数是变量b1的地址；变量b2的地址；变量b3的地址。如其所示，这三个数是连续的，意味着这三个数被连续地分配在虚拟内存地址上。

你会发现三个地址按照降序排列，意味着对象的分配，以越来越低位的方式。这些对象分配在栈上，因此看到栈从低位增长。

第一个数包含true值，由1字节表示。它由一个7位全为0的以及1位为1的值表示。类似地，第二个值也一样。第三个值false，则由全为0的8位值表示。

几乎所有现代处理器要求基础数据要有特定的内存位置，因此Rust放置这些对象在内存，以方便实现处理器的访问。

典型地对齐规则是：“每个原生类型的对象，必须要有一个地址，该地址是它自身大小的倍数”。

因此，占一个字节的对象，可能会放置在任何地方，占两个字节的对象，仅可以放置在偶数位地址，占四个字节的对象，仅可以放置在以4为倍数的地址，以及占8个字节的对象，仅可以放置在以8位倍数的地址。

另外，大对象通常有一个16倍的地址。

因此，这种对齐规则会创建无用的空间，称之为“填充(padding)”。

Sizes of Composite Data Types

当有一个组合对象序列时，出现结构填充(padding)的效果：

1
2
3
4
5
6
7
8
9
10
enum E1 { E1a, E1b };
enum E2 { E2a, E2b(f64) };
use std::mem::*;
print!("{} {} {} {} {} {}",
	size_of_val(&[0i16; 80]),
	size_of_val(&(0i16, 0i64)),
	size_of_val(&[(0i16, 0i64); 100]),
	size_of_val(&E1::E1a),
	size_of_val(&E2::E2a),
	size_of_val(&vec![(0i16, 0i64); 100]));

结果打印输出：“160 16 1600 1 16 24”。

这意味着：

  • 一个80长度的16位数组占160字节，即是 80 * 2，这里没有出现浪费；
  • 一个由16位和64位数组成的tuple占16个字节，如果两个数将占8个字节，则额外增加6个字节padding。
  • 一个100长度的16位tuple占1600字节，数组之间不会有padding，但数组条目之间的padding会随数组长度增加；
  • 一个不带数据的字段的enum，总是仅占一个字节；
  • 一个带有8字节数据字段的enum，占16个字节，即使当前值没有数据，它有7字节的padding。
  • 一个100长度的16位tuple的Vector，看起来占24字节，但由于当前测量方式遗漏了一部分。

所以，接下来仅看Vector的情况。

存放于栈空间的数据，在编译期必须知道其大小，因此数组可以完全地分配在栈空间上，而对于固定大小的vector来说，仅将header放在栈空间，剩余的数据必须放在堆空间。

Vector Allocation

我们看到向量必须实现两种结构：header固定大小的栈分配，buffer变量长度的堆分配。

理论上有很多方式实现一个向量数据结构。

一种方式是在头中保留指向缓冲区的指针。

这种方式的缺点是，每次获取一个数组长度时，需要一个间接的方式。数组的长度经常在显式地或隐式地用到，所以最好的方式是将信息保留在header中。

一个幼稚的实现缓冲的方式是令其足够大。例如，如果是一个9个i32条目的向量，在堆中分配一个9 * 4字节的缓冲区。

当有新的条目pushed进来时，缓冲区的大小必须重新分配，以及堆的分配和回收是很耗费资源的。而且，还需要将旧缓冲区内容拷贝到新缓冲区。

如果一个空的向量，以1000次的push方法来构造成为一个1000条目的向量，将会有1000次的堆空间分配，999次的堆回收，以及1000 * 999 / 2 == 499_500次的条目拷贝。

为了证实这个糟糕的性能，可能会有一个大的缓冲区被分配，仅当该缓冲区空间不够触发再分配。

因此有必要跟踪分配的缓冲区的地址数目，以及该缓冲区被使用的数据。

分配的缓冲区的地址数目通常叫容量(capacity)，它也是访问这个数据的函数名。

1
2
3
4
5
6
7
8
9
10
11
12
let mut v = vec![0; 0];
println!("{} {}", v.len(), v.capacity());
v.push(11);
println!("{} {}", v.len(), v.capacity());
v.push(22);
println!("{} {}", v.len(), v.capacity());
v.push(33);
println!("{} {}", v.len(), v.capacity());
v.push(44);
println!("{} {}", v.len(), v.capacity());
v.push(55);
println!("{} {}", v.len(), v.capacity());

结果将输出：

1
2
3
4
5
6
0 0
1 4
2 4
3 4
4 4
5 8

当一个空向量被创建，它包含0个条目，所以没有分配任何堆缓冲区，所以它的容量是0。

当添加第一个记录时，向量对象被分配在一个缓冲区容量32位(16字节缓冲区)的堆空间，因此它的容量是4，由于它包含一条记录，因此它的长度是1。

当其它三个条目被添加到向量，不再需要分配内存，因为预分配的缓冲区已经足够大容纳。

但当第5条记录被添加到向量，需要再重新分配一个大的缓冲区。新的缓冲区的容量为8。

因此，vec对象存储了三个子对象在栈空间：一个是指向堆缓冲区的指针，它是一个内存地址；一个是缓冲区的容量(capacity)大小，它是一个usize；一个是vector的条目的长度，它是一个usize值，小于或等于容量(capacity)大小。

基于这个原因，任何vector的header在64位系统占3 * 8 == 24字节，在32位系统占3 * 4 == 12字节。

让我们看看，如果添加一千个条目到一个32位的vector会发生什么：

1
2
3
4
5
6
7
8
9
10
let mut v = vec![0; 0];
let mut prev_capacity = std::usize::MAX;
for i in 0..1_000 {
	let cap = v.capacity();
	if cap != prev_capacity {
		println!("{} {} {}", i, v.len(), cap);
		prev_capacity = cap;
	}
	v.push(1);
}

可能的输出结果是：

1
2
3
4
5
6
7
8
9
10
0 0 0
1 1 4
5 5 8
9 9 16
17 17 32
33 33 64
65 65 128
129 129 256
257 257 512
513 513 1024

对于其它类型的vector，输出结果也一样。

变量cap存储了当前向量的容量；变量prev_capacity存储上一份的容量，它初始化了一个巨大的值。

对于每次迭代，在向vector添加记录之前，会检测容量是否改变。每次capacity的改变，都会打印当前容量和插入记录。

这里显示了容量的大小总是2的次方。这里发生了9次分配，8次再分配，以及4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 == 1020次拷贝，所以真实的算法比开头描述的幼稚那个版本要高效得多。