DEV Community: Lei Huang

A way to memoize Promises

Lei Huang — Thu, 08 Jul 2021 13:16:13 +0000

It's not rare in frontend development that multiple parts of a page request the same data from a remote API. To avoid duplicate requests, you may want to factor out the request to a state manager. Then, the question comes to whose responsibility is it to initialize the API call? The natural tendency is to call it when the root component loads, which is standard practice, but I'd argue that it's less maintainable. If, for some reason, you later need to remove all the components that need the data, then you have to remove the API call that lives somewhere else as well. I'd like to propose a better approach.

Instead of delegating the network request work to the outer world, each component should make its own request. We can avoid duplicate requests by memoizing the result of the first request.

Here's how we can memoize the result of a promise-returning function:

function memoPromise(asyncFn, expiresIn) {
  const memo = {}
  const statusMap = {}
  const resolves = []
  const rejects = []

  return async function memoizedFn(...args) {
    if (args.length === 0) { 
      throw new Error(
        "Must provide at least one serializable argument to generate an unique cache key"
      )
    }

    const memoKey = args.toString()

    if (memo[memoKey]) {
      return Promise.resolve(memo[memoKey]())
    }

    if (statusMap[memoKey] === "pending") {
      return new Promise((_res, _rej) => {
        resolves.push(_res)
        rejects.push(_rej)
      })
    }

    try {
      statusMap[memoKey] = "pending"
      const result = await asyncFn(...args)
      statusMap[memoKey] = "success"
      memo[memoKey] = function get() {
        if (typeof expiresIn === "number" && expiresIn > 0) {
          setTimeout(() => {
            memo[memoKey] = null
            statusMap[memoKey] = null
          }, expiresIn)
        }

        return result
      }
      resolves.forEach(res => res(result))
    } catch (err) {
      statusMap[memoKey] = "error"
      rejects.forEach(rej => rej(err))
      throw err
    }

    return memo[memoKey]()
  }
}

memoPromise is a higher order function that receives a promise-returning function and returns a new function. If we call the new function multiple times simultaneously, the calls after the first one will return a promise that resolves the result fetched by the first call, or rejects if the first call fails.

Optionally, you can pass a expire number to invalidate the memoized result after some time.

Let's put memoPromise to use and make a memoized fetch that invalidate the result after 5 seconds:

// utils.js
export const memoizedFetch = memoPromise(fetch, 5000)

Then we can call the same API in different components without worrying about duplicate requests:

// component 1
import { memoizedFetch } from './utils'

const result1 = await memoizedFetch('https://fakeapi.com/end-point').then(res => res.json())

// component 2
import { memoizedFetch } from './utils'

const result2 = await memoizedFetch('https://fakeapi.com/end-point').then(res => res.json())

Time-slicing With Continuation-passing Style

Lei Huang — Tue, 18 Aug 2020 01:04:26 +0000

Background story

In January this year, I applied for an overseas dev job. I was asked to finish a project as homework. The project required a ton of computations done on the front end, which poses a challenge as I must ensure no operations should block the main thread. I don't want to move the computation to a worker thread because the data is consumed in the main thread. Serializing and de-serializing a large set of data also has a performance cost. Furthermore, to improve indexing performance, I used Map to store the results, which is not serializable.

The task involved is as following:

Process a long list of news items, and index each item according to its tags. It looks like this in code:

const newsList = [
  {
    uid: '8be34939-bc25-4b9e-999d-2daf19fbea7b',
    title:
      'Adipisicing do eu magna ex non est eu labore nisi duis enim elit.',
    tags: ['reprehenderit', 'cupidatat', 'ad', 'ea', 'labore'],
  },
  {
    uid: '488399fc-e474-4c52-a36c-625e2218fabe',
    title: 'Elit aute tempor dolore do sunt.',
    tags: ['sint', 'ea', 'Lorem', 'consectetur', 'officia'],
  },
  {
    uid: '0340b317-bd55-4c43-9982-94bf9d08b977',
    title: 'Aliquip qui est sint veniam consectetur.',
    tags: ['sit', 'ullamco', 'consectetur'],
  },
  // ... omit remaining tens of thousands of items
];

const newsMap = new Map();

newsList.forEach((news) => {
  news.tags.forEach((tag) => {
    if (!newsMap.has(tag)) {
      newsMap.set(tag, [news]);
    } else {
      newsMap.get(tag).push(news);
    }
  });
});

In practice, I'd never done massive computations on the front-end, as JavaScript is not very efficient in handling CPU-intensive work. However, after some google search, I found a way to get around this limitation. The idea is to slice a big task to multiple ones and put them to different ticks of the event loop.

Time-slicing to the rescue

