Blog Infos
Author
Published
Topics
Author
Published

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

Job Offers

Job Offers


    Android Software Engineer (f/m/d)

    Paradox Cat GmbH
    Munich
    • Full Time
    apply now

    Mobile Engineer

    OLX Group
    Remote, Portugal, Spain, Romania, Poland
    • Full Time
    apply now

    Kotlin Multiplatform Mobile Developer

    Touchlab
    Remote
    • Full Time
    apply now
Load more listings

OUR VIDEO RECOMMENDATION

, ,

From Scoped Storage to Photo Picker: Everything to know about Storage

Persistence is a core element of every mobile app. Android provides different APIs to access or expose files with different tradeoffs.
Watch Video

From Scoped Storage to Photo Picker: Everything to know about Storage

Yacine Rezgui
Android developer advocate
Google

From Scoped Storage to Photo Picker: Everything to know about Storage

Yacine Rezgui
Android developer ad ...
Google

From Scoped Storage to Photo Picker: Everything to know about Storage

Yacine Rezgui
Android developer advocat ...
Google

Jobs

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 . The word can be hyphenated as or . 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.

YOU MAY BE INTERESTED IN

YOU MAY BE INTERESTED IN

blog
Today, We will explore the New notification 🔔 runtime permission that was added in…
READ MORE
blog
In this article, we will explore Android 13’s new clipboard UI, as well as…
READ MORE
blog
App launcher icons, the very first interaction that someone has with your app is…
READ MORE
blog
Android 13 (API 33) introduces a new tool called photo picker 🖼. Today, we…
READ MORE

Leave a Reply

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

Fill out this field
Fill out this field
Please enter a valid email address.

Menu