C语音冷门知识点:达夫机!switch还可以这么玩

小麦大叔 2022-04-22 11:30

相信大家写业务逻辑的时候,都是面向if、elseforwhileswitch编程。但是你见过switch嵌套do..while吗?

先上代码

void send( int * to, int * from, int count)
{
    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 );
    }  
}

咋的一看,这啥玩意啊,switch/while 这组合能编译通过吗?您可别怀疑,还真能。这个就是达夫设备(Duff's Device)

什么是达夫设备

百度百科说法如下:

在计算机科学领域,达夫设备(英文:Duff's device)是串行复制(serial copy)的一种优化实现,通过汇编语言编程时一常用方法,实现展开循环,进而提高执行效率。这一方法据信为当时供职于卢卡斯影业的汤姆·达夫于1983年11月发明,并可能是迄今为止利用C语言switch语句特性所作的最巧妙的实现。

达夫设备是一个加速循环语句的C编码技巧。其基本思想是--减少循环测试的执行次数。

简单讲下背景

时间要回到1983年,那是一个雨过天晴的夏天,在卢卡斯影业上班的程序员Tom Duff,他是想为了加速一个实时动画程序,实现从一个数组复制数据到一个寄存器这样一个功能,真脸如下。

一般情况下,若要将数组元素复制进存储器映射输出寄存器,较为直接的做法如下所示

do {
  /* count > 0 assumed (假定count的初始值大于0) */    
  *to = *from++;            
  /* Note that the 'to' pointer is NOT incremented 
  (注意此处的指针变量to指向并未改变) */
while(--count > 0);

但是达夫洞察到,若在这一过程中将一条switch和一个循环相结合,则可展开循环,应用的是C语言里面case 标签的Fall through特性,实际就是没有break继续执行。实现如上代码所示。

其实第一版是这样写的:

void send(to, from, count)
register short *to, *from;
register int count;
{
    /* count > 0 assumed */
    do {        
        *to++ = *from++;
    } while (--count > 0);
}

这段代码等价于:

void send(register short* to, register short* from, register int count)
{
    /* count > 0 assumed */
    do {                          
        *to++ = *from++;
    } while (--count > 0);
}

但是在这种使用场景下,不易于移植和应用,然后他就更新了第二版,代码如下:

void send2(short* to, short* from, int count)
{
    int n = count / 8;
    do {
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
    } while (--n > 0);
}

这种写法减少了比较次数,在汇编层面单纯讲到下面代码的时候

do... while(--count > 0) 

总共有6条指令。大家可以用godbolt.org/ 测一下。如下(汇编测试参考网上资源,大家可以自行测试)

subl  $1,-4(%rbp)
cmp1  $0,-4(%rgp)
setg  %al,
testb %al,%al
je    ,L8
jmp   ,L7

如果原始count是256,就这一部分指令减少(256-256/8)*6=(256-32)*6=1344。对应6条指令:

movl   -36(%rbp),%eax
leal   7(%rax),%edx
testl  %eax,%eax
cmovs  %edx,%eax
sarl   $3,%eax
movl   %eax,-4(%rbp)

但是这个版本在通用性能还不够,count一定要是8的倍数,所以经过了这两个版本的发展,最终才有了上述那个最终版本的诞生。虽然性能上没有什么优化,但是最终版的达夫设备,count不局限于一定是8的倍数了!

实现机制、代码解析

实现机制

在达夫解决这个问题的时候,当时的C语言对switch语句的规范是比较松的,在switch控制语句内,条件标号(case)可以出现在任意子语句之前,充作其前缀。

此外若未加入break语句,则在switch语句在根据条件判定,跳转到对应的标号,并在开始执行后,控制流会一直执行到switch嵌套语句的末尾。

利用这种特性,这段代码可以从连续地址中将count个数据复制到存储器中,映射输出寄存器中。

另一方面,C语言本身也对跳转到循环内部提供了支持,因而此处的switch/case语句便可跳转到循环内部。

代码解析

首先说下这段代码,编译没问题,我们写个代码如下:

#include < iostream > 
using namespace std;
int  main()
{
    int  n  = 0 ;
    switch  (n)  { 
    case 0 :  do   {cout  <<   " 0 "   <<  endl;
    case 1 :         cout  <<   " 1 "   <<  endl;
    case 2 :         cout  <<   " 2 "   <<  endl;
    case 3 :         cout  <<   " 3 "   <<  endl; 
      }   while ( -- n  > 0 ); 
   } 

根据n的不同输入,实验结果如下

n的值程序输出
00 1 2 3
11 2 3
22 3 0 1 2 3
33 0 1 2 3 0 1 2 3

这段代码的主体还是do-while循环,但这个循环的入口点并不一定是在do那里,而是由这个switch(n),把循环的入口定在了几个case标号那里。

即程序的执行流程是: 

程序执行到了switch的时候,就会根据n的值,直接跳转到 case n那里,再当它执行到while那里时,就会判断循环条件。若为真,则while循环开始,程序跳转到do那里开始执行循环;为假,则退出循环,即程序中止。(这个swicth语句就再也没有用了)

我们再看以下代码,这里 count 个字节从 from 指向的数组复制到 to 指向的内存地址,是个内存映射的输出寄存器。它把 swtich 语句和复制 8 个字节的循环交织在一起, 从而解决了剩余字节的处理问题 (当 count % 8 != 0)。

void send( int * to, int * from, int count)
{
    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 );
    }  
}

switch内的表达式计算被8除的余数。执行开始于while循环内的哪个位置由这个余数决定,直到最终循环退出(没有break)。Duff's Device这样就简单漂亮地解决了边界条件的问题。

性能表现

我们一般使用用for循环或者while循环的时候,如果执行循环内容本身用不了多少时间,本质上时间主要是消耗在了每次循环的比较语句上边。

而事实上,比较语句是有很大优化空间的,我们假设你要循环10000次,结果你从第一次开始就不断的比较是否达到上界值,这是不是很徒劳呢?

我们写一个达夫设备的函数用来测试执行时间(参考网上资源,这个测试不难,不同测试会有不同效果,大家可以自行测试一下):

int duff_device(int a)
{
    resigter x = 0;
    int n = (a) / 10;
    switch(a%10){
        case 0:do{ x++;
        case 9:x++; 
        case 8:x++;   
        case 7:x++;  
        case 6:x++;   
        case 5:x++;   
        case 4:x++;   
        case 3:x++;   
        case 2:x++;   
        case 1:x++;   
        }while(--n>0)
    }
    return x;
}

测试主函数如下

#include 
#define count 999999999
long int overtime = count;
int main()
{
    printf("over %d",duff_device(overtime));
    return 0;
}

执行时间如下

现在我们看一下传统的循环的执行时间,其测试代码如下:

int classical(int a)
{
    register x=0;
    do{
        x ++;
    }while(--a>0);
    return x;
}

测试主函数如下

#include 
#define count 999999999
long int overtime = count;
int main()
{
    printf("over %d",classical(overtime));
    return 0;
}

执行时间如下

结果显示达夫设备确实缩短了不少时间,这里x的定义是要用register关键字,这样cpu就会把x尽可能存入cpu内部的寄存器,新的cpu应该会有很通用寄存器使用。

值得一提的是,针对串行复制的需求,标准C语言库提供了memcpy函数,而其效率不会比斯特劳斯鲁普版的达夫设备低,并可能包含了针对特定架构的优化,从而进一步大幅提升执行效率。

从不同角度看达夫设备

从语言的角度来看

我个人觉得这种写法不是很值得我们借鉴。毕竟这不是符合我们“正常”逻辑的代码,至少C/C++标准不会保证这样的代码一定不会出错。

另外, 这种代码冷知识,估计有很多人根本都没见过,如果自己写的代码别人看不懂,估计会被骂的。

从算法的角度来看

我觉得达夫设备是个很高效、很值得我们去学习的东西。把一次消耗相对比较高的操作“分摊“到了多次消耗相对比较低的操作上面,就像vector中实现可变长度的数组的思想那样,节省了大量的机器资源,也大大提高了程序的效率。这是值得我们去学习的。

总结

达夫设备能实现的优化效果日趋在减弱,时代在变化,语言在发展,硬件设备在变化,编译器性能优化,除非特殊的需求下,一般还是没必要做像这种层次的性能考量的。不过,这种奇妙的 switch-case 写法经常研究一下还是很有乐趣的,你们觉得呢……

—— The End —


往期推荐



再见华为!一位嵌入式大佬的8年励志总结

会旋转的电弧,你看过吗?

整整2年!一晃就没了

显微镜下看英特尔芯片

详细的设计文档该怎么写?请注意这些地方...

动手DIY一个电机

高手经验分享,嵌入式开发出现BUG的常见原因


点击上方名片关注我

你点的每个好看,我都认真当成了喜欢
小麦大叔 一位热衷技术的攻城狮,懂点技术,会讲故事,交个朋友?
评论
  • 每日可见的315MHz和433MHz遥控模块,你能分清楚吗?众所周知,一套遥控设备主要由发射部分和接收部分组成,发射器可以将控制者的控制按键经过编码,调制到射频信号上面,然后经天线发射出无线信号。而接收器是将天线接收到的无线信号进行解码,从而得到与控制按键相对应的信号,然后再去控制相应的设备工作。当前,常见的遥控设备主要分为红外遥控与无线电遥控两大类,其主要区别为所采用的载波频率及其应用场景不一致。红外遥控设备所采用的射频信号频率一般为38kHz,通常应用在电视、投影仪等设备中;而无线电遥控设备
    华普微HOPERF 2025-01-06 15:29 160浏览
  • 大模型的赋能是指利用大型机器学习模型(如深度学习模型)来增强或改进各种应用和服务。这种技术在许多领域都显示出了巨大的潜力,包括但不限于以下几个方面: 1. 企业服务:大模型可以用于构建智能客服系统、知识库问答系统等,提升企业的服务质量和运营效率。 2. 教育服务:在教育领域,大模型被应用于个性化学习、智能辅导、作业批改等,帮助教师减轻工作负担,提高教学质量。 3. 工业智能化:大模型有助于解决工业领域的复杂性和不确定性问题,尽管在认知能力方面尚未完全具备专家级的复杂决策能力。 4. 消费
    丙丁先生 2025-01-07 09:25 108浏览
  • 村田是目前全球量产硅电容的领先企业,其在2016年收购了法国IPDiA头部硅电容器公司,并于2023年6月宣布投资约100亿日元将硅电容产能提升两倍。以下内容主要来自村田官网信息整理,村田高密度硅电容器采用半导体MOS工艺开发,并使用3D结构来大幅增加电极表面,因此在给定的占位面积内增加了静电容量。村田的硅技术以嵌入非结晶基板的单片结构为基础(单层MIM和多层MIM—MIM是指金属 / 绝缘体/ 金属) 村田硅电容采用先进3D拓扑结构在100um内,使开发的有效静电容量面积相当于80个
    知白 2025-01-07 15:02 139浏览
  • 「他明明跟我同梯进来,为什么就是升得比我快?」许多人都有这样的疑问:明明就战绩也不比隔壁同事差,升迁之路却比别人苦。其实,之间的差异就在于「领导力」。並非必须当管理者才需要「领导力」,而是散发领导力特质的人,才更容易被晓明。许多领导力和特质,都可以通过努力和学习获得,因此就算不是天生的领导者,也能成为一个具备领导魅力的人,进而被老板看见,向你伸出升迁的橘子枝。领导力是什么?领导力是一种能力或特质,甚至可以说是一种「影响力」。好的领导者通常具备影响和鼓励他人的能力,并导引他们朝着共同的目标和愿景前
    优思学院 2025-01-08 14:54 47浏览
  • 故障现象一辆2017款东风风神AX7车,搭载DFMA14T发动机,累计行驶里程约为13.7万km。该车冷起动后怠速运转正常,热机后怠速运转不稳,组合仪表上的发动机转速表指针上下轻微抖动。 故障诊断 用故障检测仪检测,发动机控制单元中无故障代码存储;读取发动机数据流,发现进气歧管绝对压力波动明显,有时能达到69 kPa,明显偏高,推断可能的原因有:进气系统漏气;进气歧管绝对压力传感器信号失真;发动机机械故障。首先从节气门处打烟雾,没有发现进气管周围有漏气的地方;接着拔下进气管上的两个真空
    虹科Pico汽车示波器 2025-01-08 16:51 51浏览
  • 在智能家居领域中,Wi-Fi、蓝牙、Zigbee、Thread与Z-Wave等无线通信协议是构建短距物联局域网的关键手段,它们常在实际应用中交叉运用,以满足智能家居生态系统多样化的功能需求。然而,这些协议之间并未遵循统一的互通标准,缺乏直接的互操作性,在进行组网时需要引入额外的网关作为“翻译桥梁”,极大地增加了系统的复杂性。 同时,Apple HomeKit、SamSung SmartThings、Amazon Alexa、Google Home等主流智能家居平台为了提升市占率与消费者
    华普微HOPERF 2025-01-06 17:23 195浏览
  •  在全球能源结构加速向清洁、可再生方向转型的今天,风力发电作为一种绿色能源,已成为各国新能源发展的重要组成部分。然而,风力发电系统在复杂的环境中长时间运行,对系统的安全性、稳定性和抗干扰能力提出了极高要求。光耦(光电耦合器)作为一种电气隔离与信号传输器件,凭借其优秀的隔离保护性能和信号传输能力,已成为风力发电系统中不可或缺的关键组件。 风力发电系统对隔离与控制的需求风力发电系统中,包括发电机、变流器、变压器和控制系统等多个部分,通常工作在高压、大功率的环境中。光耦在这里扮演了
    晶台光耦 2025-01-08 16:03 44浏览
  • By Toradex 秦海1). 简介嵌入式平台设备基于Yocto Linux 在开发后期量产前期,为了安全以及提高启动速度等考虑,希望将 ARM 处理器平台的 Debug Console 输出关闭,本文就基于 NXP i.MX8MP ARM 处理器平台来演示相关流程。 本文所示例的平台来自于 Toradex Verdin i.MX8MP 嵌入式平台。  2. 准备a). Verdin i.MX8MP ARM核心版配合Dahlia载板并
    hai.qin_651820742 2025-01-07 14:52 102浏览
  • 本文介绍编译Android13 ROOT权限固件的方法,触觉智能RK3562开发板演示,搭载4核A53处理器,主频高达2.0GHz;内置独立1Tops算力NPU,可应用于物联网网关、平板电脑、智能家居、教育电子、工业显示与控制等行业。关闭selinux修改此文件("+"号为修改内容)device/rockchip/common/BoardConfig.mkBOARD_BOOT_HEADER_VERSION ?= 2BOARD_MKBOOTIMG_ARGS :=BOARD_PREBUILT_DTB
    Industio_触觉智能 2025-01-08 00:06 84浏览
  • 这篇内容主要讨论三个基本问题,硅电容是什么,为什么要使用硅电容,如何正确使用硅电容?1.  硅电容是什么首先我们需要了解电容是什么?物理学上电容的概念指的是给定电位差下自由电荷的储藏量,记为C,单位是F,指的是容纳电荷的能力,C=εS/d=ε0εrS/4πkd(真空)=Q/U。百度百科上电容器的概念指的是两个相互靠近的导体,中间夹一层不导电的绝缘介质。通过观察电容本身的定义公式中可以看到,在各个变量中比较能够改变的就是εr,S和d,也就是介质的介电常数,金属板有效相对面积以及距离。当前
    知白 2025-01-06 12:04 209浏览
  • 根据环洋市场咨询(Global Info Research)项目团队最新调研,预计2030年全球无人机锂电池产值达到2457百万美元,2024-2030年期间年复合增长率CAGR为9.6%。 无人机锂电池是无人机动力系统中存储并释放能量的部分。无人机使用的动力电池,大多数是锂聚合物电池,相较其他电池,锂聚合物电池具有较高的能量密度,较长寿命,同时也具有良好的放电特性和安全性。 全球无人机锂电池核心厂商有宁德新能源科技、欣旺达、鹏辉能源、深圳格瑞普和EaglePicher等,前五大厂商占有全球
    GIRtina 2025-01-07 11:02 115浏览
我要评论
0
点击右上角,分享到朋友圈 我知道啦
请使用浏览器分享功能 我知道啦