An operator fusion primer

01 Apr 2020

(Assumed audience: folks familiar with Combine and its operators.)

Updates:

4/4/20:

Tim followed up and asked a question I should’ve covered more directly,

I was hoping to also read why Combine fuses operators, any idea?

I get that it simplifies types, but I have no reason to assume that that gains you anything at runtime […]

Sans working at Apple or poking at the framework with performance tests, it’s hard to tell. But, my guess is back pressure handling. Each intermediary Publisher conformance likely has its own buffering mechanism and fusion removes redundant overhead in honoring downstream subscribers’ demand.

---

Nuclear physicists 🤝 Engineers at Apple

…operator fusion.

Kidding. Well, only sort of.

“Fusion” is a term I’d see in the Reactive Java and effect system communities and struggled to build intuition around until I read through Combine’s documentation.

If anything, the goal of this primer is to be the resource younger Jasdev wish he had.

⬦

Fusion—as the word hints—fuses two structures. Which, by extension, means “operator fusion” in the Combine context joins two operators to optimize away an intermediary type.

Publishers in the framework bear two names:

• Their type-erased nickname, AnyPublisher<Output, Failure>.
• Or, their fuller, non-erased names like Publishers.Concatenate<Publishers.Map<Self, Sequence.Element>, Publishers.Sequence<Sequence, Failure>>.

The erased and full names interact with chained operators in nuanced ways—e.g. how does (2) in the snippet below retain its type after mapping whereas (1) doesn’t?

To illustrate the nuance and performance and aesthetic tradeoffs, let’s walk through an operator I’m contributing to CombineExt—a community overlay of Combine extensions—, Publisher.removeKnownDuplicates¹.

Publisher.removeKnownDuplicates

Combine ships with a three deduplicating operators:

• Publisher.removeDuplicates
• .removeDuplicates(by:)
• .tryRemoveDuplicates(by:)

They all nix pairwise duplicates from an upstream publisher by comparing the previous and next value events along an Equatable conformance or (non-)throwing predicate. If they match, the value will be dropped, if not, it’ll be published downstream.

But, what if we need distinct values across all seen so far?

That’s removeKnownDuplicates’s goal.

Of course, this operator has a warning label. Deduplicating across known value events means the operator has to track distinct values in memory, which can be problematic for sequences that publish a high number of unique elements. The operator can only free resources after a cancellation or completion event.

We’ll focus in on a specific implementation² constraining Publisher.Output to Hashable.

First, we need to record incoming value events and suppress those we’ve seen already. Maybe we can lean on Output’s Hashable conformance?

We could store all value events in a Set<Output>, say under the variable name seen, and determine uniqueness with seen.insert(incoming).inserted (for an incoming value).

If you’ve been compiling along, here’s the remaining error:

Cannot convert return expression of type

“Publishers.Filter<Self>”

to return type

“AnyPublisher<Output, Failure>.”

We’ve arrived at the “type erase?”, “fuse??”, or “???” juncture.

“To return the full type, erase, or be opaque? That is the question.”

— Wayne Gretzky

— — Michael Scott

There’s two-ish³ routes we can take (I’ll explain the “-ish” soon).

Return the full type

There’s no dancing around it. Returning Publishers.Filter<Self> leaks implementation details. But, is that such a bad thing?

The only properties on Publishers.Filter (and likewise, for other publishers) is its upstream and isIncluded predicate, both of which call sites can’t do much with—and if they do, they’d sidestep reaching for removeKnownDuplicates in the first place.

Maybe an opaque result type?

Could SE-0244’s opaque result types help?

Swapping out AnyPublisher<Output, Failure> for some Publisher

…compiles? That’s fishy—and understandably so. The issue shows up when we interface against the opaqueness.

Opaque return types are a sort of “reverse generics,” in that the callee (removeKnownDuplicate’s implementation, in our case)—instead of the caller (deduplicatedEvens) determines the resulting type.

There’s a cycle though. Our operator is stating it’s in control of the resulting type, covered by some Publisher, yet the associated type for the Publisher conformance, Output, is chosen by the caller, causing a stalemate.

This exceptional case is tucked away in the backing evolution proposal. And that’s the “-ish” I hinted at above.

Erase

We could stay course with erasure. There’s a tradeoff through, and that’s fusion.

(Sorry it took almost a thousands words to get here. Nuclear physics is no joke.)

Type erasure—as the name implies—removes detail from a specific protocol conformance, leaving behind a type that only covers the protocol’s requirements. The technique is used frequently: AnyPublisher, AnySequence, AnyIterator,AnyKeyPath, AnyView, and so on.

In Combine, we can ask if that removed detail is useful—to answer this, let’s imagine a consumer tacks on a filter call to both non-erased and erased forms of removeKnownDuplicates.

Woah. filter calls normally nest the upstream publisher a Publishers.Filter level. Yet, when filtering deduplicated, deduplicatedEvens preserved its type.

Fusion!

Since erasedRemoveKnownDuplicates wipes the type information, Combine has no other choice than to wrap it in another intermediary. On the other hand, Publishers.Filter can specialize its filter implementation by returning another instance of the same type, reducing overhead.

We can’t peek behind Apple’s closed source. But, we can guess at the implementation.

“[Tradeoffs] rule everything around me.”

Fusion is wicked. However, it’s not always needed. We have to think about our publisher’s intended use, or at least guess when exposing a public-facing API.

If the operator is meant to be used in between other, chained operators, then it’s better to return the full type and let fusion happen.

However, if the publisher is meant to be used wholesale—i.e. its implementation covers all expected transformations—, then the aesthetic benefit of shortening to an AnyPublisher (or if possible, an opaque return type) is probably the way to go.

⬦

There you have it. We covered building our own composed operator, type erasure, opaque return types, a few memes, and nuclear physics in under 1,200 words. Fusion always felt out of reach and writing this primer distilled it from orbit and into Combine and Swift for me.

I hope it does for others, too.

In short,

• if your operator is an intermediary, try to return its full type to benefit from fusion’s optimizations.
• if your publisher ends a chain, lean on either an opaque return type or erasure, in that order.

■

---

Special thanks to Peter and Wilson for feedback on an early draft of this entry.

Related reading, hat tips, and footnotes

⇒ Thomas Visser’s “Why Combine has so many Publisher types.”

⇒ Tim Ekl wrote a wonderful post detailing the evolution of Swift generics.

⇒ A notebook entry on type erasure with a postfix operator.

⇒ Kudos to Adam Sharp for talking through the tradeoffs between erasure and fusion with me in iOS Folks’ #reactive channel.

⇒ Point-Free subscribers might’ve noticed that Episode #13’s mention that “composition of maps are equivalent to the map of the composition” seems similar to fusion. And in a sense, it is! That’s because the functors we encounter in programming are strictly endofunctors.