Balisage Paper: Parallel Bit Stream Technology as a Foundation for XML Parsing Performance

Introduction

In this section, we introduce the fundamental concepts of parallel bit stream technology and present a comprehensive catalog of parallel bit streams for use in XML processing. In presenting this catalog, the focus is on the specification of the bit streams as data streams in one-to-one correspondence with the character code units of an input XML stream. The goal is to define these bit streams in the abstract without initially considering memory layouts, register widths or other issues related to particular target architectures. In cataloging these techniques, we also hope to convey a sense of the breadth of applications of parallel bit stream technology to XML processing tasks.

Basis Bit Streams

Given a byte-oriented text stream represented in UTF-8, for example, we define a transform representation of this text consisting of a set of eight parallel bit streams for the individual bits of each byte. Thus, the Bit0 stream is the stream of bits consisting of bit 0 of each byte in the input byte stream, Bit1 is the bit stream consisting of bit 1 of each byte in the input stream and so on. The set of streams Bit0 through Bit7 are known as the basis streams of the parallel bit stream representation. The following table shows an example XML character stream together with its representation as a set of 8 basis streams.

Depending on the features of a particular processor architecture, there are a number of algorithms for transposition to parallel bit stream form. Several of these algorithms employ a three-stage structure. In the first stage, the input byte stream is divided into a pair of half-length streams consisting of four bits for each byte, for example, one stream for the high nybble of each byte and another for the low nybble of each byte. In the second stage, these streams of four bits per byte are each divided into streams consisting of two bits per original byte, for example streams for the Bit0/Bit1, Bit2/Bit3, Bit4/Bit5, and Bit6/Bit7 pairs. In the final stage, the streams are further subdivided in the individual bit streams.

Using SIMD capabilities, this process is quite efficient, with an amortized cost of 1.1 CPU cycles per input byte on Intel Core 2 with SSE, or 0.6 CPU cycles per input byte on Power PC G4 with Altivec. With future advances in processor technology, this transposition overhead is expected to reduce, possibly taking advantage of upcoming parallel extract (pex) instructions on Intel technology. In the ideal, only 24 instructions are needed to transform a block of 128 input bytes using 128-bit SSE registers using the inductive doubling instruction set architecture, representing an overhead of less than 0.2 instructions per input byte.

General Streams

This section describes bit streams which support basic processing operations.

Lexical Item Streams

Lexical item streams differ from traditional streams of tokens in that they are bit streams that mark the positions of tokens, whitespace or delimiters. Additional bit streams, such as the reference streams and callout streams, are subsequently constructed based on the information held within the set of lexical items streams. Differentiation between the actual tokens that may occur at a particular point (e.g., the different XML tokens that begin “<”) may be performed using multicharacter recognizers on the bytestream representation [Cameron, Herdy and Lin 2008].

A key role of lexical item streams in XML parsing is to facilitate fast scanning operations. For example, a left angle bracket lexical item stream may be formed to identify those character code unit positions at which a “<” character occurs. Hardware register bit scan operations may then be used by the XML parser on the left angle bracket stream to efficiently identify the position of the next “<”. Based on the capabilities of current commodity processors, a single register bit scan operation may effectively scan up to 64 byte positions with a single instruction.

Overall, the construction of the full set of lexical item stream computations requires approximately 1.0 CPU cycles per byte when implemented for 128 positions at a time using 128-bit SSE registers on Intel Core2 processors [Cameron, Herdy and Lin 2008]. The following table defines the core lexical item streams defined by the Parabix XML parser.

The following illustrates a number of the lexical item streams.

UTF-8 Byte Classification, Scope and Validation Streams

An XML parser must accept the UTF-8 encoding of Unicode [XML 1.0]. It is a fatal error if an XML document determined to be in UTF-8 contains byte sequences that are not legal in that encoding. UTF-8 byte classification, scope, XML character validation and error flag bit streams are defined to validate UTF-8 byte sequences and support transcoding to UTF-16.

Control Character Streams

The control character bit streams marks ASCII control characters in the range 0x00-0x1F. Additional control character bit streams mark the tab, carriage return, line feed, and space character. In addition, a bit stream to mark carriage return line combinations is also constructed. Presently, control character bit streams support the operations of XML 1.0 character validation and XML end-of-line handling.

