Under the hood of Jetpack Compose — part 2 of 2

Under the hood of Compose

This is the second of two posts about Compose. In the first post I explained the benefits of Compose, the challenges Compose addresses, the reasons behind some of our design decisions, and how those help app developers. Also, I discussed the mental model of Compose, how you should think about the code that you write in Compose, and how you should shape your APIs.

Now I’m going to look at how Compose works under the hood. But before I start, I want to emphasize that understanding how Compose is implemented is not required to use Compose. What follows is purely to satisfy your intellectual curiosity.

What does @Composable mean?

If you’ve looked at Compose, you have likely seen the @Composable annotation in a number of code examples. An important thing to note is that Compose is not an annotation processor. Compose works with the aid of a Kotlin compiler plugin in the type checking and code generation phases of Kotlin: there is no annotation processor needed in order to use compose.

This annotation more closely resembles a language keyword. A good analogy is Kotlin’s suspend keyword.

Kotlin’s suspend keyword operates on function types: you can have a function declaration that’s suspend, a lambda, or a type. Compose works in the same way: it can alter function types.

The important point here is that when you annotate a function type with @Composable you’re changing its type: the same function type without the annotation is not compatible with the annotated type. Also, suspend functions require a calling context, meaning that you can only call suspend functions inside of another suspend function.

Composable works the same way. This is because there’s a calling context object that we need to thread through all of the invocations.

Execution model

So, what is this calling context thing that we’re passing around and why do we need to do it?

We call this object the “Composer”. The implementation of the Composer contains a data structure that is closely related to a Gap Buffer. This data structure is commonly used in text editors.

A gap buffer represents a collection with a current index or cursor. It is implemented in memory with a flat array. That flat array is larger than the collection of data that it represents, with the unused space referred to as the gap.

Now, an executing Composable hierarchy can appeal to this data structure and insert things into it.

Let’s imagine that we’re done executing the hierarchy. At some point, we’re going to re-compose something. So, we reset the cursor to the top of the array and then go through execution again. As we execute we can look at the data and do nothing or update the value.

We may decide that the structure of the UI has changed and want to make an insert. At this point we move the gap to the current position.

And now, we’re able to make inserts.

The important thing to understand about this data structure is that all of the operations — get, move, insert, and delete — are constant time operations, except for moving the gap. Moving the gap is O(n). The reason we chose this data structure is because we’re making a bet that, on average, UIs don’t change structure very much. When we have dynamic UIs, they change in terms of the values but they don’t change in structure nearly as often. When they do change their structure, they typically change in big chunks, so doing this O(n) gap move is a reasonable trade-off.

Let’s look at an example of a counter.

This is the code that we would write, but let’s look at what the compiler does.

When the compiler sees the Composable annotation, it inserts additional parameters and calls into the body of the function.

First, the compiler adds a call to the composer.start method and passes it a compile time generated key integer.

The compiler also passes the composer object into all of the composable invocations in the body of the function.

When this composer executes it does the following:

• Composer.start gets called and stores a group object
• remember inserts a group object
• the value that mutableStateOf returns, the state instance, is stored.
• Button stores a group, followed by each of its parameters.

And then finally we arrive at composer.end.

The data structure now holds all of the objects from the composition, the entire tree in execution order, effectively a depth first traversal of the tree.

Now, all of those group objects are taking up a lot of space, so what are they there for? These group objects are there to manage the moves and inserts that can happen with a dynamic UI. The compiler knows what code that changes the structure of the UI looks like so it can conditionally insert those groups. Most of the time, the compiler doesn’t need them so it doesn’t insert that many groups into the slot table. To illustrate this look at the following conditional logic.

In this composable the getData function returns some result and renders a loading composable in one case and a header and a body in another case. The compiler inserts separate keys for each branch of the if statement.

Let’s assume that when this code first executes result is null. This inserts a group into the gap array and the loading screen runs.

The second time the function runs let’s assume that result is no longer null so that the second branch of the if statement executes. This is where it gets interesting.

The call to composer.start has a group with the key 456. The compiler sees that the group in the slot table of 123 doesn’t match, so now it knows that the UI has changed in structure.

