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)
- Bake the pancake
- Decorate the pancake with toppings and happy faces
- Cut the pancake in bitesize pieces for quick and smooth processing
- Handout the pancake to the loudest person
- (eat the pancake) (of course done by the guests themselves, but part of the overall process and time lapse
We will assume eight guests that each eat three pancakes.
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.
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.
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?
The upgraded application code is accessible at GitHub: https://gist.github.com/lucasjellema/3e6070399dfbfd0033c0b646ab97fb95#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?
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.
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:
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.
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
I hope this article gives you some inspiration for introducing such thinking and the associated mechanisms in your own application.
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/
Moving Average (Wikipedia) – https://en.wikipedia.org/wiki/Moving_average