Call Out Streams

Call out bit streams mark the extents of XML markup structures such as comments, processing instruction and CDATA sections as well as physical structures such as character and entity references and general references. Call out streams are also formed for logical markup structures such start tags, end tags and empty element tags.

Name Lookup

Efficient symbol table mechanisms for looking up element and attribute names is important for almost all XML processing applications. It is also an important technique merely for assessing well-formedness of an XML document; rather than validating the character-by-character composition of each occurrence of an XML name as it is encountered, it is more efficient to validate all but the first occurrence by first determining whether the name already exists in a table of prevalidated names.

The first symbol table mechanism deployed in the Parabix parser simply used the hashmaps of the C++ standard template library, without deploying any SIMD technology. However, with the overhead of character validation, transcoding and parsing dramatically reduced by parallel bit stream technology, we found that symbol lookups then accounted for about half of the remaining execution time in a statistics gathering application [Cameron, Herdy and Lin 2008]. Thus, symbol table processing was identified as a major target for further performance improvement.

Our first effort to improve symbol table performance was to employ the splash tables with cuckoo hashing as described by Ross [Ross 2006], using SIMD technology for parallel bucket processing. Although this technique did turn out to have the advantage of virtually constant-time performance even for very large vocabularies, it was not particularly helpful for the relatively small vocabularies typically found in XML document processing.

However, a second approach has been found to be quite useful, taking advantage of parallel bit streams for cheap determination of symbol length. In essence, the length of a name can be determined very cheaply using a single bit scan operation. This then makes it possible to use length-sorted symbol table processing, as follows. First, the occurrences of all names are stored in arrays indexed by length. Then the length-sorted arrays may each be inserted into the symbol table in turn. The advantage of this is that a separate loop may be written for each length. Length sorting makes for very efficient name processing. For example hash value computations and name comparisons can be made by loading multibyte values and performing appropriate shifting and masking operations, without the need for a byte-at-a-time loop. In initial experiments, this length-sorting approach was found to reduce symbol lookup cost by a factor of two.

Current research includes the application of SIMD technology to further enhance the performance of length-sorted lookup. We have identified a promising technique for parallel processing of multiple name occurrences using a parallel trie lookup technique. Given an array of occurrences of names of a particular length, the first one, two or four bytes of each name are gathered and stored in a linear array. SIMD techniques are then used to compare these prefixes with the possible prefixes for the current position within the trie. In general, a very small number of possibilities exist for each trie node, allowing for fast linear search through all possibilities. Typically, the parallelism is expected to exceed the number of possibilities to search through at each node. With length-sorting to separate the top-level trie into many small subtries, we expect only a single step of symbol lookup to be needed in most practical instances.

The gather step of this algorithm is actually a common technique in SIMD processing. Instruction set support for gather operations is a likely future direction for SIMD technology.

Numeric Processing

Many XML applications involve numeric data fields as attribute values or element content. Although most current XML APIs uniformly return information to applications in the form of character strings, it is reasonable to consider direct API support for numeric conversions within a high-performance XML engine. With string to numeric conversion such a common need, why leave it to application programmers?

High-performance string to numeric conversion using SIMD operations also can considerably outperform the byte-at-a-time loops that most application programmers or libraries might employ. A first step is reduction of ASCII bytes to corresponding decimal nybbles using a SIMD packing operation. Then an inductive doubling algorithm using SIMD operations may be employed. First, 16 sets of adjacent nybble values in the range 0-9 can be combined in just a few SIMD operations to 16 byte values in the range 0-99. Then 8 sets of byte values may similarly be combined with further SIMD processing to produce doublebyte values in the range 0-9999. Further combination of doublebyte values into 32-bit integers and so on can also be performed using SIMD operations.

Using appropriate gather operations to bring numeric strings into appropriate array structures, an XML engine could offer high-performance numeric conversion services to XML application programmers. We expect this to be an important direction for our future work, particularly in support of APIs that focus on direct conversion of XML data into business objects.

The ILAX Streaming API

