Javascript jQuery.grep 与 Array.filter 的性能

Performance of jQuery.grep vs. Array.filter

提问by Christoph

In a questionit was discussed on how jQuery and native JS would perform against each other.

在一个问题中，讨论了 jQuery 和原生 JS 将如何相互执行。

While of course the vanilla solution performs a lot faster because it does not process the whole array I proposed the usage of Array.filterwhich I was pretty confident would be at least faster than $.grep.

当然，香草解决方案的执行速度要快得多，因为它不处理整个数组，我建议使用Array.filter它，我非常有信心至少比$.grep.

Surprisingly after adding it to the test I was taught a lesson: Testsuite

令人惊讶的是，在将其添加到测试中后，我学到了一课：Testsuite

Edgecasesof course have a different outcome.

Edgecases当然有不同的结果。

Anyone having an idea why $.grepis supposed to be over 3 times faster than the native method Arrray.filter?

任何人都知道为什么$.grep应该比本地方法快 3 倍以上Arrray.filter？

Edit: I modified the test to use the filter shim from MDNand the results are pretty interesting:

编辑：我修改了测试以使用来自 MDN的过滤器垫片，结果非常有趣：

• Chrome: Even MDN shim is faster than the native method, jQuery way ahead
• Firefox: shim a bit slower than native method, jQuery way ahead

• Chrome：即使 MDN shim 也比原生方法快，jQuery 遥遥领先
• Firefox：shim 比本地方法慢一点，jQuery 遥遥领先

and finally a result like i was hoping it to see in

最后是我希望它看到的结果

• Internet Explorer: native method is the fastest, then jQuery, shim is slowest (perhaps this is just the result of IEs rather weak JS-engine...)

• Internet Explorer：native 方法最快，然后是 jQuery，shim 最慢（也许这只是 IE 比较弱的 JS 引擎的结果......）

回答by MarcoK

As found on this blog post(which also does the same kind of tests):

正如在这篇博客文章中发现的那样（它也进行了相同类型的测试）：

If you read the documentation for filter, you will see why it's so much slower.

1. It ignores deleted values and gaps in the array
2. It optionally sets the execution context of the predicate function
3. It prevents the predicate function from mutating the data

如果您阅读 的文档filter，您就会明白为什么它的速度如此之慢。

1. 它忽略数组中已删除的值和间隙
2. 它可以选择设置谓词函数的执行上下文
3. 它防止谓词函数改变数据

回答by Mathias Bynens

Section 15.4.4.20 of the ECMAScript 5.1 specdefines Array.prototype.filter(callbackfn, thisArg)as follows:

ECMAScript 5.1 规范的第 15.4.4.20 节定义Array.prototype.filter(callbackfn, thisArg)如下：

callbackfnshould be a function that accepts three arguments and returns a value that is coercible to the Boolean value trueor false. filtercalls callbackfnonce for each element in the array, in ascending order, and constructs a new array of all the values for which callbackfnreturns true. callbackfnis called only for elements of the array which actually exist; it is not called for missing elements of the array.

If a thisArgparameter is provided, it will be used as the thisvalue for each invocation of callbackfn. If it is not provided, undefinedis used instead.

callbackfnis called with three arguments: the value of the element, the index of the element, and the object being traversed.

filterdoes not directly mutate the object on which it is called but the object may be mutated by the calls to callbackfn.

The range of elements processed by filter is set before the first call to callbackfn. Elements which are appended to the array after the call to filter begins will not be visited by callbackfn. If existing elements of the array are changed their value as passed to callbackfnwill be the value at the time filter visits them; elements that are deleted after the call to filter begins and before being visited are not visited.

callbackfn应该是一个函数，它接受三个参数并返回一个可强制转换为布尔值true或的 值false。对数组中的每个元素按升序filter调用callbackfn一次，并构造一个包含所有callbackfn返回值的新数组true。callbackfn仅对实际存在的数组元素调用；不需要数组的缺失元素。

如果thisArg提供了参数，它将用作this每次调用的值callbackfn。如果未提供， undefined则改为使用。

callbackfn使用三个参数调用：元素的值、元素的索引和被遍历的对象。

filter不会直接改变调用它的对象，但该对象可能会因调用callbackfn.

filter 处理的元素范围在第一次调用 之前设置callbackfn。调用过滤器开始后附加到数组的元素将不会被 访问callbackfn。如果数组的现有元素被更改，则它们传递给 callbackfn的值将是过滤器访问它们时的值；在调用过滤器开始之后和被访问之前被删除的元素不会被访问。

