A simple asynchronous memoizer

2021-05-24

Data arriving later (latency) is business as usual in a world entangled in API calls, database requests, and applications present Online rather than on our machines. In some respects, this has consequences for - or should have - how one write code.

In a synchronous universe the notion of ‘memoization’ make sense. Depending on how advanced a calculation is, memoization potentially saves the day and has been elevated to the JavaScript mainstream by React. But in reality, memoization is limited and especially so in a cloud computing environment such as AWS Lambda because of its short live span.

A simple, yet decently effective implementation of memoize could look something like this:

function memoize(fn) {
  const calculatedValues = new Map();
  return function (...args) {
    const argsString = JSON.stringify(args);
    if (calculatedValues.has(argsString)) {
      return calculatedValues.get(argsString);
    }
    const result = fn(...args);
    calculatedValues.set(argsString, result);
    return result;
  };
}

If this memoize would be applied to a bad function for producing the sum of 1..n positive integers, much time and computing power could be saved. In fact, this task can be solved with constant speed and simple means,

const isEven = (n) => n % 2 === 0;

const sumRangeOneTo = (n) => isEven(n)
 ? (n + 1) * Math.floor((n + 1) / 2)
 : n * Math.floor(len / 2) + n;

But since the purpose is to make a case in point about why asynchronous ‘memoization’ can be useful, we’ll make a progressively slower version (depending on the size of n),

const sum = (a, b) => a + b;

function sumRangeOneTo(n)  {
  return Array
    .from(
      {length: n},
      (_, i) => i + 1
    )
    .reduce(sum, 0);
}

With a large set, this solution would be very slow. And every time someone called sumRangeOneTo(10000000) the function would start over. Using a memoized version one would only make the calculation once,

const memoizedSum = memoize(sumRangeOneTo);

Every consecutive call to memoizedSum(10000000) would achieve the result using a look-up.

However, since the memoize function uses an in-memory data structure it is not persistent and the computer running it eventually would have issues with the working memory.

One possible solution would be to use a memoization technique using a persistent data structure, such as a database. I've made a solution for adding positive integers 1..n using an asynchronous logic, AWS lambda, and DynamoDB for persistence.

For an advanced calculation, there is a breaking point using this solution. This property is shared with Workers and WebAssembly alike, ‘it must be worth it’. If one would use a small set, an asynchronous solution would be slower since it involves a database request. On the other hand, with an established break-point one could make a solution using two functions and some kind of heuristic. For small values, use the synchronous solution and for larger sets, use the asynchronous. But since this heuristic would have to be a result of experimentation and careful, contextual deliberation. I’ve only made a proof of concept using my bad sumRangeOneTo.

The full solution is available at GitHub. If you'd want to try it follow the instructions present on GitHub. Because of how AWS DynamoDB payments works (however cheap), I don't want to host it publically.

The present solution is not generic, but could easily be refactored to correlating a function name with a dynamically created DynamoDB table. I've added a few unnecessary lines of code to prettify the result.

// handler.js

"use strict";

const AWS = require("aws-sdk");
const { promisify } = require("util");

const returnFromLambda = (statusCode, body) => ({
  statusCode,
  headers: {
    "Access-Control-Allow-Origin": "*",
    "Access-Control-Allow-Headers": "*",
    "Access-Control-Allow-Methods": "*",
    "Content-Type": "text/html",
  },
  body,
});

const db = new AWS.DynamoDB.DocumentClient();
const dbPut = promisify(db.put).bind(db);
const dbGet = promisify(db.get).bind(db);

const sum = (a, b) => a + b;

const sumRangeOneTo = (n) =>
  Array.from({ length: n }, (_, i) => i + 1).reduce(sum, 0);

const html = (body) => `
<!DOCTYPE html>
<html lang="en">
<head>
  <title>Sum positive ints 1..n</title>
  <meta charset="UTF-8" />
  <meta name="viewport" content="width=device-width,initial-scale=1" />
  <link rel="preconnect" href="https://fonts.gstatic.com">
<link href="https://fonts.googleapis.com/css2?family=Oswald:wght@300&display=swap" rel="stylesheet">
</head>
<style>
* { font-family: Oswald, sans-serif; }
h1 { size: 200%; }
</style>
<body>
  <h1>Sum positive ints 1..n</h1>
  ${body}
</body>
</html>
`;

module.exports.calculate = async (event) => {
  if (
    !event.queryStringParameters ||
    !event.queryStringParameters.len ||
    !Number.isInteger(parseInt(event.queryStringParameters.len, 10)) ||
    parseInt(event.queryStringParameters.len, 10) <= 0
  ) {
    return returnFromLambda(
      403,
      html(
        `
        <h2>Invalid params...</h2>
        <p>{BASE_URL}/dev/api/calculate?len=POSITIVE_INT</p>
        <p>Example call: {BASE_URL}/dev/api/calculate?len=1999999999</p>`
      )
    );
  }
  const len = parseInt(event.queryStringParameters.len, 10);
  const getParams = {
    TableName: "sumtable",
    Key: {
      id: JSON.stringify({ len }),
    },
  };
  const startStamp1 = new Date().getTime();
  const response = await dbGet(getParams);
  if (response.Item) {
    const endStamp1 = new Date().getTime();
    return returnFromLambda(
      200,
      html(
        `<h3>Result (fetched entry from db)</h3>
        <p>1..${event.queryStringParameters.len} summed is ${
          response.Item.result
        }</p>
        <p>Calculation time: ${response.Item.calcTime} ms.</p>
        <p>Time to fetch from DB: ${endStamp1 - startStamp1} ms.</p>`
      )
    );
  }
  const startStamp2 = new Date().getTime();
  const newResult = sumRangeOneTo(len);
  const endStamp2 = new Date().getTime();
  const putParams = {
    TableName: "sumtable",
    Item: {
      id: JSON.stringify({ len }),
      result: newResult,
      calcTime: endStamp2 - startStamp2,
    },
  };
  await dbPut(putParams);
  return returnFromLambda(
    200,
    html(
      `<h3>Result (new entry in DB)</h3>
      <p>1..${event.queryStringParameters.len} summed is ${newResult}</p>
      <p>Calculation time: ${endStamp2 - startStamp2} ms.</p>
      <p><em>The next time the result is not calculated but grabbed from the database.</em></p>
      <p><button onclick="location.reload()">Click me to grab from db.</button></p>
      `
    )
  );
};

About | Archive