In the recently published Android 13 Developer Preview blog post, Dave Burke noted two new functions around hyphenation in TextViews: fullFast or normalFast. He noted that these new flags help in rendering hyphens without visible impact in text rendering performance. He also did mention further that the most recent implementation of text rendering can see performance improvements by as much as 200%.

While we take text rendering mostly for granted, the algorithm behind how rows of text are rendered is rather fascinating. In this blog, I’ll explain two approaches in text rendering and how Android optimizes for it.

First, let’s talk about the standard approach: the greedy algorithm.

The Greedy Algorithm

The greedy algorithm in text rendering is simply to measure the width of the rendering canvas and to jam in as many words as possible for that line before moving on to the next. Here’s an example:

For the input text

AAA BB CC DDDDD

with line width 6, the greedy algorithm would produce:

------    Line width: 6
AAA BB    Remaining space: 0
CC        Remaining space: 4
DDDDD     Remaining space: 1

(source)

The greedy algorithm works very well as it is extremely fast and used in word processors and web browsers. However, if one were to look at the resulting rendered text above, he would observe that the second line seems to have a massive space left. It would be better if the paragraph is displayed like this:

------    Line width: 6
AAA       Remaining space: 3
BB CC     Remaining space: 1
DDDDD     Remaining space: 1

Notice that the second rendering is more pleasing to the eye because the amount of white space to the right of the paragraph is minimized. As one might have guessed, the algorithm to make this work out is rather more complex. This approach is called the Knuth-Plass Line Breaking Algorithm

The Knuth-Plass Algorithm

The way this algorithm works is in demerits minimization. Every group of characters and spaces has what is called a “stretchability factor.” This is the range of possible spacing between characters such that the word remains sufficiently legible. For every line that comes after the first, the algorithm will compare the line against the previous one and attempt to measure the range of possible combinations, and choose the one with the least margin of difference. The process then continues until the paragraph ends.

Android is using the Knuth-Plass algorithm as a reference in order to implement its text rendering algorithm. The actual code is from a library called Minikin and can be found here.

But wait there’s more!

Notice that thus far, we have only considered monospace font renderings. That is, every character is of the same width as the others. In reality, however, most fonts, such as Times New Roman and Arial, are not monospaced. Moreover, text rendering algorithms also have to consider cursive texts where character spacing needs to look tighter for a better visual experience.

Kerning

Source

Kerning is simply minimizing the space between characters in order to (a) save space and (b) create a more visually cohesive word. In the example above, the letter V can be pushed a few pixels to the left to align well with the letter A and providers a more cohesive rendering of LAV than the latter. Of course, when kerning is performed in every word, performance overhead applies.

Tracking

Source

Tracking, like kerning, is also a technique to reduce the spaces between characters to create a more visually appealing output. This, as seen above, is well received for cursive fonts.

Kerning and tracking are very common techniques in text rendering to help make the reading experience better. Both of these of course come at a cost. Minimal cost. Today’s computers are so fast that all these computational overheads are often overlooked and rightfully so. Until we run into another hurdle: hyphenation.

Hyphenation in Text Rendering

Hyphenation is tricky in many ways. In essence, a hyphenation algorithm requires some form of dictionary and decision heuristics in order for it to be effective. Take for example, the word impeachment. The word can be hyphenated as im-peachmentor impeach-ment. Of course, one might argue that either way works. However, it seems rather evident that the latter is more visually appealing.

Still, there are other legitimate concerns in hyphenation that must be raised.

1. It is a good idea to NOT hyphenate two adjacent lines.
2. There is no need to hyphenate the second-to-last line of a paragraph because there’s more than enough space right after to fill in the full word.

Of course, various hyphenation strategies can ignore some of these rules.

The recent Android 13 announcement helps to address some of this performance overhead somehow by giving the app developers a handle on whether they want to hyphenate or not and if so, what strategies apply. The new flags, fullFast and normalFastbasically removes some techniques such as kerning because all these extra visual optimizations add up to the performance hit. At the end of the day, as with most engineering problems, this is a problem of tradeoffs.

Now What?

It’s rather interesting to note how far Android has gone since its early days. I first developed in Android in 2010 where things are so clunky they barely work. Yet they WORK. Twelve years later, Android has found itself so mature as a platform that the engineers can start working on micro-optimizations like these which, while it does not provide any significant impact on almost anything, still makes the overall Android experience better nonetheless.

One must also note that many software engineers coming into the industry in droves in these recent half a decade or so has not seen how things are like when platforms were as clunky as they could be. C and C++ still have all sorts of problems that remain to this day. Yet they work! Software Engineering interviews, especially for fresh graduates tend to have some form of bias towards optimization which then pushes good engineers to think about premature optimizations more than shipping a working product. In all reality, Software Engineering has mostly to do with all sorts of tradeoffs. First, you make things work… and after things are working, you make them better. Time and again, including this recent update in text rendering, shows that all these micro-optimizations can take a backseat and be done much later, because the impact these extra options have on a working product is… at least in this case, next to nil.