Efficient XML Interchange Evaluation

1. Objectives

This document presents the anticipated benefits of the EXI format 1.0 compared to XML and gzipped XML. Additionally, tests for compactness include comparison to ASN.1 PER. The points of comparison are the requirements set by the EXI Working Group charter, based on the results of the XML Binary Characterization Working Group.

This summarized evaluation of the EXI format uses the testing framework built during the first phase of the EXI Working Group's work so as to select a baseline candidate technology. Although this evaluation aims at demonstrating EXI benefits in the targeted XBC Use Cases, it can be read as a summary of the EXI measurements Note.

2. Background

The methodology used in the evaluation relies on previous work on measurements. The Properties referred to in this document have been defined by the XBC Working Group. The methodology for measurement is detailed in the XBC measurement methodology document. For convenience, Appendix A gives an overview of the properties definitions, as well as some details of their measurements.

In addition, two Properties require an implementation to be evaluated: Compactness and Processing Efficiency. These Properties have been tested using the EXI measurement framework and the associated methodology.

3. Evaluation Results

At the time of the first publication of this document, the Working Group has not tested conformance of implementations. The methodology and framework designed and implemented on Japex by the Working Group are used for the properties that require implementation testing. The other properties can be asserted by checking the specification only.

3.1. Compactness results

This test has been run over the EXI Working Group's framework test data, which contains 94 test documents from 21 test groups. The following graphs show the resulting size as a percentage of the original XML document size, sorted by the EXI result, for the sake of legibility (i.e. "best" results on the left). The implementation of EXI used for the measurements is Efficient XML 4.0. It implements the specification of the EXI format 1.0 at the time of writing.

For each test case, the testing framework uses the most appropriate application class: Whenever a schema is available, EXI uses the schema information, and when a document-analysis-based technique leads to a better result, the compression option is turned on.

The graph above compares EXI to Gzipped XML. As shown by the graph, EXI is consistently smaller than gzipped XML regardless of document size, document structure or the availability of schema information. In some cases, EXI is over 10 times smaller than gzip. In addition, EXI works well in cases where gzip has little effect or even makes documents bigger, such as high volume streams of small messages typical of geolocation, financial exchange and sensor applications.

The graph above compares the same EXI numbers to the ASN.1 PER file sizes. Each EXI encoded file is smaller than the equivalent ASN.1 PER, and sometimes 20 times smaller. This holds true even for cases where EXI is preserving XML comments, processing instructions and namespace prefixes that are not preserved by ASN.1 PER. In addition, EXI works well in cases where ASN.1 PER actually increases the size of the document or fails to produce an encoding at all (e.g., due to schema deviations.)

3.2. Processing efficiency results

The processing efficiency tests were run using the EXI Working Group's framework test data and test methodology on a Windows XP machine with a 3.0 Ghz Pentium 4 CPU and 1.5 Gbytes of RAM. Processing efficiency was measured in transactions per second (TPS) and the following graphs show results as a percentage of XML speed and Gzipped XML speed, sorted by EXI result for legibility. So, for example, a measurement of 200% is two times faster, a measurement of 300% is three times faster, etc.

It is important to note that processing efficiency is also implementation dependent and not all EXI implementations will achieve the performance results illustrated here. The implementation of EXI used for these measurements was Efficient XML 4.0, that implements the EXI 1.0 format specification.

3.2.1. Decoding speed results

The following two graphs illustrate the decoding (i.e., parsing) speed of Efficient XML with and without EXI compression for each test case.

The graph above shows EXI decoding speed without compression compared to XML. The average decoding speed of EXI was 14.5 times faster than the average decoding speed of XML. The median speed increase was 6.7 times faster. To improve readibility, the graph does not show the four best cases, which ranged from 54 times faster to 257 times faster. These four test cases were SOAP web-service messages that were marshalled from a binding layer and contained repeating structures with elements and attributes from several different namespaces. As is typical for such use cases, the repeated structures contained a large number of repeated namespace declarations. EXI eliminates most of the overhead associated with namespace processing, which is why EXI achieved such a speed increase for these cases.

