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:
1 2 3 4 |
var len = getLength(); for(var i = 0; i < len; i++) { operation(); // <- 10ms - how to make it 9ms?! } |
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:
1 2 3 4 5 6 7 8 9 10 11 |
function priceLt(x) { return function(item) { return item.price < x; }; } var gems = [ { name: 'Sunstone', price: 4 }, { name: 'Amethyst', price: 15 }, { name: 'Prehnite', price: 20}, { name: 'Sugilite', price: 7 }, { name: 'Diopside', price: 3 }, { name: 'Feldspar', price: 13 }, { name: 'Dioptase', price: 2 }, { name: 'Sapphire', price: 20 } ]; var chosen = _(gems).filter(priceLt(10)).take(3).value(); |
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:
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:
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:
1 2 3 4 5 6 7 8 |
var phoneNumbers = [5554445555, 1424445656, 5554443333, … ×99,999]; // get 100 phone numbers containing „55” function contains55(str) { return str.contains("55"); }; var r = _(phoneNumbers).map(String).filter(contains55).take(100); |
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):
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:
1 |
var result = _(source).map(func1).map(func2).map(func3).value(); |
would translate roughly to this in regular Lo-Dash (strict evaluation)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
var result = [], temp1 = [], temp2 = [], temp3 = []; for(var i = 0; i < source.length; i++) { temp1[i] = func1(source[i]); } for(i = 0; i < source.length; i++) { temp2[i] = func2(temp1[i]); } for(i = 0; i < source.length; i++) { temp3[i] = func3(temp2[i]); } result = temp3; |
While with the lazy evaluation turned on it’d perform more like this:
1 2 3 4 |
var result = []; for(var i = 0; i < source.length; i++) { result[i] = func3(func2(func1(source[i]))); } |
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.
1 2 3 4 5 6 7 8 9 |
var wallet = _(assets).filter(ownedBy('me')) .pluck('value') .reduce(sum); $json.get("/new/assets").success(function(data) { assets.push.apply(assets, data); // update assets wallet.value(); // returns most up-to-date value }); |
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.
Comments
Nice article. I think there’s an error though, .filter(ownedBy(‘me’) is missing an extra closing backet.
Thanks, it’s fixed now.
Thanks for the great explanation.
contains555 in the example should be contains55, right?
Exactly, I fixed it. Thanks!
Hi, in which version of lodash we can find those awesome improvements?
In 3.0 which is W.I.P. currently.
> 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!
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 🙂
Amazing article, I would love to see more on this! Especially how we can design our own code for it
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?
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()
.[…] […]
nice work!
I learnt a lot from this post and I can’t wait to share this with others 🙂
Thanks for awesome article and work!
What about transducers thing, is it going to meet with lo-dash 3.0?
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?
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 withapply
).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!
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 […]