Text/UTF-8: Aftermath

Posted in: haskell.

What is this?

The Google Summer of Code deadline ends about now, so it is time to reflect on the progress I’ve made. Yesterday, we had a conference call with Bryan O’Sullivan, Johan Tibell and my mentor Edward Kmett in order to discuss what we should do with my results and patches.

TL;DR

The patches will not be merged into the trunk for now. However, we do consider this project succesful. Read on…

The general idea

By converting from UTF-16 to UTF-8, I slowed down a lot of functions. This is inevitable, because most functions in the Data.Text library are implemented as something like:

f :: Text -> Text
f = unstream . f' . stream

g :: Text -> Text
g = unstream . g' . stream

In this case, f' is a function that works on characters instead of bytes, and stream/unstream do the conversion from and to the byte array. Data.Text has a stream fusion framework, which means that a function such as

h :: Text -> Text
h = f . g

is (by GHC) translated to

h :: Text -> Text
h = unstream . f' . stream . unstream . g' . stream

which, in turn, gets optimized using stream fusion:

h :: Text -> Text
h = unstream . f' . g' . stream

What does this mean for us? We know that functions such as f' and g' remain exactly the same when using either UTF-16 or UTF-8: only the stream and unstream functions are affected. And since they now deal with UTF-8, which is a little more complicated, functions such as h are generally more expensive.

So where is the benefit from porting the library to UTF-8? This comes from the fact that most applications use something like:

p :: ByteString -> ByteString
p = encodeUtf8 . h . decodeUtf8

and when the internal encoding is UTF-8 as well, we can optimize both decodeUtf8 and encodeUtf8.

The results

This was an experimental project from the start, since we did not actually know whether or not these changes would make the text library faster – which is why benchmarking was such an important part of it.

It turns out that, as we predicted, it usually is an optimization, albeit a very small one, and it is not certain if the relatively small speedup will be worth all of the work involved in completely switching to UTF-8. While I completely ported the text library, it would still involve:

The list of external libraries which uses UTF-16 (and with which we might wish to communicate) is also fairly large: ICU, Java, .Net, Cocoa…

This might (or might not) outweigh the fact that we would usually have better (less) memory usage for UTF-8.

So, because there was not really a very compelling reason for Bryan to choose for either of the two, he chose to keep the UTF-16 version for now, because this requires less work.

More about memory usage

One of the reasons to switch to UTF-8 was the face that memory usage could be reduced for ASCII text, which is very common in markup languages. However, a Text value takes 6 words, plus the payload in bytes. This means that converting to UTF-8 usually would not be such a big gain in terms of memory usage if you have lots of small Text values!

That being said, UTF-8 still has some advantages here: for example, when checking two Text values for equality, the less bytes you need to check, the better.

Was all my work in vain?

Certainly not! What future is there for all the patches I’ve written?

So, as a finishing note to conclude this project (or at least the official timespan of it, because I am looking forward to doing some more work with text and my patches), thanks again to my mentor(s) Bryan, Edward and Johan!

Comments

ce0f13b2-4a83-4c1c-b2b9-b6d18f4ee6d2