top of page
  • Writer's pictureLingheng Tao

C++ Programming #1 Data and Memory

Updated: Jan 19


这篇笔记写一些关于 C++ 数值类型和内存管理的知识点。


变量类型

可能会 cover 到的变量类型如上所示。在本文中,字节(byte)指的是 8 位的内存单元,即 1 byte = 8 bits.


简单变量


分类


  1. 整数型变量:char (1 byte), short (2 bytes), int (4 bytes), long (4 bytes), long long (8 bytes)。

  2. 浮点数变量:float (4 bytes),double (8 bytes), long double (12 or 16 bytes)。


特别地,布尔类型(bool)的值只有 true 和 false。C++ 会将 0 解释为 false,将非零值都解释成 true。


C++11 提供了固定宽度的整数类型,int16_t, int32_t, int64_t。它们的长度就分别是 16 bits, 32 bits 和 64 bits(即2/4/8字节)。


计数


整数型变量的计数方式:

  • 如果整数型变量是带符号的(signed),那么第 0 位永远表示正负(1 负 0 正),除第 0 位以外的数字用以表示二进制数值大小。

  • 如果整数型变量是不带符号的(unsigned),那么所有位数都是用来表示大小的。

float (32 bits) 的计数方式:

  • 第 0 位 / 符号位(1 bit):表示正负。1 负 0 正。

  • 第 1-8 位 / 指数位(8 bits):表示数值范围。

  • 后面的所有位数 / 尾数位(23 bits):表示数值精度。

E.x. Present -15.5 in binary bits.
1. Sign: Negative, so the first bit is 1.
2. Absolute value: 15.5 = 15(int) + 0.5(decimal)
3. Binary transform: 15 = (1111)_2, 0.5 = 1/2 = 2^(-1) = (0.1)_2
4. Offset: 15.5 = (1111.1)_2 = 1.1111 * 2^3, offset = 3+127 = 130 = (10000010)_2
5. Mantissa: 1.1111 -> .1111 -> (fill to 23 bits) (11110000000000000000000)_2

Now combine all the binary parts, 
-15.5 = (1 10000010 11110000000000000000000)_2

Double (64 bits) 的计数方式:

  • 与 floats 的计算步骤是相同的。

  • 符号位 1 位,指数位 11 位,尾数位 52 位。


类型转换


C++ 允许将一种类型的值赋给另一种类型的变量。


一般来说,将一个值赋给值取值范围更大的类型通常不会导致什么问题(例如将 int 转换为 long)。但是,如果将一个很大的 long 值转换成 float,就会降低精度,因为 float 只有六位有效数字。


将一个取值范围更大的值转换成更小的值(且确实超过了其取值范围时),通常只复制右边的字节。


内存管理


计算机系统的主存被组织成一个由 M 个连续的字节大小的单元组成的数组,每个字节都有唯一的一个物理地址。


动态内存分配


在 C/C++ 程序运行时需要额外的虚拟内存时,我们就会使用动态内存分配器请求新的内存块。


动态内存分配器(Dynamic Memory Allocator)维护着一个进程的虚拟内存区域,这个区域被称作内存(heap)。分配器将堆视作一组不同大小的块的集合来维护,每个块就是一个连续的虚拟内存片(chunk),这个块要么是已经被分配的(allocated),要么是空闲的(free)。


已分配的块是应用程序正在使用的,空闲块则可以用来给应用程序使用。一个块不再使用时,为了之后的请求能有内存块可以使用,我们必须要释放(free)这个块。这种释放可以是:

  • 显式的:例如 C 中的 free,C++ 中的 delete

  • 隐式的:例如 Java, C# 中的垃圾收集器(Garbage Collector)。

当程序需要去使用一个块的时候,就要寻求动态内存分配器去分配一个块,这个分配的过程总是显式的,例如 C 中的 malloc, C++ 中的 new。


内存碎片


有的时候,内存中空闲块的总额虽然可能可以响应一个 malloc/new 的请求,但是却因为在物理上这些块被分成了多个小块且散布在堆上(或者被已分配块隔开),导致 new 无法申请到完整的一块足够大的内存块,这种情况就叫做内存碎片


上述这种情况也被叫做外部碎片。有时也会出现内部碎片,即已分配块比其有效载荷大(因为分配器可能根据最小块分配要求给它分了一个比它大的块)。


空闲链表


空闲链表是分配器用来查找和使用空闲块的数据结构。我们实现这种数据结构的方法有很多。


隐式空闲链表


一个简单的块的结构可能是:

  • 头:包括块的大小(前 29 位)以及分配情况(后 3 位,001表示已分配,000表示未分配)。

  • 有效载荷:malloc/new 请求的有效载荷。

  • 填充(可选):可能是用来满足对其要求,可能是其他。

因为空闲块实际上通过头部的大小字段就可以隐含地连接(从堆起点开始遍历,然后找到分配位为 0 的块比较大小即可)。


优点是概念和实现上都很简单,缺点是真的很慢。


显式空闲链表


在显式的一个空闲块中,头之后的结构是一个 pred 和一个 succ 指针,分别指向前一个和后一个。分配块则与隐式相同。这样一来,分配的时间从块总数的线性时间变成了空闲块的线性时间。释放块的时间可以是 O(N) 也可以是 O(1),取决于我们用 LIFO 结构存储链表,还是使用地址顺序来排序链表。


显式的优点在于优化首次适配时间,但是缺点在于更大的最小块(因为空闲块必须存储头部以及所有需要用到的指针),潜在地提高了碎片的可能性。


分离空闲链表


我们不再维护唯一的空闲链表——取而代之,我们将空闲块分成多个大小类,然后在那个大小类对应的空闲链表里面去寻找块。








11 views0 comments

Recent Posts

See All

コメント


bottom of page