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 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 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 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)
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
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
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
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...
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.
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
For my markdown handler, I'm sticking with
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!