The compiler then moves the gap to the current cursor position and extends the gap across the UI that was there, effectively getting rid of it.

At this point, the code is executed as normal, and the new UI — the header and the body — is inserted.

The overhead of the if statement, in this case, was a single slot entry in the slot table. By inserting this single group we have arbitrary control flow in our UI enabling the compiler to manage it and appeal to this cache-like data structure while executing the UI.

This concept is that we call Positional Memoization and this is the concept that Compose is built around, from the ground up.

Positional Memoization

Normally, we have global memoization meaning that the compiler caches the result of a function based on the inputs of that function. To illustrate an example of positional memoization take this composable function, which is performing a computation.

The function takes in a list of string items and a query and then performs a filter computation on the list. We can wrap this computation in a call to remember: remember is something that knows how to appeal to the slot table. remember looks at items and stores the list and query in the slot table. The filter computation then runs and remember stores the result before passing it back.

The second time the function executes, remember looks at the new values being passed in and compares them with the old values. If neither of them has changed, then the filter operation is skipped and the previous result returned. That’s positional memoization.

Interestingly, this operation was really cheap: the compiler had to store one previous invocation. This calculation could happen all over your UI and, because you’re storing it positionally, it only stores it for that location.

This is the signature of the remember function, it can take any number of inputs and then a calculation function.

But there is an interesting degenerate case here when there are zero inputs. One of the things we can do is deliberately misuse this API. We can memoize an intentionally impure calculation, such as Math.random.

If you were doing this with global memoization it would make no sense. But, with positional memoization, it ends up taking on a new semantic. Every time we use App in a composable hierarchy, a new Math.random value is returned. However, every time that composable re-composes, it will be the same Math.random return value. This gives rise to persistence and that persistence gives rise to state.

Storing parameters

To illustrate how a Composable function’s parameters are stored, let’s take a Google Composable that takes in a number, calls an address composable, and renders an address.

Compose stores the parameters of a composable function in the slot table. If this is the case, looking at the example above we see some redundancies: “Mountain View” and “CA”, which are added in the address invocation, are stored again in the underlying text invocations, so these strings will be stored twice..

We can get rid of this redundancy by adding the static parameter to Composable functions at the compiler level.

The static parameter in this case is a bit field indicating whether or not the runtime knows the parameter does not change. If a parameter is known to not change, then there’s no need for it to be stored. So, in this Google example, the compiler passes a bit field that says none of the parameters are going to change.

Then, in Address, the compiler can do the same thing and pass it into text.

This bitwise logic is hard to read and is confusing, but there is no need for us to understand this: compilers are good at this, humans aren’t.

In the Google example, we see that there is redundant information but there are also constants here. It turns out, we don’t need to store them either. So the entire hierarchy is determined by the number parameter and that is the only value that the compiler needs to store.

Because of this, we can go further and generate code that understands that number is the only thing that’s going to change. This code can then work so that if a number hasn’t changed the body of the function would be skipped entirely, and we can just instruct the composer to move its current index to where it would be as if the function had executed.

The composer knows how far to fast forward the execution to resume where it needs to.

Recomposition

To explain how recomposition works, let’s go back to the counter example.

The generated code the compiler creates for this counter has a composer.start and compose.end. Whenever Counter executes, the runtime understands that when it calls count.value, it’s reading the property of an appmodel instance. At runtime, whenever we call compose.end, we optionally return a value.

Then we can call an updateScope method on that value with a lambda that tells the runtime how to restart this Composable, if it needs to. This is equivalent to the lambda that LiveData would otherwise receive. The reason that the question mark is here — the reason that this is nullable — is because, if we don’t read any model objects during the execution of Counter there’s no reason to teach the runtime how to update this because we know it never will update.

Closing thoughts

It is important to remember that most of these details are just implementation details. Composable functions have different behaviors and capabilities from standard Kotlin functions, and it can sometimes be helpful to understand how those are implemented, but while the behaviors and capabilities will not change, the implementation might.

Likewise, the compose compiler is able to generate code that is more efficient in certain situations. Over time, we hope for these optimizations to improve.