else语句会拖慢运行时间?
在做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 回复
不必太抠细节,后面还有 三数之和,四数之和 等你。有你扣细节的时候。 这个东西还是经过基准测试再说吧,不过一般来说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 @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打印出的无效信息过多了。