The graph above shows EXI decoding speed with compression compared to XML with compression. The average decoding speed of EXI was 9.2 times faster than the average decoding speed of GZipped XML. The median speed was 4.4 times faster. To improve readibility, the graph does not show the four best cases, which ranged from 30 times faster to 102 times faster. These were the same four SOAP web-service test cases described in the previous paragraph.

3.2.2. Encoding speed results

The following two graphs illustrate the encoding (i.e., serialization) speed of Efficient XML with and without EXI compression for each test case.

The graph above shows EXI encoding speed without compression compared to XML. The average encoding speed of EXI was 6.0 times faster than the average encoding speed of XML. The median speed increase was 2.4 times faster. To improve readibility, the graph does not show the best case, which was 21 times faster.

The graph above shows EXI encoding speed with compression compared to XML with compression. The average encoding speed of EXI was 5.4 times faster than the average encoding speed of Gzipped XML. The median speed increase was 2.7 times faster. The graph does no show the best case, which was just over 18 times faster.

3.3. Summary

The XBC working group analyzed all the properties desired by the XBC use cases and identified a minimum set of required properties for the W3C EXI format in its XBC Characterization document. For several of these properties, the XBC working group defined specific thresholds a data format must achieve to satisfy the requirements of the XBC use cases. For example, several XBC use cases required a data format with compactness similar to custom binary formats. In discussing the needs of these use cases, it was determined that the format must be no larger than ASN.1 PER + 20% when schemas optimizations are used to satisfy the "compactness" requirements of these use cases. The table below lists those properties and scores EXI for each. For comparison purposes, scores are also given for XML(+gzip).

these properties were designed to determine whether candidate EXI formats meet the requirements and specific performance thresholds of the XBC use cases. So, when the table says XML(+gzip) does not meet the compactness requirement, it means it does not meet the specific compactness threshold required by the XBC use cases. Similarly, when the table says XML(+gzip) does not meet the processing efficiency requirement, it means that XML(+gzip) does not meet the specific processing efficiency requirements of the XBC use cases. Several of these use cases specify a need for a format that was "faster to process than XML" (e.g., to be competitive with binary RPC mechanisms), so by definition it was impossible for XML to achieve this requirement.

The XBC working group classified these properties into two categories based on the observation that some properties are inherent to the format (e.g., compactness), while some are also properties of implementations of the format (e.g., processing efficiency), but characteristics of the format could prohibit implementations from achieving them. As such, the first category lists properties the format must support inherently. The second category lists properties of implementations the format must not prevent.

The score given for each property is the evaluation result of the format or implementation thereof, obtained by following the methodology defined in the XBC Measurement Methodologies document.

4. Discussion

DRAFT @@ other items for discussion?

• For a variety of test cases that were collected so as to cover the XBC Use Cases, the achieved compactness is better than gzipped XML and ASN.1 PER (in some cases by a significant margin): While there are cases for which those solutions don't work or are useless, using the right option in EXI gives a reasonable result. Therefore EXI is usable and customizable for a broadest range of use cases.
• The required properties are met (as far as we can evaluate at this time). The desirable additional properties are not prevented by the use of EXI. Some properties are achieved by enabling given EXI options. The EXI Working Group provides information in the EXI format specification and in additional resources to help users understand the options and their correct use, as well as guiding their choice of options for their data usage.

5. References

[EXI Measurements]

EXI Measurements, Greg White, Jaakko Kangasharju, Don Brutzman, Stephen Williams editors, World Wide Web Consortium, 25 July 2007. http://www.w3.org/TR/exi-measurements/.

[XBC Use Cases]

XML Binary Characterization Use Cases, Mike Cokus, Santiago Pericas-Geertsen editors, World Wide Web Consortium, 31 March 2005. http://www.w3.org/TR/xbc-use-cases/.

[XBC Properties]

XML Binary Characterization Properties, Oliver Goldman, Dmitry Lenkov editors, World Wide Web Consortium, 31 March 2005. http://www.w3.org/TR/xbc-properties/.

[XBC Measurements]

XML Binary Characterization Measurement Methodologies, Stephen D. Williams, Peter Haggar editors, World Wide Web Consortium, 31 March 2005. http://www.w3.org/TR/xbc-measurement/.

[XBC Characterization]

XML Binary Characterization, Oliver Goldman, Dmitry Lenkov editors, World Wide Web Consortium, 31 March 2005. http://www.w3.org/TR/xbc-characterization/.