If you've been working with React long enough, you've probably heard of React Fiber and time-slicing. React Fiber is a new reconciliation algorithm inside of the React core. It was designed to enable React to handle computations(mostly diffing caused by setState) in a non-blocking way. When high priority tasks occur due to user inputs, React can pause low priority tasks and handle them immediately.

The fiber architecture is very complicated. The implementation of it is quite cryptic and daunting. Implementing a fiber algorithm in my little project would be an overkill, if not infeasible. However, I can still do time-slicing in JavaScript in an easier way.

The solution lies in JavaScript's power in asynchronicity and callback functions. Encountered with asynchronous tasks, we tend to shun away from callbacks because of the dreaded "callback hell." However, when handled properly, callbacks and asynchronicity are a good fit. The callback soup I'm about to introduce is very powerful and irreplaceable.

If you used to pass callbacks in Ajax programming or node.js event handlers, you already know the technique I'm going to show you. I just find a fancier name for it: CPS(Continuation-passing Style).

What is CPS

Here's an identity function you would write normally:

function id(x) {
  return x;
}

and here is a CPS version:

function id(x, cb) {
  cb(x);
}

In continuation-passing style, instead of "return" the procedure to its caller, you invoke the "current continuation" callback (provided by the caller) on the return value.

The foundation of CPS is simple:

Procedures can take a callback to invoke upon their return value.

Slice it up!

The atomic operation we need to do in processing the list is as following:

function indexNews(item, tag) {
  if (!newsMap.has(tag)) {
    newsMap.set(tag, [item]);
  } else {
    newsMap.get(tag).push(item);
  }
}

So we need to slice our previous one big task to many small tasks like the above one. Here's how to do it:

function indexNews(item, tag, continuation) {
  if (!newsMap.has(tag)) {
    newsMap.set(tag, [item]);
  } else {
    newsMap.get(tag).push(item);
  }

  continuation();
}

function iterate(list, processTask, continuation) {
  function handleOne(i, j, _continuation) {
    if (i < list.length) {
      const item = list[i];
      if (j < item.tags.length) {
        processTask(item, item.tags[j], function handleNext() {
          handleOne(i, j + 1, _continuation);
        });
      } else {
        handleOne(i + 1, 0, _continuation);
      }
    } else {
      _continuation();
    }
  }

  handleOne(0, 0, continuation);
}

iterate(newsList, indexNews, () => {
  // Indexing is done,
  // we can enable features that depend on indexing safely here.
  console.log('done');
});

This introduces too many recursions and makes our code way more complicated without improving performance. But we are very close!

Notice a very important feature of the indexNews function. It takes a continuation callback and calls the continuation after finishing the current task. We've achieved "Inversion of Control" here. We can tell indexNews what to do in the next iteration.

In our case, we want it to move subsequent tasks to different new call stacks so that we don't put too much pressure on the current call stack.

However, we don't want to move every task to its own call stack, which is unnecessary.

So, here's the rule:

Each call stack can take 500 tasks, after that limit, we put the next new tasks in the next call stack. Repeat until all tasks are done.

We just need a few modifications to our previous code to achive this:

function indexNews(item, tag, continuation) {
  if (!newsMap.has(tag)) {
    newsMap.set(tag, [item]);
  } else {
    newsMap.get(tag).push(item);
  }

  if (indexNews.skip++ % 500 === 0) {
    setTimeout(continuation, 0);
  } else {
    continuation();
  }
}
indexNews.skip = 0;

Because of how event loop works in JavaScript, the setTimeout method will move its callback to the next execution call stack.

Summary

We introduced a technique we already know and rediscovered the hidden power of it. Continuation-passing Style enables us to have control over what happens next when the current operation is completed. Relying on this feature, we first sliced a very big task to many small ones, and then chunk them to different call stacks.

Check out the project here.

Typewriter Effect With RxJS

Lei Huang — Mon, 30 Mar 2020 04:01:25 +0000

Background

I recently rewrote my blog website from scratch in Gatsby. This time, I didn’t use a starter template, so I had to make a lot of design decisions. When I wrote the bio section on the home page, initially I put a long heading there as a one-sentence introduction. As I was gazing at the screen, I felt something was wrong. It was too wordy. But after I took out a few words, I was not satisfied with what was left.

After some trying, I came up with an idea. Why not add a typewriter to present more contents with less space? It also adds a lot of fun and dynamic to the page. It seems like legit reasoning, so I did it. I was satisfied at this time.

A typewriter effect requires dealing with asynchronicity. I can do it in vanilla JavaScript, but the result code would be very complex, with a lot of timer events scattering around. When dealing with complex asynchronous event handling, my rule of thumb is to use tools that help me focus on the desired effects, rather than the housekeeping juggling work. RxJS stands out as my tool of choice for this role.

