Lazy evaluation — LoDash source code interpretation

preface

One reason for LoDash’s popularity is its superior computing performance. And its performance can have such outstanding performance, a large part comes from its use of the algorithm – lazy evaluation. This article will describe the principle and implementation of lazy evaluation in loDash source code.

First, the principle analysis of inert evaluation

Lazy Evaluation, also known as call-by-need, is a concept in computer programming that minimizes the amount of work a computer has to do. Parameters in lazy evaluation are not evaluated until needed. This program is actually executed backwards from the end. It determines what it needs to return and continues backward to determine what values it needs to do so.

How to Speed Up lo-Dash ×100? Introducing Lazy Evaluation. (How to improve lo-DASH 100 times? An introduction to lazy computing), which visually illustrates lazy evaluation.

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();
Copy the code

The purpose of the program is to filter the gems of the dataset and select 3 data whose price is less than 10.

1.1 General practice

If you drop the loDash library and let you implement var chosen = _(gems).filter(priceLt(10)).take(3); So, you can use the following method: _(gems) get the data set and cache it. Then execute the filter method to traverse the GEMS array (length 10) and fetch the data that meets the conditions:

[{name: 'Sunstone'.price: 4 },
   { name: 'Sugilite'.price: 7  },
   { name: 'Diopside'.price: 3 },
   { name: 'Dioptase'.price: 2}]Copy the code

The take method is then executed to extract the first three pieces of data.

[{name: 'Sunstone'.price: 4 },
   { name: 'Sugilite'.price: 7  },
   { name: 'Diopside'.price: 3}]Copy the code

The total number of traversals is: 10+3. An example of this execution is shown below:

1.2 Lazy evaluation

One problem with the common approach is that each approach does its own thing and wastes a lot of resources without coordination. If you can first do things, with a small notebook to write down 😎, and then wait until the real data, and then use the least number of times to achieve the goal, is not better. That’s what lazy computing does. Here’s how to do it:

• _(gems)Take the data set and cache it
• encounterfilterMethod, write it down
• encountertakeMethod, write it down
• encountervalueMeans the time has come
• Let’s take the little book out and look at the requirements: I want to pick three numbers, price<10
• usefilterThe judgment method in the methodpriceLtJudge the data on a case-by-case basis

[{name: 'Sunstone'.price: 4}, => priceLt adjudicates => meets the requirements, passes => gets1A {name: 'Amethyst'.price: 15}, => priceLt ruling => not meet the requirements {name: 'Prehnite'.price: 20}, => priceLt ruling => not meet the requirements {name: 'Sugilite'.price: 7}, => priceLt adjudicates => meets the requirements, passes => gets2A {name: 'Diopside'.price: 3}, => priceLt adjudicates => meets the requirements, passes => gets3That's it! Knock it off! {name: 'Feldspar'.price: 13 },
    { name: 'Dioptase'.price: 2 },
    { name: 'Sapphire'.price: 20}]Copy the code

As shown above, it only takes 5 executions to get the result. An example of this execution is shown below:

1.3 summary

The characteristics of lazy computing can be obtained from the above example:

• Delayed calculation, the calculation to do first cache, do not execute
• The data pipeline, data by data, passes through the “adjudication” method in a process similar to security check, and only the data that meets the requirements are left behind
• trigger, method cache, then you need a method to trigger execution. Lodash is about usingvalueMethod, the notification really begins to calculate

Second, the implementation of lazy evaluation

Based on the above characteristics, I split the lazy evaluation implementation of LoDash into the following parts:

2.1 Cache for delayed calculation

Realize the _ (gems). I’m using lazy(gems) instead for semantic clarity.

var MAX_ARRAY_LENGTH = 4294967295; // The maximum array length

// Cache the data structure
function LazyWrapper(value){
    this.__wrapped__ = value;
    this.__iteratees__ = [];
    this.__takeCount__ = MAX_ARRAY_LENGTH;
}

// Lazy evaluation entry
function lazy(value){
    return new LazyWrapper(value);
}
Copy the code

• this.__wrapped__Cache data
• this.__iteratees__A method of “ruling” in a cache data pipeline
• this.__takeCount__Record the number of data sets required to meet the requirements

Thus, a basic structure is completed.

2.2 implementationfiltermethods

var LAZY_FILTER_FLAG = 1; // filter the flag of the method