That in itself is already a lot of work; a lot of steps that the ECMAScript engine needs to perform.

这本身就已经是很多工作了；ECMAScript 引擎需要执行的许多步骤。

Then it goes on to say the following:

然后它继续说以下内容：

When the filter method is called with one or two arguments, the following steps are taken:

Let Obe the result of calling ToObjectpassing the thisvalue as the argument. Let lenValuebe the result of calling the [[Get]]internal method of Owith the argument length. Let lenbe ToUint32(lenValue). If IsCallable(callbackfn) is false, throw a TypeError exception. If thisArg was supplied, let T be thisArg; else let T be undefined. Let A be a new array created as if by the expression new Array() where Array is the standard built-in constructor with that name. Let k be 0. Let to be 0. Repeat, while k < len Let Pk be ToString(k). Let kPresent be the result of calling the [[HasProperty]] internal method of O with argument Pk. If kPresent is true, then Let kValue be the result of calling the [[Get]] internal method of O with argument Pk. Let selected be the result of calling the [[Call]] internal method of callbackfn with T as the this value and argument list containing kValue, k, and O. If ToBoolean(selected) is true, then Call the [[DefineOwnProperty]] internal method of A with arguments ToString(to), Property Descriptor {[[Value]]: kValue, [[Writable]]: true, [[Enumerable]]: true, [[Configurable]]: true}, and false. Increase to by 1. Increase k by 1. Return A.

The length property of the filter method is 1.

NOTE The filter function is intentionally generic; it does not require that its this value be an Array object. Therefore it can be transferred to other kinds of objects for use as a method. Whether the filter function can be applied successfully to a host object is implementation-dependent.

当使用一两个参数调用过滤器方法时，将采取以下步骤：

让O是调用ToObject将this值作为参数传递的结果。让lenValue成为使用参数调用[[Get]]内部方法的结果。让是OlengthlenToUint32(lenValue). 如果 IsCallable(callbackfn) 为 false，则抛出 TypeError 异常。如果提供了 thisArg，则设 T 为 thisArg；否则让 T 未定义。让 A 成为一个新数组，就像由表达式 new Array() 创建的一样，其中 Array 是具有该名称的标准内置构造函数。设 k 为 0。设为 0。重复，而 k < len 设 Pk 为 ToString(k)。令 kPresent 是调用 O 的 [[HasProperty]] 内部方法和参数 Pk 的结果。如果 kPresent 为真，则让 kValue 是调用 O 的 [[Get]] 内部方法的结果，参数为 Pk。令 selected 是调用 callbackfn 的 [[Call]] 内部方法的结果，其中 T 作为 this 值和包含 kValue、k 和 O 的参数列表。如果 ToBoolean(selected) 为真，则调用 [[DefineOwnProperty]]带参数 ToString(to) 的 A 的内部方法，属性描述符 {[[Value]]: kValue, [[Writable]]: true, [[Enumerable]]: true, [[Configurable]]: true}, 和 false。增加到 1。将 k 增加 1。返回 A。

filter 方法的长度属性为 1。

注意过滤器功能是有意通用的；它不要求它的 this 值是一个 Array 对象。因此，它可以转移到其他类型的对象以用作方法。过滤器功能是否可以成功应用于宿主对象取决于实现。

Some things to note about this algorithm:

关于这个算法的一些注意事项：

• It prevents the predicate function from mutating the data
• It optionally sets the execution context of the predicate function
• It ignores deleted values and gaps in the array

• 它防止谓词函数改变数据
• 它可以选择设置谓词函数的执行上下文
• 它忽略数组中已删除的值和间隙

In a lot of cases, none of these things are needed. So, when writing a filtermethod of your own, most of the time you wouldn't even bother to perform these steps.

在很多情况下，这些东西都不需要。因此，在编写filter自己的方法时，大多数情况下您甚至不会费心执行这些步骤。

Every ES5.1-compliant JavaScript engine must conform to that algorithm, and must thus perform all those steps every time you use Array#filter.

每个符合 ES5.1 的 JavaScript 引擎都必须符合该算法，因此每次使用Array#filter.

It should be no surprise that any custom-written method that only performs a part of those steps will be faster :)

任何只执行这些步骤的一部分的自定义编写的方法都会更快，这应该不足为奇:)

