The Pipelined Pancake Party - demonstrating the Power of Parallelization and Pipelining in JavaScript with Promises and Asynchronous Generators image 31

The Pipelined Pancake Party – demonstrating the Power of Parallelization and Pipelining in JavaScript with Promises and Asynchronous Generators

This article is an attempt to demonstrate the performance gains – and programming elegance – that is at our disposal with the advent of asynchronous generators in ES 2018 (JavaScript), for example in Node 10 and later. With asynchronous generators and Promises, we can implement parallel, asynchronous and pipelined processing that allow us to process a result set ahead of time.

The business case at hand… a pancake party (this may be a very Dutch example). The situation is like this: eight children attend a birthday party. At some point, they are done running around and want to be fed. They have been promised pancakes, a typical treat for a Dutch birthday party. The challenge now is to get pancakes to the young and perhaps not so patient guests. Starting from a naïve approach (when my son turned 6) to a smarter approach (we acquired skills over the years), we managed to get the time-to-first-pancake-on-plate down to less than 5% of what it originally was and the time to done-baking-start-cleaning down to less than 35% of what is was at first.

The process is outlined in this visualization: (I left out the preparation of the batter, as that can be done ahead of time, as well as all cleaning and washing up – as I leave that to my wife)

  1. Bake the pancake
  2. Decorate the pancake with toppings and happy faces
  3. Cut the pancake in bitesize pieces for quick and smooth processing
  4. Handout the pancake to the loudest person
  5. (eat the pancake) (of course done by the guests themselves, but part of the overall process and time lapse

image

We will assume eight guests that each eat three pancakes.

And we will soon be looking at some JavaScript code as well. Promise.

The Naïve Approach

The naïve approach I applied to the first pancake party was the following:

Using a single pan, bake a big stack of pancakes. Decorate all pancakes. Cut all pancakes. Using a single plate: tut one pancake on the plate and hand it to child number one. When that child is done with that pancake, put the second baked, decorated and sliced pancake on the plate and hand it to child number two.

image

You may get the feeling that this approach is not ideal. And it is not.

However, in programming, we may not have capabilities in our language to make use of parallelism, asynchronous operations and pipelining. And we may very well be forced to come up with something like a naïve approach.

image

Function bakeAllPancakes() is invoked from orchestrator function party to produce the full stack of pancakes, returned as an array of pancake objects. Function bakeOnePancake() is invoked as many times as the number of required pancakes. The function sleeps for approximately timeToBakeOnePancake to simulate the actual baking of the pancake.

Function party next invokes function decoratePancakes() with the full stack of pancakes (the entire array). This function iterates over the pancakes and decorates each one with a randomly selected topping. It sleeps during timeToDecoratePancake , to simulate the decoration processing time. When all pancakes have been decorated, the full stack of all decorated pancakes is returned – a complete array again. Function party next invokes function sliceAndDicePancakes(). This function slices the pancakes, processing one by one in much the same way as decoratePancakes() does. The result – an array of sliced and diced and ready to eat pancakes – is returned when all processing is done.

Function party can now start to make eaters happy. This function does a loop over three eating rounds (based on the assumption that each guest eats exactly three pancakes), and then loops over the guests. Then, a pancake is handed to a guest – a call is made to function eatPancake(). This too is an asynchronous function – because it uses the sleep() function to simulate the time it takes to eat a pancake. Only when eatPancake returns does party continue with handing the next pancake to the next guest. Excruciating, isn’t it? It results in very long time to first pancake delivery and of course much longer to all pancakes eaten.

Here is the output from executing the code for this naïve approach. Note: when a close comparison is made to the real world (of the pancake party), this code feels incredibly stupid. However, are you sure that your code would never be so laughably sequential when the comparison is not so easily made?SNAGHTML1723c5c7

 

image

 

The JavaScript code that implements this straightforward, unthinking approach is shown below:

The upgraded application code is accessible at GitHub: https://gist.github.com/lucasjellema/3e6070399dfbfd0033c0b646ab97fb95#file-pancake-party-0-js

https://gist.github.com/lucasjellema/3e6070399dfbfd0033c0b646ab97fb95.js?file=file-pancake-party-0-js 

Smart Approach – Using Asynchronous and Parallel Processing and Pipelining

In real life, we know we can be much smarter about the pancake birthday party.

Why use only a single pan. Why not leverage the stove (and our collection of pans) to the fullest? Doing things in parallel is typically one of the best ways to speed things up – if we have the resources available for running the processes in parallel.

Why not take the pancakes immediately when they have been baked to be decorated, followed by slicing and dicing and handing to a guest for eating? Pipeline all the way through all steps. If we have the resources, we can have baking, decorating, slicing and eating taking place all at the same time.

And why use a single plate and hand out one pancake at a time? Why not handout pancakes to all guests so they can eat at the same time?

image

This can be done in JavaScript code as well.

Even though JavaScript runs in a single thread execution environment, many actions involve waiting for input from the external world and can be executed in an asynchronous way. Multiple asynchronous activities can be executed in parallel – assuming that they are waiting for a substantial portion of the time. Promises are a fairly recent addition to JavaScript that make handling asynchronous activities fairly easy to program.

Note: the asynchronous activity in this example application is represented by the sleep() function. In real application, there would not be a sleep() function, but instead a call to an external service, a query against a database or a file read or write activity – all actions that involve substantial wait time and allow for parallelization to be taken advantage of.

Function bakeAllPancakes() has been improved with support for parallelism: it works with multiple pans and the pans are put to work in parallel. A promise is returned from function bakeOnePancake(). These promises will at some point resolve to real results – in our case: real pancakes. Promise.all(bakingNow) is our instruction to wait on all pans to deliver their pancake. When the fresh pancakes are in, they are yielded.

Yield is similar to return. Yet different. JavaScript has introduced support for generator functions. These are functions that return multiple results. But instead of returning the result set as one chunk of data – as an array or set for example – the result is returned one by one. And the invoker of the generator function can start processing the results one by one as soon as they become available. This is the foundation for pipelining in JavaScript. In ES 2018, support was added for asynchronous generator functions. This means that the results can be produced by the generator function using promises or other asynchronous mechanisms. That is the crucial link for pipelining asynchronously produced results.

In our code, this mechanism enables some drastic changes. Function party is still in the driving seat. However instead of calling bakeAllPancakes(), decoratePancakes() and sliceandDicePancakes one by one, strictly sequentially and passing the complete array of pancakes back and forth, party() now uses a single pipe line that engages these functions (now all generator functions) on elements generated at the initial generator function to have these elements processed through the entire pipeline as quickly as possible.

This single line of code defines the pipeline and triggers most of the processing.

readyToEatPancakes = sliceAndDicePancakes(decoratePancakes(bakeAllPancakes(totalNumberOfPancakes)))

Variable readyToEatPancake hold an iterable – which can be regarded as a Promise to multiple results. By calling next() on this iterable, these results can be retrieved – as promises (to a real result). When bakeAllPancakes yields the first batch, the first pancake of that batch is decorated, sliced and becomes available for eating. Function party hands pancake promises retrieved  to function eatPancake(). This function also returns a promise that resolves when the pancake has been eaten. Function party does not await the resolution of the promise – it hands out pancake promises to all eaters as quickly as it can. When all guests have received a pancake (promise), function party uses Promise.all(<all handed out pancake promises>) to wait for all guests to finish eating their pancakes. When all guests are done with their pancake, all promises are resolved and Promise.all() completes. The next round can start in party() until all rounds are complete.

The new implementation can be visualized as follows:

image

The upgraded application code is accessible at GitHub: https://gist.github.com/lucasjellema/3e6070399dfbfd0033c0b646ab97fb95#file-pancake-party-2-js

I run the new code, for two pans and otherwise the same settings as before.

The first section of logging is shown here. We can see parallel activity – with Guest 1 eating their pancake very early on while at that same time pancake two is decorated and sliced and pancakes three and four are baked.

image

Here we see the last section of the logging. What we notice of course are the vast improvements in time (from 11 to 0.5 for the first pancake on a plate an from 18.2 to 8.9 for all pancakes eaten; with four pans, we are completely done in 7.1). What should also strike you from this logging is the massive parallel activity. While Guest 5 is eating pancake #21, pancake 22 is decorated and sliced, pancakes 23 and 24 are baked and pancake 22 is attacked by Guest 6. Instead of one activity taken place at any one moment in time – as was the situation in the naïve approach – we now have

image

Summary

From this somewhat silly example, we can draw some serious lessons. Parallel execution of (asynchronous) activities is a great way to speed up the overall process. Promises are the key mechanism in JavaScript to make such parallel activities happen. A different type of parallelism is pipelining when multiple subsequent activities on a set of elements are carried out at the same time – on different elements – and each element is produced by each step as quickly as possible (instead of processing the whole set in its entirety in each step). Asynchronous generator functions in JavaScript (introduced in ES 2018) are the crucial enabler for this behavior.

Whenever you find yourself writing code in JavaScript that processes a set of elements and that takes long to complete – there may be hope for improvement. By executing activities in parallel and by speeding up the delivery at least of the first results from that set of input elements.

I hope this article gives you some inspiration for introducing such thinking and the associated mechanisms in your own application.

 

Resources

Code (GitHub Gist)

First appearance of the Pipelined Pancake Party in my JavaOne 2012 presentation “Thinking Through Enterprise Performance” on SlideShare: https://www.slideshare.net/AMIS_Services/oow-2012-thinking-through-java-enterprise-performance-lucas-jellema

Iterate partial results of Promise.all – https://agentcooper.io/iterate-promise-all/

JavaScript Arrays — Finding The Minimum, Maximum, Sum, & Average Values – https://codeburst.io/javascript-arrays-finding-the-minimum-maximum-sum-average-values-f02f1b0ce332

Moving Average (Wikipedia) – https://en.wikipedia.org/wiki/Moving_average

How to make your JavaScript functions sleep – https://flaviocopes.com/javascript-sleep/

Javascript – Generator-Yield/Next & Async-Await – https://codeburst.io/javascript-generator-yield-next-async-await-e428b0cb52e4

Asynchronous Generators and Pipelines in JavaScript – https://dev.to/nestedsoftware/asynchronous-generators-and-pipelines-in-javascript–1h62

Let’s experiment with functional generators and the pipeline operator in JavaScript – https://medium.freecodecamp.org/lets-experiment-with-functional-generators-and-the-pipeline-operator-in-javascript-520364f97448