The simple yet powerful technique of Memoization

As a developer making integrations systems, the server programs I write at work generally make a lot of HTTP requests. But a single HTTP request involves a lot of steps in the background:

• The HTTP request is constructed by the HTTP client (like Axios, Got…).
• The request is then prepared for transport through the TCP protocol, the famous TCP-Handshake is done, then the request is split into multiple TCP segments (it is split because TCP has a max size limit for segments, as this protocol is optimized for reliability).
• The domain of the request is resolved to an IP address through DNS lookup, then the IP packet is wrapped up: source IP, destination IP and the previous TCP segments are all cosy together. All that is sent to the nearest router again and again.
• For each Hop of the node, the IP packet is encapsulated inside an Ethernet or a Wi-Fi frame containing the source MAC address of the client’s network card, the destination MAC address and of course the IP packet. The correspondence between the IP address and the MAC address is done through ARP (Address Resolution Protocol) and the ARP table. The frame is sent over the network again until destination is reached.
• Finally we arrived! The frame is converted into a bit-stream (0s and 1s), these bits are transmitted through electrical signals (Ethernet), light pulses (optic fiber) or radio waves (Wi-Fi). This signal travels through the destination infrastructure to the targeted machine!

And this is only for the request, all these steps must be done in reverse for the response.

Moreover the API you are talking to surely have a rate limiter in place, so the request might take even longer.

In short, the less API calls you do, the better.

The situation

I had an issue with one of our integration at work, it took approximately 4 hours to complete its data synchronization. You can imagine it is waaaay too long and our customer began to raise questions.

So I read the code, run some tests and quickly figure out two things:

• We were rate-limited more than usual by the external API.
• No “memoization” was done.

Now, I couldn’t do anything about the 1st point. I wrote some email to our contact to check if that was normal but that’s it. But the second point was less frustrating.

Memoization, what is this thing?

Well, it’s a really simple but powerful optimization technique, it’s a form of “dynamic” caching, belonging to the world of Dynamic Programming.

The idea is to store the result of an (expensive) operation and reuse that result if the same input(s) occurs again, during execution of the program.

This way you never do the same operation/calculation twice.

The caching is done at runtime, losing the cached data once the program has finished its execution.

In the program that was taking too long, for example, an API request was done for each Student ID that we fetched previously.
As there was no caching in place, one student might be fetched 2, 10, 50 times! By applying this technique, each student would be fetched one time and one time only.

The implementation is quite simple (here’s a TypeScript example kept as minimal as possible for the sake of conciseness):

async getStudent(studentId: string): Promise<Student> {
            try {
                // Read cache and return. 
                // The benefits of memoization happens here.
                if (studentId && this.studentsCache.has(studentId)) {
                    return this.studentsCache.get(studentId);
                }
        
                // Does not exist in cache, 
                // so fetch it using whatever HTTP client you're using in the project.
                // Typically a GET request would be done using the input as query parameter (might need sanitization).
                const { data: student } = await axios({
                    method: "get",
                    baseUrl: "https://api.example.com", // Generally comes from some config object elsewhere or an .env file
                    url: `/student/${studentId}`, // Or construct a new URL() and set its params
                    headers: {} // Whatever headers needed (tracking, authorization, MIME...)
                });
        
                // Save to cache. The act of memoization happens here.
                // Notice that we save the INPUT (studentId) and not student.id which is a part of the result itself.
                // Next time, if we encounter a studentId input with the same value, 
                // the API call won't be executed as the function will return early with the previously saved result.
                if (studentId && student) {
                    this.studentsCache.set(studentId, student);
                }
        
                return student;
        
            } catch (error) {
                throw new Error(`[::getStudent::] Error while fetching student ${studentId} - ${error}`);
            }
        }

I did this for every resources that was handled, and the integration ran under 1 hour.
The rest of the execution time is attributable to the thousands of resources it still handles through API calls and we’re very rate-limited on the both ends, but a 3 hours gain with such a simple technique is a huge win in my opinion.

Of course, the operation performed can be whatever it needs to be, I took the example of an HTTP call but it can be an expensive math calculation, a huge JSON (de)serialization, anything, it doesn’t matter, the idea is the same.

Maybe you already knew this technique or didn’t know it had a name, but I figured I’d share it because you would not believe the number of situations I’ve seen where the same exact operation were executed over and over again.

Anyway, hope this was helpful, happy coding and remember… have fun.