Balisage Paper: ZenoString: A Data Structure for Processing XML Strings

Monolithic char arrays

Java and C# represent a string as an array of 16-bit char units, in contiguous memory. A character above the 16-bit limit (a so-called astral character) is represented as a surrogate pair: that is, a sequence of two 16-bit numbers in a reserved range. This means that the number of bits per Unicode codepoint is variable (16 or 32), which in turn means that Unicode codepoints are not directly addressible.

Since Java 9, strings consisting entirely of 8-bit characters use an optimized representation that allocates 8 bits per character rather than 16. This creates a discontinuity: the space occupancy of a long string doubles as soon as it contains a single non-ASCII character. It also increases the cost of string concatenation if one of the operands needs to be widened from an 8-bit to a 16-bit representation.

The main disadvantages are:

Building a large string incrementally in Java with a sequence of string concatenation operations notoriously has O(n²) performance, and to counter this, the language offers a mutable StringBuilder class to hold a string temporarily while under construction. This is fine to underpin some XPath operations such as string-join(), where there’s no problem using a mutable data structure transiently during the execution of the function. But it doesn’t work where the user application constructs a string incrementally, for example by use of a recursive function or by a fold-left() operation. In such cases each intermediate string needs to be fully accessible at every stage of processing, and immutable, so update operations such as concatenation are not allowed to modify their operands.

Strings in Saxon

In the Saxon XSLT processor^[3] (at any rate, the version built using Java as the implementation language), a number of techniques are used to mitigate the disadvantages of the native string representation:

Saxon implements XDM node structures using a data structure called the TinyTree. This economises on space by avoiding the traditional one-Java-object-per-node tree design, and provides fast searching by representing node names in the tree as a single array of integer name codes. (If a document contains one million nodes, then searching for an element by name reduces to a sequential search of a contiguous array of one million 32-bit integers, which is extremely fast as a result of CPU caching: often faster than using an index.)

Text nodes in the tiny tree are represented using integer offsets into a LargeTextBuffer structure which is an array of fixed-length segments. Each segment except the last is exactly 65535 Unicode characters in length; segments represent characters using 8, 16, or 24 bits per character depending on the highest codepoint present in that segment. This achieves Unicode codepoint addressibility. In principle it allows more than 2³¹ characters in a string, but we don’t actually exploit this because it uses 32-bit int values for addressing, and because many operations require XDM strings to be converted to Java strings. One of the original ideas was that the characters representing the string value of a non-leaf element (defined as the concatenation of its descendant text nodes) would be directly available as a contiguous section of the LargeTextBuffer, but again, we don’t actually exploit this capability, largely because of the complications caused by compressed whitespace text nodes. When an operation calls for atomization of an element or text node, we represent the result as a CharSequence: if the characters needed are contiguous in a single segment, we avoid any copying operations, but if the value spans segments, we make a copy.

One of the disadvantages of the extensive reliance on the CharSequence interface is that it has no equivalent in the C# language^[4]. The way in which we derive Saxon products for both the Java and C# platforms from a single code base [Kay 2021] is beyond the scope of this paper; but the requirement to do so means that we make our life easier if we confine ourselves to functionality available in both languages.

The overall effect of these various techniques has been to give reasonably good all-round performance. But the limitations mean that we have been looking for something better.

Ropes

A relatively little-known data structure for handling strings is the rope [Boehm, Atkinson, and Plass 1995].

A rope represents a string as an immutable binary tree of short segments. Typically each non-leaf node in the tree represents a substring of the overall string, and contains pointers to left and right substrings^[5], plus a length field. Substring operations extract a subtree; concatenation forms a supertree. Operations such as replace() can reuse parts of the original string that are unaffected by the change, without copying. The structure thus affords a good solution for most of the requirements, including addressibility, scaleability, and immutability without excessive copying.

The main problems are keeping the tree balanced, and preventing excessive fragmentation. The definitive paper on ropes sketches an algorithm for keeping the tree balanced, but it makes no attempt to prevent fragmentation: specifically, a string built by appending a large number of small substrings will not be consolidated into a smaller set of larger substrings, which means that the number of objects used to represent the tree can become very large, and the depth of the tree can also grow to an uncomfortable level. A fragmented tree also leads to poor locality of reference and therefore poor CPU cache effectiveness.

