关于循环展开优化

这几天蛋疼，下手开始实现一个虚拟机，主要的参考书籍是Bill Blunden的<Virtual Machine Design and Implementation in C/C++>，书中实现了一个基本完整的HEC虚拟机。除了实践一下其中的知识以外，最主要的还是实际调查一下自己对原作者实现中不满意的地方，如果时间和精力足够，再添加没有实现的JIT以及配套的高级语言编译器。

在Hec的实现中，有一个基本的功能，就是实现虚拟机字节码的endian与native code的endian之间的转换（如果相反），只是简单的颠倒字节顺序。主要在虚拟机加载字节码，开始执行之前调用，直接影响字节码加载到开始执行期间用户的等待时间。

Blunden为了优化性能，在这部分应用了循环展开[1]技术。本文记录了在开发过程中采用的几种与Blunden不同的实现方法，以及初步的对比。

0. Blunden原始实现

原始实现提供了一系列单独的bytecodeToTypeName以及typeNameToBytecode全局函数：

U2 bytecodeToWord(U1 bytes[]);
U4 bytecodeToDWord(U1 bytes[]);
U8 bytecodeToQWord(U1 bytes[]);
F4 bytecodeToFloat(U1 bytes[]);
F8 bytecodeToDouble(U1 bytes[]);

void wordToBytecode(U2 word, U1 arr[]);
void dwordToBytecode(U4 dword, U1 arr[]);
void qwordToBytecode(U8 qword, U1 arr[]);
void floatToBytecode(F4 flt, U1 arr[]);
void doubleToBytecode(F8 dbl, U1 arr[]);

其中U代表unsigned，后面的数字代表位长，在win32平台下的定义为：

#define S1	signed char
#define S2	signed short
#define S4	signed long
#define S8	signed __int64	

#define U1	unsigned char
#define U2	unsigned short
#define U4	unsigned long
#define U8	unsigned __int64

以下仅列举U8版本的qwordToBytecode实现：

void qwordToBytecode(U8 qword, U1 arr[])
{
	U1 *buffer;

	buffer = (U1*)&amp;qword;
	arr[0] = buffer[7];
	arr[1] = buffer[6];
	arr[2] = buffer[5];
	arr[3] = buffer[4];
	arr[4] = buffer[3];
	arr[5] = buffer[2];
	arr[6] = buffer[1];
	arr[7] = buffer[0];

	return;

}/*end qwordToBytecode*/

可以看出Blunden的实现是C Style的，基本上就是一大堆全局函数与变量，缺乏封装性。各个类型的转换函数没有统一的调用接口，而且由于采用了循环展开，导致对每一个类型转换的函数体都非常冗长，整个代码就变成了一大堆重复代码的组合。

当然这主要是出于性能的考虑，不过考虑到现在的C++编译器的性能已经不再是当年的情况，C++完全可以做到与C相同甚至更好的性能，同时提供更易于维护的代码。实际上，很多C语言写的程序最后也是用C++编译器编译的。

1.实现一：For Loop

在讨论优化之前，要有个被优化的对象作为对比，以下是用For循环在一个struct中实现同样的功能：

template &lt;typename T&gt;
struct ForLoopAssign
{
	inline static void AssignBytes(const U1 src[], U1 dest[])
	{
		for (int i = 0; i &lt; sizeof(T); i++)
		{
			dest[i] = src[sizeof(T) - i - 1];
		}
	}
};

这里只是最主要的交换赋值部分，采用了模板类，为的是同一个接口实现不同类型转换功能的调用，而不是若干个单独的函数。

模板类在编译时就会被展开，因此在运行时的性能损耗很小。

可以看到这段代码的优点是简短，易于维护，几行代码实现了几十行代码的功能。缺点当然是For-Loop造成的性能损耗。

调用：

1	ForLoopAssign<T>::AssignBytes(src, dest);

2.实现二：手动循环展开

