Improve Your System Performance With Lazy Evaluation

One of the principles of software development is “Resource Allocation Is Initialization", or RAII. This is useful as it avoids uninitialized values in your code, because all values are initialized when they're declared. It's a great way of avoiding problems with uninitialized references, because there aren't any!

You might not know it as RAII, but there's always the feeling that when you declare something you should initialize it, if only to stop the code linter from complaining.

Like anything else though, it's easy to go too far with this. When the objects in your system take an appreciable amount of time to create, and you want a lot of them, you'll find your application slows to a crawl.

Lazy Evaluation can improve performance dramatically!

For example, the following Python code:

class ValueClass:

    def __init__(self, key: str):
        self.value = self._get_value(key)

    @staticmethod
    def _get_value(key: str) -> Any:
        # Generate a value based on the given key
        return get_value_from_database_or_some_slow_generation_process(key)

Say that this example takes a second to create an object. It's not too bad, so you assume it's not worth optimizing at all, because someone you work with said something about “premature optimization" being evil. Then someone decides to do this:

# Create the set of values we need
objects = [ValueClass(i) for i in range(0, 1000)]

Suddenly your process stops for 1,000 seconds – 16 minutes 40 seconds – while is builds up a list of objects. You might think of using multi-threading – notoriously dreadfully-performing in Python, but you might be using a different language. Assuming one thread per CPU core, you might dramatically reduce the overall time to just over four minutes. That's pretty underwhelming. Still, you decide that whatever time it takes will be insignificant compared to the overall running time of your system.

Then, to add insult to injury, as so often happens. The next piece of code that the caller adds is:

for item in range(0, 1000):
    if item % 10 == 0:
        print(f"{item}: {objects[item].value}")

Why would anyone do this? I don't know; maybe there's a logical reason, maybe they just hate you, but trust me, it's going to happen.

So, you've spent over quarter of an hour creating a collection of objects, filling the memory with them, and then only 10% of them get used. This is less than optimal.

Surely There's a Better Way!

There is! Remember that the purpose of RAII is to avoid uninitialized values that have been allocated. Initializing them is taking a long time, so what if we just don't allocate them until we need them? We can wrap up the technicalities and hide them in an abstraction – it's what Object Orientation is REALLY about, don't let anyone tell you otherwise! Hiding the ugly stuff is where it's at!

In the example above, we only need the value when we first reference it. Up until then it doesn't matter whether it exists or not, so let's write something that uses lazy evaluation and doesn't create or get the value until we want it:

class ValueClass:

    def __init__(self, key: str):
        self._key = key

    @property
    def value(self) -> Any:
        # Generate a value based on the given key
        return get_value_from_database_or_some_slow_generation_process(self._key)

This solves some of the problem we were having. It doesn't create or store the value unnecessarily, so this piece of code now runs almost instantaneously:

# Create the set of values we need
objects = [ValueClass(i) for i in range(0, 1000)]

That's a great improvement. Now let's look at the rest of the code your apparent nemesis wrote:

for item in range(0, 1000):
    if item % 10 == 0:
        print(f"{item}: {objects[item].value}")

This references the value property of 100 objects, and each time that happens get_value() is called, and that takes around a second. So, our run time has dropped to about 100 seconds, which is a 90% improvement.

Surely There's An EVEN Better Way!

No, there isn't. The caller wanted 100 items, and that takes 100 seconds to generate, at least in our example. You could argue that optimization, fancy database queries, amazing algorithms and various other techniques will help, and it might. You still can't get past the fact that 100 items are needed, and we need time to create them.

Of course, the situation with the calling code might not be as straightforward as the first example showed. What if the caller uses their code more than once in the execution of the application. A simple version might be functionally the same as:

for call_count in range(0, 100):
    for item in range(0, 1000):
        if item % 10 == 0:
            print(f"{call_count}: {item}: {objects[item].value}")

This will take around 10,000 seconds, or about 3¾ hours to run. At this point I'm wondering whether referring to the author of this code as a nemesis it actually true, rather than just a lighthearted comment. In any case, this is the calling code we're stuck with, so we have to deal with it.

You can see from the code above that the same values are being referenced multiple times. You may be wondering about some form of caching, and you'd be right:

As well as delaying evaluation until it's required, the other part of lazy evaluation that makes it so effective is caching the value until it is no longer needed.

So, adding some caching to the original class, gives:

class ValueClass:

    def __init__(self, key: str):
        self._key = key
        self._value = None
        self._value_evaluated = False

    @property
    def value(self) -> Any:
        # Evaluate the value only if we need to, and if we haven't before
        if not self._value_evaluated:
            self._value = self._get_value(self._key)
            self._value_evaluated = True

        return self._value

    @staticmethod
    def _get_value(key: str) -> Any:
        # Generate a value based on the given key
        return get_value_from_database_or_some_slow_generation_process(self._key)

There are a few things to note here:

As well as the _value member of the class, which holds the calculated value, there's a flag: _value_evaluated. This is set when the value has been successfully obtained. Theoretically it would be possible to do without this flag, but you need SOME way of checking whether the value has been obtained or not. In this example, it's possible that the value could be None, or maybe 0 or some other value that evaluates to False in boolean. If we don't keep track of whether it's been evaluated, rather than just being None, we might end up evaluating it every time the value is accessed.

The value property is still used to access the lazily-evaluated value because the caller is only interested in the value. They don't, and shouldn't, care how that value is calculated or obtained. It really is none of their business. Changing the interface of the class just because you changed the implementation is bad practice.

If we look at the calling code from the previous examples we have:

# Create the set of values we need
objects = [ValueClass(i) for i in range(0, 1000)]

Just as before, this is almost instantaneous, because the values are still not being calculated or obtained yet. The slightly updated code to obtain the values:

for call_count in range(0, 100):
    for item in range(0, 1000):
        if item % 10 == 0:
            print(f"{call_count}: {item}: {objects[item].value}")

This will operate much more quickly than it previously would. Instead of each of the 100 values in the inner loop being recalculated 100 times because of the outer loop, the following happens:

1. On the first iteration of the outer loop, the inner loop initializes 100 objects. This takes around 100s as before.
2. On every subsequent iteration of the outer loop, the value property for each item returns the value that it calculated previously – it never has to recalculate anything.

Other Languages

The above examples are obviously using Python, but the principle of Lazy Evaluation is exactly that: a principle. As such it works with most languages, even though most of the time you have to at least specify that you want to use it.

I've used it a lot with C#, which even provides the Lazy<T> class. This lets you specify a function to create the object to be stored, and was something I used a lot developing high-performance systems. C++ was another language where the lazy evaluation was implemented in similar way to the Python examples, and it worked well.

Summary

If you discover that your system is taking a long time to calculate or retrieve values that are repeatedly accessed, or that are never accessed at all, try using Lazy Evaluation. You don't need to know exactly which values are needed or not needed, that's all handled automatically by the code. You'll minimize the time and memory used by your system, and get rid of any large set-up delays; they'll be spread through the application.