Finger Trees

A finger tree [Hinze and Paterson 1995] is a flexible functional data structure used to represent ordered sequences or lists. It’s designed to provide efficient implementation of a broad range of operations including insertion, deletion, scanning, and searching; a particular characteristic compared with other tree representations is that the tree is shallower at its extremes, and deepest in the centre, which makes addition of entries at either end of the sequence particularly efficient.

Although strings are sequences of characters, general purpose list structures are not well suited for storing strings because of the space overhead, and because of the need for locality of reference (which implies using contiguous storage for adjacent characters where possible). Of course a rope, as described in the previous section, is a tree of substrings, and there is no reason why this tree should not be implemented as a finger tree.

But any structure that maintains strings as a list of substrings needs to consider how and when adjacent substrings should be consolidated. As mentioned above, the literature on ropes has little to say on this subject, and implementing the tree as a finger tree doesn’t solve the problem.

The key idea with finger trees, which are shallower at the extremities to provide extra efficiency for prepend and append operations, suggests that a similar idea might be applied to the consolidation of substrings within a rope structure, namely using shorter segments at either end of the string. This is the principle of the ZenoString structure presented in the next section.

Case Study: Dictionary-based Word Substitution

The first task I propose to measure is as follows: for a sequence of a dozen or so pairs of short strings (X, Y), replace all occurrences of X in a text of moderate length by Y. For our input text we’ll use the text of Shakespeare’s Othello, and for our replacement strings we’ll take the dramatis personae (Othello, Desdemona, Iago, Emilia, etc: eleven names in total), and wrap these names in square brackets so they become [Othello], [Desdemona] etc. So Roderigo’s line^[12] Is that true? why, then Othello and Desdemona return again to Venice becomes Is that true? why, then [Othello] and [Desdemona] return again to Venice.

Note: this task is not the one for which the design of ZenoStrings is optimized: changes to the content of a string can occur anywhere within the string, so there is no particular benefit from having short segments at the string’s extremities.

We can express this task using the following XPath 3.1 implementation (where $text is the input text, as a single string)^[13]:

                     let $personae := 
  ('Othello', 'Desdemona', 'Iago', 'Emilia', 
   'Brabantio', 'Gratiano', 'Lodovico', 'Cassio', 
   'Roderigo', 'Montano', 'Bianca')
