C++

C++的位优化

    之前的中国象棋初版重在实现，老实说不论是时空效率还是健壮性都不太拿得出手，于是导师要求继续优化改进。考虑和调查过后，时间效率上可以借助之前设想的并行计算得到小幅优化，此外使用类似bool数组的手段也可以在走法生成器中小幅优化边界判断过程，最重要的时间效率优化手段是把博弈机改造成查表器，即以查表为主博弈为辅改变重心。以上都是时间效率优化，这篇文中暂且不展开，我的中国象棋初版在搜索深度大时（大于等于４层）开始出现程序崩溃的现象，暴露了空间效率问题。作为空间效率优化的铺垫，这次我来做个C++位优化的自科普。

    关于空间效率优化，从前顶多考虑到基本变量类型选择的程度，然而C++提供了一些更精细的特性，供程序员进行位级别的内存微操——位域、bitset、vector<bool>。

1 位域

1.1 字节对齐

    介绍位域之前，还需要做一点铺垫。业界C/C++面试、笔试题中，经常考到结构体的字节对齐问题。比如，可能会问下面两个结构体分别占多大内存：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct s1
{
	char a;
	double f;
	int b;
	long long g;
	char c[9];
	float e;
	short d;
};

struct s2
{
	char a;
	char c[9];
	short d;
	float e;
	int b;
	double f;
	long long g;
};

    sizeof(s1)和sizeof(s2)分别为56字节和40字节。先不管为什么装着同样变量的结构体占用的内存大小会不同，如果结构体中变量紧密排列，应该占多大内存？ａ：1字节，ｂ：4字节，ｃ：9字节，ｄ：2字节，ｅ：4字节，ｆ：8字节，ｇ：8字节，共36字节。显然这些变量实际上不是紧密排列的，存在一些对齐、填充字节的规则：

  • 有效对齐值默认为结构体最宽基本类型成员的大小，注意结构体的结构体成员必须到内部寻找基本类型成员变量计算有效对齐值；
  • 结构体变量的首地址能够被其有效对齐值所整除；
  • 结构体每个成员相对于结构体首地址的偏移量都是其本身大小的整数倍，如有需要编译器会在成员之间加上填充字节；
  • 结构体的总大小为结构体有效对齐值的整数倍，如有需要编译器会在最末一个成员之后加上填充字节；
  • 存在指定对齐值（#pragma pack (value)中的value）时，有效对齐值 = min{默认对齐值, 指定对齐值}。

    至于为什么要做字节对齐，这与CPU取数方式有关，尤其与CPU与内存间数据总线宽度（现在除了单片机通常为32位）有关。因为数据总线宽度是硬件相关，所以一次取数的位数是固定的，假设总线宽度32位，那么一次取数的数据大小就为4字节，那么CPU读取内存数据就将以内存首地址为基址，以4个字节为偏移量单位。如果结构体中有一个char型和一个int型变量，紧密排列存储在内存中，读char型变量时照样取了结构体的前4个字节，其中高8位的哪个字节是存储着char型变量，会经过一些位运算后被提取出来（比如按位右移24位，这仅仅是猜测），到此为止看不出什么不好的。可是当读int型变量时问题就来了，CPU无法一次读取到整个int变量了，原因前面提到了：CPU读取内存数据就将以内存首地址为基址，以4个字节为偏移量单位。经过两次取数才能获得被分割在两个字（32位内存单位）中完整的int型变量，这还不算完，还要分别从两个字中提取恰当的位并进行拼接，这很浪费时间。
    按特定规则进行字节对齐后，虽然浪费了一些填充字节的内存空间，情况还是好多了。以s1为例，有效对齐值是double型和long long型的8字节即两个字，这里称其为一个对齐空间，装填a（填充7个字节），装填f，装填b（填充4个字节），装填g，装填c（一个对齐空间内放不下，第二个空间中也放了1个字节，填充7个字节），装填e，装填d，结构体整体填充2字节，填满对齐空间的整数倍。
    同理也可求得s2的内存占用，至于两个结构体的内存占用不一样的原因，是它们的成员变量排列顺序不同，而结构体给成员变量分配内存的顺序与定义变量的顺序相同。
    当指定对齐值小于默认对齐值，可令结构体的成员变量排列更紧密，更省空间，但可能降低取数效率。特别的，当指定对齐值为1，结构体成员变量完全紧密排列。

1.2 位域与其利弊

    不管是为数据结构的成员变量设计合适的排列顺序，还是指定合适的字节对齐值，都是在字节的层次上优化程序空间效率。而使用位域，可以在位的层次上优化程序空间效率。
    还是以1.1节中的s1为例，只在字节层面上优化，以不损失时间效率为前提，最佳策略如下：

1
2
3
4
5
6
7
8
9
10
11
12
#pragma pack(4)
struct s1
{
	double f;
	long long g;
	int b;
	float e;
	short d;
	char a;
	char c[9];
};
#pragma pack()

    实际上就是保证按32位字（4字节）对齐，变量按大小降序排列。此时的sizeof(s1)为36字节，空间开销等同变量成员紧密排列，时间效率没有受到影响。
    下面这种写法不知读者见过没有：

