CppCon 2017: Victor Komarov “Universal Memoization Decorator”

CppCon 2017: Victor Komarov “Universal Memoization Decorator”


So today I want to talk
to you about Memoization. What’s memoization? It’s basically caching function calls in order to avoid the same computations happening over and over again
with the same parameters. Often implementing it
several times in my code I wondered if it’s possible to implement it once and for
all, like universally. In Python, once you
have the decorator ready it takes just one line
to decorate the function. It looks like this. But as we now know, Python may take you up to several months to get your data. And besides that, it’s
a C++ conference, so, let’s do something comparably
neat in our favorite language. I want to have a function like the same that we have in Python. And take it’s name, specify
the container I want to use, and just call the decorated versions with the same arguments. How are we going to do this? First let’s talk about the container. Suppose we have a function that takes the arguments, returns the value, we create a key from the decayed arguments of that functions
and then use it as a key. The value is a value. And the suitable implementation of a container will look like this, and so it’s some kind of a hash map that’s supposed to
operations, set and get, set updates the cache, get returns the pointer to
the element if it’s present or no pointer if it’s not and after Cade Gregory’s talk this morning I’m considering using this
std::optional, std::optional. Now once we have the container ready let’s think where it should be placed. Luckily as we know each
instantiation of class or function template has
it’s own static variable. So if parameterize our
decorator with a function we can store the cache
in a static variable. However, there is a
problem with this approach. If we parameterize template
as a type of a function which is basically its signature, we can run into collision if we want to decorate two functions
having the same signature. However, there is a
remedy to this problem. This thing looks weird if you
see it for the first time, but it does very useful thing. It allows us to parameterize
templates with values rather than just types. Consider this example. We have a template of this
form with a static function and the static variable
inside that function, and what this function does, it just brings the address
of the static variable. And we have three distinct instantiations with three distinct integers, and on my machine this program
outputs the following numbers so the static variables
inside are distinct. Let’s build the decorator. We start with a template declaration. The first line of the parameters respond to the trick I mentioned. The second line is about the container. Then we specialize our
decorator for functions because we don’t want
to call the decorator on integers or strings or whatever. So first comes the function signature then comes the function self, then the container we want
to store our results in. Here is where all the work is done. So the function call is
supposed to be called instead of the function we are decorating. We have cache stored in a steady variable, we create key, we search our cache for an element with that key, if the result is present, return it, if it’s not we call the function but belay the cache and return the value. Okay, so how does usages look like? They look like this, our
initial example looks just as neat as I want it to. And with Decotype I don’t
have to write by hand the function signature like
back in the good old times. Okay, we can even decorate
the recursive functions, so here’s a Fibonacci example, and we just declare the function first and define it after we define the function with all the work. Obviously it’s a simplification and there is a lot of details left behind like how does this thing
operate with lambdas, std::functions, stud::bind. What containers can we
use to store the cache, there’s a bunch of fancy
hash maps to choose from. We can use LRU or whatever. How do we support concurrency, so how do we protect
the access to the cache if the decorator is
used in several threads? We can boot simple mutics,
we can use our voloc, we can even declare the cache thread local so each thread has its own copy. So it’s a work in progress and I hope you hear more
about it in the future. Thank you.


Leave a Reply

Your email address will not be published. Required fields are marked *