Menu

Filip Zawada

👨🏻‍💻 iOS tinkerer

How to Speed Up Lo-Dash ×100? Introducing Lazy Evaluation.

This post begins a series of articles about algorithms, inspired by my recent “lazy evaluation” contribution to Lo-Dash. Stay tuned for more!

I always thought libraries like Lo-Dash can’t really get any faster than they already are. Lo‑Dash almost perfectly mixes various techniques to squeeze out the most from JavaScript. It uses JavaScript fastest statements, adaptive algorithms, it even measures performance to avoid accidental regressions in subsequent releases.

Lazy Evaluation

But it seems I was wrong – it is actually possible to make Lo-Dash significantly faster. All you need to do is stop thinking about micro-optimizations and start figuring out the right algorithm to use. For example, in a typical loop we usually tend to optimize a single‑iteration time:

But it’s often hard and very limited. Instead, it makes a lot more sense in some cases to optimize getLength() function. The smaller the number it returns, the less 10ms cycles we have.

This is roughly the idea behind the lazy evaluation in Lo-Dash. It’s about reducing the number of cycles, not reducing a cycle time. Let’s consider the following example:

We want to take only first 3 gems with price lower than $10. Regular Lo-Dash approach (strict evaluation) filters all 8 gems – then returns the first three that passed filtering:

Lodash naïve approach

It’s not cool though. It processes all 8 elements, while in fact we need to read only 5 of them. Lazy evaluation algorithm, on the contrary, processes the minimal number of elements in an array to get the correct result. Check it out in action:

Lo-Dash regular approach

We’ve easily gained 37.5% performance boost. But it’s not all we can achieve, actually it’s quite easy to find an example with ×1000+ perf boost. Let’s have a look:

In such an example map and filter is ran on 99,999 elements, while it may be sufficient to run it only on e.g. 1,000 elements. The performance gain is massive here (benchmark):

benchmark

Pipelining

Lazy evaluation brings another benefit, which I call a “pipelining”. The idea behind is to avoid creating intermediary arrays during the chain execution. Instead we should perform all operations on a single element in place. So, the following piece of code:

would translate roughly to this in regular Lo-Dash (strict evaluation)

While with the lazy evaluation turned on it’d perform more like this:

Lack of temporary arrays may give us a significant performance gain, especially when source arrays are huge and memory access is expensive.

Deferred execution

Another benefit that was brought together with the lazy evaluation is deferred execution. Whenever you create a chain, it’s not computed until .value() is called implicitly or explicitly. This approach helps to prepare a query first and execute it later with the most recent data.

It may also speed up execution time in some cases. We can create a complex query early and then, when time is critical, execute it.

Wrap up

