Fast UTF-8 handling for modern C++ with support for legacy C

Fast UTF-8 handling for modern C++ with support for legacy C ♦ Overview

By Kirk J Krauss

What’s here

An introduction to the FastUtf8::Uniseries C++ class;

A reason to target just UTF-8 for C/C++ internationalization: it slashes case folding bloat associated with unnecessary encodings;

An introduction to the C-compatible functions that do the heavy lifting for FastUtf8; and

A discussion of included methods for expressive queries against semistructured internationalized content and their outstanding performance results relative to prior methods.

Background

The footprint of the global datasphere is estimated to be in the hundreds of zettabytes. Most of it is unstructured or semistructured data. There are hundreds of natural languages represented on the Internet, with less than half of websites in English. Mature programming languages, including C/C++, stem from a time frame when the Internet wasn’t this way.

Providing for natural language support, in steps composed entirely via imperative programming, can lead to layers of sophisticated code. For example, to pick out a title from a semistructured list comprising titles of books and corresponding authors, one step might involve case folding for a given author’s name. Another step might involve separating the list into discrete lines based on tokens. Yet another step, where mixed natural languages are involved, might include matching various further tokens used in those languages. The result: slow, kludgy, narrowly focused code. Such code has worked in the past, and it still can – but isn’t there a better fit for the scope of data we have today?

In the world of structured data, such as what’s associated with relational databases, declarative queries are the norm. Expressive syntax is handled via fast, tested methods that hide the complexities of finding content. As distributed systems consultant Martin Kleppmann puts it, “In a declarative query language, like SQL or relational algebra, you just specify the pattern of the data you want... but not how to achieve that goal.” Can any sort of declarative query be applied, in C/C++, to semistructured data? Even modest steps toward making it happen could result in more reliable and fast internationalized applications.

Declarative queries for semistructured natural language

Aiming for a rich declarative arrangement, like SQL but targeted at semistructured data, may not be helpful. There are a great many natural languages that C/C++ code might parse, and each may have a way of its own for delimiting content. On the other hand, to a certain degree, semistructured data formats tend to be shared across those languages. A declarative query that works for one locale can work for another, so long as there’s enough flexibility in the query, and in the mechanism enabling it, to account for cross-locale distinctions. For that reason, any such mechanism may best follow this rule of thumb: the simpler its interface, the better.

Neither an SQL-style arrangement nor a multi-step method, such as in the book title example of the second paragraph above, is particularly simple. That is, methods for handling semistructured data in C/C++ have centered around carefully-arranged loops that a developer must be able to comprehend and modify, for every little change in the data or its format. Still, the very idea of enabling expressive queries for semistructured data has seldom arisen. Over twenty years ago, knowledge base consultant Mike Bergman put the situation this way:

Generally, most academic, open source, or other attention to these problems has been at the superficial level of resolving schema or definitions or units. Totally lacking in the entire thrust for a semi-structured data paradigm has been the creation of adequate processing engines... You know, it is very strange. Tremendous effort goes into data representations like XML, but when it comes to positing or designing engines for manipulating that data the approach is to clone kludgy workarounds on to existing relational DBMSs or text search engines.

Making Validation Make Sense

A random sequence of bytes might be interpretable as valid UTF-8, but the more bytes there are in the sequence, the less likely this becomes. A byte sequence isn’t valid UTF-8 unless it conforms to the standard encoding format. There also are standards that call for error handling. But what to do, in terms of a sensible programmatic approach, when there’s an error? And in which situations does well-designed software best validate a UTF-8 sequence?

For the second question, an impulsive answer would be to validate every byte every time it’s read. If we’d been considering ASCII content, the possibility would hardly have come to mind. The conditions that could clobber content are roughly alike, for both ASCII and UTF-8, and the idea of detection based on the...