Compose Hackathon: Day… the rest

I meant to write down this on Friday, however received caught up attempting to assemble some final bits of knowledge after my dev setting fell over and determined to cease operating benchmarks altogether.

Since Wednesday…

Within the final submit, I left off having constructed the piece desk I initially meant to. The outcomes weren’t nice. So I spent a while attempting to scrub up how the items themselves had been managed, and be certain that after each operation solely the minimal variety of items required to signify the string had been left. I additionally made higher use of PersistentList‘s mutation APIs (you may create a mutable Builder object to extra effectively carry out a number of modifications directly). In spite of everything that, and another tweaks, I used to be in a position to get the numbers down a bit however they had been nonetheless a lot worse than the unique hole buffer.

In these charts, ignore the final bar on the proper for now, I will get into that subsequent. The cyan bar is the results of all of the above work.

Allocation chart

I additionally turned on profiling for the Microbenchmark library, by including this line to the benchmark module’s gradle config:

android {
  defaultConfig {
    testInstrumentationRunnerArguments["androidx.benchmark.profiling.mode"] = 'StackSampling'
Enter fullscreen mode

Exit fullscreen mode

It seems more often than not was spent in PersistentList code, so I figured it was time to surrender on that library and check out a distinct method. I changed the checklist of items with a easy linked checklist, which ought to, in principle, carry out loads higher at including and eradicating items in the course of the desk. It wasn’t. That final bar within the charts above are the linked checklist, and it is even worse than the persistent checklist implementation.

Numerous time was additionally spent in snapshot-related code nevertheless – studying and writing state objects will not be free, and within the linked checklist case every operation concerned many such operations. And I nonetheless hadn’t even dealt with the case the place a number of snapshots are writing to the piece desk in parallel. In my persistent checklist implementation, the entire mutable properties of the piece desk had been saved as immutable fields in a single “file” object inside a MutableState, and within the linked checklist model each checklist node pointer was its personal MutableState. As I mentioned in my (final) Monday submit, I figured I might have to get my fingers soiled with snapshot IDs to deal with multithreaded competition, and now I used to be beginning to marvel if I might use the state system extra effectively as properly.

Getting comfy with MVCC

Compose’s snapshot state system is an implementation of multi-version concurrency control, or MVCC. Coming into this week, I had a type of hand-wavy thought about how the high-level ideas labored, however was nonetheless foggy on a number of the particulars. So I re-watched a brief discuss Chuck gave internally a number of weeks in the past on Thursday night time, and over espresso Friday morning learn by the snapshot state code once more, and eventually all of it clicked. Once I was initially considering by how this might work, I figured that if I might one way or the other make the piece desk conscious of whether or not it was performing a number of mutations in the identical snapshot, and no different snapshots had entry to the interior, mutable knowledge buildings, I might simply mutate them in-place and avoid wasting work. I figured I might have to trace snapshot IDs manually one way or the other.

For an introduction to methods to how snapshots behave at a excessive degree, and methods to use them, see some of my other blog posts.

Seems, the entire snapshot state system is constructed to help precisely this use case. I feel that is tremendous cool – so cool, in reality, that it deserves its personal explainer submit, Coming Quickly. The largest factor I took away from this hackweek venture was not solely a greater understanding of the snapshot system, however a normal approach for making any mutable knowledge construction snapshot-friendly.

However till I get round to writing that, the basic factors are:

  1. A mutable snapshot state object internally accommodates a duplicate of all of its knowledge for every open snapshot (every copy known as a “file”), and
  2. Each mutable snapshot state object being written to inside a mutable snapshot (e.g. inside a Snapshot.withMutableSnapshot block) will get its personal file, that it will possibly solely see inside that snapshot, and no different snapshot is aware of about, till the snapshot is utilized/dedicated.

Because of this, internally, a snapshot state object is a mixture of mutable and immutable information. Each operation carried out in a mutable snapshot has a mutable file that it will possibly write to in-place so long as that snapshot is open, and when the snapshot is utilized or dedicated, that file is successfully “frozen” and turns into immutable, so that it’ll by no means be modified once more however new snapshots can learn from it, and new mutable snapshots will make copies of it for writing to. Additionally, new information are solely created when the item is definitely written to. So creating new snapshots (each read-only and mutable) is affordable.

Snapshots and copy-on-write

Snapshot state objects are successfully copy-on-write: When written, they’re requested to create a duplicate of their present state, after which for the remainder of the lifetime of the snapshot the copy will be written to straight.

And since the state objects themselves are copy-on-write, you may theoretically make any mutable knowledge construction snapshot-aware by making it copy-on-write internally. The one factor it’s important to take into consideration is the tradeoff between how costly it’s to create a duplicate, vs how costly it’s to mutate-in-place. For instance, a easy array is about as low-cost as you will get for in-place mutation, however to create a duplicate it’s important to copy the entire array. However, persistent knowledge buildings like PersistentList are very low-cost to repeat, however have just a little extra overhead to vary.

Fortunately, by this level I’ve already carried out a chunk desk utilizing each easy mutable knowledge buildings (principally ArrayList) and one utilizing persistent lists. Each of those approaches are very straightforward to adapt to incorporate an non-obligatory copy operation earlier than writing. The linked-list piece desk could possibly be tailored as properly, however because it ended up being the worst of each worlds performance-wise, and that is with out even copying the entire checklist, I did not trouble exploring it any additional.

I used to be excited by this realization as a result of it meant I might deal with analyzing that tradeoff between copy and write efficiency, and so long as I ensured the copy-on-write logic labored appropriately, the remainder of the snapshot state object necessities can be happy. And it additionally meant that the efficiency of any such knowledge construction must be nearly equal to its non-snapshot-aware variant in all circumstances besides the primary write in a brand new snapshot. That is very helpful attribute for one thing like a textual content modifying buffer, which must carry out a number of inside operations for a single exterior write, and which could be requested to carry out a number of writes in fast succession (IME instructions will be despatched in a batch that must be utilized atomically).

It additionally means, regardless of performing any variety of inside operations for a single exterior write, we solely have to do a single “snapshot write”, which includes a small quantity of its personal overhead so minimizing them is a win.

Utilized studying

So with this in thoughts, and the hackweek demo session quick approaching, I rapidly set to work Friday morning modifying my unique piece desk implementation (the ArrayList one) to be copy-on-write. Sadly, since the entire benchmarks I used to be utilizing function with out information of snapshots, which suggests they’re all successfully working within the world snapshot, they solely measure the “write” a part of “copy-on-write”, and never the “copy” half. If I find yourself engaged on this extra, I’d add further benchmarks, however I used to be okay ignoring this for now for the reason that hottest code modifying an information construction like this could most likely be all performed inside a single snapshot anyway, for isolation and atomic change notification.

It was extraordinarily straightforward to make this alteration, since all I needed to do was:

  1. Make a file class that saved the size, add buffer, piece checklist, and a writeable flag indicating whether or not the lists wanted to be copied for this file.
  2. Contained in the mutating change methodology, get the present writeable file (utilizing the Snapshot API StateRecord.writable) examine the writeable flag and, if not set, change the lists with copies and set the flag on the file.

The remainder of the piece desk logic stayed precisely the identical, simply engaged on the checklist from the file.

Sadly, I used to be not in a position to evaluate the efficiency of this new implementation with the others, since my dev setting determined to fully cease working with the telephone I might been operating benchmarks on, and I ended up having to modify telephones and re-run all of the benchmarks on that gadget for an correct comparability (so within the charts beneath, do not attempt to evaluate the precise numbers with the charts above). The outcomes had been very promising: the brand new piece desk (cyan) ran a lot faster than all the opposite snapshot-aware implementations I constructed (yellow, inexperienced, orange), and solely just a little slower than the non-snapshot-aware one (pink).

Time chart
Allocations chart

In fact, the hole buffer is quicker, and requires loads fewer allocations, than all of the piece tables. And I have never had the time to construct this, however the hole buffer must also be adaptable utilizing the identical approach. Hole buffers are extraordinarily quick at adjoining writes as a result of they find yourself being easy array writes. The one costly operation on a niche buffer is when writing to a distinct place, because it requires transferring the hole, which suggests shifting/copying a probably massive (even the complete) array – for this reason the hole buffer does so poorly within the “random, discontinuous writes in massive textual content” benchmark. In a copy-on-write adaptation, we might mitigate this as a result of after we make the copy, we already know the place we have to transfer the hole to, so since we’re copying the entire array anyway we will transfer the hole on the identical time. So, once more, the ensuing snapshot-aware hole buffer ought to have nearly equivalent efficiency to the non-snapshot-aware one, besides when performing the primary write in a brand new snapshot.

And now that we all know methods to simply make each these knowledge buildings snapshot-aware, it even must be straightforward to undertake a hybrid method the place we change inside knowledge buildings on the fly when the buffer surpasses a sure dimension.

Lastly, we get another bonus function: it turns into extraordinarily low-cost to make a whole copy of knowledge buildings carried out on this approach, for instance to retailer in an undo stack. The info construction merely must create a brand new occasion of itself with a duplicate of the present file, and flag its personal present file as needing one other copy-on-write (e.g. by internally performing the learn inside a brand new snapshot, which is able to trigger the snapshot system to try this mechanically).


So far as I am involved, this hackweek was an awesome success. I received a significantly better understanding of how the snapshot system can really be used to implement advanced knowledge buildings, and received sufficient knowledge to be fairly assured that we might feasibly ship a snapshot-aware textual content modifying buffer in manufacturing. That opens up some thrilling potentialities for cleansing up the present inside textual content(discipline) code, in addition to potential new public textual content rendering and modifying APIs.

To summarize my highlights,

  • The Jetpack Microbenchmark library is tremendous helpful for measuring and optimizing knowledge buildings.
  • Implementing knowledge buildings from scratch is de facto enjoyable, particularly when it is to unravel an precise real-world drawback and never simply move a course.
  • Given any fancy, advanced mutable knowledge construction, you may give it the isolation, consistency, and atomicity ensures of the snapshot system by merely making it copy-on-write and wrapping in a skinny layer of StateObject+StateRecord boilerplate (though you will most likely wish to measure and discover additional optimizations from there).
  • Hole buffers > piece tables.

Should you made it this far, thanks for following alongside, and keep tuned for a deeper dive into methods to really implement a StateObject!

Add a Comment

Your email address will not be published. Required fields are marked *