Why RxJS?

As I see it, the greatest power of RxJS is that it enables you to encode time into values. Time becomes tangible and can be mixed and matched with other values. In the movie Arrival, an alien language can encode time in itself, so the speaker of that language is capable of foreseeing the future. RxJS is similar in a sense. When programming, you’re the dictator of all events, you already knew what will happen before you start. In RxJS, or reactive programming in a broader sense, you can encode future events in a placeholder (I try to avoid 'variable' because it may be confusing for beginners) as you declare it.

Think about the typewriter effect. What we really want is to display different texts on the screen over time. For instance, if we want to type ‘hello’ and then delete it, we want the texts delivered to us over time like this:

// type
h---he---hel---hell---hello

// pause
-------------

// delete
hello---hell---hel---he---h

// pause
-------------

We can tell RxJS, “Hey, this is the word, I want you to slice it up like this and give the pieces back to me over time.”

Encode time in values

After we have a clear vision of what we want, let’s do it and write the code!

Start with the basics. We need to type a single word first. It’s easy.

const type = ({ word, speed }) =>
  interval(speed).pipe(
    map(x => word.substr(0, x + 1)),
    take(word.length)
  );

The interval source will fire up events as per the speed value we provide in milliseconds. Each time it will emit a number increasingly. When the event occurs, we map the emitted value to characters from the word. The interval timer will fire indefinitely, but we only take what we want. After passing the limit specified by the take operator, the timer will stop.

We also need a delete effect. Let’s add a parameter ‘backward’ to the type function. We slice differently when ‘backward’ is specified.

const type = ({ word, speed, backward = false }) =>
  interval(speed).pipe(
    map(x =>
      backward
        ? word.substr(0, word.length - x - 1)
        : word.substr(0, x + 1)
    ),
    take(word.length)
  );

To combine the type-pause-delete-pause effects together, we need the concat operator to concatenate 4 event sources (we'll call them observables from now on)

const typeEffect = word =>
  concat(
    type({ word, speed: 70 }), // type
    of('').pipe(delay(1500), ignoreElements()), // pause
    type({ word, speed: 30, backward: true }), // delete
    of('').pipe(delay(300), ignoreElements()) // pause
  );

We type and delete at different speeds. And also pause differently after typing and deleting. For pausing effect, we emit an empty string and delay the event. ignoreElements operator just ignore emmited values. This is to only encode time itself and discard any values.

Then we move on to type multiple words. Using the from operator, we can turn an array into an observable, which is a term to describe "values over time". After this, we know RxJS will feed us the items in the array over time. But how frequently? In what form? We’ll tell RxJS in the pursuing operators.

const value = useObservable(() =>
  from(words).pipe(concatMap(typeEffect), repeat())
);

useObservable is a helper function to turn values emitted from observables into React state.

we use concatMap to map every word into a new observable and concatenate them. Say we feed RxJS value [‘hello’, ‘how are you’, ‘bye’ ], in a diagram, it will look like this:

---------typeEffect(‘hello’) ----typeEffect(‘how are you’)---typeEffect(‘bye’)---

The repeat operator tells RxJS to repeat the source observable forever.

That's all the code you need to build a typewriter effect!

Here is a fun demo:

Algorithms in Go: Length of the Longest Substring

Lei Huang — Mon, 09 Mar 2020 12:04:54 +0000

Finding the length of the longest substring of a given string is a very common algorithms question in interviews. In this post, I'm going to walk you through how to solve this problem in Go.

The problem

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with a length of 3.

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with a length of 1.

Explain the solution

I'll be using a technique called sliding window. Here is how it works:

Iterate over the string.
Maintain two pointers to represent the left and right bound of a window. Both two pointers start at index 0.
As we iterate along the string, the right pointer acts as the looping counter, while the left pointer stays where it was, unless the right pointer encounters a character that was visited before, and the left pointer is behind the visited character. When this happens, the left pointer moves to the next iteration position.
To determine if a character was already visited or not, we need to maintain a hash map to store the indices of every character that the right pointer has encountered.
For each iteration, we calculate the window length and compare it with the previous longest length. If the current length is longer, we update the longest length record.
When the iteration finishes, we'll have the longest window length.

Solution

func lengthOfLongestSubstring(s string) int {
    // making a map the go way
    m := make(map[byte]int)
    res := 0

    for l, r := 0, 0; r < len(s); r++ {
        if index, ok := m[s[r]]; ok {
            // only update the left pointer if 
            // it's behind the last position of the visited character
            l = max(l, index)
        }
        res = max(res, r-l+1)
        m[s[r]] = r + 1
    }
    return res
}

func max(n, m int) int {
    if n > m {
        return n
    }
    return m
}