Exploring Spannable Performance

I've been working on a new markdown handler for Trello Android. It uses commonmark-java to parse an abstract syntax tree, which is then converted into a single, complex Spannable. That Spannable is constructed piece-by-piece from the AST, so it involves a lot of appending text and setting spans.

My first implementation used SpannableStringBuilder to construct the Spannable, as that's the natural first choice when you want both mutable text and spans.

However, I stumbled across some shocking performance characteristics of SpannableStringBuilder when I first started benchmarking my constructor. It turned out that simply adding text and setting spans was taking up 98% of the construction time. That is, construction took 51ms, and 50ms of that was just calls to SpannableStringBuilder.

Internally, SpannableStringBuilder has a rather complex data structure - a balanced interval tree of spans, implemented as a collection of arrays. The commit which setup this data structure notes that it was done for the speed of editing (since editing can occur anywhere in the CharSequence) - but not, apparently, for initial construction speed.

That led me to ask myself: Can I use something besides SpannableStringBuilder that increases its construction speed (especially since I don't need to edit it later)?

StringBuilder + SpannableString

My first thought was to use a SpannableString instead. SpannableString does not allow for mutable text, so I start with a StringBuilder + a list of spans to eventually apply. The data structure looks like this:

val sb = StringBuilder()
val spans = mutableListOf<SpanInfo>()

data class SpanInfo(val what: Any, val start: Int, val end: Int, val flags: Int)

Once we scan through the markdown and construct the above data structure, it's a simple matter to create a SpannableString and attach all the spans to it:

val ss = SpannableString(sb)
spans.forEach {
  ss.setSpan(it.what, it.start, it.end, it.flags)
}

This alone resulted in an incredible performance boost - from 51ms to 2ms. Construction was 25x faster than using SpannableStringBuilder!

Custom Spannable

Constructing the SpannableString was still taking up a decent chunk of time, though - about 50% of the construction time. This seemed rather silly since I already had a data structure that held all the data I needed.

As such, I took a crack at writing my own, simpler version of SpannableStringBuilder. I adopted most of its interfaces minus Editable (since I didn't need insertion or deletion):

class SpannableBuilder : CharSequence, Appendable, Spannable, GetChars

Inside of it, I'm using the same data structure outlined before. Then it was simply a matter of implementing all the functions, which is an exercise I leave to the reader (but it's not too tricky, especially when half of it is delegating to the StringBuilder and the other half can just be copied logic from SpannableStringInternal).

Going this route gained me a 2x speed boost (down to 1ms) because I simply skipped having to reconstruct the Spannable after the initial parse.

Or had I?

When I went to actually use SpannableBuilder, I discovered was that TextView resists using custom Spannables. If you send it a Spannable, by default it actually converts that into a SpannableString (or SpannableStringBuilder if it's an EditText). Even though I was speeding up my part of the code by skipping the conversion step, I still ended up converting it in the end!

You can skip this conversion by specifying BufferType.SPANNABLE when setting the text and also providing your own Spannable.Factory implementation to the TextView (which you can read more about that in this excellent article about spans). That's plenty of hassle, though, and it turns out that there are other performance concerns besides construction...

Layout Performance

Siyamed Sinir pointed out to me that there's another potential performance cost: text measurement and layout.

When laying out text, the layout class needs to access all the spans via Spanned.getSpans(). The speed of getSpans() can vary wildly depending on the class itself.

I ran some new benchmarks that tried laying out my various solutions into a StaticLayout and was surprised to see that performance varied greatly. SpannableStringBuilder, with its complex tree-based data structure, came in first with 9ms for a layout. Next was SpannableString with its array-based data structure at 16ms. And in dead last was my custom Spannable, clocking in around 33ms.

I realize now another place SpannableStringBuilder needed extra speed - for layout. This makes a lot of sense, since it's the driver behind EditTexts, and those require laying out far more often than static text.

Conclusion

Here's a quick visualization of how each setup performed in my benchmarks (smaller numbers are better):

(These measurements were taken on a Samsung S7. The test corpus was 5,855 characters long, had 456 spans, and construction involved 713 append calls.)

These benchmarks demonstrate the benefits of smart optimization. I could've spent time optimizing the conversion from an AST to text/spans, but at best I'd only have reduced the construction time by 1ms. The real problem was SpannableStringBuilder.

For my markdown handler, I'm sticking with StringBuilder + SpannableString. It's simple to write, constructs fast, and lays out moderately quickly. My custom SpannableBuilder proved too troublesome to implement well, though I may revisit the idea if we decide we need to grab every last ounce of performance we can get.

I do not want your takeaway here to be that SpannableStringBuilder is slow and should be avoided. It's perfectly fine for most use cases (and in fact is faster during layouts). However, if you're in a situation like mine (where you're constructing a large Spannable and not editing it later) you can really boost performance avoiding SpannableStringBuilder. As with everything in programming, it's all about tradeoffs.

Many thanks to Siyamed Sinir for both helping me analyze Spannable performance and proofreading this article!