1
2
3
4
5
6
7
8
9
10
11
12
#pragma pack(4)
struct s1
{
	double f;
	long long g: 21;
	int b: 7;
	float e;
	short d;
	char a;
	char c[9];
};
#pragma pack()

    对这样定义的结构体s1，sizeof(s1)是28字节。变量b、g后面的‘:’和数字就是位域的描述方式。位域的作用是把一些用不到当前类型变量中所有位的变量做进一步压缩，比如这里的s1结构体中的g变量，原来占用64位，使用位域压缩后g变量只使用原内存空间的高21位，填充3位补满3个字节后，原long long变量的后5个字节就可以自由分配了；b变量，原来占用32位，使用位域压缩后b变量只使用原内存空间的高7位，填充1位填满1个字节后，原int变量的后3个字节的内存空间就可以自由分配了。b、g压缩过后刚好占据4个字节一个32位字，比原来少占８个字节。
    于是，借由位域压缩技术，C++得以进行位层次的空间效率优化了。然而位域的使用有着诸多限制和缺陷：

  • 位域不可以用于浮点型变量的压缩；
  • 位域压缩有符号数时，由于其存储变量的编码方式是源码而非平常变量的补码，变量符号将可能出现不可预料的状态；
  • 位域压缩将局部解除变量间原有的的字节对齐规范，即使位域压缩的变量与相邻变量紧密排列，这可能引起取数时间效率的损失。

2 bitset

    这一节我要介绍的是比特集，正如字面意思，它是一种比特的集合的特殊数据结构。位域是C遗留下来的特性，存在很多不完备和妥协的地方,C++中推荐的替换方案之一就是bitset。它的具体使用方法我不想细讲，这里只做个概念介绍，想了解更多可以看标准C++手册，其实是我困了懒得写。
    比特集维护一个静态定义其长度的比特串，内存占用以系统字长（通常为机器字长，即CPU中寄存器的位数，即CPU进行数据计算的单位位宽，而非前面提到的数据总线宽度，但机器字长一定是数据总线宽度的整数倍）为单位长度，当然如果读者使用64位的机器却安装32位的系统则是把机器当做32位机使用，每个CPU寄存器只使用一半的位数。比特集可以通过包含‘０’、‘１’的字符串来构造，也可以通过无符号的整型变量来构造。为什么是无符号数？因为比特的集合本来就是逻辑的、离散的，符号在比特集中没有意义。当然如果想用某个逻辑位来作为符号位也随用户喜欢。相应的，比特集也可以转换成‘０’、‘１’字符串或者整型数。理所当然的，比特集类封装了一系列位运算符号和逻辑位操作方法，注意比特集的位操作符号两边都应该是比特集，位移操作符除外。
    也许有读者想了解bitset的内存占用情况，我进行了下面的一系列测试：

1
2
3
4
5
6
7
8
cout << sizeof(bitset<10>) << endl;	//8
cout << sizeof(bitset<20>) << endl;	//8
cout << sizeof(bitset<40>) << endl;	//8
cout << sizeof(bitset<80>) << endl;	//16
cout << sizeof(bitset<160>) << endl;	//24
cout << sizeof(bitset<320>) << endl;	//40
cout << sizeof(bitset<640>) << endl;	//80
cout << sizeof(bitset<1280>) << endl;	//160

    测试结果我写在注释里了，可以看到，bitset的存储单位是8个字节，而我的这台笔记本电脑正是64位机器字长的，测试环境是64位的Ubuntu 14.04版本操作系统。
    同样的，比特bitset也有它的不足之处，比如它不能再与普通整型数直接进行位运算，且它一经构造，不可以改变长度。至于时间效率，可以充分相信它不比普通整型的同类操作慢。

3 vector<bool>

    当我第一次在手册中看见vector<bool>时我并没有留意，虽然也对bool型的vector容器为什么有一套独立的API感到了一丝困惑。后来在查找bitset相关资料时发现有人写了vector<bool>与bitset的比较文章，这才知道，vector<bool>是C++提供的bitset之外的另一种位层次数据结构微操方案，同等长度的两者的内存占用几乎一样。vector<bool>的具体用法读者依旧可以查看手册，是的我又偷懒了XDDD。
    既然vector<bool>实现在vector库文件中，想必读者也能猜到它与bitset最大的不同，没错它是可变长的。相应的，作为牺牲，考虑数组与vector的区别，也不难猜到，vector<bool>比bitset慢。首先它的位操作也比bitset少得多，其次vector<bool>中的位不再能够用下标随机存取，而需要使用迭代器来访问。其实比起bitset的变长版本，我觉得说vector<bool>是bool型vector的空间优化版本更合适一些。

    以上就完成了简单的位层面程序空间效率优化的相关概念引入，下面会继续跟进我的中国象棋的改进版本。

Fork me on GitHub