Why is the for() function faster than ES6 map() and some() for finding duplicates?

Question

I wanted to benchmark the function that I am using to find out if there is a duplicated attribute in an array of objects using map() and some() versus another function that does the same thing but using a for() inside another for().

let array = [ { "value": 41}, { "value": 12}, { "value": 32} ];

let itens = array.map(x => x.value);

let haveDuplicate = itens.some((item, idx) => itens.indexOf(item) !== idx);

versus:

let array = [ { "value": 41}, { "value": 12}, { "value": 32} ];

let haveDuplicate = false;

for (let i = 0; i < array.length; i++) {
    let x = array[i];
    for (let j = (i + 1); j < array.length; j++) {
        if (array[j]) {
            let y = array[j];
            if (x.value === y.value) {
                haveDuplicate = true;
                return;
            } else {
                haveDuplicate = false;
            }
        }
    }
}

Using JsPerf I can see that the function that uses map() and some() runs 90% ~ 100% slower. Click here to check the benchmark

Can someone explain to me why?

EDIT: this question is duplicate of this one: Why most JavaScript native functions are slower than their naive implementations?

Thank you for asking this question. The use of `.map()`, `.reduce()`, etc. are becoming chronically overused in our community. Imagine putting 500 `.map()` calls, each 80% slower, into an app..uhg. — Randy Casburn, Apr 06 '18 at 01:27
What is this supposed to do? `let a = x => x.value; let itens = array.map(a);` — zer00ne, Apr 06 '18 at 01:30
The Array methods call a function (the callback you pass to them) for each element in the array, whereas the loop doesn't call any. — ibrahim mahrir, Apr 06 '18 at 01:30
**Loop iterations:** your logic, your logic, your logic, your logic, ... **Array methods iterations:** function call + your logic + internal logic, function call + your logic + internal logic, function call + your logic + internal logic, ... — ibrahim mahrir, Apr 06 '18 at 01:33
`.map()` - Internally: **Pre-loop:** Create an Object, steps call 5 internal functions. **Each-Iternation:** steps call 5 internal functions and the external callback function. `for()` - internally: **Pre-loop**: 1 internal function call, **Each-Iteration:** 6-7 internal function calls. — Randy Casburn, Apr 06 '18 at 01:48
keep in mind the internal function calls mentioned are in machine language code; while the `.map()` external callback is JavaScript code run in the VM (V8) — Randy Casburn, Apr 06 '18 at 01:50
Your premise is a bit biased: try to initiate your array with 30000 objects and you'll see the some one is faster. — Kaiido, Apr 06 '18 at 01:58
map() does more: outputs new arrays, filters empty slots ex: `Array(55).map(f)`, accepts an optional `this` context, etc. `_.map` is a closer approximation to for loops, without all the spec-required baggage. — dandavis, Apr 06 '18 at 02:05
Gonna review all the comments for understanding, but I did a research and found 4 mainly used methods for this purpose, doing the benchmark here: https://jsperf.com/testing-performance-finding-duplicate-value-javascript — cassmtnr, Apr 06 '18 at 04:08
It really [should be equally fast](https://youtu.be/EhpmNyR2Za0?t=17m15s) (apart from having to create an extra array). — Bergi, Apr 06 '18 at 14:35
@TheReason How come it is a possible duplicate if I am not using forEach in this question? Unflag please. — cassmtnr, Apr 06 '18 at 15:01
My doubt is between map/some versus for(), also I am updating tonight the question to include more information. — cassmtnr, Apr 06 '18 at 15:03
@CassianoMontanari take a look at general overview about this problem [`here`](https://stackoverflow.com/questions/21037888/why-most-javascript-native-functions-are-slower-than-their-naive-implementations) — The Reason, Apr 06 '18 at 15:05

Bryan Chen · Accepted Answer · 2018-04-06T02:11:42.843

3

There are few reasons the loop version is faster.

The .map version can have overhead of calling functions, which requires allocate memory, push to stack, some runtime checking the function is callable, etc. It may get optimized, or not.
The code are not equivalent. .indexOf need to scan the whole array if item does not exist where as the for loop version the second loop does not always scan the whole array.

Also, you better to use Set (or just object incase Set is not available) to do the duplicate check.

Pick the right data structure/algorithm is usually the most important optimization step.

let itens = array.map(x => x.value);

haveDuplicate = new Set(itens).size !== itens.length

edited Apr 06 '18 at 02:11

answered Apr 06 '18 at 02:06

Bryan Chen

45,816
18
112
143

2

*"Pick the right data structure/algorithm is usually the most important optimization step."* And it's not always an easy step. e.g, the Set way would be slower than any other with a big Array which has duplicate values at the beginning of the array. – Kaiido Apr 06 '18 at 02:26
@Kaiido you may have a very specific use case, which a specific solution will perform better for you. But here I just provide a general solution/suggestion that for the general use cases which I assumed is what OP wants. – Bryan Chen Apr 06 '18 at 02:44
Yes sure, just wanted to note that this is indeed an hard step, and that this *right algorithm choice* is not an easy thing and mainly depends on the data. – Kaiido Apr 06 '18 at 02:46
That's true. Especially the right algorithm to do may change over time. e.g. when deal with cryptography and security – Bryan Chen Apr 06 '18 at 02:49
1

The faster algorithm would be `function hasDuplicates(array) { const set = new Set; for (const {value} of array) { if (set.has(value)) return true; else set.add(value); } return false; }` – Bergi Apr 06 '18 at 14:38
You should first emphasize this: **The codes are not equivalent.** The benchmark makes no sense in OP because algorithms are different. Once this fixed, OP can start comparing `.some` vs `for`. – RaphaMex Apr 06 '18 at 15:32
@RaphaMex can you please edit an test case to make the algorithms equivalent? – cassmtnr Apr 06 '18 at 20:12
@CassianoMontanari: I have no time for this, but it should not be hard to do. Write your `for` loop based on `some` [polyfill](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/some#Polyfill). Also, see Bergi's comment: you need no `map`. – RaphaMex Apr 07 '18 at 00:33

Why is the for() function faster than ES6 map() and some() for finding duplicates?

1 Answers1