达夫设备——swtich、while的结合达夫设备

71 阅读 0 评论 47 点赞

我是靠谱客的博主优美皮带，最近开发中收集的这篇文章主要介绍达夫设备——swtich、while的结合达夫设备，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

达夫设备

达夫设备是switch语句和while语句结合在一起的一种很精妙的应用，它的主要作用是避开了大量的条件检验，减少了CPU的分支预测带来的性能损耗，主要用在复制大量的数据上

虽然在编译技术和CPU技术高速发展的现在，达夫设备的作用已经微乎其微了，但是它仍然给我们提供了一些很好的思路

首先，要移动一定数量的数据，最容易想到、也是最简单的方法是：

while (n--) {
	*to++ = *from++;
}

这段代码中，条件检验的数量和进行数据复制的次数是一样的，都是n次

这么做的缺点是，大量的条件检验拖慢了程序运行的速度

为了加速这个过程，我们可以先假设，n的值是8的倍数，则使用循环展开技术，可以将这段代码优化如下：

for (int i = 0; i < n; i += 8) {
	*to++ = *from++;
	*to++ = *from++;
	*to++ = *from++;
	*to++ = *from++;
	*to++ = *from++;
	*to++ = *from++;
	*to++ = *from++;
	*to++ = *from++;
}

这么做的好处是，大大减少了条件判断的数量。
原来要移动n个数据，需要比对n次，现在只需要n/8次，当n很大的时候，这个优化带来的增益就很明显了。

但是，美中不足的是，我们此处已经假设了n为8的倍数。
若n不为8的倍数，那么可以这么优化：

int t = n % 8;
n -= t;
for (int i = 0; i < n; i += 8) {
	*to++ = *from++;
	*to++ = *from++;
	*to++ = *from++;
	*to++ = *from++;
	*to++ = *from++;
	*to++ = *from++;
	*to++ = *from++;
	*to++ = *from++;
}
while (t--) {
	*to++ = *from++;
}

一般来说，这么做就已经足够
但是一个叫达夫的人，想出了一个更牛逼的优化方式

int n = (count + 7) / 8;
switch(count % 8) {
	case 0 :    do { * to ++ = * from ++ ;
	case 7 :          * to ++ = * from ++ ;
	case 6 :          * to ++ = * from ++ ;
	case 5 :          * to ++ = * from ++ ;
	case 4 :          * to ++ = * from ++ ;
	case 3 :          * to ++ = * from ++ ;
	case 2 :          * to ++ = * from ++ ;
	case 1 :          * to ++ = * from ++ ;
 		} while ( -- n >    0 );
 }