【C++ Efficiency】over-eager evaluation的两种做法：caching和prefetching

over-eager evaluation

超急评估：在要求你做某些事情之前就完成它们。

做法一：caching

最简单的做法：
caching（缓存）已经计算出来而有可能再被需要的值。

举例

写一个程序用来提供职员信息，你预计职员的房间号码常常会被使用。职员的相关信息存储在一个数据库中，为了避免增加程序给数据库造成负担，可以写一个findCubicleNumber函数缓存数据，后续直接在高速缓存cache中完成任务，不必再查询数据库。

int findCubicleNumber(const string& employeeName)
{
	typedef map<string,int> CubicleMap; //map用来作为局部缓存
	static CubicleMap cubes;
	
	CubicleMap::iterator it = cubes.find(employeeName);
	
	if(it  == cubes.end())
	{
		cubes[employeeName] = cubicle;	//没找到就将数据对加入cache
		return cubicle;
	}
	
	else
		//return it->second;			
		return (*it).second; //保证有效运行	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

做法二：prefetching

预提取：
希望未来的扩张能落入我们此刻所增加的弹性范围内。

template<class T>
class DynArray{...}; //动态数组
 
DynArray<double> a; //此时，只有a[0]是合法的数组元素
 
a[22] = 3.5;		 //a被自动扩张，索引0-22是合法的数组
 
a[32] = 0;			//a再度扩张自己，索引0-32是合法的数组
1
2
3
4
5
6
7
8

//DynArray对象如何才能在需要的时候扩张自己？
//最简单的方法就是:
//为新加入的索引做内存动态分配行为

template<class T>
T& DynArray<T>::operator[](int index)
{
	if(index < 0)
		throw an exception;  //负值索引无效
	
	if(index > 当前最大的索引值)
		调用new分配足够内存;   //调用new会触发operator new
						     //operator new调用底层操作系统
						     //比进程内函数的调用速度慢，尽量不采用
	
		返回该位置上元素;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//使用over-eager evaluation方法
template<class T>
T& DynArray<T>::operator[](int index)
{
	if(index < 0)
		throw an exception;
	
	if(index > 当前最大的索引值)
		int diff = index - 当前最大的索引值;
		调用new分配足够的额外内存，使得index+diff合法;
	
	返回index位置上的元素;
}

//于是
DynArray<double> a; //此时，只有a[0]是合法的数组
 
a[22] = 3.5;		 //调用new扩张a的空间，有效索引到0-44
 
a[32] = 0;			 //不用调用new了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

总结

较佳的速度往往导致较大的内存成本。

• caching会消耗较多的内存，但是可以降低已被缓存的结果重新生成的时间；
• prefetching需要一些空间来放置被预先取出来的东西，但可以降低访问他们所需要的时间。

区分：

• 当你必须支持某些运算而其结果并不总是需要时，lazy evaluation可以改善程序效率；
• 当你必须支持某些运算而其结果几乎总是被需要或经常被多次需要时，over-eager可以改善程序效率。