else语句会拖慢运行时间?
发布于 9 天前 作者 fulvaz 791 次浏览 来自 问答

在做leetcode的题目. 练习2sum的时候, 我的代码如下

var twoSum = function(nums, target) {
    const set = {};
    for (var i = 0; i < nums.length; i++) {
        const val = nums[i];
        const find = set[val];
        if (find !== undefined) {
            return [find, i,];
        } else {
            // 如果将来某个值满足target - nums[i], 则可以和这个位置匹配
            set[target - val] = i;
        }
    }
};

80 ms, 排在60%

然后看了排在80%的代码, 就比我少了一个else, 我自己测试一下代码

var twoSum = function(nums, target) {
    const set = {};
    
    for (var i = 0; i < nums.length; i++) {
        const val = nums[i];
        const find = set[val];
        if (find !== undefined) {
            return [find, i,];
        } 
		// 就这里去除了else
		// 如果将来某个值满足target - nums[i], 则可以和这个位置匹配
		set[target - val] = i;
    }
};

56 ms, 排88%

一个else语句能有这么大影响? 什么原理?

11 回复

看起来像是常数时间的差距,有没有多提交几次看看结果。。。

搞acm的时候要是被卡常数时间,会很想杀了出题人。。

不必太抠细节,后面还有 三数之和,四数之和 等你。有你扣细节的时候。 这个东西还是经过基准测试再说吧,不过一般来说else在代码解析上是要走代码块跳转,最终编译成汇编也是走了地址跳转,这样CPU还要进行分支预测,100%走else,何必再搞个else。

使用 v8 7.1.302.4 生成的字节码,两者一模一样:

[generated bytecode for function: twoSum]
Parameter count 3
Frame size 48
   22 E> 000001BA957CE3BA @    0 : a5                StackCheck 
   55 S> 000001BA957CE3BB @    1 : 7e                CreateEmptyObjectLiteral 
         000001BA957CE3BC @    2 : 26 f9             Star r2
   76 S> 000001BA957CE3BE @    4 : 0b                LdaZero 
         000001BA957CE3BF @    5 : 26 f8             Star r3
   88 S> 000001BA957CE3C1 @    7 : 28 03 00 00       LdaNamedProperty a0, [0], [0]
   81 E> 000001BA957CE3C5 @   11 : 69 f8 02          TestLessThan r3, [2]
         000001BA957CE3C8 @   14 : 99 45             JumpIfFalse [69] (000001BA957CE40D @ 83)
   63 E> 000001BA957CE3CA @   16 : a5                StackCheck 
  123 S> 000001BA957CE3CB @   17 : 25 f8             Ldar r3
  127 E> 000001BA957CE3CD @   19 : 2a 03 03          LdaKeyedProperty a0, [3]
         000001BA957CE3D0 @   22 : 26 fb             Star r0
  153 S> 000001BA957CE3D2 @   24 : 25 fb             Ldar r0
  156 E> 000001BA957CE3D4 @   26 : 2a f9 05          LdaKeyedProperty r2, [5]
         000001BA957CE3D7 @   29 : 26 fa             Star r1
  171 S> 000001BA957CE3D9 @   31 : 9c 1e             JumpIfUndefined [30] (000001BA957CE3F7 @ 61)
  209 S> 000001BA957CE3DB @   33 : 7a 01 07 25       CreateArrayLiteral [1], [7], #37
         000001BA957CE3DF @   37 : 26 f6             Star r5
         000001BA957CE3E1 @   39 : 0b                LdaZero 
         000001BA957CE3E2 @   40 : 26 f7             Star r4
         000001BA957CE3E4 @   42 : 25 fa             Ldar r1
  217 E> 000001BA957CE3E6 @   44 : 31 f6 f7 08       StaInArrayLiteral r5, r4, [8]
         000001BA957CE3EA @   48 : 0c 01             LdaSmi [1]
         000001BA957CE3EC @   50 : 26 f7             Star r4
         000001BA957CE3EE @   52 : 25 f8             Ldar r3
  223 E> 000001BA957CE3F0 @   54 : 31 f6 f7 08       StaInArrayLiteral r5, r4, [8]
         000001BA957CE3F4 @   58 : 25 f6             Ldar r5
  226 S> 000001BA957CE3F6 @   60 : a9                Return 
  316 S> 000001BA957CE3F7 @   61 : 25 fb             Ldar r0
  327 E> 000001BA957CE3F9 @   63 : 35 02 0a          Sub a1, [10]
         000001BA957CE3FC @   66 : 26 f6             Star r5
         000001BA957CE3FE @   68 : 25 f8             Ldar r3
  334 E> 000001BA957CE400 @   70 : 30 f9 f6 0b       StaKeyedProperty r2, r5, [11]
   97 S> 000001BA957CE404 @   74 : 25 f8             Ldar r3
         000001BA957CE406 @   76 : 4c 0d             Inc [13]
         000001BA957CE408 @   78 : 26 f8             Star r3
         000001BA957CE40A @   80 : 8a 49 00          JumpLoop [73], [0] (000001BA957CE3C1 @ 7)
         000001BA957CE40D @   83 : 0d                LdaUndefined 
  345 S> 000001BA957CE40E @   84 : a9                Return 
Constant pool (size = 2)
Handler Table (size = 0)

@justjavac 本来还想V8的优化器应该没这么强,但大佬验证过了,应该是妥了。 这种靠参数判断的都能进行优化,强。 —这句话不准确容易产生误导,请看我8楼回答

@justjavac @fulvaz 如果我只定义twoSum方法,打印出的汇编代码如下,else代表有else,noelse代表无else。 norun.png 根本没有执行,也就是说明jsutjavac的汇编是twoSum传入参数后执行后的优化结果。所以V8也是根据参数传入后再进行优化的。 但由于twoSum的在if内被return了,所以这个函数是不可能被采取分支的,也就是说要么是被return,要么else一定执行。如果我对这个函数稍作修改,并传入不通参数会怎么样呢?即if内的把return去除,同时传入不同参数,会是怎么样呢?即

else.js:

// else.js
var twoSum = function(nums, target) {
    const set = {};
    for (var i = 0; i < nums.length; i++) {
        const val = nums[i];
        const find = set[val];
        if (find !== undefined) {
            [find, i,];
        } else {
            // 如果将来某个值满足target - nums[i], 则可以和这个位置匹配
            set[target - val] = i;
        }
    }
};

twoSum([1,2,3],4)

elseno.js:

// elseno.js
var twoSum = function(nums, target) {
    const set = {};
    for (var i = 0; i < nums.length; i++) {
        const val = nums[i];
        const find = set[val];
        if (find !== undefined) {
            [find, i,];
        } 
		// 就这里去除了else
		// 如果将来某个值满足target - nums[i], 则可以和这个位置匹配
		set[target - val] = i;
    }
};

twoSum([1,2,undefined],4)

结果是不同的,如下: run.png

细心的人就会发现,else.js的汇编码,多出了地址跳转!我的一般理解,看来是没错的。而上文的汇编码正好一致,也恰好是这个方法的return造成。但这个并不代表V8的优化器的成本下降,即使是优化后是相同汇编码,但else可能造成走更多步的优化策略。

备注:汇编是使用目前v8的master分支的d8打印的,node打印出的无效信息过多了。

我忽略这个了,谢谢 @zy445566

@justjavac 并没有,你上文只是说了一个事实,我觉得可能太简单了,容易让人有错误的遐想。所以做了下补充

@zy445566 代码里是判断 undefined,我的测试代码居然没有使用 undefined,失误失误

回到顶部