又一个有趣的面试题

又一个有趣的面试题

大家还记得前些天的那个火柴棍式的面试题吗?很有趣吧。下面是我今天在StackExchange上看到的一个有趣的面试题。大家不妨一起来思考一下。问题如下——

有两个相同功能代码如下,请在在A,B,C是什么的情况下,请给出三个原因case 1比case 2快,还有三个原因case 2会比case 1要执行的快。(不考虑编译器优化)

for (i=0; i<N; ++i){
    A;
    B;
    C;
}
for (i=0; i<N; ++i){
    A;
}
for (i=0; i<N; ++i){
    B;
}
for (i=0; i<N; ++i){
    C;
}

我的第一个反应是——

  • case1 要快一些,因为只有一个i++的i<N的操作,而case 2却有三个,这在点上,case 1就比case 2要快。
  • case2如果要快的话,有一个原因是,A, B, C其中一个需要去先获得一个资源(比如一个锁),在case1下,每次都要去拿这个资源,而case2下,只需要拿一次然后。但这个可能是不对的,因为我无法想出一个相同的语句块放在case 1中会和放在case 2中有差别。(不过可能比较接近了)

继续思考:这个题有点像是“同步和异步”的问题,case 1是同步,case 2是异步,所以,异步快于同步,也许可以从这个方向出发,写出A, B, C的语句块。

不过,其要三个原因啊。各位,你们有想法吗

—-更新 1—-

刚才在twitter上与人讨论,发现又有一种情况,case 2要比case 1要快。比如,A, B, C分别访问是不同的内存块(数组),那么case 1就得在不同的内存块上来回切换寻址,而case2则可以连续地访问内存块。访问连续的内存效率要高。尤其是三块大内存。

—-更新 2—

正如本贴评论中所说的,CPU的cache也是其中一个因素。大家对底层知识了解的都很不错啊。赞一个。

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

好烂啊有点差凑合看看还不错很精彩 (17 人打了分,平均分: 3.82 )
Loading...

又一个有趣的面试题》的相关评论

  1. 很简单的一种情况,abc共享一个全局变量,a的第N次执行会导致此变量被至一个值,bc执时发现这个值就直接返回

  2. 刚好最近想换个环境,拿来练习一下。猜到几点:
    1,cache的影响,cache是分组的,假设是分成4组,那么地址最后两位一样的地址将被分到同一组,如果AB共享同一cache line,可能导致B每次都刷掉A的内容,引起大量的cache miss,这种情况下case2性能可能更好。
    2,CPU流水线的影响,假设ABC全是加法指令,case1中CPU是会进行流水操作的,case中却要每执行一次加法,再执行一次比较。但是如果B依赖A的结果,比如A:y=2*x, B:z=2*y,那么B必须等待A执行完才能进行,无法进行流水线操作。不过这种情况下,在case2中,因为所有的A都已经计算完成,就为B流水线操作创造了条件。
    3,磁盘寻道的影响,如果在A操作时磁头停下的位置刚好就是B的起始位置,那么case1比较有利,如果这N次循环中,假设要读A[N]次磁盘,它们之间的位置离得比较近,而与B比较远,那么明显case2中集中读完所有的A再读B会比较有效。
    4,缓存,前面主要是讲cache miss的情况,这里主要是指每读一次cache的时候,是读一块区域,如果ABC的数据都是在同一个cache线里,那么在case1中可能一次就全部读出来了,在执行BC时直接用就可以了。同理,如果这N次读取的A的值相邻,而与B无关,那么case2也许更有效,一次把所有的A全读出来。这理论同样适用于磁盘,因为linux系统都是先将数据读到高速缓存中,以块为单位,而实际要读的也许只有一个字节。
    5,假设A是申请大量内存的程序,B释放A申请内存的程序,想想会有什么现象?在case1中,申请释放,没有问题,在case2中就不一样的,当连续申请大量内存的时候,内存可能没有了,此时申请内存的程序就会被调度出动,然后尝试各种办法去收集一些内存(比如交换到磁盘上去),等有空间了再唤醒分配内存的程序,此时轻舟已过万重山了。
    6,假设A是CPU消耗型程序,它起来后就不停地检查B是否已经起来,如果起来了就结束,很明显,这种情况下case1要快,因为case2要N个满负荷的A都在跑了之后,B才起来,之后A才一个一个死去。由于case2的CPU压力较大,所以case2肯定要慢,当然多核就不一定了,只好进行核绑定了。同理如果A是要检查是否N个A都已经起来后死亡,那么case2应该先结束。
    7,还有中断没考虑到,中断在上半部的处理中是关中断的,如果这段时间发中断,是会丢的,只要想办法让谁在这段时间内多丢一些中断,那么处理时间就会变少,嗯,应该也有办法!

  3. 还有另一种情况,就是:
    A=B=C=() => i – 0.4
    case1死循环了;case2不会死循环~~~

  4. 1.当A,B,C的运算需要用到上次运算结果时,2会比1快
    2.当A,B,C的运算需要条件判断时,2会比1快

  5. 这种题真是没啥意思.试想一下,那只不过是在考虑在什么情况下满足什么条件,完全是脱离实际出一道题,让其去反推实际多少种情况会出现什么现象.

  6. 这是我QQ好友的答案:case1比case2快
    情况1:
    A: nop
    B: i++
    C: i–
    情况2:
    A: break
    B: nop
    C: nop
    情况3:
    A: i++
    B: nop
    C: nop
    case2比case1快按同样的思路即可解决。

  7. 一般来说只用一个循环的快。 另外记起以前读martin flower的重构时有说到一种情况就是访问大量数据时CPU cache失效的情况下有可能多个循环的快。

  8. case2比case1快的一个原因:如果只有一个物理页架的话,case1中每次循环A,B,C都要互相更换;case2的话循环之间只需要切换一次就行了。

  9. 从做事情的角度考虑,假设ABC都是画直线,那么1>2;
    而如果A是画直线,B是画方块,C是画圆,那么2>1。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注