[PER]

Information Technology - ASN.1 Encoding Rules: Specification of Packed Encoding Rules (PER) [The ASN.1 PER Standard (ITU-T Rec X.691 | ISO/IEC 8825-2)], International Telecommunication Union (ITU), July 2002. http://www.itu.int/ITU-T/studygroups/com17/languages/X.691-0207.pdf.

[XML 1.0]

Extensible Markup Language (XML) 1.0, Tim Bray et al editors, World Wide Web Consortium, 4 February 2004 (Third Ed). Latest version http://www.w3.org/TR/REC-xml/.

[Efficient XML]

AgileDelta's Efficient XML 4.0, accessed March 2009.

[JAPEX]

Japex Manual, Santiago Pericas-Geertsen, java.net, April 2006. https://japex.dev.java.net/docs/manual.html.

Appendix A. Properties definitions

A.1. Directly Readable and Writable

A format is directly readable and writable if it can be serialized from an instance of a data model and parsed into an instance of a data model without first being transformed to an intermediate representation. The retained data model for EXI is the XML Infoset.

A.2. Transport Independence

A format is transport independent if the only assumptions of transport service are "error-free and ordered delivery of messages without any arbitrary restrictions on the message length".
However, a protocol binding can specify how a format is transmitted as payload in a specific transport (e.g., TCP/IP) or messaging (e.g., HTTP) protocol.

A.3. Compactness

The Compactness property measurement represents the amount of compression a particular format achieves when encoding data model items. There are three categories of methods to reduce the size of a data object or data model items:

• Compression is the transformation of data into corresponding data that takes less storage through the removal or reuse of redundant information and more efficient coding of data.
• Decimation is the process of eliminating some details that are not used or of less importance than more important components of the original data (e.g. comments). This is called "lossy compression" as opposed to "lossless compression" or just "compression".
• Externalization is the process of representing an original data model items as an external representation with varying degrees of reuse and a data object that relies on that external instance as a source of redundancy. This external information can be considered shared information between a sender and receiver. A schema-based method for certain aggregate data types, structure, and/or values is a type of externalization

This property is measured in the EXI testing framework in 4 measurement modes: "Neither" optimization (pure tokenization), "Schema" (schema-based compression), "Document" (data analysis), "Both" (data analysis + schema-based compression).

A.4. Human Language Neutral

A format is human language neutral if it is not significantly more optimal for processing when its content is in a given language or set thereof, and does not impose restrictions on the languages or combinations of languages that may be used with it. Historically, it has often been a property of many data and document formats that they only supported certain character encodings. XML do not suffer from similar limitations, and it is expected that EXI will not limit the usage of particular human languages.
In terms of compactness or processing efficiency, it is not possible to ensure the same performance for a language that can be entirely captured using a single byte per character and for one that requires a multi-byte encoding, but an internationalization support equivalent to XML is necessary for a wide adoption.

A.5. Platform Neutrality

Platform neutrality is the property of formats that are not significantly more optimal for processing on some computing platforms or architectures than on others (e.g. endianness, native structures for programming language). Platform neutrality ensures not only that wide adoption is possible, but also makes the format more resilient to the passing of time.
In some cases, options in the format may be used based on the preferred parameters of the systems involved. Thus, the XBC Working Group proposed 3 possible values:

• not platform neutral at all (for instance, may be the native serialization of a given programming platform)
• defined in a platform-neutral manner, but with fixed values for certain parameters that may advantage a platform over another.
• defined in a platform-neutral manner, and multiple options (word-length, float format, etc.) can be set so that users may choose locally optimal encodings when the platforms involved in a given interchange are known.

It must also be noted that allowing too many mechanisms (options or parameters) for optimization may in fact prove to be a pessimisation.

A.6. Integratable into XML Stack

Per the EXI Working Group charter, this property must be seen as a strong requirement. The integration of the EXI format in the stack of the existing XML specifications for validation, transformation, querying, APIs, canonicalization, signatures, encryption, etc. is a key to a wide adoption.

A.7. Royalty Free

The EXI format will be unencumbered and royalty-free as ensured by the process W3C. It will lead this technology to a better adoption across the industry. A free format is also more likely to have free, open source code for processing it and free tools for building applications which use it. In addition, per the EXI Working Group charter, the EXI format will be proven to have at least one publicly available implementation before becoming a W3C Recommendation.

