DEV Community

loading...

Write a Custom JavaScript Filter Function that is 60% faster than Array.filter

functional_js profile image Functional Javascript 惻3 min read

Here is a simple rewrite of a javascript filter func...

/**
@func util
a custom high-performance filter

@perf
60% faster than the built-in JavaScript filter func

@typedef {(e: *) => boolean} filterFnAny
@param {filterFnAny} fn
@param {*[]} a
@return {*[]}
*/
const fil = (fn, a) => {
  const f = []; //final
  for (let i = 0; i < a.length; i++) {
    if (fn(a[i])) {
      f.push(a[i]);
    }
  }
  return f;
};

Here is a sample test to show how this func is used...

//@tests
const aNums = [1, 2, 3, 4, 5, 6, 7, 8];
log(fil(e => e < 5, aNums)); // [1, 2, 3, 4]

From this we create a runtime-enforced strongly-typed variant.
(We curry-ify it so we can use this func in our strongly-typed functional pipelines (See the sample usages below).

/**
@func curry
filter an arr of objs

@typedef {(e: object) => boolean} filterFnObjs
@param {filterFnObjs} fn
@return {(a: object[]) => object[]}
*/
export const filterObjs = fn => a => throwIfNotArrOfObjs(a) || fil(fn, a);

Here are three different idomatic usages of this strongly-typed filter...

//@tests
const objs = [{ n: 15 }, { n: 2 }];

//a.
log(filterObjs(o => o.n > 3)(objs)); // [ { n: 15 } ]

//b.
const p1 = pipeArrOfObjs(
  filterObjs(o => o.n > 3), lArr, // [ { n: 15 } ]
);
p1(objs);

//c.
const p2 = pipeNil(
  () => objs,
  filterObjs(o => o.n > 3), lArr, // [ { n: 15 } ]
);
p2();

Stongly-Typed Functional Pipeline Notes:

1.

Two runtime-enforced strongly-type pipe funcs indicate what type of data must be passed into the start of the pipe...

// invocation of this pipe must receive data of type "object[]",
// - otherwise it throws
pipeArrOfObjs
// invocation of this pipe must receive no arguments
// - otherwise it throws
pipeNil

2.

Funcs that begin with an "l" indicate a log func.
The "l()" func can receive any type, which will be logged.
"lArr()" must receive an arr, otherwise it throws.

3.

Test example "c." is what's called a "closure pipe", meaning it accepts data from it's outer scope, in this case via a lambda (anonymous function), the "objs" data is injected into the pipe, "() => objs".

Closure pipes are very powerful and flexible, as you can inject outside data at any point within the piping process.

4.

The JSDoc syntax informs the development-time experience of type issues, and is also used by the TypeScript background compiler in VSC (Visual Studio Code) to infer and inform on type issues.

Performance Gains:

Here are the results of running each function independently, comparing the performance difference between the built-in js filter func and the custom-built loop-based one.

// test a: one iteration on large array
// loop wins by being 62% faster
const aNums = genNums(10e6);
timeInLoop("Array.filter", 1, () => aNums.filter(n => n < 10e6)); //Array.filter: 1e+0: 1.460s
timeInLoop("fil", 1, () => fil(n => n < 10e6, aNums)); // fil: 1e+0: 896.562ms

// test b: large iteration on small array
// loop wins by being 9% faster
const aNums = [1, 2, 3, 4, 5, 6, 7, 8];
timeInLoop("Array.filter", 10e6, () => aNums.filter(n => n < 8)); //Array.filter: 1e+7: 1.748s
timeInLoop("fil", 10e6, () => fil(n => n < 8, aNums)); //fil: 1e+7: 1.601s

timeInLoop (performance test func) Source Code:

https://gist.github.com/funfunction/91b5876a5f562e1e352aed0fcabc3858

Contact:

More real world examples coming up in the future.

Feel free to subscribe if you'd like to see more Javascript-based runtime-enforced strongly-typed functional pipelining.

And leave a comment if you have any questions or input.
Or tweet me or DM me at
https://twitter.com/reactivizer

See you soon!

Discussion (4)

pic
Editor guide
Collapse
joelnet profile image
JavaScript Joel

I couldn't reproduce the results. I am showing fil running about 35% slower in node 14.8.0 on my machine.

Screenshot of code showing filter 241ms and fil 367ms

One problem with this type of micro-optimization is it will run differently depending upon a lot of factors, one of them being the engine it is run in.

It is possible that this type of code may run fast in Engine-123 today, but slower in other engines. Also, optimizations to that engine may render this method slower tomorrow.

It is generally recommended to leave this type of optimization up to the compiler and instead optimize your code for readability. Only when the code has been measured to be a bottleneck in the application should an optimization like this be considered.

Cheers šŸ»

Collapse
functional_js profile image
Functional Javascript Author

Interesting, using your example I get massive speed boost on both mac and windows using the loop.
To test properly, run each independently to avoid compiler optimizations of one influencing the other.

Yes a microoptimization would be small changes, like 5 to 10%.
But when it's running many times faster, you want to use the most perfomant.

There is nothing special about the built-in functions that the compiler will optimize better than custom functions. Though some of it may run in C++, it all runs in the V8 sandbox.
In rare cases the V8 team will optimize the V8 engine for some operations on new releases, usually on major releases.

In almost all cases a simple loop will always win out.

However many algorithms will vary in performance due to the data profile.

When you have a set of tools that can test a function you've written in less than a minute, it's worth it.
It's not always about comparing with the built-in function, though you should add them to the set of candidate algorithms if apropos.

Readability is not related to the complexity of the function.
The documentation is.
For example, you're not going to choose not to use memoization just because it's more readable not to, when it could improve the performance of your code 10x or 100x.

By testing the performance of your functions, means you understand your functions better; you understand the compiler better; you understand what idioms work better, and you make your codebase more performant as a whole.

I agree with you that everything has pros and cons that must be evaluated. And that I wouldn't worry about the small differences, and focus on the big difference.
But you should performance test all your functions, and robust test them, and fuzz test them.

Thanks for your input and testing that out. Your input is valuable!

const lt = console.time;
const le = console.timeEnd;

const a = genNums(10e6);
// const a = genRandNums(1, 10e6, 10e6);

// fil: 73.986ms - on windows
// fil: 33.733ms - mac
lt("fil");
fil(n => n < 8, a);
le("fil");

// filter: 506.438ms - on windows
// filter: 153.095ms - on mac
lt("filter");
a.filter(n => n < 8);
le("filter");

P.S.

I have a post here on how to evaluate what code to use before commiting it to production.
dev.to/functional_js/squeezing-out...

Collapse
aleksandrhovhannisyan profile image
Aleksandr Hovhannisyan • Edited

To take this a step further, you can add this as a method to Array.prototype so you can call it on any array:

Array.prototype.customFilter = function(fn) {
  const f = []; //final
  for (let i = 0; i < this.length; i++) {
    if (fn(this[i])) {
      f.push(this[i]);
    }
  }
  return f;
};

The performance gain is negligible, though, because passing an array into a method as an argument isn't all that inefficient to begin with (arrays collapse to pointers to the first element, and pointers are lightweight).

Collapse
functional_js profile image
Functional Javascript Author

Honestly speaking Aleksandr, I would not go down that path.
It's considered an antipattern to touch the prototype object.

One big danger is that this is not universal. You would always have to call this code first if you wanted to use the function. That would create massive spaghetti and bug vulnerabilities in your code.
Nevermind having dozens of user-defined functions tacked on to the prototype.
You would never know what's where.

I imagine you don't use ESLint. Unless you've turned off the "never modify the prototype" rule.

Thanks for you input though, it's an important point to highlight

Javascript Prototype Antipattern

P.S.
Here is a list of JavaScript constructs I do not use...
dev.to/functional_js/what-subset-o...