Lazy evaluation is not the new idea in the industry. It has already been there with excellent libraries like LINQ, Lazy.js and many others. The main difference Lo-Dash makes, I believe, is that you still have good ol` Underscore API with a new powerful engine inside. No new library to learn, no significant code changes to make, just a pending upgrade.

But even if you’re not going to use Lo-Dash, I hope this article inspired you. Now, when you find a bottleneck in your application, stop trying to optimize it in jsperf.com try/fail style. Instead go, grab a coffee and start thinking about algorithms. Creativity is important here, but a good math background won’t hurt too (book). Good luck!

TBC… I’d like to write another – more advanced – post explaining how the Lazy algorithm is implemented in detail. If you like the idea, vote on it by following me on Twitter.

Coding makes me happy! I’m an award-winning consultant, architect, writer & speaker. If you struggle to find a trustworthy developer – let’s talk to me!

Comments

gotofritz says:

Nice article. I think there’s an error though, .filter(ownedBy(‘me’) is missing an extra closing backet.

Filip Zawada says:

Thanks, it’s fixed now.

Sorin says:

Thanks for the great explanation.

contains555 in the example should be contains55, right?

Filip Zawada says:

Exactly, I fixed it. Thanks!

Sergey says:

Hi, in which version of lodash we can find those awesome improvements?

Filip Zawada says:

In 3.0 which is W.I.P. currently.

Jim Witschey says:

> vote on it by following me on Twitter.

Not sure what you mean here. But this is a great post, I’d love to see more!

Filip Zawada says:

Thanks for kind words. As an explanation, the number of my followers has doubled since I published this post. For me this means there’s a real demand for another post covering this topic. It’s extremely motivating 🙂

Charlie says:

Amazing article, I would love to see more on this! Especially how we can design our own code for it

foljs says:

Maybe it’s me but in the whole article I didn’t get an exact answer about lazy evaluation in LoDash.

Is it available in upstream stable LoDash?

If not, is it scheduled for the next (3.0?) release?

Does it need a special configuration to be enabled?

Is it just some experiments you did based on LoDash, but not to be included in LoDash proper?

Filip Zawada says:

Right, I’ll include this info in the next article. Currently Lazy Evaluation is available in Lo-Dash v3.0.0-pre with methods map(), filter(), reverse() and few others being lazy. It doesn’t need any special configuration, it just works whenever you do chaining _(src).map().filter().reverse().first().

wayou says:

nice work!
I learnt a lot from this post and I can’t wait to share this with others 🙂

Victor says:

Thanks for awesome article and work!
What about transducers thing, is it going to meet with lo-dash 3.0?

Filip Zawada says:

Hi Victor, thanks for kind words. Currently there’s no plan for transducers support.

This is exciting!

I’m a little puzzled by this minor detail:

assets.push.apply(assets, data);

Why can’t you just do:

assets.push(data);

In this situation?

Filip Zawada says:

Sorry for late reply, glad you solved it already. For anyone else wondering, since data is an array this is equivalent of: assets.push(data[0], data[1], ..., data[data.length-1]) (obviously we don’t know length upfront, so we use this trick with apply).

gopinath says:

Lols… you can use concat though 😛 but nice I learn this now.

Wouldn’t .concat() do the trick?

Also, great article! Looking forward to part two.

Never mind, my coworker figured it out!

Shien says:

No offence, but that should really be your responsibility. lodash is meant to find the most general algorithm, with the best performance. It’s fine as it is. If you need lazy evaluation you can easily layer it on yourself, no need to hack it onto lodash. but if lazy evaluation is added onto lodash, it’ll be impossible to remove it yourself, even if it would improve performance, which it would in some scenarios.

[…] 이야기를 듣고 검색하게 되었다. 검색 결과로 찾은, Filip Zawada의 How to Speed Up Lo-Dash ×100? Introducing Lazy Evaluation 포스트를 번역한 […]

[…] 이야기를 듣고 검색하게 되었다. 검색 결과로 찾은, Filip Zawada의 How to Speed Up Lo-Dash ×100? Introducing Lazy Evaluation 포스트를 번역한 […]

[…] How to Speed Up Lo-Dash ×100? Introducing Lazy Evaluation […]

[…] was to create a performant version of underscore (which it was very successful in doing). About a year ago, Lodash started using lazy evaluation to dramatically speed up its support for chained […]

[…] thing that is somewhat popular now adays is Lazy Evaluation.  Lodash implemented a form after a competitor (Lazy.js) where showing big promise for takeover. However, […]

[…] NPM package.  I’ve read some excellent Lodash articles by Colin Toh, Marius Shulz, and Filip Zawada.  Today, I’ll throw in my 2 […]

[…] This is actually a pretty weak example for highlighting huge performance gains.  I suspect the most dramatic performance gains will occur when there is no sorting and when the .take() method is used.  In this case, it is not farfetched to achieve a 100X or 1,000X performance improvement.  Filip Zawada is the Lodash contributor who implemented most of the lazy evaluation upgrade.  He does a much better job of explaining the advantages of lazy evaluation. […]

[…] and contains the entire kitchen sink. It is also one of the most performant, with features such as lazy evaluation. You don’t have to include the whole thing if you don’t want to, either: Lodash lets you […]

[…] réside dans l’utilisation d’un mécanisme de résolution différée des méthodes chaînées (deferred lazy chaining). Le changelog complet peut être utile car cette version inclue quelques changements non […]

[…] and contains the entire kitchen sink. It is also one of the most performant, with features such as lazy evaluation. You don’t have to include the whole thing if you don’t want to, either: Lodash lets […]

[…] and contains the entire kitchen sink. It is also one of the most performant, with features such as lazy evaluation. You don’t have to include the whole thing if you don’t want to, either: Lodash lets you […]

[…] 就是一个功能非常齐全的工具库,并且由于惰性执行 等特性,其性能很优越。此外,Lodash 支持开发按需引用资源。在 4.x […]

[…] 是此类工具中的佼佼者。此外,由于它惰性执行的特性,也让它是目前性能最佳的工具之一。使用 Lodash […]

[…] 是此类工具中的佼佼者。此外,由于它惰性执行的特性,也让它是目前性能最佳的工具之一。使用 Lodash […]

[…] 原文:http://filimanjaro.com/blog/2… […]

[…] 是此类工具中的佼佼者。此外,由于它惰性执行的特性,也让它是目前性能最佳的工具之一。使用 Lodash […]

Leave a Reply to Filip Zawada Cancel reply

Blue Captcha Image
Refresh

*