If you write your own filterfunction, chances are it's not gonna be as complex as the above algorithm. Perhaps you won't be converting the array to an object at all, as depending on the use case it may not be needed just to filter the array.

如果您编写自己的filter函数，则它可能不会像上述算法那样复杂。也许您根本不会将数组转换为对象，因为根据用例可能不需要仅过滤数组。

回答by nicojs

I found out something interesting. As explained by MarcoK, $.grep is just a simple implementation with a for loop. Filter is slower in most cases, so the implementation must be different. I think i found the answer:

我发现了一些有趣的事情。正如 MarcoK 所解释的，$.grep 只是一个带有 for 循环的简单实现。大多数情况下过滤器较慢，因此实现必须不同。我想我找到了答案：

function seak (e) { return e === 3; }

var array = [1,2,3,4,5,6,7,8,9,0], i, before;
array[10000] = 20; // This makes it slow, $.grep now has to iterate 10000 times.
before = new Date();

// Perform natively a couple of times.
for(i=0;i<10000;i++){
    array.filter(seak);
}

document.write('<div>took: ' + (new Date() - before) + '</div>'); // took: 8515 ms (8s)

before = new Date();

// Perform with JQuery a couple of times
for(i=0;i<10000;i++){
    $.grep(array, seak);
}
document.write('<div>took: ' + (new Date() - before) + '</div>'); // took: 51790 ms  (51s)

The native 'filter' is much faster in this case. So i think it iterates the properties rather than the array index.

在这种情况下，原生“过滤器”要快得多。所以我认为它迭代属性而不是数组索引。

Now lets get back to 'big' problems ;).

现在让我们回到“大”问题；)。

回答by Riek Steenwegen

Isn't your script wrong?

你的剧本是不是错了？

For array.filteryou are doing the measurement 1000 times and present it by taken the sum divided by 1000

因为array.filter您正在进行 1000 次测量，并通过将总和除以 1000 来表示它

For JQuery.grepyou are doing the measurement 1 time and present it by taken the sum divided by 1000.

因为JQuery.grep您正在进行 1 次测量，并通过将总和除以 1000 来表示它。

That would mean your grep is actually 1000 times slower than the value you use for comparison.

这意味着您的 grep 实际上比您用于比较的值慢 1000 倍。

Quick test in firefox gives:

Firefox 中的快速测试给出：

Machine 1:
average filter - 3.864
average grep - 4.472

Machine2:
average filter - 1.086
average grep - 1.314

Quick test in chrome gives:

chrome 中的快速测试给出：

Machine 1:
average filter - 69.095
average grep - 34.077

Machine2:
average filter - 18.726
average grep - 9.163

Conclusion in firefox (50.0) is a lot faster for your code path, and filter is about 10-15% faster than jquery.grep.

firefox (50.0) 中的结论对于您的代码路径要快得多，而 filter 比 jquery.grep 快 10-15%。

Chrome is extremely slow for your code path, but grep seems to be 50% faster than array.filter here making it 900% slower than the firefox run.

Chrome 对于您的代码路径非常慢，但 grep 似乎比 array.filter 快 50%，这使它比 firefox 运行慢 900%。

回答by Matas Vaitkevicius

TLDR;Grep is faster by a magnitude... (hint on why can be found here)

TLDR；Grep 快了一个数量级......（提示为什么可以在这里找到）

It looks to me like .filter forces it's this to Object, checks the callback IsCallable and sets this in it as well as checking for existence of property in each iteration whereas .grep assumes and skips these steps, meaning there is slightly less going on.

在我看来，.filter 将其强制为 Object，检查回调 IsCallable 并将其设置在其中，并在每次迭代中检查属性的存在，而 .grep 假设并跳过这些步骤，这意味着发生的事情会少一些。

Here is the script I used for testing:

这是我用于测试的脚本：

function test(){
var array = [];
for(var i = 0; i<1000000; i++)
{
array.push(i);
}

var filterResult = []
for (var i = 0; i < 1000; i++){
var stime = new Date();
var filter = array.filter(o => o == 99999);
filterResult.push(new Date() - stime);
}

var grepResult = [];
var stime = new Date();
var grep = $.grep(array,function(i,o){
return o == 99999;
});
grepResult.push(new Date() - stime);

$('p').text('average filter - '+(filterResult.reduce((pv,cv)=>{ return pv +cv},0)/1000))
$('div').text('average grep - '+(grepResult.reduce((pv,cv)=>{ return pv + cv},0)/1000))
}
test();

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<p></p>
<div></div>