return fold-left($personae, $text, function($str, $persona) {
  replace($str, $persona, '[' || $persona || ']')
}

Now, it happens that under the released product Saxon 10.5, this query gives perfectly acceptable performance when we use the system function fn:replace() to do the string replacement. It executes in an average of 12.8ms, using peak memory of 320Mb^[14]. If we expand the source document from 250Kb to 2.5Mb (ten copies of Othello concatenated end-to-end), it still executes in 88ms, with a similar memory requirement. That's because fn:replace(), being a system function, already optimizes the way it assembles the result string by using a mutable Java StringBuilder internally^[15]. Trying to improve this using a ZenoString internally (in the hope of saving time or space by reusing the long substrings that are copied unchanged from the input to the output) turns out to give no benefits: on the contrary, execution time increases to 14.5ms in the 250Kb case and 392ms in the 2.5Mb case.

This changes if, instead of using the system function fn:replace, similar logic is implemented in user code, for example using the XQuery 3.1 function:

                     declare function local:replace($text, $old, $new) {
   if (contains($text, $old))
   then substring-before($text, $old) || $new || 
        (substring-after($old) => local:replace($old, $new))
   else $text
};

(It’s easy to find a slight variation in the requirements that would necessitate such logic: for example, changing all the matched strings to upper-case is beyond the capabilities of fn:replace().)

In fact with a large number of matches, this user-written function fails with a stack overflow exception because it recurses too deeply. We can avoid this problem by rewriting it to take advantage of tail call optimization:

                     declare function local:replace($text, $old, $new) {
   local:replace2("", $text, $old, $new)
};
declare function local:replace2($left, $right, $old, $new) {
   if (contains($right, $old))
   then local:replace2($left || substring-before($right, $old) || $new, 
           substring-after($right, $old), $old, $new)
   else $left || $right
};

Using the released product Saxon 10.5, this query takes 29.8ms. When we scale up the source document from 250Kb to 2.5Mb, the elapsed time increases rather dramatically to 1911ms.

With ZenoStrings used to hold intermediate results, the elapsed time drops to 11.2ms for the 250Kb document, 537.4ms for the 2.5Mb case: around three times as fast. Furthermore, Saxon 10.5 shows peak memory usage of 550Mb, while the ZenoString solution is steady at around 300Mb.

Analyzing the behaviour of the two implementations (one using the system function fn:replace(), one using a home-grown alternative), it’s not hard to see why the ZenoString implementation should deliver benefits only in the second case.

For what it’s worth, the final result of the ZenoString solution (as currently implemented), is a ZenoString with segment lengths (25, 501, 16295, 24987, 30408, 39241, 21561, 16868, 4747) for the shorter input text, and (25, 501, 16295, 24987, 30408, 39241, 59997, 154633, 309266, 618532, 154633, 55395, 39241, 21561, 16868, 4747) for the longer.

Case Study: Word-wrap

The second task chosen for performance benchmarking is word-wrapping of text: that is, taking an input string and arranging it in such a way that each word is added to the current line if it fits within some maximum line length, or placing it on a new line otherwise^[16].

Once again I’ve written the code to take advantage of tail-call optimisation, so it reads like this:

declare variable $NL := codepoints-to-string(10);
declare function local:wordwrap($text, $lineLength) {
   local:wordwrap2("", tokenize($text), 0, $lineLength)
};
declare function local:wordwrap2($result, $tokens, 
                                 $currentLineLength, $maxLineLength) {
   if (empty($tokens))
   then $result
   else if ($currentLineLength + string-length(head($tokens)) ge $maxLineLength)
   then local:wordwrap2($result || $NL || head($tokens), 
                        tail($tokens), 
                        string-length(head($tokens)), 
                        $maxLineLength)
   else local:wordwrap2($result || ' ' || head($tokens), 
                        tail($tokens), 
                        $currentLineLength + string-length(head($tokens)) + 1, 
                        $maxLineLength)
};
local:wordwrap($input, 80)

For readers unfamiliar with XQuery, tokenize() splits a string on whitespace boundaries returning a sequence of strings; || performs string concatenation, head() and tail() return the first item in a sequence, and the remainder of the sequence, respectively; string-length() returns the length of a string in Unicode codepoints; empty() tests whether a sequence is zero-length.

We’ll exercise this code by running it with samples of Lorem Ipsum text of different lengths (measured in words, defined here as space-separated tokens). The text is all lower-case ASCII alphabetic characters.

For short input texts (texts that are representative of the paragraphs that are likely to be word-wrapped in a real publishing application), the performance is excellent with both the conventional string representation in Saxon 10.5, and with the new ZenoString code. In both cases it appears to scale linearly with the length of the text, and the ZenoString gives an improvement that is around a factor of two:

Time (in ms) to word-wrap inputs of 100 to 1000 words

Further investigation, however, shows that the apparent linear scaleability is an illusion. There is actually a quadratic element to the cost: the elapsed time can be expressed as

Time (in seconds) to word-wrap inputs of 100K to 500K words

The quadratic element arises from the cost of string concatenation. On each recursive call of the wordwrap function, we are adding one token to the result string, and with the conventional approach, this involves copying the existing string, which has a cost proportional to the length of the string. With the ZenoString, concatenation has constant cost, which eliminates the quadratic element of the total elapsed time of the query.

In this case study, ZenoStrings show only a modest benefit for workloads that are likely to be encountered in everyday practice. But the case study also shows that they can deliver very substantial improvements for more extreme workloads; and perhaps as importantly, that the additional complexity does not cause any problems when applied at the smaller scale.

Unlike the previous case study, this task plays to the ZenoString’s strengths: because we are repetitively adding small increments at the end of a long string, the consolidation algorithm’s policy of leaving the shortest segments at the right-hand end of the string leads directly to the improved bottom line in query execution time. However, we've resisted the temptation to tweak the algorithm to give even better results: we could exploit the fact nothing is being done with the wordwrapped string other than to send it to the serializer, but we haven't done so.