Click here to Skip to main content
15,565,568 members
Articles / General Programming / Performance
Tip/Trick
Posted 30 May 2022

Tagged as

Stats

3.9K views
1 bookmarked

How Utilizing Lazy Evaluation and Caching can Save Us from Wasteful Computation

Rate me:
Please Sign up or sign in to vote.
4.47/5 (5 votes)
30 May 2022CPOL4 min read
This article shows how utilizing lazy evaluation and caching can save us from wasteful computation
On the example of leetcode task, we'll see how instead of a naive solution, we can utilize more elegant lazy evaluation.

I’m usually skeptical about leetcode tasks since this is not something you’ll encounter in your daily line-of-business code. But the idea behind this particular task has fascinated me. So I’ll break it down here.

I’ll provide a slightly simplified version of the task so you could capture the gist of it more easily.

Quote:

Write an API that generates fancy sequences using the append, addAll, and multAll operations.

Implement the Fancy class:

    Fancy() Initializes the object with an empty sequence.
    void append(val) Appends an integer val to the end of the sequence.
    void addAll(inc) Increments all existing values in the sequence by an integer inc.
    void multAll(m) Multiplies all existing values in the sequence by an integer m.
    int getIndex(idx) Gets the current value at index idx (0-indexed). If the index is greater or equal than the length of the sequence, return -1.

Example 1:

Input
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
Output
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

Explanation
Fancy fancy = new Fancy();
fancy.append(2);      // fancy sequence: [2]
fancy.addAll(3);        // fancy sequence: [2+3] -> [5]
fancy.append(7);      // fancy sequence: [5, 7]
fancy.multAll(2);       // fancy sequence: [5*2, 7*2] -> [10, 14]
fancy.getIndex(0);    // return 10
fancy.addAll(3);       // fancy sequence: [10+3, 14+3] -> [13, 17]
fancy.append(10);   // fancy sequence: [13, 17, 10]
fancy.multAll(2);     // fancy sequence: [13*2, 17*2, 10*2] -> [26, 34, 20]
fancy.getIndex(0);  // return 26
fancy.getIndex(1);  // return 34
fancy.getIndex(2);  // return 20

Constraints:
1 <= val, inc, m <= 100
0 <= idx <= 105
At most 105 calls total will be made to append, addAll, multAll, and getIndex.
Number of read operation surpasses number of mutations

The naive solution would be to perform each operation on all elements of an array and then get element at desired index. However, this solution is suboptimal since we may need only a couple of items from the collection so there’s clearly no need to calculate each item for such a case.

Alternatively, we might want to compute each item of the array on-demand leveraging some sort of lazy evaluation. In such a case, we need to ensure that we don’t calculate the same item twice. For such an occasion, we need to store the result of the calculation in an intermediary data structure. map would be the best fit for such structure since it allows us to get the desired element at O(1) time. The element index will serve as a key while the value of the map is the result of the calculation.

So the types are declared as follows:

Go
type Operation struct {
    operationCode   int8
    operand         int
    valuesLastIndex int32
}

type Fancy struct {
    values     []int8
    operations []Operation
    cache      map[int]int
}

When appending values, we’re just increasing array of values:

Go
func (this *Fancy) Append(val int) {
    this.values = append(this.values, int8(val))
}

When adding or multiplying, we’re increasing array of operations. No evaluation happens at this point in time.

Go
func (this *Fancy) AddAll(inc int) {

    this.operations = append(this.operations, 
                      Operation{-2, inc, int32(len(this.values))})
    this.cache = make(map[int]int)
}

func (this *Fancy) MultAll(m int) {

    this.operations = append(this.operations, 
                      Operation{-1, m, int32(len(this.values))})
    this.cache = make(map[int]int)
}

Evaluation occurs on-demand. We either try to hit a cache or calculate it if we miss a cache:

Go
func (this *Fancy) GetIndex(idx int) int {

    if idx < 0 || idx >= len(this.values) {
        return -1
    }

    if val, ok := this.cache[idx]; ok {
        return val
    }

    var vv uint64

    vv = uint64(this.values[idx])

    for _, v := range this.operations {
        if idx >= int(v.valuesLastIndex) {
            continue
        }

        switch os := v.operationCode; os {
        case -2:
            vv += uint64(v.operand)
        case -1:
            vv *= uint64(v.operand)
        }
    }

    if this.cache == nil {
        this.cache = make(map[int]int)
    }

    this.cache[idx] = int(vv)

    return int(vv)
}

As some of you might have noticed each mutation operation leads to clearing the cache. So this method might be ineffective when the number of mutations surpasses the number of reads. So (as with every other solution in software engineering) it is advisable to evaluate your constraints before applying methods from your toolbox.

Evaluating cache

One thing that is worth noting is that cache we construct occupies space in memory. That means that we should evaluate using it so it won’t turn into a huge memory leak. For the same reason, you should have cache expiration strategy for most of your projects.

Since we know that the maximum number of operations is 10^5 we can deduce that cache size will reach its peak we won’t perform any additions or multiplications thus clearing the cache but instead half of the operations will be appending items and the other one will be evaluating them thus calculating new item each time.

func BenchmarkMemoryConsumption() {
    var m1, m2 runtime.MemStats
    runtime.GC()
    runtime.ReadMemStats(&m1)
    const MaxOperations int = 100000
    fancy := Constructor()
    for i := 0; i < MaxOperations/2; i++ {
        fancy.Append(100)
    }
    for i := 0; i < MaxOperations/2; i++ {
        fancy.GetIndex(i)
    }
    runtime.ReadMemStats(&m2)
    fmt.Println("total:", m2.TotalAlloc-m1.TotalAlloc)
    fmt.Println("mallocs:", m2.Mallocs-m1.Mallocs)
}

I’ve found built-in benchmarking functionality providing allocs per second metric irrelevant for this case so instead I’ve came up with the benchmark as above. The output is

 

<code>total: 3082976
mallocs: 1986
</code>

3MBs for the cache of maximum size? Easy for most of the line-of-business applications.

Conclusion

In case we’re presented with the perspective of doing a lot of wasteful computations, we can omit that by restoring to computing values when necessary using lazy evaluation.

History

  • 30th May, 2022 - Published initial version
  • 10th August, 2022 - Added paragraph about possible drawbacks

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Team Leader
Ukraine Ukraine
Team leader with 8 years of experience in the industry. Applying interest to a various range of topics such as .NET, Go, Typescript and software architecture.

Comments and Discussions

 
QuestionIt's still naive Pin
Dmitry Mukalov31-May-22 11:02
Dmitry Mukalov31-May-22 11:02 
First of all thank you for your article. It's interesting approach but I have to admit that it's still naive as it doesn't respect the cases when number of mutation operations significantly surpasses number of read operations, likewise the classical naive approach doesn't respect the opposite situation. In general cases when we aren't able to make an assumption about expected read and write operations ratio I'd say that a segment tree based approach would be the best bet as it's able to provide logarithmic complexity for both types of operations.
AnswerRe: It's still naive Pin
Bohdan Stupak1-Jun-22 0:38
professionalBohdan Stupak1-Jun-22 0:38 
BugDifference between naive vs lazy calculation in example Pin
Member 1061738531-May-22 9:09
Member 1061738531-May-22 9:09 
GeneralRe: Difference between naive vs lazy calculation in example Pin
Bohdan Stupak1-Jun-22 0:40
professionalBohdan Stupak1-Jun-22 0:40 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.