在JavaScript中实现LINQ——一次“失败”的尝试

这篇文章的起因是我在知乎上对JavaScript 函数式编程存在性能问题么?这个问题的回答。其实在这个问题之前挺久我就想做相关的尝试,但懒癌无药医,挖坑如山倒,填坑如抽丝。

废话不多说,走你。

C# 3.0引入了引以为豪的LINQ(Language INtergrated Query),可以用类函数式的方式操作集合(C#中的IEnumerable接口)。

在JS中,数组也有类似的filtermapreduce一类方法,但存在重复遍历问题,利用C#中LINQ的思路,给JS实现一套LINQ是否可行呢?

C#中的LINQ

C#中的LINQ是通过yield来避免重复遍历的,抽象的说,Where(对应filter)、Select(对应map)这类的方法调用的时候,都只会把操作“暂存”起来,直到调用了ToArrayAggregate(对应reduce)之类的方法,才会“驱动”它去进行遍历。

举一个简单的例子

1
2
3
4
5
var array = new []{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
var sum = array.Where(n => n % 2 === 0)
.Select(n => n + 3)
.Aggregate((sum, n) => sum + n, 0);
// 代码不一定能编译,我是裸写的

上面是一个最基本的filter/map/reduce的过程(下文也会继续用这个例子),只有在Aggregate调用的时候,才会对数组进行遍历,而WhereSelect只是一些类型为IQueryable<T>的中间过程。

C#中的LINQ得益于C#的yield关键字,配合First-Class-Function可以不费吹灰之力地构建IEnumerable<T>,而C#中的foreach提供了对IEnumerable<T>的语法糖,这样就可以很自然的对LINQ的中间结果进行二次加工,而不需要繁琐地手工调用.Next()

JS中的filter/map/reduce

JS中的原生数组就自带了filter/map/reduce等一系列函数化的集合操作方法,但使用中有一个隐患就是,每次调用它们都会进行一次完整的遍历,这样当用这样连写的风格,就会造成重复遍历

1
2
3
var sum = array.filter(n => n % 2 === 0)
.map(n => n + 3)
.reduce((sum, n) => sum + n, 0)

上面的代码,在filtermap被调用的时候,都会遍历一次数组,reduce的时候再遍历一次,这样总共就被遍历了三次,当集合比较大的时候,这估计不是大家所想见发生的事情。

如果在filter/map/reduce的回调函数里打印一些调试信息,我们会发现调用的次序大概会是这样的

1
2
3
4
5
6
7
8
9
10
11
12
filter
filter
filter
... x10
map
map
map
... x5
reduce
reduce
reduce
... x5

JS中的LINQ

yield/generator

ES6中有了yield和Generator Function(不熟悉的可以先回顾一下我几百年前写的这篇这篇文章),并且,由于Symbol.iteratorfor of语法的引入,能用生成器构造集合了,并且还能和for of无缝衔接。

也就是说,ES6已经有了C#那样优雅地实现LINQ的基础设施,我们就来实现一个简单的试试。

IQueryable

首先我们像C#那样实现一个IQueryable类,并且它通过Symbol.iterator能够支持被for of遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Queryable {
constructor(iterable) {
this.iterable = iterable
}
[Symbol.iterator]() {
let iterator = this.iterable[Symbol.iterator]()
return iterator
}
}
Array.prototype.asQueryable = function() {
return new Queryable(this)
}

由于我们是“面向接口编程”的,这里我们并不关心new Queryable(xxx)传入的是一个Array、一个Generator还是一个Queryable,反正它们都可以被for of遍历。

然后为了方便,在Array.prototype上挂了一个方法,别嫌脏,娱乐而已。

尝试一下

1
2
3
4
let arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for (let item in arr.asQueryable()) {
console.log(arr)
}

filter/map/reduce

我们的Queryable类已经可以享受for of语法糖的便利了,然后我们就可以基于这个给它愚快地添加各种集合操作方法了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
function* _filter(iterable, predicate) {
for (let item of iterable) {
let checked = predicate(item)
if (checked) {
yield item
}
}
}
function* _map(iterable, mapper) {
for (let item of iterable) {
let mapped = mapper(item)
yield mapped
}
}
class Queryable {
constructor(iterable) {
this.iterable = iterable
}
[Symbol.iterator]() {
let iterator = this.iterable[Symbol.iterator]()
return iterator
}
filter(predicate) {
let iterable = _filter(this, predicate)
return new Queryable(iterable)
}
map(mapper) {
let iterable = _map(this, mapper)
return new Queryable(iterable)
}
reduce(reducer, initial) {
let result = initial
for (let item of this) {
result = reducer(result, item)
}
return result
}
}