The In-Line API for XML (ILAX) is the base API provided with the Parabix parser. It is intended for low-level extensions compiled right into the engine, with minimum possible overhead. It is similar to streaming event-based APIs such as SAX, but implemented by inline substitution rather than using callbacks. In essence, an extension programmer provides method bodies for event-processing methods declared internal to the Parabix parsing engine, compiling the event processing code directly with the core code of the engine.

Although ILAX can be used directly for application programming, its primary use is for implementing engine extensions that support higher-level APIs. For example, the implementation of C or C++ based streaming APIs based on the Expat [Expat] or general SAX models can be quite directly implemented. C/C++ DOM or other tree-based APIs can also be fairly directly implemented. However, delivering Parabix performance to Java-based XML applications is challenging due to the considerable overhead of crossing the Java Native Interface (JNI) boundary. This issue is addressed with the Array Set Model (ASM) concept discussed in the following section.

With the recent development of parallel parsing using bitstream addition, it is likely that the underlying ILAX interface of Parabix will change. In essence, ILAX suffers the drawback of all event-based interfaces: they are fundamentally sequential in number. As research continues, we expect efficient parallel methods building on parallel bit stream foundations to move up the stack of XML processing requirements. Artificially imposing sequential processing is thus expected to constrain further advances in XML performance.

Efficient XML in Java Using Array Set Models

In our GML-to-SVG case study, we identified the lack of high-performance XML processing solutions for Java to be of particular interest. Java byte code does not provide access to the SIMD capabilities of the underlying machine architecture. Java just-in-time compilers might be capable of using some SIMD facilities, but there is no real prospect of conventional compiler technology translating byte-at-a-time algorithms into parallel bit stream code. So the primary vehicle for delivering high-performance XML processing is to call native parallel bit stream code written in C through JNI capabilities.

However, each JNI call is expensive, so it is desirable to minimize the number of calls and get as much work done during each call as possible. This mitigates against direct implementation of streaming APIs in Java through one-to-one mappings to an underlying streaming API in C. Instead, we have concentrated on gathering information on the C side into data structures that can then be passed to the Java side. However, using either C pointer-based structures or C++ objects is problematic because these are difficult to interpret on the Java side and are not amenable to Java's automatic storage management system. Similarly, Java objects cannot be conveniently created on the C side. However, it is possible to transfer arrays of simple data values (bytes or integers) between C and Java, so that makes a reasonable focus for bulk data communication between C and Java.

Array Set Models are array-based representations of information representing an XML document in accord with XML InfoSet [XML Infoset] or other XML data models relevant to particular APIs. As well as providing a mechanism for efficient bulk data communication across the JNI boundary, ASMs potentially have a number of other benefits in high-performance XML processing.

Character Class Compiler

The first compiler component that we have implemented is a character class compiler, capable of generation all the bit stream logic necessary to produce a set of lexical item streams each corresponding to some particular set of characters to be recognized. By taking advantage of common patterns between characters within classes, and special optimization logic for recognizing character-class ranges, our existing compiler is able to generate well-optimized code for complex sets of character classes involving numbers of special characters as well as characters within specific sets of ranges.

Regular Expression Compilation

Based on the character class compiler, we are currently investigating the construction of a regular expression compiler that can implement bit-stream based parallel regular-expression matching similar to that describe previously for parallel parsing by bistream addition. This compiler works with the assumption that bitstream regular-expression definitions are deterministic; no backtracking is permitted with the parallel bit stream representation. In XML applications, this compiler is primarily intended to enforce regular-expression constraints on string datatype specifications found in XML schema.

Unbounded Bit Stream Compilation

The Catalog of XML Bit Streams presented earlier consist of a set of abstract, unbounded bit streams, each in one-to-one correspondence with input bytes of a text file. Determining how these bit streams are implemented using fixed-width SIMD registers, and possibly processed in fixed-length buffers that represent some multiple of the register width is a source of considerable programming complexity. The general goal of our compilation strategy in this case is to allow operations to be programmed in terms of unbounded bit streams and then automatically reduced to efficient low-level code with the application of a systematic code generation strategy for handling block and buffer boundary crossing. This is work currently in progress.