A.8. Fragmentable

Fragmentability is the ability to encode instances that do not represent the entirety of a document together with sufficient context for the decoder to process them. In addition to this ability to process fragments in isolation, it covers storing one or more parts of a document instance as immediately extractable fragments, so that they can be pulled out with little or no additional processing cost.

A.9. Streamable

Streamability is the ability to generate correct partial output from partial input. This property is needed in memory-constrained environments where it is important to be able to handle data as it is generated to avoid buffering of data inside the processor. Hence it is also characterized by the amount of buffering that needs to be done in the processors. In particular, required buffer space for encoding or decoding must be constant, no matter what the input document is or how it is mapped to the data model. This requirement precludes some serialization techniques (e.g. Gzip compression over the entire XML document).

A particular attention must be paid to the need for lookahead in the format parser, since it is not always available. For some types of sequences it can be beneficial to have the length of the full serialized form of the sequence that precede the actual sequence, so the serializer must buffer the whole sequence before outputting anything. If such sequences can be arbitrarily long, this sacrifices output streamability.

A.10. Roundtrip Support

A format supports roundtripping if converting a file from XML to that format and back produces an output equivalent to the original input. A format supports roundtripping via XML if converting a file from that format to XML and back produces an output equivalent to the original input.

This property is measured by comparing the data which can be represented in XML with those that can be represented in the EXI format:

• Evaluation of Roundtrip Support (XML to EXI to XML):
  If the XML Infoset is a proper superset of the data model supported by the format, the measurement is "Does Not Roundtrip". If the transformations to and from the EXI format are byte preserving, the measurement is "Exact Equivalence". Otherwise, the measurement is "Lossless Equivalence".
• Evaluation of Roundtripping via XML (EXI to XML to EXI):
  If the XML Infoset is a proper subset of the data model supported by the format, the measurement is "Does Not Roundtrip". If the transformations to and from the EXI format are byte preserving, the measurement is "Exact Equivalence". Otherwise, the measurement is "Lossless Equivalence".

A.11. Generality

A format has the property of generality if it is competitive with alternatives across a diverse range of XML documents, applications and use cases. The EXI testing framework covers the XBC use cases. The goal of this set of test cases is to include a range of different document sizes, different uses of schemas and various XML features (comments, whitespaces, etc.)

The measurement of this property is defined by the XBC Working Group as a score over 20 items, 1 point per item:

• Can represent documents without a schema
• Can represent documents that include elements and attributes not defined in the associated schema (i.e., open content)
• Can represent any schema-invalid document
• Can leverage available schema information to improve compactness, processing speed, and resource utilization
• Can leverage available schema information to improve compactness, processing speed, and resource utilization even when documents contain elements and attributes not defined in the schema
• Can leverage available schema information to improve compactness, processing speed, and resource utilization for any schema-invalid document.
• Can leverage document analysis to improve compactness
• Can suppress document analysis to increase speed and reduce resource utilization
• [optional] Can adjust document analysis to meet application performance and resource utilization criteria
• Can structure the binary XML stream to increase net compactness when off-the-shelf compression software is built in to the communications infrastructure
• [optional] Supports high fidelity XML representations that preserve an exact copy of the original XML document, including all whitespace and formatting
• Supports reduced fidelity XML representations that preserve all data model items, but discard whitespace and formatting to improve compactness
• Supports reduced fidelity XML representations that preserve all information needed by a particular application, but discard specified information items that are not needed (e.g., comments and processing instructions) to improve compactness
• Supports reduced fidelity XML representations that preserve the logical structures and values of an XML document, but discard lexical and syntactic constructs to improve compactness
• Can consistently produce XML representations that are close to the same size or smaller than XML documents compressed using gzip
• Can consistently produce more compact XML representations than XML documents compressed using gzip
• Can consistently produce more compact XML representations than binary XML documents created with document analysis suppressed, then compressed using gzip
• Can consistently produce XML representations that are close to the same size or smaller than the equivalent ASN.1 PER encoding plus 20%
• Can consistently produce XML representations that are more compact than the equivalent ASN.1 PER encoding plus 20%
• [optional] Can consistently produce XML representations that are more compact than the equivalent ASN.1 PER encoding plus 20% compressed using gzip