这里注意,filtermap分别调用了_filter_map方法,它们返回的结果都是Generator,我们知道一个Generator只定义了集合如何“被遍历”,而事实上它没有真正发生操作,需要调用next()或者for of(也就是next()的语法糖)来“驱动”它进行遍历。

reduce当中调用了for of,也就是它真正发生了遍历。

赶紧爽一爽

1
2
3
4
var sum = array.asQueryable()
.filter(n => n % 2 === 0)
.map(n => n + 3)
.reduce((sum, n) => sum + n, 0)

如果在filter/map/reduce的回调函数里打印一些调试信息,我们会发现调用的次序大概会是这样的

1
2
3
4
5
filter/map/reduce
filter
filter/map/reduce
filter
...

只遍历了一遍

扩展LINQ

有了上面三个方法我们可以顺便构造一下lengthtoArray这类的方法,比如

1
2
3
4
5
6
7
8
9
10
Queryable.prototype.length = function() {
return this.reduce(n => n + 1, 0)
}
Queryable.prototype.toArray = function() {
return this.reduce((arr, it) => {
arr.push(it)
return arr
}, [])
}

当然其实map/reduce都是foldl/foldr的具象(吃我一发安利,参考我写的使用JavaScript实现“真·函数式编程”,所以上面的那些方法其实都可以写得更“函数式”,但既然这篇文章只是为了实验,就不搞那么多幺蛾子了。

性能测试

我们用benchmark模块对上述代码进行性能测试,并且引入两个对照组,不多说了,直接看代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function useRawLoop() {
let result = 0
for (let i = 0; i < arr.length; ++i) {
let n = arr[i]
if (n % 2 === 0) {
n += 3
result += n
}
}
return result
}
function useLoop() {
let result = 0
for (let n of arr) {
if (isEven(n)) {
n = add3(n)
result = sum(result, n)
}
}
return result
}
function useArray() {
return arr.filter(isEven)
.map(add3)
.reduce(sum, 0)
}
function useLINQ() {
return arr.asQueryable()
.filter(isEven)
.map(add3)
.reduce(sum, 0)
}

用长度为100的数组进行测试,结果

1
2
3
4
RawLoop x 380,068 ops/sec ±1.01% (88 runs sampled)
Loop x 138,121 ops/sec ±1.91% (81 runs sampled)
Array x 59,682 ops/sec ±1.14% (89 runs sampled)
LINQ x 17,235 ops/sec ±1.69% (87 runs sampled)

可以看出,我们的LINQ性能非常非常的废柴,主要原因:

  • JS对Generator的优化非常废柴
  • JS对for of的优化非常废柴——因为它就是Generator#next()的语法糖

结论

虽然我们通过ES6的一系列新特性给JS实现了lazy的LINQ,避免重复遍历,是实现了,但想象中的性能提高却是化为泡影。

当然,通过不断优化,减少for of的使用,改为手工.next()遍历,也许性能还会高一些,但一来我不太相信它会有很明显的变化。二来更重要的是,不用for of的话,我们就不能实现“无痛”的集合操作代码编写了,既然已经不能“无痛”,那么同样“痛”的方法自然有性能更优的,而且根本不需要Symbol.iterator、Generator等等这一大堆新特性。

所以这是一个成功的尝试,也是一个失败的尝试。成功之处在于很开心能看到ES6有如此强大的基础设施用于编写优雅代码,发挥创造力。失败之处么,自然是由于现阶段的JS引擎并没有对这些新引入的特性进行值得称道的优化,这也提醒我对于这些新特性——至少是说,需要runtime支持的新特性——不要盲目的追新。

更新

时间来到2017年8月1日中国人民解放军建军90周年,在node.js 8.x上,新的V8对for-of和Iterator进行了惊人的优化,上面的测试结果变成了:

1
2
3
4
RawLoop x 422,242 ops/sec ±1.31% (84 runs sampled)
Loop x 974,206 ops/sec ±1.03% (82 runs sampled)
Array x 63,109 ops/sec ±1.11% (85 runs sampled)
LINQ x 115,294 ops/sec ±5.03% (86 runs sampled)

使用for-of遍历数组竟然比用for循环直接遍历还要快一倍这简直不科学,让我怀疑是不是掉进了陷阱!!!而且用LINQ方式也比用Array原生方法迭代更快了,快了将近一倍!

这意味着LINQ以后性能将会可以接受,它可行了!意味着在JS里面终于可以优雅地实现迭代器模式了!哦,这样啊,真是一个激动人心的好消息啊,反正我是懒得去把它写完的。