Prototype：

template &lt;int byteLen&gt;
struct ExplicitUnrolling
{
	inline static void AssignBytes(const U1 src[], U1 dest[]);
};

特化：

template &lt;&gt;
struct ExplicitUnrolling&lt;1&gt;
{
	inline static void AssignBytes(const U1 src[], U1 dest[])
	{
		dest[0] = src[0];
	}
};

template &lt;&gt;
struct ExplicitUnrolling&lt;2&gt;
{
	inline static void AssignBytes(const U1 src[], U1 dest[])
	{
		dest[0] = src[1];
		dest[1] = src[0];
	}
};

template &lt;&gt;
struct ExplicitUnrolling&lt;4&gt;
{
	inline static void AssignBytes(const U1 src[], U1 dest[])
	{
		dest[0] = src[3];
		dest[1] = src[2];
		dest[2] = src[1];
		dest[3] = src[0];
	}
};

template &lt;&gt;
struct ExplicitUnrolling&lt;8&gt;
{
	inline static void AssignBytes(const U1 src[], U1 dest[])
	{
		dest[0] = src[7];
		dest[1] = src[6];
		dest[2] = src[5];
		dest[3] = src[4];
		dest[4] = src[3];
		dest[5] = src[2];
		dest[6] = src[1];
		dest[7] = src[0];
	}
};

其实就是对C Style实现的C++封装，性能接近原实现，调用只需要一句：

1	ExplicitUnrolling<sizeof(T)>::AssignBytes(src, dest);

显然，作为显示实现的代码，也是难于维护的。

3.实现3：模板元递归

递归模板：

template &lt;int byteN, int byteLen&gt;
struct AssignByte
{
	static inline void Assign(const U1 src[], U1 dest[])
	{
		dest[byteN - 1] = src[byteLen - byteN];
		AssignByte&lt;byteN - 1, byteLen&gt;::Assign(src, dest);
	}
};

递归边界：

template &lt;int byteLen&gt;
struct AssignByte&lt;1, byteLen&gt;
{
	static inline void Assign(const U1 src[], U1 dest[])
	{
		dest[0] = src[byteLen - 1];
	}
};

调用：

1	AssignByte<sizeof(T), sizeof(T)>::Assign(src, dest);

和For Loop实现相比，这段代码只长了几句，但是却实现了循环展开。

以U4为例，调用的时候实际上是：

1	AssignByte<4, 4>::Assign(src, dest);

在Assign函数体中形成递归调用：

1
2
3

dest[4 - byteLen] = src[4 - byteLen];
//递归调用
AssignByte&lt;4 - 1, byteLen&gt;::Assign(src, dest);

直到传入的byteN == 1到达递归边界。

但这个递归是在编译时进行的，实际上是编译器递归的生成了如下代码：

AssignByte&lt;4, 4&gt;::Assign(const U1 src[], U1 dest[])
{
	dest[3] = src[0];
	AssignByte&lt;3, 4&gt;::Assign(src, dest);
}

AssignByte&lt;3, 4&gt;::Assign(const U1 src[], U1 dest[])
{
	dest[2] = src[1];
	AssignByte&lt;2, 4&gt;::Assign(src, dest);
}

AssignByte&lt;2, 4&gt;::Assign(const U1 src[], U1 dest[])
{
	dest[1] = src[2];
	AssignByte&lt;1, 4&gt;::Assign(src, dest);
}

AssignByte&lt;1, 4&gt;::Assign(const U1 src[], U1 dest[])
{
	dest[0] = src[3];
}

所以在运行时没有任何递归，只是一系列的函数调用，但更妙的是对于足够短的函数体，编译器会自动进行inline优化，省略函数调用，以上代码最后编译后等效于人肉实现的循环展开。

dest[0] = src[3];
dest[1] = src[2];
dest[2] = src[1];
dest[3] = src[0];

