Introduction
This piece of code will leak memory and eventually crash your Node.js process or browser:
// Tested on Node.js 7.10, Firefox 57 and Chrome 61
//
// Usage of `setImmediate` is to prove that we have
// async boundaries, can be removed for browsers
// not supporting it.
function signal(i) {
return new Promise(cb => setImmediate(() => cb(i)))
}
function loop(n) {
return signal(n).then(i => {
if (i % 1000 == 0) console.log(i)
return loop(n + 1)
})
}
loop(0).catch(console.error)
It takes a while to fill GBs of heap, plus Node is less conservative, the GC eventually freezing the process trying to recover memory, so give it a few seconds.
This is equivalent with this async
function:
async function loop(n) {
const i = await signal(n)
if (i % 1000 == 0) console.log(i)
// Recursive call
return loop(n + 1)
}
Of course, if this loop would be synchronous, not using Promise
or async
/ await
,
then the process would blow up with a stack overflow error because
at the moment of writing JavaScript does not do
tail calls optimizations
(until everybody implements ECMAScript 6 fully at least).
But before you jump to conclusions, this has nothing to do with JavaScript’s
lack of TCO support. This is because in our recursive function it’s
not JavaScript’s call stack
that’s managing that loop, but rather the Promise
implementation.
That recursive call is asynchronous and so it does not abuse the call stack
by definition.
Unfortunately, just like a regular function using the call stack for those
recursive calls, the Promise
implementation is abusing the heap memory,
not chaining then
calls correctly. And that sample should not leak,
the Promise
implementation should be able to do the equivalent of TCO
and in such a case eliminate frames in the then
chain being created.
The Spec is The Problem #
We’re talking of the Promise/A+ specification. Relevant links to known issues on GitHub, explaining why:
- Node.js issue, now closed: node/#6673
- Promise/A+ spec issue, open since 2014: promises-spec/#179
As you’ll see, there are some reasonable arguments for why the Promise
implementation is allowed to leak memory. But I can’t agree.
The Non-leaky Solution #
The solution, if you insist on using JavaScript’s Promise
, is to work
with non-recursive functions:
async function loop(n) {
let i = 0
while (true) {
i = await signal(i + 1)
if (i % 1000 == 0) console.log(i)
}
}
But at this point any semblance of functional programming, if you ever had any, goes out the window, see below.
Common Objections #
Gathering feedback from people, here are the common objections:
1. This is Normal #
No, if you judge this implementation, relative to other Promise
/ Future
implementations in the industry, which are setting expectations.
Here are the implementations that I know about that DO NOT leak memory:
- Bluebird, probably
the most popular non-standard
Promise
implementation for JavaScript - Scala’s standard
Future,
in the wild since 2013; the fix for the leaky
flatMap
chains was added by Rich Dougherty in this PR, inspired by Twitter’sFuture
implementation - Twitter’s Future, which is used in all of Twitter’s backend infrastructure, being integrated in Finagle
- Trane.io, a Java Future implementation providing a
TailRec
builder meant precissely for this use-case - My very own Funfix Future and Monix CancelableFuture
Interestingly, complaints for Scala’s Future
happened due to usage of
Play’s Iteratees,
with which people have been modeling stream processing.
2. But It Does Unlimited Chaining of Promises #
Yes, that’s why it’s leaking memory.
No, the implementation should not chain promises like that and an alternative implementation is possible and well known, as evidenced by the implementations mentioned that don’t leak.
The fault lies with the standard Promise
implementation, not with
the shown sample, being a legitimate use-case.
3. That Sample Does Not Use the Return Value #
The sample is kept simple for didactic purposes, however:
- you can easily imagine a loop that processes a very long stream of data, aggregating information along the way, returning a result later
- the script does do error handling and without that inner
return
, the.catch(console.error)
would have no effect
4. That’s the Equivalent of a Stack Overflow #
Yes, I’ve mentioned this above, but just to set your mind at rest on this point, proper Tail-Calls Optimizations are coming for normal call sites, being part of ECMAScript, see:
You can’t rely on it yet, but you can rest assured that in the future if that sample would be synchronous, it would not trigger a stack overflow.
Therefore, given that asynchronous calls are by definition processes / events happening independently of the current call stack / run loop, this behavior is actually surprising, since one of the reasons to go async is to escape the limitations of the call stack.
5. You Don’t Understand How Promises Work #
I’ve been told that I don’t understand promises. So I apologize for the appeal to authority that I’m about to make.
Data types for dealing with asynchrony have been a hobby of mine since 2012 and I’ve been authoring several projects in which I implemented Promise-like data types:
- Monix, which implements
Task
, one of the best ports of Haskell’sIO
, along with a complementaryCancelableFuture
and what I think is the best back-pressured RxObservable
implementations in existence - Funfix, a JavaScript library for FP,
delivering a
Future
and anIO
implementation, see below - have contributed to cats-effect,
a more conservative
IO
port
Bonus — see my presentation from Scala Days!
My work, good or bad, has followed a certain pattern, which is why I do understand promises, I do understand at least two solutions to this, hence this article.
6. No Use-cases, This is a Niche #
Functional programming might be a niche, however more and more projects, including at big companies such as Facebook, are now using an actual FP style.
You cannot describe any functional programming algorithm involving loops without tail recursions. If folds are used, then folds are described with tail recursions as well. That’s because:
- any loop can be described with a tail recursion
- you can’t have immutability of the state you’re evolving without it
An example of a use-case is the processing of really long / infinite streams of events, for which it’s really natural to describe algorithms using tail recursions and for which you can’t really work with imperative, mutation-based loops.
Imagine reading chunks of data from a file and describing them with a data structure like this:
interface List<A>
class Next<A> implements List<A> {
constructor(
public readonly head: A,
public readonly next: () => Promise<List<A>>
) {}
}
class Halt implements List<A> {
constructor(public readonly error?: any) {}
}
Sample is using TypeScript (could be Flow) for making it clear what the types are. You can work with plain JavaScript of course.
This structure is really cheap and effective, being a lazy, asynchronous, referentially transparent stream. And in fact it’s really similar to JavaScript implementations of async iterators, so yes, you are going to work with something like this in the future, even if you don’t like it ;-)
And describing transformation functions like this one is really fun too:
function map<A, B>(list: List<A>, f: (a: A) => B): List<B> {
if (list instanceof Next) {
try {
const cons = list as Next<A>
return new Next(f(cons.head), () => cons.next().then(xs => map(xs, f)))
} catch (e) {
return new Halt(e)
}
} else {
return list
}
}
Alas, with the Promise
implementation leaking, this doesn’t work ;-)
Alternatives #
Fluture #
Project Page: github.com/fluture-js/Fluture
This is the most popular Promise
alternative that I know of.
It isn’t a direct replacement however because it has lazy behavior, being meant for suspending side effects. This is more like an IO
data type. Which is cool, you should use something like it, but it’s also apples vs oranges.
I don’t have enough experience with it, making this recommendation solely based on its popularity and I double checked that it indeed preserves stack safety.
Funfix #
I’ve been building a new project, Funfix, a JavaScript library for functional programming (capital FP), supporting TypeScript and Flow types out of the box.
Funfix exposes Future<A>, an
eager Promise
alternative that’s safe, cancellable and filled with goodies,
along with IO<A>, a lazy, lawful,
cancellable data type for handling all kinds of side effects, inspired by Haskell,
the two being complementary.
This piece of code powered by Future
does not leak:
import { Future } from "funfix"
function loop(n) {
return Future.of(() => n).flatMap(i => {
if (i % 1000 == 0) console.log(i)
return loop(n + 1)
})
}
loop(0).recover(console.error)
And neither does this one, powered by IO
:
import { IO } from "funfix"
function loop(n) {
return IO.of(() => n).flatMap(i => {
if (i % 1000 == 0) console.log(i)
return loop(n + 1)
})
}
loop(0).run().recover(console.error)
This IO
is a port of Monix’s
Task, being a better
IO
than Haskell’s IO
due to its cancellable nature ;-)
In this PR I’ve also
fixed the memory leak for Future
, doing the same tricks that
Scala’s Future
is doing. Now released in v6.2.0.
And note that this is harder to do for Funfix’s Future
due to also
having to deal with chains of Cancelable
references, which can
also leak.
Author’s Rant — in response to this article I’ve been called a scumbag
for “shameless self promotion”.
I’m building stuff that I share with the world and I like talking about
it on my personal blog. I’m not going to apologize for it.
Final Words #
That the current JavaScript Promise
implementation has this leak
is a big problem, because tail-recursive calls are the cornerstone
of functional programming.
Yes, it’s true that Promise
is not a useful monadic type for doing FP,
since it does not suspend side effects (which is why you should
use IO), but that’s
beside the point, plus for the FP purists out there, you can always
suspend it in a thunk, assuming that it doesn’t leak in then
chains.
This is also why I fear standardization by committee in general. Along with
the totally awkward then
signature that can’t be safely described with
TypeScript’s or Flow’s types, this is another example of how standard
solutions can be harmful, because by being pushed as a standard, it makes
it hard for alternatives to exist, since most people are just going to
use the standard implementation, especially in JavaScript’s ecosystem
where people are afraid to take on dependencies.