A.12. Schema Extensions and Deviations

A format supports schema extensions and deviations if it allows applications to encode XML Infosets that are not conformant to the schema or not defined in the schema associated with the document.

A.13. Format Version Identifier

This property refers to the ability to efficiently determine the version of a format from a document instance. It is desirable to access this information as early as possible, so a format that does not make this information available when the processing starts should be considered inefficient as far as this property is concerned.

A.14. Content Type Management

This property refers to the definition in the format of one or more media types and/or encodings to be used when transferring documents. It is required for content negotiation, hence its importance for the Web.

The XBC Working Group proposed four degrees of support:

• provides no media type or encoding specification
• provides a media type but not a content coding
• provides a media type suffix akin to "+xml"
• provides a content coding

A.15. Self Contained

An XML format is self-contained if the only information that is required to reproduce the data model instance is (i) the representation of the data model instance and (ii) the specification of the XML format. When no external information is known by the receiver, the document needs to be self-contained.

A.16. Processing Efficiency

This property refers to the speed at which a new format can be generated and/or consumed for processing. It covers serialization, parsing and data binding. The XBC Working Group proposed the following criteria for its measurement:

1. Parsing into a DOM - The time it takes to parse into a DOM memory structure.
2. Parsing to SAX - The time it takes to parse to SAX events (push or pull).
3. Parsing to a new proposed interface (optional) - The time it takes to parse into a DOM-like memory structure proposed for binary XML as an improvement of DOM.
4. Query processing - The time it takes to process standard queries.
5. Update (creation, insertion, deletion) - The time it takes to modify an instance in a predetermined pattern of operations.
6. Retrieval - The time it takes to retrieve information from an instance.
7. XPath streaming - The time it takes to find a series of xpaths and associated data in a stream of data.
8. Serialization - The time it takes to generate the alternate format from a memory structure including DOM, SAX-related, and an optional proposed interface.
9. Lifecycle - Using the best available method, create an instance with data, interpret instance to get partial data, and modify or create new instance with some changes. Memory of the instance at each write/read point must not be reused at the next step.

Each measurement should be recorded as a percentage faster than a standard text-based alternative for each type of operation.

The EXI testing framework implements parsing from SAX and serialization through SAX. Alternative APIs can be used.

A.17. Small Footprint

This property refers to the size of a processor implementing a new format with respect to that of a processor implementing XML. Ideally, the evaluation of this property would be done through a range of implementations in different languages on various platforms. Since a complete evaluation could not be easily achieved during the development of the format itself, due to the small number of implementations at this time, an alternate solution consists in considering the number and/or complexity of the mandatory features (which impacts the size of the code segment) and the amount of data that must be available to a processor in order to support the format (which impacts the size of the initialized data segment).

A.18. Widespread Adoption

A format is more ubiquitous to the extent it has been implemented on a greater range and number of devices and used in a wider variety of applications. There is a tradeoff between the format implementation cost and complexity and the adequation to the applications' needs.

A.19. Implementation Cost

A requirement on XML was "It shall be easy to write programs which process XML documents." A rough estimate of implementation cost can be made by considering how much time does it take for a solitary programmer to implement sufficiently robust processing of the format (the so-called Desperate Perl Hacker measure).

The possibility to reuse common APIs (including DOM, SAX, StAX) lowers the cost of implementation of an alternate encoding of the XML Infoset. This property benefits from the Integration in the XML Stack property.

A.20. Space Efficiency

This property refers to the memory requirements of a processor implementing EXI with respect to that of a processor implementing XML. The measurement is a percentage of the dynamic memory costs for equivalent XML processing.

The measurement for this property is by inspection of format specification, logical analysis, and empirical testing on test scenarios. The EXI testing framework measures the heap size in each test case.

A.21. Forward Compatibility

A format must support the evolution of data models and must allow corresponding implementation of layered standards. Format version and extension points are related to this property. Evolution of XML and its data models could mean additional character encodings, additional element/attribute/body structure, or new predefined behavior similar to ID attributes. Integration of the EXI format into the XML Stack is also related to this property.

Appendix B. Generality evaluation