V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
GTD
V2EX  ›  Java

关于 for 循环中的 j - 1>=0 和 j > 0 的效率问题,太诡异了

  •  
  •   GTD · 2020-11-12 11:55:53 +08:00 · 3312 次点击
    这是一个创建于 1457 天前的主题,其中的信息可能已经有所发展或是发生改变。

    先看图,先用 j > 0 跑选择排序

    然后改成 j - 1 >= 0,继续测试选择排序

    这个算法一模一样,什么都没改,我跑了 30 多次,每次用 j - 1 > =0 都是 17 秒左右,而用 j >0 都在 16 秒左右,这两个效率怎么会有这么大差别,不应该啊。

    而且我跑了 30 多次,每次都一样,一个是 16 秒,一个是 17 秒,只是小数点后不一样而已

    第 1 条附言  ·  2020-11-12 14:09:37 +08:00
    问了一个大佬,大佬这么说:

    “第二种写法每次要多计算一个 j - 1,也就是多了一个减法操作:)

    对于 10 万级别的数据,内层循环执行的级别是 100 亿,也就是第二种写法多了这么多次操作,差 0.6 秒,我觉得差不多”
    19 条回复    2020-11-12 17:44:09 +08:00
    xuanbg
        1
    xuanbg  
       2020-11-12 11:59:58 +08:00
    >=难道没有多跑一次吗?
    GTD
        2
    GTD  
    OP
       2020-11-12 12:00:52 +08:00
    @xuanbg #1 我跑了 30 多次,都是差不多一样,一个是 17 秒 一个是 16 秒
    GTD
        3
    GTD  
    OP
       2020-11-12 12:01:20 +08:00
    @xuanbg #1 哦哦,你说>=效率低一点,会多跑一次吗?
    chendy
        4
    chendy  
       2020-11-12 12:27:52 +08:00
    代码发出来大家试试?
    v2yybb
        5
    v2yybb  
       2020-11-12 12:32:36 +08:00
    j-1>=0;每次都计算 j-1,然后才判断.
    j>0 的话 每次只判断
    xiangyuecn
        6
    xiangyuecn  
       2020-11-12 12:32:48 +08:00
    你理想中认为编译器是智能的,实机上编译器是一个智障。
    chendy
        7
    chendy  
       2020-11-12 12:35:32 +08:00
    多了一步减法,字节码多了一条 isub
    大于小于 和 大于等于 小于等于 都是一条字节码,没区别
    JeffGe
        8
    JeffGe  
       2020-11-12 12:36:54 +08:00 via Android
    你要说 j - 1 >= 0 快,才叫诡异吧
    no1xsyzy
        9
    no1xsyzy  
       2020-11-12 12:41:38 +08:00
    ( JVM 不清楚,按对 C - asm 的理解应该差不多吧)
    j - 1 >= 0 是
    取 j,取 1,相减,取 0,比较并跳转
    j > 0 是
    取 j,取 0,比较并跳转
    即使理论上等效,但目前所有优化都是启发式的,不一定能发现最优解
    guixiexiezou
        10
    guixiexiezou  
       2020-11-12 13:02:16 +08:00
    所有 java 相关的,建议都热身后再跑测试,不然和你预想的有很大不一样
    dazhangpan
        11
    dazhangpan  
       2020-11-12 13:26:17 +08:00
    不负责任地瞎猜是在分支条件这里的逻辑影响了 CPU 分支预测器的正确率
    可以用 perf 抓一下看看 mispredict 的比例是不是上升了
    lakehylia
        12
    lakehylia  
       2020-11-12 13:44:44 +08:00
    试试 j - 1 >= 0 改成 j >= 1,看看时间是不是一样的。
    GTD
        13
    GTD  
    OP
       2020-11-12 14:15:59 +08:00
    @lakehylia #12 不行,刚刚试了一下,j >=1 还是一样,只有改成 j>0 才能 16s 左右
    Mohanson
        14
    Mohanson  
       2020-11-12 14:37:09 +08:00
    判断 j > 0 在 x86 上智商正常的编译器会用 jns 指令(Jump if not sign)而不会用比较跳转指令, 判断条件是 SF = 0

    判断 j >= 1 在 x86 上用的是 jg 指令(Jump if greater), 判断条件是 ZF = 0 and SF = OF

    以上是 gcc 的逻辑(我完全不会 java 也不知道 jvm 到底怎么操作的)
    geelaw
        15
    geelaw  
       2020-11-12 14:42:39 +08:00   ❤️ 12
    显然 j - 1 >= 0 和 j > 0 是完全不同的意思,因为 Java 规定有符号数的溢出行为。如果 j = -2147483648,那么 j - 1 >= 0 是 true 而 j > 0 是 false 。

    因此,编译器很难进行优化,故会采用先减后判断符号的方式,多做一次减法当然会慢。
    lakehylia
        16
    lakehylia  
       2020-11-12 15:22:17 +08:00
    @GTD 那结果就明显了,编译器在变量跟 0 的对比上有优化,而其他值没有。
    misaka19000
        17
    misaka19000  
       2020-11-12 15:23:50 +08:00
    直接看编译后的字节码,对比区别
    XuanFei990
        18
    XuanFei990  
       2020-11-12 17:23:53 +08:00
    我以为下边的会短呢,那才奇怪。
    多了一步减法操作吧,循环次数少,没什么感觉,循环次数多的话就产生明显差异了
    Yantc
        19
    Yantc  
       2020-11-12 17:44:09 +08:00   ❤️ 1
    @GTD

    j >=1:先做 j-1,再将 j-i 后的 ans 和 0 判断大小还要看是否存在溢出
    j>0:直接将 j 的 bit 位或起来,就直接可判断,1:则 j 大于 0,0:则 j==0.

    显然第二种情况快啊
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2689 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 15:00 · PVG 23:00 · LAX 07:00 · JFK 10:00
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.