// Filter data according to the filter method iteratee
function filter(iteratee){
    this.__iteratees__.push({
        'iteratee': iteratee,
        'type': LAZY_FILTER_FLAG
    });
    return this;
}

// Bind the method to the prototype chain
LazyWrapper.prototype.filter = filter;
Copy the code

Filter method, which caches the ruling method iteratee. The important point here is to record the type type of iteratee. In LoDash, there are methods like Map that filter data, and they pass in a decision method called Iteratee. Because the filter method and the map method have different filtering methods, type is used to mark them. Here’s another trick:

(function(){
    // Private methods
    function filter(iteratee){
        /* code */
    }

    // Bind the method to the prototype chainLazyWrapper.prototype.filter = filter; }) ();Copy the code

Methods on the stereotype are declared with ordinary functions and then bound to the stereotype. If you need to use filters internally, use declared private methods. The benefit is that external if change LazyWrapper. The prototype filter, inside the tool, is does not have any effect.

2.3 implementationtakemethods

// Truncate n data
function take(n){
    this.__takeCount__ = n;
    return this;
};

LazyWrapper.prototype.take = take;
Copy the code

2.4 implementationvaluemethods

// lazy evaluation
function lazyValue(){
    var array = this.__wrapped__;
    var length = array.length;
    var resIndex = 0;
    var takeCount = this.__takeCount__;
    var iteratees = this.__iteratees__;
    var iterLength = iteratees.length;
    var index = - 1;
    var dir = 1;
    var result = [];

    // Label statement
    outer:
    while(length-- && resIndex < takeCount){
        // The array for the outer loop to process
        index += dir;

        var iterIndex = - 1;
        var value = array[index];

        while(++iterIndex < iterLength){
            // The inner loop handles the method on the chain
            var data = iteratees[iterIndex];
            var iteratee = data.iteratee;
            var type = data.type;
            var computed = iteratee(value);

            // Handle data inconsistencies
            if(! computed){if(type == LAZY_FILTER_FLAG){
                    continue outer;
                }else{
                    breakouter; }}}// After the inner loop, the required data is met
        result[resIndex++] = value;
    }

    return result;
}

LazyWrapper.prototype.value = lazyValue;

Copy the code

One important point here is the tag statement

    outer:
    while(length-- && resIndex < takeCount){
        // The array for the outer loop to process
        index += dir;

        var iterIndex = - 1;
        var value = array[index];

        while(++iterIndex < iterLength){
            // The inner loop handles the method on the chain
            var data = iteratees[iterIndex];
            var iteratee = data.iteratee;
            var type = data.type;
            var computed = iteratee(value);

            // Handle data inconsistencies
            if(! computed){if(type == LAZY_FILTER_FLAG){
                    continue outer;
                }else{
                    breakouter; }}}// After the inner loop, the required data is met
        result[resIndex++] = value;
    }

Copy the code

The data pipeline implementation of the current method is essentially the inner while loop. By fetching the decision method cached in Iteratees to determine the value of the current data. If the ruling is not true, it is false. Then at this point, there is no need to use the subsequent adjudication method for judgment. Instead, jump out of the current loop. Result [resIndex++] = value; result[resIndex++] = value; It’s still going to be implemented, which we don’t want. It is only right to break out of the inner and outer loop at once and continue with the outer loop. Label statements, which do just that.

2.5 small detection

var testArr = [1.19.30.2.12.5.28.4];

lazy(testArr)
    .filter(function(x){
        console.log('check x='+x);
        return x < 10
    })
    .take(2)
    .value();

// Output is as follows:
check x=1
check x=19
check x=30
check x=2

// Result: [1, 2]
Copy the code

2.6 summary

The whole implementation of lazy evaluation, the focus is on the data pipeline. And the wonderful use of tag statements here. In fact, this is not the only way to do it. However, the main points are the three mentioned above. Mastering the essence, it’s easy to be flexible.

conclusion

Lazy evaluation is one of the biggest things I found in reading the LoDash source code. At the beginning, I did not understand lazy evaluation very much and wanted to see the implementation of javascript, but I only found a literature mentioned above on the Internet. The remaining option, then, is to perform dissection analysis on Lodash. Because of this, this article was born. I hope this article has been helpful to you. Give a star if possible 🙂

Finally, the full source code for lazy.js is attached: github.com/wall-wxk/bl…

---

Friends who like my articles can follow me in the following ways:

• “Star” or “watch” my GitHub blog
• RSS subscribe to my personal blog:Mr. Wang’s base