这种方法最后做到了与For Loop相近长度的易于维护的代码，以及（理论上）与人肉循环展开一致的性能。

4.测试与结果分析

测试代码分别调用以上3种实现100000000、1000000000、10000000000次，记录执行时间。

测试平台：Windows 7 Ultimate 32bit + Visual Studio 2010

Release Build:

----------------------------------
Test U2
For-Loop x100000000: 207
Template x100000000: 88
Explicit x100000000: 119

Test U4
For-Loop x100000000: 183
Template x100000000: 85
Explicit x100000000: 93

Test U8
For-Loop x100000000: 182
Template x100000000: 86
Explicit x100000000: 86

----------------------------------
Test U2
For-Loop x1000000000: 1768
Template x1000000000: 878
Explicit x1000000000: 1169

Test U4
For-Loop x1000000000: 1796
Template x1000000000: 879
Explicit x1000000000: 882

Test U8
For-Loop x1000000000: 1760
Template x1000000000: 881
Explicit x1000000000: 893

----------------------------------
Test U2
For-Loop x10000000000: 13508
Template x10000000000: 7648
Explicit x10000000000: 13349

Test U4
For-Loop x10000000000: 12094
Template x10000000000: 6005
Explicit x10000000000: 6267

Test U8
For-Loop x10000000000: 12075
Template x10000000000: 5914
Explicit x10000000000: 6314

输出中For Loop为循环实现，Template为模板元递归实现，Explicit为人肉实现。

可以看到，For loop不出意外的慢。

在Release Build模式下，模板元递归的性能与人肉循环展开一致，甚至在位长等于2的类型中优于后者，这应该是编译器优化造成的（待考）。

在Debug Build模式下出现了反常，模板元递归实现的执行时间意外的比人肉实现慢：

-------------------------------------------
Test U2
For-Loop x100000000: 5187
Template x100000000: 9629
Explicit x100000000: 3576

Test U4
For-Loop x100000000: 4821
Template x100000000: 16005
Explicit x100000000: 3533

Test U8
For-Loop x100000000: 7009
Template x100000000: 28891
Explicit x100000000: 4171

-------------------------------------------

查看Disassemblely：

//static inline void Assign(const U1 src[], U1 dest[])
//{
01156D30  push        ebp
01156D31  mov         ebp,esp
01156D33  sub         esp,0C0h
01156D39  push        ebx
01156D3A  push        esi
01156D3B  push        edi
01156D3C  lea         edi,[ebp-0C0h]
01156D42  mov         ecx,30h
01156D47  mov         eax,0CCCCCCCCh
01156D4C  rep stos    dword ptr es:[edi]
//	dest[byteN - 1] = src[byteLen - byteN];
01156D4E  mov         eax,dword ptr [dest]
01156D51  mov         ecx,dword ptr [src]
01156D54  mov         dl,byte ptr [ecx]
01156D56  mov         byte ptr [eax+1],dl
//	AssignByte&lt;byteN - 1, byteLen&gt;::Assign(src, dest);
01156D59  mov         eax,dword ptr [dest]
01156D5C  push        eax
01156D5D  mov         ecx,dword ptr [src]
01156D60  push        ecx
01156D61  call        AssignByte&lt;1,2&gt;::Assign (11511FEh)
01156D66  add         esp,8
//}

可以看出造成反常的原因是编译器为了便于debug，并没有进行inline优化，依然是函数调用。

另外Debug模式会插入许多额外代码方便调试器，因此造成了整体性能的下降。

5.小结

因为偷懒，本文并未比较C实现与C++实现之间的性能差异，虽然有理由相信实现一中结构体静态成员函数调用的成本与C全局函数调用成本不相上下，但仍然是不严密之处。

仅就3种实现的对比而言，可以确定的是：

a.循环展开优化是有效果的

b.执行成本：函数调用>循环>展开后代码

c.实际优化结果结果依赖于编译器以及编译模式