This Working Group Note presents measurement results of various
high-performance XML interchange encoding formats and their associated
processors, made by the Efficient XML Interchange (EXI) Working Group. The
measurements have been conducted following the recommendations of the XML Binary Characterization (XBC)
Working Group. In particular, this draft covers measurements of the
properties of "compactness", "processing
efficiency" and "roundtrip
support", as defined by the XBC WG. We start by describing the context in
which this analysis is being made, and the position of an efficient format in
the landscape of high performance XML strategies. Then we describe the
measured quantities in detail and the test framework in which they were made,
and give a short description of each format. Finally, a summary of the
results and the conclusions of the group are included. The
full measurements and analysis are included in an appendix and supporting
documents.
As a result of the measurements described here, the working group selected
Efficient XML ([EffXML]) to be the
basis for the proposed encoding specification to be
prepared as a candidate W3C Recommendation. Follow up work has centered
around integrating some features from the other measured format technologies,
particularly variations for both more efficient structural and value
encodings.
This section describes the status of this document at the time of its
publication. Other documents may supersede this document. A list of current
W3C publications and the latest revision of this technical report can be
found in the W3C technical reports index
at http://www.w3.org/TR/.
This note presents measurement results of the EXI Working Group's tests of
various high performance XML interchange encoding formats. This draft (see non-normative version above) concentrates on the
properties of "compactness", "processing
efficiency" and "roundtrip
support".
This draft adds analysis to the measurement results. Additionally
measurements of network interactions are included. The results
reported in this draft are considered to be stable, though there are still
some minor issues to correct with the measurement framework that are also
reported.
Following drafts of this note may add measurements of further features
under consideration for the candidate format recommendation, such as
performance enhancement under strict schema dependence, IEEE float support,
random access, etc. (as listed, at the time of writing, in appendix E of the
First Draft of the format specification).
While compactness will not generally vary from implementation to
implementation, processing efficiency may vary widely between implementations
of a given format. The current framework characterizes processing efficiency
of specific implementations, rather than attempting to evaluate any nominal
upper limit of processing efficiency for each format's primary algorithm.
This document was developed by the Efficient XML Interchange (EXI) Working
Group. A complete list of changes to this document is available.
Comments on this document are invited and are to be sent to the public<EMAIL_ADDRESS>mailing list (public archive). If
substantive comments are received, the Working Group may revise this Working
Group Note.
Publication as a Working Draft does not imply endorsement by the W3C Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.
This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. The group does not expect this document to become a W3C Recommendation. W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) must disclose the information in accordance with section 6 of the W3C Patent Policy.
1. Objectives
The objective of this document is to provide an analysis of the expected
performance characteristics of a potential "Efficient XML Interchange" (EXI)
encoding format. A successful EXI format will include facilities for helping
computers encode and decode the entities of XML documents efficiently and in
a compact form. The purpose of such a format would be to enable the use of
tools and processing models in the current XML technology stack, in
environments where the costs of producing, exchanging, and consuming XML are
currently high or prohibitive. Additionally, such a format may well enable an
expansion of the use of web technologies to new applications or industries,
which presently find some facilities of XML attractive, but are limited by
some hard constraints on encoded length or some aspect of computational
efficiency.
Based on the measurements described here, the working group has selected
Efficient XML ([EffXML]) to be the
basis for the proposed encoding specification to be
prepared as a candidate W3C Recommendation.
2. Methodological Context
The Extensible Markup Language (XML), is an application profile of
Standard Generalized Markup Language (SGML). It provides a well defined
syntax and encoding by which structured, textual, data can be examined by
people, and exchanged and interpreted by computers. The well defined basis of
XML, and its simple syntax that permits ready semantic interpretation, has
resulted in a very broad range of successful uses. There are a number of use
cases for which these advantages are tempered by inefficiencies which stem
from the textual encoding of XML. These cases, for instance, require a
compact form, such as in small portable devices like mobile phones, or an
encoding which avoids the time spent on floating point conversion, such as in
scientific and engineering fields. Many use cases, and the properties of XML
to which they are sensitive, were documented extensively by the XML Binary Characterization Working
Group, in [XBC Use Cases] and [XBC properties].
The XBC WG recommended that work on an Efficient XML Interchange format
proceed, since alternative formats which appeared to meet some or all of the
property criteria already existed. However, the XBC WG did not perform a
quantitative analysis of those formats, nor define measurable thresholds of
performance which should be achieved for each use case and property. This
Note provides measurement data regarding some of the quantitative Properties of XML relevant to
the creation of an efficient format for the interchange of XML, including its
encoding and processing. In general, we do not here review the simple-valued
properties of each format, such as whether they are "Royalty Free".
This draft concentrates on the two most critical properties of XML for a
potential efficient interchange format: "compactness" and
"processing
efficiency". These are important in that they are both significant
drawbacks with existing XML solutions in many use cases, and they are
difficult to accurately model. In addition, results for the "roundtrip
support" property are reported, as that is a necessary
property for any XML format, and failing to properly roundtrip
may allow a candidate to achieve unrealistically good results in
the other two properties.
In order to characterize the performance of the candidates with respect to
these properties, the EXI working group assembled a significantly larger set
of test data than was collected by the XBC. The group has also created a testing framework, based on Japex, which enables efficient testing of different
candidate formats and implementations against a variety of different XML
data. The wide set of test data is intended to highlight any binary-encoding
format which achieves good results at the expense of being narrowly focused,
and to help determine the generality of each format. The inclusion of many
candidate algorithms improves the likelihood of identifying superior
solutions which might ultimately inform an ideal single-format EXI
recommendation.
Results are included for each of these candidates versus common XML
solutions. Since processing efficiency is a measure of both format and
implementation combined, the EXI group issued a public call for fast XML
implementations to avoid drawing misleading conclusions. As a result of this
call, an existing high-performance XML parser (Xals) was provided, and used
in the measurements to obtain a baseline of XML processing efficiency. XML
Screamer was tested outside the framework, but intellectual property issues
forbade its inclusion in the framework and therefore comparative measurements
could not be made.
Submitted: May, PH. Integrated: 23-May, GW. Edited: 27-May, GW: Collapsed
intent from OG's viability arg and Peter's HP XML parsing/screamer arg, into
smaller space. June 4: SW: rewrote introduction, edited, included condensed
thoughts from PH's note.
As documented in [XBC
Characterization], the main properties that are considered lacking from
XML are Compactness and Processing Efficiency, and these shortcomings have led to the
development of alternative formats. However, due to the ubiquity of XML, it
would be better for interoperability to attempt to rectify these problems
without moving away from XML. For Compactness, the only widely available
alternative is generic compression below the XML level, as XML-specific
compression algorithms have not achieved wide usage. Another option is
to design the XML document structure so that it becomes more compact,
for instance by choosing short element and attribute names and preferring content in
attributes, as is the case with FIXML.
For improving Processing Efficiency, there are more options. An XML parser
is a complex system and a naïve implementation is rarely very efficient.
Furthermore, Processing Efficiency also encompasses phases like schema
validation and conversion into application data, so improvements may need to
be considered throughout the XML stack. The general way to improve Processing
Efficiency is to optimize parser performance. Even widely-used parsers may
have room for significant improvement. For instance, preliminary measurements
in the EXI framework indicate that the default parser shipped with Java
improved noticeably from version 5.0 to version 6, showing 2-3-fold
improvement for some cases.
Other improvements to XML Processing Efficiency are cases where the
performance is improved for a specific usage pattern. Published techniques
can be largely divided into three classes: schema-derived parsing, differential
parsing, and stack integration. None of these techniques improves processing
performance for all, or even a majority of, XML documents in a single
application. Rather, they provide techniques that can be used to improve
performance in each applicable use case individually.
Schema-derived parsing refers to the technique of pre-compiling an
available schema in some manner so that documents conforming to the schema
are parsed efficiently. The product of the compilation can be either
executable code [ChiuLu] or data structures for a
generic parser [EngelenAutomata]. Of
these, the latter is usually preferred in dynamic environments where new
schemas may be required to be recognized. Furthermore, there should be little
difference in efficiency between the two techniques as XML is a simple enough
language that techniques for generating efficient parsing tables are well
established.
Typical XML processing systems do not expect to receive arbitrary XML.
Rather, the common case is that incoming documents in a single use case
follow some schema, either an explicit or an implicit one. This observation
is the basis behind differential parsing. A differential parser will store
information on the XML documents it processes. Then, when another document is
being processed, this stored information is used to efficiently process the
parts in the document that match the stored information, leaving only the
differences to be processed with the general system. Differential parsing has
been based both on saving the parser state by creating checkpoints in the
processed stream [Abu-Ghazaleh2] and on
creating a finite automaton based on the byte sequences in the processed
documents [Takase].
Stack integration considers the full XML processing system, not just the
parser. By selectively combining the components of the processing stack through
abstract APIs, the system can directly produce application data from the
bytes that were read. Two prominent examples of this technique are [Screamer] and [EngelenGSOAP]. Both of these can also be called
schema-derived as they compile a schema into code. However, neither simply
generates a generic parser, but rather a full stack for converting between
application data and serialized XML. This gives a significant improvement
compared to just applying the pre-compilation to the parsing layer.
Of these techniques, none is specific to XML, but could be
applied to the implementation of an EXI format as well. An EXI format is required to be able to use
a schema to achieve improved Compactness, which implies a level of schema
awareness that could potentially be used to also improve Processing
Efficiency. Depending on the format specifics, it may be amenable to
differential parsing as well. Properly-designed stack integration of an EXI
format is expected to provide large benefits, especially for applications
that process large amounts of data in floating point format or other formats
with an inefficient text representation [BXSA].
The EXI Working Group published a call for efficient XML parser
implementations to obtain a reasonable point of comparison in the
measurements. The only parser that was provided as a result of this call was
Xals from Fujitsu, a fully conforming high-performance XML parser that
supports the usual APIs such as SAX and DOM. The main technique used in Xals
is the integration of character decoding into the parser instead of using the
platform's default libraries. This avoids the need to copy data in memory
prior to it being passed to the application. Xals also checks most of the XML
constraints prior to decoding, achieving greater efficiency than with
character-based checking. An additional benefit of these techniques is
greater portability, as there is no need to rely on a platform's default
library for character decoding.
4. Test Methodology
This section describes the measured characteristics, the
measurement process, and the analysis employed, to evaluate the
performance of submitted candidate formats for efficient XML
interchange.
4.1. Measured Characteristics
The independent data characteristics over which we measured the
candidates were firstly size, and secondly an aggregate called
"content density", described below. We also present a taxonomy of use
case groups to classify the test data, and so scope the results for a
given potential user.
Submitted: 25-Apr by GW. Integrated: 1-May, GW. Status: Edited 1-May, GW
Forward Reference: Note that the property of a format that it can handle
large documents will probably not be satisfied by those which require to load
the whole document into memory!
4.1.1. Characteristics of XML Complexity
The XBC Measurements Document [XBC
Measurements] <IP_ADDRESS> (Measurement
Considerations) says that processing efficiency is related to size
and to complexity. Additionally, it discusses data complexity in the context
of a large number of scenarios and property profiles of use cases. However,
how to quantitatively determine the complexity of a single document, in order
to gauge the response of a format's processing characteristics to complexity,
is not discussed.
Size can naturally be considered the primary determinant of
candidate format performance for many quantitatively measurable
properties, and therefore the test documents must be
characterized along the size axis. As the measurement of size,
the group selected the size of the document in bytes, encoded as
it was provided to the group. Since processing efficiency is
partly determined by the amount of time that it takes for the
document to be transferred into accessible memory, using the
number of bytes instead of characters as the metric is the
sensible choice.
Quantitatively measuring the complexity of an XML document is
more difficult than simply measuring its size. Determining
the Complexity of XML Documents ([DET-COMPLEXITY]) uses the following
complexity metrics in addition to size:
- total number of elements,
- total number of distinct elements,
- height of the tree, and
- sum of the depths of the nodes.
[DET-COMPLEXITY] also considers the
complexity of DTDs, but since many of the test documents do not
have associated DTDs or other schemas, these considerations are
not applicable.
Characterizing the test suite along too many different
complexity axes may not be sensible, as the test documents would
then be split into groups too small to facilitate meaningful
aggregate conclusions. Therefore, the group decided
to use only one complexity metric in addition to size for
measuring the amount of structure in an XML document. This
metric is content density (CD),
computed as follows:
-
gather all character data information items that are the
direct children of an element information item
-
gather all the values of all the attribute information items
-
sum up the size in characters of the text data gathered in the previous
two steps
-
the content density is the ratio of the the sum in the
previous step on the size of the entire document in characters
In summary, the documents in the test suite are characterized
along two axes: size in bytes and content density. These
characteristics are largely independent of each other, since
content density is measured as a percentage.
4.1.2. Test Data Classification
For test data, the group obtained more than 10000 XML documents
of various vocabularies. A subset of these were selected for
analysis, based on overall representativeness, and the XBC use
cases. These data are characterized in detail in the Appendix B: Description of Measurements
Test Suite. Almost all of the XBC use
cases were present. The missing four use cases are X3D Graphics
Model Compression, Serialization and Transmission, XMPP Instant
Messaging Compression, Business
and Knowledge Processing, and SyncML for
Data Synchronization.
As described above, the independent
characteristics of the test documents over which we measured the performance
of the various formats, were document size, and content density (the ratio
between text and markup, abbreviated CD). A plot of these two metrics
for the EXI test suite is shown below.
Looking at the plot above, four clusters of approximately equal size can
be distinguished. The four also exhibit properties that make them interesting
as analysis groups.
- High CD (22 documents)
- This cluster consists of documents having content density higher than
33%. Due to the prominence of data, these documents behave similarly
with EXI candidates.
- Low CD (66 documents)
- There are a number of documents with content density less than 33%.
Therefore this group is split according to size into three separate
clusters:
- Large (25 documents)
- This cluster consists of the low content density documents with
size more than 100 kilobytes.
- Small (24 documents)
- This cluster consists of the low content density documents with
size between 1 and 100 kilobytes.
- Tiny (17 documents)
- This cluster consists of the low content density documents with
size less than 1 kilobyte.
Note that the test documents do not divide neatly such that each test
group fits entirely into a single cluster, thereby entailing that documents
from the same test group frequently belong to separate content density
clusters.
Another axis along which to order the test groups relates to the use cases
to which they correspond (either because they map to the same use case, or
because the use cases that they map to are similar in terms of the properties
that they require). This approach yields eight rough categories of test
groups, henceforth called Use Groups, that show no overlap:
- Scientific information
- This covers data that is largely numeric in nature, used in
scientific applications. The use group includes GAML, HepRep MAGE-ML,
and XAL.
- Financial information
- This use group includes cases in which the information is largely
structured around typical financial exchanges: invoices, derivatives,
etc. It is comprised of FixML,
FpML,
and Invoice.
- Electronic documents
- These are documents that are intended for human consumption, and can
capture text structure, style, and graphics. This use group covers
OpenOffice, SVGTiny, and Factbook.
- Web services
- This use group consists of documents related to Web services, both
messages and other types of documents. The included test groups are
Google and WSDL.
- Military information
- These documents are encountered in military use cases. Included
groups are AVCL,
ASMTF and JTLM.
- Broadcast metadata
- The type of information in this use group captures information
typically used in broadcast scenarios to provide metadata about
programs and services (e.g. title, synopsis, start time, duration,
etc.). The use group includes CBMS.
- Data storage
- This use group covers data-oriented XML documents of the kind that
appear when XML is used to store the type of information that is often
found in RDBMS. It includes DataStore and Periodic.
- Sensor information
- Documents in this use group are information potentially provided by a
variety of sensors. The group includes Seismic, epicsArchiver, LocationSightings.
Conversely to the case with the content density clusters, with use groups
every test group belongs to a single use group, but the individual
characteristics of the documents inside a use group may vary, even
significantly.
As many of the test groups are applicable to more than one use case, the
division of test groups into use groups is, to a degree, a matter of
judgment. The major intent behind this specific division has been to include
a sufficient number of test documents so that aggregate conclusions are valid
over a use group, but not too many so that individual results get lost in the
noise.
<IP_ADDRESS>. Caveats
There are still some caveats regarding the test data and the parameters
that were used in the measurements.
- Schema quality
- Not all test groups include vocabularies for which complete and
normative schemata are available. Further analysis is therefore
desirable concerning the impact of using schema or not.
- DTDs
- The test groups SVG Tiny, MAGE-ML,
XAL all require
preservation of DTDs. As all candidates were not able to preserve them
at the time of the measurement runs, DTD preservation was disabled so
as not to penalize the compactness results of candidates able to
preserve them.
- Google
- This test group requires preservation of namespace prefixes due to
the use of SOAP encoding. This preservation option was accidentally
left out of the analyzed measurements, but will be present in any
future measurements.
It also needs to be noted that, despite the attempt to provide useful
use groups, some of them may not be of sufficient quality to
enable useful aggregate conclusions to be made. In particular,
the Broadcast use group consists of only a single test group
where all of the documents are very similar to each other in
size and somewhat similar in content density as well. This
means that aggregate statistics are in danger of being perturbed
by large amounts due to anomalous behavior from even a single
document. Another potentially problematic use group is the
Sensor group that consists of a number of minor variations of a
single very small document, one middle-sized document, and one
very large document that is also atypical XML. Therefore it is
not advisable to attempt to make significant conclusions based
on the results of this use group either.
4.2. Figures of Merit
Submitted: 25-Apr, GW. Integrated: 1-May, GW. Edited: 1st pass 1-May, GW, for
syntax. Needs content review.
For this draft of the Note we measured one of the three Algorithmic
Properties described in the XML Binary Characterization
Properties, for each contributed format; Processing
Efficiency. Additionally, the tests measure the Format
Properties of Compactness and
Roundtrip
Support. This section describes the quantities used to characterize those
properties in each potential EXI format that has been measured.
An Algorithmic
Property important for many use cases is Space
Efficiency, which is not measured in this document. An implementation of
the measurement exists in the framework for the Java-based candidates, using
access to heap usage statistics provided by Java, but currently the
measurement does not properly differentiate between different components of
the property, causing anomalous results and thus making it not sensible to
report the measured values.
4.2.1. Characterization of Processing Efficiency
This subsection describes the quantities we use to evaluate each format's
Processing Efficiency.
In addition to characterizing the speed of processing, the XBC
Measurement Methodologies [XBC Measurements]
document, section 6.2.1 Processing
Efficiency Description, delineates four properties of a format's
algorithm which need to be analyzed for processing efficiency; Incremental
Overhead, Standard APIs vs Abstract Properties, Processing Phases, and
Complexity [of the algorithm itself, not of the input data]. Of these, really
only incremental overhead is amenable to empirical testing. Incremental
Overhead refers to whether a format "allows and supports the ability to
operate efficiently so that processing is linear to the application logic
steps rather than the size of data complexity of the instance"
[emphasis added]. That is, it is reasonable to expect the processing time of
an application using an efficient format to be dominated by the complexity of
the application, not by the processing implied by the processing of the
format. So the desirable characteristic of a format is that its processing
time be (only) linearly or sublinearly dependent on the input data
complexity.
For most users of XML, linearity over a broad range is likely to be a
secondary concern. Of primary interest will be expected wall-clock elapsed
time to process "most" typical examples of an individual's use cases, in
their own scenarios. From the perspective of the XML community however, we
require good performance over a very broad spectrum of document complexities.
Therefore, as described above in Data
Characteristics and Complexity, the complexity requirement as a whole is
dominated by size, which makes the linearity requirement a necessary
one in addition to the small elapsed wall-clock time.
<IP_ADDRESS>. Measured Tasks of Processing
Efficiency
Processing speed was measured for each of the following processing tasks,
derived from the XML Binary
Characterization Measurement Methodologies document, part 6.2.2.
However, the measurement process was different for Java as opposed to C/C++
("native") format candidates. These are described separately below.
For Java based candidates, processing efficiency was
measured in each of the following contexts:
- Encoding to loopback using SAX API
- Encoding to network using SAX API
- Decoding from loopback using SAX API
- Decoding from network using SAX API
For each of these contexts, measurements were made for each of the "application classes" (see below),
neither (no schema and no compression), document
(compression), schema (use of metadata), and both
(use of both compression and metadata).
For the Java candidates, processing efficiency measurements were
made over a variety of networks. See below, Measurement Framework for a full
description of the measurement process.
For C/C++ ("native") candidates, processing
efficiency was measured only for encoding and decoding to and from memory.
Formats which include schema-aware encoding methods were allowed to use
them in cases where schemas exist. Since some formats required a schema,
where no schema existed for a test group, a naive XML Schema (root of
xsd:anyType) instance was generated for purposes of format performance
comparison. Where a schema or some other meaningful shared state might be
exchanged, timing tests do not include the time it would take to share the
state, such as exchanging the schema.
4.2.2. Characterization of Compactness
A figure of merit for compactness used in the literature, is the
normalized compactification rate = 1-(c/l), (that's one minus
c over l) where l is the length of the original
XML document (say utf-8 encoded on disk), and c is the length using
some compactification scheme. The factor can be multiplied by 100 to get a
percent compaction. This formalism results in higher positive values
(0..1-eps; or 0..100-eps%) the more compaction there is
(and negative values when the output is bigger than the input). In order to
provide more intuitive figures we have chosen to use, at least initially and
for presentation of results, simply c/l, or (c/l)*100%.
That is, smaller is better.
Note that the XBC Measurement Methodologies document [XBC Measurements] describes the property
"Compactness", of which one method is "compression". "Compression" in this
Note, means "document compression", which is taken to mean loss-less
compression algorithms—those which use redundant information in a document
to encode its data in a smaller space. Roughly speaking, compactness includes
compression, but may also derive from other methods.
The XBC Measurements Methodology document says that the compactness
property for a given format can be characterized separately for each of the
following methods from which overall compactness may be derived ([XBC Measurements], section 6.1.2):
- Tokenization—if possible, use of the format's encoding without the
use of any of the methods below. In the Japex reports this is called
"Neither"
- Schema—the use of schema-based encoding methods
- Compression—by data analysis. In the Japex reports this is called
"Document"
- Schema and Compression ("Document") combined. In the japex reports this
is called "Both"
- Deltas—use of a template, parent or earlier message (no formats use
this, so not measured)
- Lossy—use of some compression scheme where accuracy is traded for
compression (no formats use this, so not measured).
In accordance with the XBC Measurements Methodology document, each of the
elements in this 6-vector was to be measured and evaluated numerically, or
else characterized as follows "N/S (not supported) if the method is not
supported, or N/A (not applicable) if the method does not apply" ([XBC Measurements] part
6.1.2 para 1). The evaluation of lossy compression itself was to be
characterized by a vector, being the amount of compression obtained as a
function of the lossiness implied by each (if more than one) combination of
lossy compression schemes used by a format (possibly in combination with an
input "permitted lossiness parameter").
For these measurements of compaction we have taken two simplifying steps.
First, the tests do not attempt to characterize the compactification that may
be gained from delta encodings and lossy encodings (5 and 6 above). None of
the formats submitted so far utilize deltas in any integral way. If a
non-trivial schema was not provided for the test group, the format is not
permitted to look for one "elsewhere" (like at a URI). Just as for the
processing efficiency measurement, if there is no non-trivial schema, the
format's processor is permitted to use a pre-generated trivial schema (root
of xsd:anyType).
Also none of the formats we considered include a lossy compression
scheme.
<IP_ADDRESS>. Measurement of Compactness
Each candidate's measurement framework driver transforms the XML document
into the candidate's own format. The result is placed into a memory buffer.
The EXI framework gets a reference to this buffer and calculates its size. At
the time of writing, all such compactness results reported in this draft, in
Appendix A: Measurement Details, are expressed as a
factor to that of XML.
<IP_ADDRESS>. Application Classes
As all considered candidates are able to utilize only schema-based
techniques and document analysis on top of the always-allowed tokenization,
these two techniques combine to form four different application classes:
- Neither
- In this case the candidate has no access to external information such
as a schema or has it but the encoded instances that it produces are
still self-contained, and does not perform any compression bases on
analysing the document. Typically, simple tokenization of the XML
document is performed.
- Document
- In this case the candidate does not have access to external information
such as schema or has it but the encoded instances that it produces are
still self-contained, but may perform various document-analysis
operations such as frequency-based compression.
- Schema
- In this case the candidate does not perform any manner of document
analysis but may rely on externally provided information, typically a
schema, and the resulting bit stream may not be self-contained.
- Both
- In this case the candidate may use methods available in both of the
Document and the Schema
cases.
As the techniques available to candidates will be different in each
application class, the data analysis of processing efficiency results was
split four ways according to these classes, in addition to the analysis of
compactness. In the Document and Both classes, candidates are compared against gzipped XML,
while in the Neither and Schema
cases, the comparison was to plain XML.
4.3. Measurement Framework
In order to make consistent measurements of all candidates over the whole
test suite set, we used a framework based on Japex. Japex is a simple tool that is
used to write Java-based micro-benchmarks. It can also be used to test native
language (e.g. C/C++) systems via the Java Native
Interface (JNI), which we used to test native
candidate implementations.
Japex is similar in spirit to JUnit in that it does most of the
repetitive programming tasks necessary to make a measurement. These tasks
include loading and initializing the required drivers, warming up the VM,
forking multiple threads, timing the inner loop, etc.
The input to Japex is an XML file describing a given test. The file's
primary constituents are the location of a test data group (for example all
of our examples of X3D XML files), and references to one or more "drivers".
These drivers interface Japex to the code which is under test. Each
implements some well defined micro-benchmark measurement, such as "encoding
with schema".
The output of Japex is a timestamped report in XML and HTML formats. The
HTML reports include one or more charts generated using JFreeChart. The output
gives, for each observable under test, results for each data file, plus
aggregated results for the test group.
4.3.1. Framework's Measurement of Processing
Efficiency
To measure a candidate's Processing Efficiency, we measured aggregate
throughput for each of the processing
tasks.
For our purposes, the term "throughput" is defined to be work over time.
Japex is designed to estimate an independent throughput for each of the tests
in the input. Throughput estimation is done based on some parameters defined
in the input file. There are basically two ways to specify that: (i) fix the
amount of work and estimate time, or (ii) fix the amount of time and estimate
work. We fixed the time and measured work. In addition to each test's
individual throughput, aggregate throughtputs in the form of arithmetic,
geometric and harmonic means of results for all files in the test suite are
computed for each test.
The measurement consisted of feeding the events of the in-memory
representation, one by one, to the measured encoder, and then using the
measured decoder to parse the produced bytes back into the in-memory
representation. Subsequently, if the application class was either Document or
Both, the output, or input, streams were wrapped into GZIP deflater or
inflater objects, respectively - except in the case of EFX where the built-in
compressor was used. Processing time was measured separately for the encode
and decode phases.
See the Japex Manual [JAPEX] for
further information about Japex.
Two different computer systems were used in the measurements,
detailed in Appendix E:
Characterization of Measurement Machines. The systems were
carefully prepared to ensure reproducible measurements by
disconnecting any peripherals that were not needed to avoid
interrupts and by running only the measurement framework during
the measurements. As the measurement is intended solely for
comparing between technologies, this use of a limited number of
computer systems is a reasonable choice.
4.3.2. Reproducibility Criteria, Warm-up and
Caching
In our tests, measurements were made by a Java-based micro-benchmark
framework, both for processors implemented in Java and those implemented in
native languages. Since a Java Virtual Machine (JVM) typically performs a
just-in-time compilation of the running code, the first run does not usually
reflect actual application performance. Therefore, the actions of each
experiment were repeated as a warm-up, without measurement, until sufficient
cycles had passed to ensure that the measurements were stable.
This process has the intended effect of approximating and benchmarking the
performance of a warmed-up application. However, systematic effects may still
arise from caching (or warming-up) the input data, in addition to the code.
For example, if the benchmarking framework repeatedly reads a copy of the
input data from a fixed location in memory while warming up the code, the
processor will have the input data in high-speed cache memory, allowing
access times typically over 25 times faster than a real application might
encounter. One way to address this problem is by sequentially processing
multiple copies of the input data laid out end-to-end in memory. However,
simplistic versions of this memory access pattern might cause the results to
be skewed by pre-fetch caching hardware. Although these issues can be
addressed, care must be taken to tailor buffers, gaps, and total data so that
cache levels are cleared while avoiding virtual memory paging.
The cache cannot be removed or defeated for an empirical assessment
because caching behavior has a significant positive impact on the performance
of modern systems. For example, an algorithm designed to have a good locality
of reference to take advantage of caching and pre-caching architectures would
perform significantly worse if the cache is disabled than it would in actual
practice. In addition to data cache effects, modern processors are affected
significantly by branch prediction. Modern branch prediction is based on
local and global historical branch activity, meaning that warming up the
processor on data that is significantly different than the test data can
result in some performance difference. Most of the performance of modern
systems relies on caching, branch prediction, and related capabilities.
Our primary interest was to understand the performance of each potential
EXI format algorithm independently of I/O related factors. Therefore, the
benchmarking framework attempts to accurately model the code paths and memory
access patterns of real applications to the extent possible, while minimizing
the cost of I/O, blocking, context switches, etc. To factor out the majority
of the I/O, blocking and context switching costs associated with network I/O,
we used a local loopback interface. The local loopback reads and writes all
data through local memory instead of a physical network, essentially modeling
a memory-speed network. This approach uses the same buffering algorithms,
code paths and memory access patterns as a real-world application,
reproducing realistic caching effects without warming-up the input data. At
the same time, since it's memory-speed, the interface will probably provide
data faster than an EXI algorithm can consume it. This way, the algorithm
remains CPU bound throughout the duration of the test and is not subject to
I/O related blocking or context switching. The resulting benchmarks show the
processing efficiency of each EXI algorithm isolated from the speed or I/O
effects of a particular network.
The benchmarks that are likely to most accurately reflect the performance
of real EXI applications are those that include I/O to some external media,
like a network or file system. EXI is about interchange, so most EXI use
cases will read or write EXI documents to and from devices that are often
slower than main memory (i.e., networks or storage media) although there are
important cases of memory to memory interchange. Therefore, the benchmarks
that are likely to most accurately model real-world performance for many
cases will be those that read and write EXI documents to and from networks
and storage devices. Careful scrutiny is needed, especially when not using a
loopback interface, to detect bandwidth bottlenecks that are smaller than the
throughput of algorithms being tested. These benchmarks are expected to
accurately model the interaction between the caching algorithms employed by
modern computing architectures and the memory access patterns of buffering
algorithms employed by typical device drivers. They also are expected to
accurately model the subtle, but significant performance implications of
blocking and context switching that occur as algorithms shift repeatedly
between CPU and I/O. For a given platform and use case, the average time
spent doing context switches and being I/O-bound vs. CPU-bound will differ
from one EXI format to another. It will be influenced by a variety of
factors, including the average throughput of the EXI algorithm, the average
throughput of the I/O device, and the compactness of the EXI format. It must
be noted however that this interaction with operating system characteristics
may not be deterministic. The determinism of a trial may be subject to
particular buffer sizes or other details that are not obvious. Therefore, for
higher confidence, a comparison might be needed between a
network-intermediated trial and a cache-clearing, memory to memory trial.
To look more closely at those effects of the network, in a real-world-
like setting, the framework has been extended to measure the performance of
EXI algorithms reading and writing from any TCP/IP based network (e.g., Wired
LAN, WI-FI LAN, Internet, GPRS, etc.). This will enable us to collect
benchmarks using the same network media, buffering algorithms, device
drivers, and code paths employed by EXI use cases. As such, it replicates the
memory access patterns, blocking patterns, context switches, etc. of, at
least, TCP/IP based real-world applications. Results from 100Mbps network
tests using this extension, have been included in this draft of the note.
4.3.3. Measurement of Processing Efficiency of Java Based
Candidates
This section describes the measurement framework's setup for the
measurement of Java based candidates. The
quantities so measured for Java based candidates are given above.
<IP_ADDRESS>. Decode
For the measurement of decoding speed of a Java candidate, the candidate's
driver first transforms the XML document into its own format. The result is
placed into a memory buffer. If decoding from memory, this memory buffer is
wrapped into an input stream and passed to the driver for parsing. All Java
drivers parse this input stream using the SAX API (an XMLReader) with an
empty SAX content handler, essentially dropping every event after it's
reported. If decoding from the network, an "echoing" server is started either
as a separate thread, if in localhost mode, or as a separate process, if in
non-localhost mode. The framework then sends the entire stream to the echoing
service for buffering. It then creates an input stream that reads from the
network socket connected to the echoing server and passes it to each driver.
Each driver operates identically regardless of whether they are reading from
a memory buffer or the network.
<IP_ADDRESS>. Encode
For the measurement of encoding speed, the XML document is parsed using a
SAX parser and all the events recorded in a data structure (an event array).
If encoding to memory, a memory buffer is created and wrapped into an output
stream. This output stream is set in each driver and the stream of SAX events
is played back to the candidate's encoder. If encoding to the network, a
server is started, either as a separate thread, if in localhost mode, or as a
separate process, if in non- localhost mode. The framework then creates an
output stream connected to the socket on which the server listens. Just as in
the in-memory case, the stream of SAX events is played back to each driver.
4.3.4. Measurement of Processing Efficiency of Native
(C/C++) Candidates
This section describes the measurement framework's setup for the
measurement of C/C++ based candidates. The
quantities so measured for C/C++ based candidates are given above.
In the case of libxml2, the reference XML processor, the serialization
process was first to read the entire XML document to be tested into a DOM
tree structure in the initialization function (the time to do this was not
measured). It would then repeatedly serialize this DOM tree to an XML
document in memory for either a fixed duration or for a set number of
iterations depending on how the test was set up. For decoding, the time to
execute empty SAX handlers was measured. The document was read into memory in
the initialization function and then repeatedly parsed in the time
measurement loop by the SAX parser.
All of the native candidates were based on ASN.1, and for each of them a
form of data binding was used. An ASN.1 specification that was equivalent to
a given XML schema specification was created using a standardized procedure
(specified in X.694). This specification was then run through an ASN.1
compiler to created hard bindings of the structure to C program variables.
For example, an XML schema sequence having 3 integer member variables (a, b,
and c) would result in the generation of a C structure with 3 equivalent
integer members and code would be produced to encode to and from this
structure. For encoding, the initialization procedure loaded the XML document
into this custom C structure. The encoding loop would then repeatedly invoke
the custom encode function to serialize the data to XML form. For decoding,
the process was reversed. The XML document was read into memory in the
initializer. It was then repeatedly decoded into the C structure in the
timing loop to get the decode time. Note that the C structure variable would
be cleaned and memory reset between invocations to alleviate the memory cache
effect.
4.4. Native Language Implementation Considerations
Some of the candidates currently being considered as a basis for an EXI
standard only have C or C++ implementations, as opposed to Java, available at
this time. In order to test the processing efficiency of these candidates
using Japex, the framework was augmented to provide a driver API through the
Java Native Interface (JNI), that allows non-Java applications to be
benchmarked.
The JNI is used in such a way as to isolate the performance of the C/C++
implementation from the Java processing in the Japex framework. This is done
by doing all of the timing on the native (i.e. C/C++) side of the interface.
Clearly, there will be some residual systematic effect, since at least a JVM
is cohosted, but we believe that effect is negligible.
However, the processing efficiency timing results that are produced cannot
be directly compared with results for Java candidate implementations for
several reasons:
- There is no "JVM effect" in C/C++. One would expect processing times to
be somewhat faster since no byte code interpretation is required and
there are fewer overhead tasks such as garbage collection (though of
course an algorithm implemented in native code will also have to do
housekeeping). The actual amount of this speedup is not known in detail,
since we do not yet have any candidate with isomorphic implementations in
both Java and C/C++. In further work, we may try to evaluate whether this
fraction, the amount of speedup, is what we would expect for comparable
applications (see Appendix C: Further
Work)
- The methodology for getting events into the
native applications for processing is different. Since it is not
practical to feed Java Events across the JNI boundary for processing, and
no existing implementation of a SAX-like typed-event API could be found,
an alternative to the SAX and typed-SAX APIs which are used for Java was
required. One method that is currently being used is to construct a DOM
tree from an XML source and then to use this tree to populate objects for
serialization into the candidate binary format. For deserialization, the
time to deserialize from the binary format to objects is measured. Two of
the native formats are those based ASN.1 and the objects are those of
classes generated by compiling the ASN.1 schema.
- Different implementation types. At least two known candidates that
currently have C/C++ implementations use data binding technologies as
opposed to the more standard XML technologies. Data binding produces
tightly coupled, very performant applications by building information
directly from schemas into the compiled native code. The XML Screamer
application [Screamer] has used this
technology to produce impressive performance results with XML.
For these reasons, it would not be accurate to compare native candidates
with Java ones for processing efficiency. Instead, a comparison is done with
an existing C/C++ based XML processor. We used the open source libxml2
library (http://xmlsoft.org), a highly performant implementation available in
most Linux distributions. Libxml2 doesn't resolve all issues; for instance,
it does not provide data binding.
4.5. Fidelity Considerations
In this section we also describe the taxonomy with which the group
evaluated the extent to which each EXI format candidate satisfies the lexical
reproducibility requirements of the examples in the test suite .
The degree to which a candidate can accurately reproduce the information
represented by a test group is determined jointly by the following:
- properties of the candidate. For example, candidates may not be able to
support the preservation of certain information or support the
preservation of information with only a particular fidelity
- properties of the test group and more broadly the use cases to which
the test group belongs. For example, test groups that contain signed
information (as specified by W3C XML-Signature Syntax and
Processing [XML Signature]) may require
higher fidelity to the original than test groups that contain no signed
information.
To characterize the extent to which each candidate preserved the
information necessary for a test group, each test group was annotated with
what information must be preserved, and with what accuracy, to satisfy the
particular requirements of that case.
The "roundtrip support" measurement property of the test framework was
used to determine whether the candidate accurately reproduced the information
represented by each test group, according to the annotation. If the result of
this measurement was that the candidate did not reproduce the information
with the required fidelity, or it was predetermined to fail without running
the test, then the candidate was determined to have failed the round-trip
support measurement property for that test group.
The fidelity requirements were communicated to the test framework, and to
each candidate under test, through japex parameters. Those parameters
prescribed what did and did not need to be preserved. Candidates were free to
examine the parameters to optimize their encoding. For example, if
preservation of comments and processing instructions was not required, as is
the case for SOAP message infosets, then a candidate was allowed to use that
knowledge to encode SOAP message infosets more efficiently than it could were
it not permitted to make such a narrowing assumption.
The following information represented by a test group did not need to be
preserved by a candidate:
- the XML declaration
- the use of single or double quotes characters for quoted strings
- markup white space.
It is not anticipated nor expected that candidates will accurately
reproduce information on a syntactic or byte-per-byte basis [see fidelity
scales 3 and 4].
The following subsections present the distinct sets of information that
may or may not be preserved by a candidate.
<IP_ADDRESS>. Preservation of White Space
If a white space needs to be preserved then all non-markup white space
information [see 2.10 White Space Handling, XML 1.0] represented by the test
group MUST be preserved.  Such non-ignorable white space information may be
determined from a schema, if present with the test case, and/or by inspection
of the test group.
<IP_ADDRESS>. Preservation of Comments
If comments need to be preserved then all comment information represented
by the test group MUST be preserved. Otherwise, comment information need not
be preserved.
<IP_ADDRESS>. Preservation of Processing Instructions
If processing instructions need to be preserved then all processing
instruction information represented by the test group MUST be preserved.
Otherwise, processing instruction information need not be preserved.
<IP_ADDRESS>. Preservation of Namespace Prefixes
If namespace prefixes need to be preserved exactly then all namespace
prefix information represented by the test group MUST be preserved verbatim.
Otherwise, namespace prefix information need not be preserved identically.
The verbatim preservation of namespace prefixes is important when a test
group contains signed information or prefixes as part of a qualified name
information in element content or attribute values. Preservation of namespace
prefixes is important in any case to maintain document validity and
correctness.
<IP_ADDRESS>. Preservation of Lexical Values
If lexical values need to be preserved then all character data (see
Extensible Markup language (XML) 1.0 [XML 1.0]
section 2.4 Character Data and Markup) information represented by the
test group must be preserved. Otherwise, lexical values need not be
preserved.
Lexical values may not be fully preserved if a candidate chooses to encode
a lexical value into a more efficient lexical value, or in binary form, and
the original lexical value cannot be reproduced. For example, the decimal
lexical value of "+1.0000000" might be converted to the more efficient
canonical decimal lexical value "1.0". Similarly, the boolean lexical value
"1" might be converted to binary form as one bit of information and it may
not be determinable from the binary form whether the original lexical value
was "true" or "1".
<IP_ADDRESS>. Preservation of the Document Type Declaration
and Internal Subset
If the document type declaration and internal subset need to be preserved
then the document type declaration and internal subset information
represented by the test group must be preserved. Otherwise, document type
declaration and internal subset need not be preserved.
4.5.2. Fidelity Scale
Candidate formats, and test groups, can be classified according to a
"scale of fidelity". For formats, the scale is a metric of the extent to
which information is preserved with respect to various XML data models. For
test groups the same scale is used to classify the requirement the of the
test group for round-trip accuracy. We defined it to go in order of
increasing fidelity. A candidate which has been determined to score at a
certain level on the scale may still preserve some, but not all, information
specified at higher levels.
Note that this does not imply that documents produced by candidates have
an isomorphic representation of the information represented by certain XML
data models, rather that a candidate stores enough information to be able to
reproduce the preserved information.
Table 1: The Fidelity Scale for Classification of EXI
Candidates
| Level |
Preserves |
| -1 |
Preserves only a subset of the XPath data model
Level -1 defines the class of candidates that preserve a subset of
the XPath 1.0 data model. For example, a candidate might not preserve
namespace prefixes.
|
| 0 |
Preserves the XPath data model
Level 0 defines the class of candidates that preserve the XPath
1.0 data model.
Such preservation includes the root node, elements, text nodes,
attributes (not including namespace declarations), namespaces,
processing instructions and comments.
Unexpanded entities, the document type declaration and the
internal subset are not preserved.
This level corresponds to a common denominator in XML processing,
it is equivalent to the SOAP XML subset with the addition of
processing instructions and comments.
|
| 1 |
Preserves the XML Information Set
Level 1 defines the class of candidates that preserve the XML
Information Set data model.
The XML Information Set preserves more of the information
represented in the document type declaration and internal subset than
the XPath 1.0 data model but not all information, such as attribute
and element declarations, is preserved.
The [all
declarations processed] property of the Document
Information Item is not, strictly speaking, part of the Infoset
[XML Infoset] and therefore does
not need to be preserved.
NOTE: A candidate can fully support level 1, level 2, and the
preservation of the complete internal subset by including and
encoding the internal subset as a string, thereby leaving it up to
the decoder to optionally process it.
|
| 2 |
Preserves the the XML Information Set and all
declarations
Level 2 defines the class of candidates that preserve the XML
Information Set data model, as in level 1, in addition to all
information that is not purely syntactic. Such additional information
will include the attribute, element and entity declarations.
This level covers the preservation of all information represented
by an XML document but does not accede to supporting purely syntactic
constructs.
NOTE: A candidate can fully support level 2 by including and
encoding the internal subset as a string, and thus leaving it up to
the decoder to optionally process it.
|
| 3 |
Preservation of syntactic sugar of the XML document
Level 3 defines the class of candidates that preserves all
information represented by an XML document, as in level 2, in
additional to some but not all syntactic information.
NOTE: Full syntactic information is supported by level 4.
Such preservation includes but is not limited to:
- CDATA Sections
- resolved external entity reference boundaries (when an entity
is resolved a candidate will flag the part in the produced
infoset where the information included from it starts and
ends)
- the use of single or double quotes characters for quoted
strings
- white space in markup
- the difference between empty element variants
- the order of attributes.
|
| 4 |
Preservation of bytes
Level 4 defines the class of candidates that preserve the XML
document byte-per-byte.
NOTE: This is the simple level supported by generic encodings such
as gzip.
|
4.6. Analysis Methodology
Creating a benchmarking framework that is able to produce a variety of
measurements fairly and accurately, using multiple format implementations
from many vendors is a complex and arduous task. This difficulty has affected
both the analysis aspects covered in this document as well as the whole
methodology of producing measurements.
First, while the XBC Characterization Note
lists a number of requirements for an EXI format, this document covers only
three: roundtrip support, compactness, and processing efficiency. However,
many of the listed requirements are not amenable to measurement as such, but
would rather be evaluated based on the format specification. Since this task
does not require precise measurement, it is expected to take considerably
less time and has been left for later.
The full methodology is an iterative process, starting with a measurement
run. The results of such a run are reviewed for stability and perceived
correctness. Any discovered problems are corrected and a new run
commissioned. Meanwhile, results that have been deemed stable are used as a
basis for preliminary analysis. The results presented here come from a stored snapshot that has
been judged sufficiently stable for making decisions.
Even so, there is still some variation in the results. This is a concern
especially with the C-based candidates that may exhibit enormous and
inexplicable variance between different test documents. It is therefore
likely that there are still some problems with how the test framework's Java
code interacts with the C code of the candidates. Accordingly, the results
from the C-based candidates were filtered more carefully, by eliminating
results for individual documents that were obviously incorrect. In addition,
the stableness review of the results paid careful attention to any
improvements in these candidates in particular.
The measurement process produces a large amount of data, consisting of 88
documents, four application classes, three separate runs, and eight
candidates. Furthermore, as different applications require different
properties of a format in differing proportions, it is not feasible to
produce a single, or even a few, figure of merit for comparing candidates.
Instead, comparison needs to be performed over a variety of use cases or the
like.
A variety of analysis methodologies were used, ranging from graphs, both
summaries and detailed ones, to statistical methods for estimating average
performance. Comparisons were always made to best available XML
implementations, used as would be normal for each particular case under
analysis.
Review of the results and aggregation was performed with a spreadsheet
program that allows live re-grouping of the data. This leads to an easy
viewing of the anomalous results and their elimination from consideration.
Other analysis methods included drawing of graphs for particular sub-groups
of the whole test suite, making inferences based on these graphs, and then
verifying the inferences and establishing precise performance bounds by
reviewing the individual measurements.
The overall goal of the measurement and analysis process was to select one
or more distinguished candidates that could serve as a basis for the EXI
format. Accordingly, much of the analysis was focused on picking the top
performers and verify that their top performance was consistent throughout
the different use cases, and especially to make sure that none of the
distinguished candidates disqualified themselves in any particular case.
5. Contributed Candidate EXI Implementations
This section provides a technical description of the basic architecture of
each of the contributed XML formats whose performance characteristics were
measured (see Results). The statements in these
descriptions are those of representatives of each format and have not been
validated by the working group.
5.1. X.694 ASN.1 with BER
Submitted: 25-Apr, ED. Integrated: 25-Apr, GW. Edited: partly edited for
content 25-Apr, GW.
The X.694 ASN.1 BER candidate submission uses a set of standards that have
been in place for many years for binary messaging (ASN.1 itself since the
early 1980s). There are three parts to the candidate:
- The Abstract Syntax Notation 1 (ASN.1), from the International
Telecommunications Union - Telecommunications Group (ITU-T), and the
International Standards Organization (ISO), is a schema much like the XML
Schema for describing abstract message types
- The ITU-T/ISO Basic Encoding Rules (BER), is a set of encoding rules to
be used with ASN.1 to produce a concrete binary representation of a set
of values described using an ASN.1 schema
- The ITU-T/ISO X.694 standard provides a mapping of XML Schema (XSD) to
ASN.1, and allows the use of ASN.1 and its associated encodings in XML
applications.
In this format candidate, BER encoding was selected in preference to PER
(Packed Encoding Rules - see X.694 ASN.1 with
PER below) because it was felt that the flexibility in the
tag-length-values (TLV) that it provides, is closer in spirit and
functionality to XML than the tightly coupled encodings produced by PER. The
general principle is that each element construct in XML;
<tag>textual content</tag>
is replaced by a similar binary encoding consisting of a tag-length-value
descriptor.
Efficiencies are gained from two properties of this format: 1) the tags
and lengths are binary tokens that are in general much shorter than XML
textual start and end tags, and 2) the content is in binary instead of
textual form.
Some advantages of using ASN.1 BER to encode XML are that the TLV format
is similar to XML's start-tag / content / end-tag pattern; encoded
length can be 5 to 10 times less than textual XML, and encoding and decoding
is very efficient - no compression or other CPU intensive algorithms are
used. Additionally, ASN.1 BER is mature and stable, and its security has been
studied in-depth.
However, it is schema-based - an XSD or similar schema is needed to encode
and decode, and some fraction of the XML Information Set can not be
represented (for example, randomly occurring comments and Processing
Instructions).
See references [USE-OF-ASN.1], [ASN.1], [BER], [X.694].
Submitted: 15-May, PT. Integrated: 16-May, GW. Edited: 1st pass. Needs to be
checked by Paul, changed quite a lot.
5.2. X.694 ASN.1 with PER
Similarly to the X.694 ASN.1 with
BER candidate format described above, this one uses X.694 to map from an
XML Schema document to ASN.1. In this variation, we add the use of two
further ITU-T standards, X.693 and PER. These additions allow direct output
in textual XML, and a somewhat more compact binary encoding.
PER, which stands for Packed Encoding Rules [PER],
is one of the ASN.1 Encoding Rules published by the ITU-T, IEC, and ISO. PER was specifically designed to minimize
the size of messages needed to convey information between machines. It has
been widely adopted in critical infrastructure where bandwidth is limited. It
originated from work on an efficient air-to-ground communication protocol for
commercial aviation, and has since been used in many areas including cell
phones, internet routers, satellite communications, internet audio/video, and
many other areas.
Another of the ASN.1 Encoding Rules, Extended XML Encoding Rules, or
"EXTENDED-XOR" [X.693], defines a set of encoding
rules, that can be used in a way analogous to XML Schema, and applied to
ASN.1 types to produce textual XML.
Since the schema notation used by XML Schema is quite different from the
ASN.1 notation, ITU-T Rec. X.694 | ISO/IEC 8825-5 was created to give a
standard mapping from schemas in XML Schema to ASN.1 schemas in such a way
that XML Schema aware endpoints, could exchange documents with ASN.1 aware
endpoints, using the EXTENDED-XER Encoding Rules.
With the ASN.1 schema generated using X.694 from an XML Schema instance,
one can generate not only XML documents (using the ASN.1 engine with
EXTENDED-XER), but binary encodings with any of the ASN.1 Encoding Rules, of
which PER is the most compact.
Submitted: 25-Apr, JK. Integrated: 29-Apr, GW. Edited: style & content
29-Apr.
5.3. Xebu
The Xebu format
is a product of research into XML messaging on small mobile devices. The
central XBC Properties considered in its design were; Streamable, Small
Footprint, and Implementation
Cost.
Xebu models an XML document as a sequence of events, similarly to StAX or
SAX. The event sequence is serialized one by one. The basic Xebu format,
applicable to general XML data, includes mappings from strings in the XML
document to small binary tokens. These mappings are discovered dynamically
during processing.
Xebu also includes three optional techniques for when a schema is
available:
- Pretokenization; this populates the token mappings beforehand, based on
the strings appearing in the schema
- Typed-content encoding; this results in a more efficient binary form
for certain data types, than can be achieved without a schema
- Event omission; this leaves out events from the sequence if their
appearance and placement can be deduced from the schema.
The main advantages of Xebu are; its support for general XML with varying
levels of schema-awareness, a direct correspondence with well-understood XML
data models, so making XML compatibility easy to achieve, and that it's
simple and straightforward to implement.
See reference [XEBU1]
5.3.1. Caveats
The implementation used in the measurements has been written for mobile
phones, and therefore it does not perform as well as an implementation
written for desktop machines or servers would.
The measurements with a schema were run with only pretokenization enabled.
Typed-content encoding was not enabled due to the difficulties of accessing
type information efficiently. The event omission implementation cannot handle
arbitrary schemas, so only a subset of the test document schemas would have
produced an effect. Furthermore, the implementation is written for RELAX NG,
and conversion from XML Schema worked only for a very few cases. Because of
these issues, event omission was also disabled in the measurements.
5.4. Extensible Schema-Based Compression
(XSBC)
Submitted: 29-Apr, DM. Integrated: 29-Apr, GW. Edited: partly edited for
content 29-Apr, GW. Edited 3-may. GW: 27-May, removed editorial comments
flagging editorial changes in prep for publication - so should be
checked.
Extensible Schema-Based Compression (XSBC) is a system for encoding XML
documents that are described by schemas into a binary format. The result is
more compact, faster to parse, and has better databinding performance than
textual XML.
XSBC preprocesses the schema that describes an XML document, and creates
lookup tables consisting of integers that index the string values of element
names. The schema's type information about marked-up data, if any, is
captured in one lookup table. In the same way, element attribute names are
added to a lookup table, along with their type information. The size of the
integers that correspond to the element and attribute names is chosen so that
if only a few names are in the document, smaller numbers are used.
Once the schema has been processed and the lookup tables have been
populated, the XML file is transcoded into binary format. Text element start
and end tags are replaced by the binary format whole numbers to which they
correspond in the element lookup table. Additionally, if any marked-up text
data can be represented in an equivalent binary format, such as
floating-point, it is replaced.
Element attributes are added after the binary element start tag. Attribute
representations may be only the attribute start tag, followed by the
attribute data, in binary format, if the schema type information makes this
possible.
The marked-up data in binary format, for either element data or attribute
data is then passed through data compressors. In the case of simple,
fixed-length integers and floats, the standard IEEE 754 format can be used.
Variable length data, such as strings, can be represented by a starting value
that includes the length, followed by the actual data. The data compression
system is easily extended to handle data other than that represented by the
standard data compressors, and in fact can be extended dynamically. For
instance, it's possible to write custom compressors for sparse or repetitive
matrices, floating point data which is representable in only a certain number
of significant digits, or other specialized data types.
Encoding and decoding a textual XML document to an XSBC document is quite
straightforward. A simple finite state machine can be constructed to decode
XSBC documents. An XSBC decoder can step through the document easily because
of the structure of the document.
An XML Schema instance is required to encode the document. In future, the
XSBC team plans to implement a feature in which a document without a schema
can be "pre-preprocessed" and a stand-in schema generated for it. This
stand-in schema will be untyped (all data will be represented as strings) but
this would allow an arbitrary XML document without a schema to be
represented.
XSBC's virtue is its simplicity. It is, essentially, every programmer's
first idea of how to represent an XML document in binary form. There is a
strong correspondence between the textual XML representation and the binary
representation.
5.5. Fujitsu XML Data Interchange Format
(FXDI)
Submitted: 1-May, TK. Integrated: 3-May, GW. Status: Edited, some
clarification of encoders needed. 27-May GW; removed editorial comments for
publication. Should be checked. References needed. 29-May: TK resubmitted
with clarified distinction between encoders. Text says that diff encoders are
used for compactness and PE, although my recollection is that was to be not
allowed - all properties results should be presented for all configurations.
emailed group to confirm.
The Fujitsu XML Data Interchange (FXDI) format was designed to serve as an
alternative encoding of the XML Infoset, which allows for more efficiency,
both in the exchange of data between applications and in the processing of
data at each end-point. FXDI's primary design goals were document
compactness, and to enable the implementation of fast decoder and encoder
programs, which run in a small footprint, and without involving much
complexity.
FXDI is based on the W3C XML Schema Post Schema Validation Infoset (PSVI),
though some of the format features derive from the XPath2 Data Model.
Although FXDI performs much better when schemas are prescribed before
documents are processed, it is capable of handling schema-less documents and
fragments through its support for Infoset tokenization.
At the core of FXDI is the "compact schema". FXDI uses Fujitsu Schema
Compiler to compile W3C XML Schema into a "schema corpus". A schema corpus
contains all the information expressed in the source XML Schema document plus
certain computed information such as state transition tables. A compact form
of the schema is then computed from a schema corpus by distilling only those
information items which are relevant to the function of FXDI processors.
There are two types of FXDI processors. Firstly, those that are used to
generate FXDI documents. These are called "FXDI Encoders". Conversely, FXDI
Decoders, decode FXDI documents into data usable by programs.
FXDI supports two different methods to create FXDI documents:
- An encoder API, that allows programs to convert an XML text stream or
SAX events into FXDI documents. FXDI has two independent encoder API
implementations. The "validating encoder", which has the ability to
conduct full-fledged schema validation while encoding subject to the
constraints expressed in an XML Schema. The other encoder is
non-validating. It is incapable of schema-validation, but performs much
faster than the validating encoder. Although their implementations and
techniques are very different, the two encoders always generate the same
result given an XML schema and an XML instance document
- A Direct-writing API, which is suitable in scenarios that allow for the
use of data-binding. It always performs faster than the Encoder API
because no schema-machinery is involved in the process.
In the EXI Test Framework tests, the validating encoder was used in the
compactness tests. The validating encoder carries out schema-validation as
part of encoding process and logs any errors in test case XML documents. This
is useful for diagnosing performance anomalies caused by test case documents
that deviate from their associated XML Schemas. On the other hand, the
non-validating encoder is used in the encoding tests for maximizing
processing efficiency.
FXDI works well with conventional document redundancy-based compression
such as gzip. That facilitates use cases that need the additional compression
and can spend the additional CPU cycles.
See W3C
EXI WG and Fujitsu for more information.
5.6. Fast Infoset
Fast Infoset is an open, standards-based binary format based on the
XML Information Set [XML Infoset].
ITU-T Rec. X.891 | ISO/IEC 24824-1 (Fast Infoset) [FI] is also itself an approved ITU-T
Recommendation as of 14 May 2005. An ISO ballot has been initiated (and is
near completion) that will result in ISO/IEC 24824-1 being available for free
when published.
The XML Information Set specifies the result of parsing an XML document,
referred to as an "XML infoset" (or just an "infoset"), and a glossary of
terms to identify infoset components, referred to as "information items" and
"properties". An XML infoset is an abstract model of the information stored
in an XML document; it establishes a separation between data and its
representation that suits most common uses of XML. An XML infoset (such as a
DOM tree, StAX events or SAX events in programmatic representations) may be
serialized to an XML 1.x document or, as specified by the Fast Infoset
specification, may be serialized to a Fast Infoset document. Fast Infoset
documents are generally smaller in size and faster to parse and serialize
than equivalent XML documents.
The Fast Infoset format has been designed to jointly optimize the axes of
compression, serialization and parsing, while retaining the properties of
self-description and simplicity. The approach has been to find, when not
taking advantage of advanced features, a "sweet spot" where moderate
compression can be achieved but not at the undue expense of creation,
processing performance and simplicity.
The use of tables and indexing is the primary mechanism by which Fast
Infoset compresses many of the strings present in an infoset. Recurring
strings may be replaced with an index (an integer value) which points to a
string in a table. A serializer will add the first occurrence of a common
string to the string table, and then, on the next occurrence of that string,
refer to it using its index. A hash table can be used for efficient checking
of strings (the string being the key to obtaining the index; every time a
unique string is added to the hash table, the index of the table is
incremented. A parser will add the first occurrence of a common string to the
string table, and then, on the next occurrence of that string, obtain the
string by using the index into the table.
Fast Infoset is a very extensible format. It is possible, via the use of
encoding algorithms, to selectively apply redundancy-based compression or
optimized encodings to certain fragments. Using this capability, as well as
other advanced features, it is possible to tune the "sweet spot" for a
particular application domain. An example of this is the use of a built-in
encoding algorithm to directly encode binary blobs without the need for any
additional encoding, in a way similar to the Message Transmission Optimization
Mechanism(MTOM), but with the binary blobs encoded inline as
opposed to as attachments. Other built-in algorithms can be used to
efficiently encode arrays of primitive data types like integers and floats, a
feature often used by scientific applications to reduce message size and
increase processing efficiency.
Additional features of Fast Infoset include support for restricted
alphabets (for better compactness) and for external indexing tables, for
those cases in which a tighter coupling is acceptable in the interest of
achieving better performance.
5.6.1. Caveats
For the Schema and Both
application classes Fast Infoset is not fully optimised to utilise schema:
- For the cases where prefixes do not need to be preserved (or in the
more general case when a set of sample documents can be utilised in
conjunction with schema) further reductions in compactness and processing
efficiency are possible.
- The use of encoding algorithms or restricted alphabets to convert
lexical representations of text content or attribute values to more
optimised binary forms that may be faster to process and/or more compact.
5.7. Efficient XML
Submitted: 11-May, JS. Integrated: 13-May, GW. Status: Moved 1st 2 paras to
end and removed assertions that might reasonably be made of all formats
without supporting data. Also removed assertion about w3 requirements, since
that is what the data is intended to show, and again the point is to show
this for all formats.
Efficient XML is a general purpose interchange format that works well for
a very broad range of applications. It was designed to optimize performance
while reducing bandwidth, battery life, processing power and memory
requirements. It is the only format currently being tested that supports all
of the features specified by the minimum binary XML requirements defined by
the W3C XBC group XML Binary
Characterization [XBC
Characterization].
The encoding is schema "informed", meaning that it can leverage available
schema information to improve compactness and performance, but does not
depend on accurate, complete or current schemas to work. It will work very
effectively with partial schemas or no schemas at all. It also supports
arbitrary schema
extensions and deviations and allows dynamic schema negotiation,
discovery and acquisition.
Efficient XML achieves broad generality, flexibility, and performance, by
unifying concepts from formal language theory and information theory into a
single, relatively simple algorithm. The algorithm uses a grammar to
determine what is likely to occur in an XML document and encodes the most
likely alternatives in fewer bits. The fully generalized algorithm works for
any language that can be described by a grammar (e.g., XML, Java, HTTP,
etc.); however, Efficient XML is optimized specifically for XML languages.
The built-in Efficient XML grammar accepts any XML document or XML fragment
and may be augmented with productions derived from XML Schemas, RelaxNG
schemas, DTDs or other sources of information about what is likely to occur
in a set of XML documents. The Efficient XML encoder uses the grammar to map
a stream of XML information items onto a smaller, lower entropy, stream of
tokens. The encoder then encodes the stream of tokens using a Huffman tree
derived from the grammar or, if additional compression is desired, passes the
stream of tokens to a more sophisticated XML compression algorithm that
replaces frequently occurring token patterns to further reduce size. When
schemas are used, Efficient XML also supports a user-customizable set of
datatype CODECs for efficiently encoding typed values and provides typed
streaming APIs for efficiently accessing typed values.
The binary form of Efficient XML is very compact. It is competitive with
hand-optimized formats and is consistently smaller than both ASN.1 PER and
gzipped XML. Even on very large, repetitive documents where gzip works best,
it is not uncommon for Efficient XML to be 2-5 times smaller than gzipped
XML.
Production implementations of Efficient XML have been integrated into a
broad range of platforms, including mass market mobile phones, PDAs,
application servers, web servers, high-volume message routers, pub-sub
systems, vehicles, aircraft, and satellite broadcast systems. High quality,
commercial implementations are available for Unix, MS-Windows and a wide
variety of mobile devices running both Java and Microsoft.NET.
See Theory, Benefits and Requirements for Efficient Encoding of XML
Documents [EffXML] for more
information.
5.7.1. Caveats
The Efficient XML implementation used for W3C tests is a non-production
implementation designated for evaluating W3C-proposed changes to Efficient
XML. In addition to implementing the minimum W3C requirements, it includes
the format features required to support advanced requirements, such as random
access, accelerated sequential access and digital signatures. As a
non-production version it has not been fully optimized.
5.8. X.694 ASN.1 with PER + Fast Infoset
This uses both "X.694 with PER" as described above as well as "Fast
Infoset" also described above. Where there is an XML Schema, X.694 is used to
map the schema to ASN.1. If there is no schema, or if the XML Document
deviates from the schema, the entire XML document is serialized using Fast
Infoset instead.
Note that in general better performance will be gained if there is a
schema from which the documents do not deviate (in which case PER will be
used). Any exceptions to this will be handled by Fast Infoset.
5.9. Efficiency Structured XML (esXML)
Efficiency Structured XML (esXML) is a format that encodes the XML data
model in a way that is flexible, compact, and efficient to process. The
format allows a range of encoding methods, from purely byte-oriented
tokenized data to bit-oriented, variable-token table-based encoding and from
fully self-contained instances to a spectrum of externalized forms, such as
schema-based encoding. This externalized information, which can include
metadata, value typing and table priming, structure, templates, and encoding
choices is encoded in the esXML format in an XML Meta Structure (XMS)
instance. (A template is a range of XML data that is referred to later in a
document so that its structure is copied, with or without data, as a
reference with new data slotted.) An XMS instance can be created from one or
more schemas, example data, or any other process. The XMS instance captures
any information externalized from a logical document and, along with esXML
instances created relative to it, can be used to recreate the fully
self-contained logical data. The important distinction for an XMS is that it
is a directly-interpretable, portable, and standardized representation of
schema-like information that can be shared at run time between disparate
implementations and used to both encode and decode application data. This
avoids sharing schemas, compiling them into usable form, and even agreeing on
a common schema language. This also allows for automated choice of encoding
options.
Certain widely-useful semantics are part of esXML which could be layered
on XML only in inefficient fashion. These semantics allow for stable pointers
to data in an instance, copy-on-write layering of arbitrary changes to a base
document at both high and low levels, and flexible indexing of element
content. These mechanisms can be used for efficiently capturing changes in a
delta instance, for direct efficient representation of any data structure,
such as a graph, and for random access into an instance. Indexing can be both
deep and shallow, hash or sorted, and can occur at any element.
Encoding of data types is flexible, supporting not only text-based values,
but opportunistic and schema-informed binary encoding of scalar types,
including IEEE floats, doubles, and quads. The two major byte orders are
allowed, reader makes right, with only a bit indicating the default order for
the document. A unique restricted character set encoding with escapes allows
taking advantage of narrow use of character values even in the presence of
occasional exceptions. Binary data is encoded directly if indicated by the
schema or library hints from the application. An encapsulation token allows
any element subtree to be individually compressed, signed, or encrypted
without affecting the data model.
The structure of an esXML instance is encoded in either of two modes: byte
oriented or bit oriented. The byte oriented mode uses a compact token, which
is either 4 bits + ID, 8 bits, or 8 bits + argument, and lengths that are
encoded in an variable-length integer, called a "Scalable Int", which is byte
by byte continued with the 8th bit. The bit-oriented encoding can be thought
of as a table-based encoding of byte sequences which are tokens, IDs, and
lengths. In other words, the sequence "Element, ID=8, Length=13" which would
take 2 bytes in byte oriented mode, might take 2 bits in bit-oriented mode.
Because esXML has a major requirement to support in-place accessing of
data, whether for random access or simply to reduce copies when traversing an
instance, aligned byte-oriented operation is desired whenever possible. An
example of this might be a series of byte-sized character strings or a large
array of IEEE floats. A key insight is that bit-oriented and byte-oriented
encoding can be combined in the same instance. While this is sometimes done
with padding before every byte-sized value, this is inefficient and often
seriously detracts from the bit-oriented space savings. EsXML now uses a
Hybrid Byte-Aligned Format (HBAF) which is a simple, low-level mechanism in
the memory access layer to pack bit-aligned data while aligning byte-sized
data. This mechanism can be tuned so that very little buffering is required:
128 bytes would yield almost no overhead compared to fully bit-packing all
data. HBAF simply maintains two output pointers, gliding bit-sized data to
holes before recent byte-sized data until a pointer spread distance is
reached, at which point the rest of the remaining hole becomes padding. This
method could also be used for word aligning scalars if desired.
Because XML instances often vary in schema and characteristic, often
distinguished by an envelope and content elements from differing
specifications, esXML supports the use of multiple XMS instances, created
from different schemas perhaps, and mode switching at each element when
desired. This allows an envelope to be processed most efficiently while a
content element might be most compressed relative to an XMS instance.
EsXML supports both start/stop token indication and length-prefixed data
as there are instances where each can be more efficient in terms of space,
buffering, and processing efficiency. In particular, higher-level elements in
a large document can be length prefixed to facilitate rapidly skipping
through data. To allow such length prefixing to be done without arbitrary
buffering requirements, a continuation token was invented that allows length
prefixing to be chunked in an efficient manner. The continuation token
indicates which level of the XML tree is being continued in the next chunk of
data.
EsXML was created with respect to many requirements that became those of
the W3C XBC and EXI working groups. Additional requirements to directly
support certain ranges of important application architectures indicate the
need for pointers, deltas, random access, and, in some cases, random
modification. EsXML addresses this full set of requirements by the optional
addition of a Storage Layer format, in addition to the Representation Layer
format described above. This Storage Layer, using a structure called "Elastic
Memory", directly supports efficient processing of pointers, low level deltas
(i.e. byte/bit oriented ranges), and random modification (inserts, deletes,
replacement) in a way that allows an application stack to avoid parsing and
serialization.
See The esXML Specification [ESXML]
for more information.
5.9.1. Caveats
The tested version of esXML does not implement schema-informed encoding,
has dropped tests for a couple files, and is producing copious debugging
information which drastically affects processing efficiency. The version
tested operates only in byte-oriented mode, not the more compact bit-oriented
compact form. No XMS, templates, or restricted character sets are turned on.
5.10. Self-Assessment
The XBC Characterization
document specifies the set of minimum requirements a format must satisfy
to meet W3C requirements. The chart below lists all of the candidates
reviewed here in the EXI measurements document and shows which requirements
each claims to satisfy. Each candidate name also links to a more detailed
discussion on the table entries for that candidate. It is important to note
that at this points the assessment has been performed by the candidate
submitters themselves.
The XML+gzip candidate in the below table is built from technologies available currently, which means XML that is compressed with gzip when the use case allows document analysis. The candidate assessments are made on the basis of each candidate's encoding, plus generic compression, or a format specific compression scheme if the candidate has one. An example of the later for instance, is Efficient XML, which implements integrated schema-analysis and document analysis.
| Status |
| Format |
XML + gzip |
Fast Infoset |
FXDI (Fujitsu Binary) |
Efficient XML |
Xebu |
X.694 with BER |
X.694 with PER |
X.694 with PER +
Fast Infoset |
esXML |
| Passes min. bar? |
No |
No |
No |
Yes |
No |
No |
No |
Yes |
No |
| MUST Support |
| Format |
XML + gzip |
Fast Infoset |
FXDI (Fujitsu Binary) |
Efficient XML |
Xebu |
X.694 with BER |
X.694 with PER |
X.694 with PER +
Fast Infoset |
esXML |
| Directly Readable & Writable |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
| Transport Independence |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
| Compactness |
No |
No |
Yes |
Yes |
No |
No |
Yes |
Yes |
No |
| Human Language Neutral |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
| Platform Neutrality |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
| Integratable into XML Stack |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
| Royalty Free |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
| Fragmentable |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
No |
Yes |
Yes |
| Streamable |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
No |
Yes |
Yes |
| Roundtrip Support |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
| Generality |
No |
No |
Yes |
Yes |
No |
No |
No |
Yes |
No |
| Schema Extensions and Deviations |
Yes |
Yes |
Yes |
Yes |
Yes |
No |
No |
Yes |
Yes |
| Format Version Identifier |
Yes |
Yes |
No |
Yes |
No |
No |
No |
Yes |
Yes |
| Content Type Management |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
Yes |
| Self-Contained |
Yes |
Yes |
Yes |
Yes |
Yes |
No |
No |
Yes |
Yes |
| MUST NOT Prevent (DNP =
Does Not Prevent; P = Prevents) |
| Format |
XML + gzip |
Fast Infoset |
FXDI (Fujitsu Binary) |
Efficient XML |
Xebu |
X.694 with BER |
X.694 with PER |
X.694 with PER +
Fast Infoset |
esXML |
| Processing Efficiency |
P |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
| Small Footprint |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
| Widespread Adoption |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
| Space Efficiency |
P |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
| Implementation Cost |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
| Forward Compatibility |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
DNP |
Of the candidates reviewed in this draft, two claim to satisfy all the
minimum W3C requirements. While any of the formats above could form the basis
for a W3C standard, it must be noted that those that satisfy fewer
constraints would likely require more modifications than those that already
meet the minimum W3C requirements.
Each modification to a format will impact the processing efficiency of the
format and may also impact other characteristics, such as compactness. For
example, it is possible (but not necessary) that modifications required to
meet the W3C compactness requirements may significantly reduce processing
efficiency and modifications required to improve processing efficiency may
impact compactness. As such, the performance characteristics of each
candidate presented in this table that does not meet all requirements
illustrate what is possible when certain W3C requirements are not met, but do
not illustrate the performance of a format based that candidate modified to
comply to the W3C requirements.
It must therefore be noted that analysis of candidates should take into
account whether candidates meet all or a subset of the W3C requirements.
6. Summary and Analysis of Test Results
The full analysis of the results, being quite long, has been placed in Appendix A: Measurement Details. This section provides
a summary of those results.
These summaries focus on the level of complete content density clusters
and use groups, as such level of detail was considered more appropriate when
the intent is not to provide all the details. It must be noted, though, that
there can be variation in performance also inside such groups, and therefore
a full consideration of the performance must consider the detailed analysis
as well.
6.1. Compactness
While Compactness is defined as a "binary" property, that each format either
has or does not have, this is typically insufficient information for
application. Therefore, it is also necessary to analyze the precise
Compactness results as measured in the framework.
6.1.1. Analysis Based on the XBC Compaction Metrics in the
Various Classes
To begin with, the XBC Characterization
Measurement Methodologies Note defines thresholds for whether a candidate
format achieves sufficient compactness for each of the application classes identified above.
- Neither
- All candidates can be said to achieve sufficient compactness
consistently across the full test suite. A major exception is the
LocationSightings group for which Xebu, FXDI, and esXML all fail for
all documents. Other failure cases are FixML partially for Xebu and
esXML and the Seismic group for all candidates. The latter is explained
by the single document in that group consisting nearly completely of
floating-point values; without document analysis or schema information
there is little that a format can do.
- Document
- Apart from a few isolated cases, candidate Xebu does not achieve
sufficient compactness for any documents in the test suite. Of the
others, both Fast Infoset and esXML have trouble passing the bar on
many smaller documents, but achieve it consistently for larger
documents. FXDI and Efficient XML do better, with the exception of the
FixML documents (all for FXDI, some for Efficient XML), and some
scientific data for FXDI and the Google test group for Efficient XML.
- Schema
- By definition, ASN.1 PER achieves sufficient
compactness for all documents. Both FXDI and Efficient XML achieve
sufficient compactness in most cases. Apart from a single DataStore
document, Efficient XML passes the compactness bar in all cases. FXDI
additionally misses the compactness bar for some of the ASMTF documents
as well as for one SVG document for which ASN.1
PER performs much
better than for other SVG documents.
- Both
- Sufficient compactness in the Both class is defined as having
sufficient compactness in both the Document and Schema classes.
Therefore there is no separate analysis.
6.1.2. Compactness Summary
The compaction results between candidates are very consistent across the
whole test suite. Efficient XML emerges as the best performer for nearly all
test documents in all application classes. FXDI is, due to its ability to
leverage a schema efficiently, the clear second, when considering all
application classes. Fast Infoset is close to FXDI in the classes that do not
leverage a schema, but especially for the cases where a good schema is
available, Fast Infoset does not come close to the performance of the other
two.
Considering the best candidates and their performance in each use group
reveals that the largest benefits, when schema and document analysis are not
options, come in the Military, Scientific, and Storage groups. Of these
groups, only Military has useful schemas for the majority of its test
documents, and the results show that schema usage would appear to improve the
results even further.
When only document analysis is applicable, the general trend in
performance is approximately equal to or slightly higher than gzipped XML.
Best overall results are in the Document and Storage use groups, with
Finance and
Scientific also getting significantly better performance than gzipped XML.
As can be expected, combined schema usage and document analysis has a
benefit only in cases where good schemas are available. The
best examples of this are provided by the Military and Finance
use groups where the best candidates demonstrate a consistent
manyfold improvement in compression compared to gzipped XML.
Naturally, when good schemas are not available, there is no
significant effect compared to document analysis alone.
The content density clusters tell a slightly different story. The
elimination of the high CD documents shows that the candidates perform very
well compared to plain XML when the documents have much more structure than
content. Schema usage provides a clear benefit especially in the
Low-Tiny and Low-Small clusters when good schemas are
available. On the larger documents of the Low-Large cluster
and the less structured ones of the High cluster, the effect
is much less noticeable.
Considering the average performance of the two primary candidates, FXDI
and Efficient XML, that achieve sufficient compactness in all
application classes, we can note from the summary tables that FXDI has a
compactification rate of approximately 60% in the Neither class that
increases to 70% when schema usage is permitted. For Efficient XML, these
numbers are, respectively, nearly 70% and 80%. In the Document and Both
cases, FXDI does not perform appreciably better than gzipped XML, but
Efficient XML achieves a further 10% compactification over gzip in the Both case.
6.2. Processing Efficiency
A summary of the results will be given here for the speed of processing,
for each format, in each of the aggregations.
6.2.1. Processing Efficiency Summary
Processing efficiency results were not nearly as uniform as the compaction
results. This is to be expected, as processing efficiency is much more
dependent on implementation aspects, as well as the testing framework and its
environment. However, it was possible to distinguish the three candidates
FXDI, Fast Infoset, and Efficient XML as usually taking the top spots in
performance, even though there is no clear winner. However, the document
analysis performed by Efficient XML is clearly faster than that of the other
candidates, both encoding and decoding.
In encoding, the overall best reliable results would seem to be achieved
in the Finance, Military, and Storage use groups. The performance of document
analysis is here clearly better than that of gzipped XML, though not as much
as in the cases without document analysis. Schema usage does not appear to
have a significant general effect on performance. Interestingly, performance
of the candidates seems to be comparatively better in the High content
density cluster than in the Low clusters.
In decoding, the Finance, Military, and Storage use groups again
demonstrate the best performance. Document analysis would seem to be
comparatively more efficient than in the encoding case, for all of the best
candidates. Schema usage seems to improve the performance of both FXDI and
Efficient XML. Again, the High content density cluster would seem to enjoy
better performance than the Low clusters, though the difference is not as
pronounced as in the encoding case, and is non-existent for some candidates
and Low clusters.
Considering the average performance of the two primary candidates, FXDI
and Efficient XML, that achieve sufficient compactness in all
application classes, we can note from the summary tables that in the Neither class,
FXDI achieves a 50% improvement in encoding and a 160% improvement in
decoding over the baseline. The same numbers for Efficient XML are 40% and
180%. Schema usage lowers these numbers slightly, and Document analysis more.
With Document analysis, FXDI is only 20% faster and Efficient XML is 10%
slower when encoding, but in decoding FXDI is 110% faster and Efficient XML
70% faster.
6.3. Roundtrip Support
To measure the property Roundtrip
Support, the framework uses a contributed XML differencing tool [Faxma]. After a compaction run, the candidate-produced
result is parsed with the candidate's decoder, and the result of this parsing
is compared with the result of parsing the original XML document. This
differencing process supports all the fidelity
options, ignoring data that does not need to be preserved in each test
group.
The results of the fidelity testing are that the candidates Xebu, FXDI,
Fast Infoset, and Efficient XML all pass in all application classes. The
framework does not yet support difference computation for C-based candidates,
and no successful differencing run has yet been made with esXML.
7. Conclusions
The results of the measurements allow us to draw several conclusions relating
to the viability of a general-purpose format. Conclusions regarding individual
properties are summarized above, but to determine the viability of a format
it is necessary to examine the properties in combination.
One conclusion that can be drawn is that neither Compactness nor
Processing Efficiency on its own is sufficient. Good Processing Efficiency
helps only up to the point where the CPU is the application bottleneck, as
shown by the network measurements. On the other hand, additional Compactness
is usually available by spending more processing time, but this is not
acceptable in many use cases.
Considering XML as an encoding of the XML Information Set, the
results demonstrate that it is possible for an alternate
format to achieve significant improvements in
both Processing Efficiency and Compactness simultaneously.
Therefore, even though sometimes one property can be traded for
the other, as illustrated by comparing the Neither and
Document classes, this does not mean that XML itself is
optimal in either property.
Another point to note is that there is little variation in each
candidate's performance across the use cases. This demonstrates that none of
the candidates is an application-specific format, but rather designed for
general-purpose XML use.
To summarize, the results indicate that it is possible to achieve
substantial gains over XML, for both examined properties simultaneously, and in a
wide variety of use cases. This demonstrates the general viability of the
alternate serialization concept.
Based on examining the format specifications and the results of these
measurements, the group selected Efficient XML as the basis for development
of the Efficient XML Interchange format. Some individual features from other
formats were also deemed sufficiently integrable into the Efficient XML
structure encoding that their inclusion will be considered. This further
consideration will be based on implementation cost as well
as further measurements of their effectiveness.
8. Bibliography
- [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/.
- [Screamer]
- XML
Screamer: An Integrated Approach to High Performance XML Parsing,
Validation and Deserialization, Margaret G. Kostoulas et al,
proceedings of the 15th International World Wide Web Conference, May
2006. http://www2006.org/programme/item.php?id=5011.
- [MTOM]
- SOAP Message
Transmission Optimization Mechanism, Martin Gudgin, Noah
Mendelsohn, Mark Nottingham, Hervé Ruellan editors, World Wide Web
Consortium, January 2005. Latest version
http://www.w3.org/TR/soap12-mtom/.
- [XOP]
- XML-binary
Optimized Packaging, Martin Gudgin, Noah Mendelsohn, Mark
Nottingham, Hervé Ruellan editors, World Wide Web Consortium, January
2005. Latest version http://www.w3.org/TR/xop10/.
- [WSRF]
- Web Services Resource
Framework (WSRF), Globus Alliance, OASIS,
April 2006.
- [Engelen]
- Pushing the
SOAP Envelope With Web Services for Scientific Computing.
Robert van Engelen, ICWS 2003.
- [gSOAP]
- The gSOAP
Toolkit for Web Services and Peer-To-Peer Computing
Networks. Robert van Engelen, Kyle A. Galliva. Proceedings
of the 2nd International Symposium on Cluster Computing and the GRID,
2002.
- [Chiu]
- Investigating
the Limits of SOAP Performance for Scientific Computing. K.
Chiu, M. Govindaraju, and R. Bramley. Proceedings
of 11th HPDC, pp 246-254. July 2002.
- [NUX]
- NUX - Efficient and Powerful
XML Processing Made Easy. Distributed Systems Department, Lawrence
Berkeley National Laboratory. http://dsd.lbl.gov/nux/
- [BXML]
- BXML-CWXML Home
page. CubeWerx. http://www.cubewerx.com/main/cwxml/.
- [Abu-Ghazaleh]
- Differential
Serialization for Optimized SOAP Performance, Nayef
Abu-Ghazaleh, Michael J. Lewis, Madhusudhan Govindaraju. Proceedings of
the 13th HPDC, pp 55-64, June 2004. Describes bSOAP.
- [Abu-Ghazaleh2]
- Differential
Deserialization for Optimized SOAP Performance, Nayef
Abu-Ghazaleh, Michael J. Lewis. Proceedings of the 2005 ACM/IEEE
Conference on Supercomputing.
- [ChiuLu]
- A
Compiler-Based Approach to Schema-Specific XML Parsing,
Kenneth Chiu, Wei Lu. Proceedings of the First International Workshop
on High Performance XML Processing, 2004.
- [EngelenAutomata]
- Constructing Finite
State Automata for High Performance Web Services, Robert van
Engelen, 2004.
- [Takase]
- An Adaptive,
Fast, and Safe XML Parser Based on Byte Sequences
Memorization, Toshiro Takase et al. Proceedings of the 14th
International World Wide Web Conference, 2005.
- [EngelenGSOAP]
- Code
Generation Techniques for Developing Light-Weight XML Web Services for
Embedded Devices, Robert van Engelen. Proceedings of the ACM
Symposium on Applied Computing, 2004.
- [BXSA]
- A Binary
XML for Scientific Applications. Kenneth Chiu, Tharaka
Devadithya, Wei Lu, Aleksander Slominski.
- [DET-COMPLEXITY]
- Determining
the Complexity of XML Documents, Mustafa H. Qureshi, M. H.
Samadzadeh, ITCC'05.
http://ieeexplore.ieee.org/iel5/9755/30769/01425179.pdf (complete article requires IEEE login).
- [USE-OF-ASN.1]
- The Use
of ASN.1 Encoding Rules for Binary XML, Ed Day, Objective System Inc.,
http://www.obj-sys.com/docs/ASN1forBinXML.pdf.
- [ASN.1]
- Information
technology — Abstract Syntax Notation One (ASN.1): Specification
of Basic Notation [The ASN.1 Standard (ITU-T Rec. X.680)],
International Telecommunication Union (ITU), July 2002.
http://www.itu.int/ITU-T/studygroups/com17/languages/X.680-0207.pdf.
- [BER]
- Information
technology — ASN.1 encoding rules: Specification of Basic
Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished
Encoding Rules (DER) [The ASN.1 BER Standard (ITU-T Rec
X.690)], International Telecommunication Union (ITU), July 2002.
http://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf.
- [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.
- [X.694]
- Information
technology — ASN.1 encoding rules: Mapping W3C XML schema
definitions into ASN.1 [ITU-T Rec X.694], International
Telecommunication Union (ITU), January 2004.
http://www.itu.int/ITU-T/studygroups/com17/languages/X694.pdf.
- [X.693]
- Information
technology — ASN.1 encoding rules: XML Encoding Rules
(XER) [ITU-T Rec X.693], International Telecommunication
Union (ITU), December 2001.
http://www.itu.int/ITU-T/studygroups/com17/languages/X.693-0112.pdf.
This work is also standardized by ISO/IEC 8825-4 (with Amendment
1).
- [FAXMA]
- Fast and
Simple XML Tree Differencing by Sequence Alignment,
Tancred Lindholm, Jaakko Kangasharju, and Sasu
Tarkoma. In ACM Symposium on Document Engineering, October
2006.
- [XEBU1]
- Xebu: A
Binary Format with Schema-based Optimizations for XML
Data, Jaakko
Kangasharju, Sasu Tarkoma,
and Tancred
Lindholm. In 6th International
Conference on Web Information Systems Engineering, Lecture Notes in Computer Science 3806, Springer-Verlag, November
2005. http://dx.doi.org/10.1007/11581062_44.
- [XML Signature]
- XML-Signature
Syntax and Processing, Donald Eastlake, Joseph Reagle, David
Solo editors, World Wide Web Consortium, 12 February 2002. Latest
version http://www.w3.org/TR/xmldsig-core/.
- [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/.
- [XML Infoset]
- XML
Information Set, John Cowan, Richard Tobin editors, World
Wide Web Consortium, 4 February 2004 (Second Ed). Latest version
http://www.w3.org/TR/xml-infoset/.
- [FI]
- ITU-T Rec. X.891
| ISO/IEC 24824-1 (Fast Infoset), International
Telecommunication Union (ITU), May 2005.
http://www.itu.int/rec/T-REC-X.891/.
- [EffXML]
- Theory,
Benefits and Requirements for Efficient Encoding of XML
Documents, AgileDelta, Inc.
http://www.agiledelta.com/EfficientXMLEncoding.htm.
- [ESXML]
- The esXML
Specification, Stephen D. Williams, January 2006.
- [JAPEX]
- Japex
Manual, Santiago Pericas-Geertsen, java.net, April 2006.
https://japex.dev.java.net/docs/manual.html.
- [CN]
- HTTP/1.1
Content Negotiation, R. Fielding et al, World Wide Web
Consortium, June 1999.
http://www.w3.org/Protocols/rfc2616/rfc2616.html.
- [FXDI]
- W3C
EXI WG and Fujitsu, Takuki Kamiya, Fujitsu, June 2006.
http://software.fujitsu.com/en/interstage-xwand/activity/xbrltools/indexFXDI.html.
9. Appendices
9.1. Appendix A: Measurement Details
The complete measurement reports are available at http://www.w3.org/XML/EXI/test-report.
This includes the full Japex reports, in both HTML and XML formats, as well
as graphs that were used in the detailed analysis below. It will also include
new measurements and updates of existing measurements as those are prepared
and deemed stable by the group.
9.1.1. Methods of Detailed Analysis
The detailed analysis below consists of three different parts for each
specific property (and, in the case of Processing Efficiency, for each data
source or sink). Summary information is given in the form of graphs showing
all candidates for all documents, and by estimating the average ratio of
performance of a candidate over the baseline. Detailed consideration is given
to each use group and content density cluster as text, highlighting the
best-performing candidates and the approximate range of their performance
compared to the baseline. Due to time constraints, detailed text is not
provided for all cases, though the detailed graphs used are still provided at
the above link.
<IP_ADDRESS>. Graphical Representation
A graph is a common way to summarize measurement data. The graphs below
show the performance of the candidates across the full set of test documents.
Each application class is shown in its own graph. The performance is shown as
a ratio to XML (this includes the Document and Both graphs where gzipped XML
is also shown as a ratio to uncompressed XML), and the test documents are
sorted in the order of the XML result. It is worth noting that the orders in
the Compactness and Processing Efficiency graphs do not have a direct
correspondence, as size is not the sole determinant of speed in XML
processing, even though there is a strong correlation.
As the test data encompasses a wide scale of different sizes, the X axis
in all the graphs is logarithmic. The Y axis is also logarithmic, to make it
easier to estimate the relative performance of two candidates; estimating the
relative performance of a candidate to XML is already taken care of by using
ratios instead of the actual measurement results. It is worthwhile to
note that the test suite
composition is somewhat skewed towards smaller documents,
so equal portions of the X axis do not always correspond to
equal numbers of test documents.
In some cases the candidate failed to produce a result altogether or
produced only a partial result (e.g., encoding a document failed after some
output had already been produced). The actual failures are reported by Japex
as N/A, so they are simple to recognize. The other case is handled by
reviewing the results, taking note of anomalously good performance, and then
investigating whether the produced result is credible. A failure in these
cases is declared for only the truly exceptional results that cannot be
explained, i.e., it was felt better to err on the side of the caution. No
matter how the failure was detected, all failed results are normalized in the
graphs to the baseline, that is, the level of XML, which gives the resulting
ratio of 1.
<IP_ADDRESS>. Tabular Representation
Another way to summarize the data is to aggregate the measurement results
into a single figure of merit. As noted in 4.7. Analysis Methodology, producing a
single figure of merit for the complete set of measurements is not feasible.
Rather, it was determined to approximate the performance of the candidates
for each application class in each use group and content density cluster. As
the percentage of compaction achieved by generic compression typically
increases with increasing document size, the baseline for the Document and
Both classes was selected to be gzipped XML in both Compactness and
Processing Efficiency. Similarly, to get a comparison to the best
performance, the decoding baseline was selected to be Xals, or gzipped Xals
in the Document and Both classes.
The method of approximation is based on the assumption that the
performance ratio of a candidate over XML is constant inside each use group
and content density cluster for a particular application class. Therefore, by
plotting the measurements in an (XML,candidate) coordinate system the
resulting plot should be approximatable by a straight line, which can be
obtained through a straightforward linear regression analysis. The slope of
this line then gives the ratio of performance of the candidate over XML.
Unlike in the case with graphs, where unavailable or incorrect results were
normalized, in this case they were dropped, and if this led to having too few
data points for the candidate, the whole group was dropped for that
candidate. For clarity, all tables were constructed so that a higher ratio
means better performance from the candidate. Each table cell for a
candidate-group pair contains four slopes, for each of the four application
classes. There are arranged so that the top row is Neither-Document and the
bottom row is Schema-Both. In the case of ASN.1 PER, there is only the
Schema-Both row.
In addition to performing this analysis for the use groups and content
density clusters, the same process was also followed for the complete test
suite, the results of which are reported as All in the
tables. Even though, as noted above, a single number cannot be used to
completely characterize a candidate's performance, the result produced for
the All group can act as a rough average for the candidate over the whole
test suite. It must, however, be kept in mind that the whole test suite may
have biases affecting this result, and these potential biases are not yet
fully understood.
As the approximation is not exact, the computed ratios are shown as 95%
confidence intervals. These were computed in the standard manner, that is, if
μ is the computed slope and σ its estimated standard deviation, the
95% confidence interval is then [μ - t(0.975)*σ, μ +
t(0.975)*σ] where t stands for the t distribution with the appropriate
number of degrees of freedom. Use of the t distribution is indicated as the
number of measurements in each group is small. A consequence of using
confidence intervals is that if the intervals of two candidates do not
overlap, it can be concluded that there is a statistically significant
difference in the performance of the candidates. However, if the intervals do
overlap, the opposite conclusion cannot be drawn without additional
statistical tests.
The precise meaning of these figures can be interpreted in many ways. One
way is to begin with the assumption that each group is sufficiently
homogeneous that candidate performance for any document in the group, when
compared to XML, will be approximately equal. Then, there will be a single
number that gives the ratio of the candidate's performance for that group. As
the documents in the groups form a subset of all potential documents, any
value gained from the measurements will be an approximation of this "true"
value. The confidence intervals therefore indicate that we can be 95%
confident that the true value is contained within the given interval.
9.1.2. Compaction Analysis Details
<IP_ADDRESS>. Tabular and Graphical
Representation of Compaction Results
See Graphical Representation on
how to interpret these graphs.
The graphs contain a large amount of information and therefore it is not
trivial to extract information out of them. One point that does leap out is
that Efficient XML, in most cases, has a clear advantage over the others in
the Neither and Schema classes. In the Document class all candidates are very
close to each other and to gzipped XML, though again Efficient XML has better
performance in some cases. The graphs in the Both class have mostly a similar
shape to the Document class, though both FXDI and Efficient XML do much
better for the smaller documents, and for some isolated larger ones.
Note that these runs were made at a time when ASN.1 BER was not yet
producing stable results, so it is completely excluded. Similarly, the two
candidates based on ASN.1 PER were not producing correct results in the Both
class, so they are excluded from that graph.
Making the assumption that the test data is a uniform collection over the
relevant use cases, another beneficial view would be to order the X axis not
by size but simply by document, giving each document equal representation in
the graph. In this case, ordering the documents by the best compactness
result achieved by a candidate offers an alternative picture of the overall
performance of the candidates.
See Tabular Representation on how
to interpret the following table.
There are very few oddities in the compaction ratios, and mostly the
confidence intervals appear to be reasonably tight, indicating that at least
some of these numbers are potentially useful metrics. However, it is prudent
to keep in mind the method of arriving at these numbers. For reasonably
homogeneous groups that are well represented through the sizes, such as the
Low CD clusters and the Scientific
and Finance use groups, these numbers would be expected to provide an
accurate representation of the average behavior. On the other hand, for
groups such as the Sensor use group that has a very large scale of document
sizes and few documents in between the extremes, these numbers may be less
useful as a basis for decisions.
| Compaction Summary |
| Group |
PER |
PER+FI |
Xebu |
FXDI |
FI |
EFX |
esXML |
Group |
| High |
|
|
| [ 0.71, 0.81 ] |
[ 0.35, 0.35 ] |
|
| [ 0.96, 1.06 ] |
[ 0.99, 1.00 ] |
| [ 0.71, 0.81 ] |
[ 0.35, 0.35 ] |
|
| [ 0.96, 1.05 ] |
[ 0.99, 0.99 ] |
| [ 0.96, 1.05 ] |
[ 0.99, 0.99 ] |
|
| [ 0.96, 1.06 ] |
[ 1.00, 1.01 ] |
| [ 1.86, 1.93 ] |
[ 1.05, 1.06 ] |
|
| [ 0.96, 1.05 ] |
[ 0.99, 1.00 ] |
| [ 0.96, 1.05 ] |
[ 0.99, 1.00 ] |
|
| [ 0.95, 1.06 ] |
[ 0.98, 1.02 ] |
| [ 2.26, 2.42 ] |
[ 1.09, 1.12 ] |
|
| [ 0.96, 1.05 ] |
[ 0.99, 1.00 ] |
| [ 0.96, 1.05 ] |
[ 0.99, 1.00 ] |
|
High |
| Low-large |
|
|
| [ 3.02, 3.80 ] |
[ 0.07, 0.10 ] |
|
| [ 3.98, 4.69 ] |
[ 1.11, 1.27 ] |
| [ 3.05, 3.83 ] |
[ 0.07, 0.10 ] |
|
| [ 2.40, 3.00 ] |
[ 0.65, 0.76 ] |
| [ 2.40, 3.00 ] |
[ 0.65, 0.76 ] |
|
| [ 2.87, 3.64 ] |
[ 0.86, 1.03 ] |
| [ 2.87, 3.90 ] |
[ 0.89, 1.08 ] |
|
| [ 2.57, 3.35 ] |
[ 1.04, 1.17 ] |
| [ 2.53, 3.25 ] |
[ 1.01, 1.17 ] |
|
| [ 4.73, 5.93 ] |
[ 1.25, 1.47 ] |
| [ 4.75, 5.95 ] |
[ 1.32, 1.52 ] |
|
| [ 2.09, 2.80 ] |
[ 1.01, 1.16 ] |
| [ 2.09, 2.80 ] |
[ 1.01, 1.16 ] |
|
Low-large |
| Low-small |
|
|
| [ 0.55, 1.19 ] |
[ -0.01, 0.08 ] |
|
| [ 3.32, 5.14 ] |
[ 0.99, 1.06 ] |
| [ 0.68, 1.22 ] |
[ 0.00, 0.09 ] |
|
| [ 3.05, 4.12 ] |
[ 0.79, 0.85 ] |
| [ 3.10, 4.20 ] |
[ 0.80, 0.88 ] |
|
| [ 3.03, 3.68 ] |
[ 0.96, 1.07 ] |
| [ 3.59, 5.14 ] |
[ 1.01, 1.27 ] |
|
| [ 3.23, 4.71 ] |
[ 0.96, 1.04 ] |
| [ 3.35, 4.69 ] |
[ 0.94, 1.11 ] |
|
| [ 3.72, 6.49 ] |
[ 1.05, 1.23 ] |
| [ 3.67, 7.52 ] |
[ 1.04, 1.35 ] |
|
| [ 3.21, 4.05 ] |
[ 0.93, 1.03 ] |
| [ 3.21, 4.05 ] |
[ 0.93, 1.03 ] |
|
Low-small |
| Low-tiny |
|
|
| [ 0.61, 1.31 ] |
[ 0.13, 0.48 ] |
|
| [ 1.28, 1.90 ] |
[ 0.91, 1.00 ] |
| [ 1.03, 1.58 ] |
[ 0.38, 0.53 ] |
|
| [ 1.32, 1.68 ] |
[ 0.86, 1.02 ] |
| [ 1.27, 1.71 ] |
[ 0.78, 1.01 ] |
|
| [ 1.07, 1.58 ] |
[ 1.04, 1.17 ] |
| [ 0.79, 1.47 ] |
[ 0.65, 1.12 ] |
|
| [ 1.33, 1.97 ] |
[ 0.94, 1.09 ] |
| [ 1.18, 2.01 ] |
[ 0.75, 1.21 ] |
|
| [ 1.56, 2.46 ] |
[ 1.09, 1.29 ] |
| [ 1.23, 2.25 ] |
[ 0.71, 1.23 ] |
|
| [ 1.04, 1.75 ] |
[ 0.90, 1.05 ] |
| [ 1.04, 1.75 ] |
[ 0.90, 1.05 ] |
|
Low-tiny |
| Broadcast |
|
| [ 0.93, 1.67 ] |
[ 0.83, 1.07 ] |
| [ 0.93, 1.67 ] |
[ 0.19, 0.70 ] |
|
| [ 0.86, 1.54 ] |
[ 0.76, 0.92 ] |
| [ 0.74, 1.50 ] |
[ 0.62, 0.86 ] |
|
| [ 1.00, 1.51 ] |
[ 0.91, 1.04 ] |
| [ 0.72, 1.72 ] |
[ 0.58, 1.12 ] |
|
| [ 0.83, 1.69 ] |
[ 0.83, 0.97 ] |
| [ 0.74, 1.63 ] |
[ 0.58, 0.95 ] |
|
| [ 0.89, 1.86 ] |
[ 0.93, 1.04 ] |
| [ 0.71, 1.76 ] |
[ 0.54, 1.14 ] |
|
| [ 0.77, 1.56 ] |
[ 0.82, 0.97 ] |
| [ 0.77, 1.56 ] |
[ 0.82, 0.97 ] |
|
Broadcast |
| Document |
|
|
| [ -0.06, 2.80 ] |
[ 0.26, 0.50 ] |
|
| [ 1.50, 2.60 ] |
[ 1.07, 1.09 ] |
| [ 1.49, 2.60 ] |
[ 0.18, 0.40 ] |
|
| [ 1.31, 2.42 ] |
[ 0.95, 0.97 ] |
| [ 1.31, 2.42 ] |
[ 0.95, 0.97 ] |
|
| [ 1.64, 2.17 ] |
[ 1.10, 1.12 ] |
| [ 1.46, 2.51 ] |
[ 1.09, 1.14 ] |
|
| [ 1.48, 2.49 ] |
[ 1.04, 1.07 ] |
| [ 1.48, 2.49 ] |
[ 1.04, 1.07 ] |
|
| [ 1.44, 2.90 ] |
[ 1.35, 1.51 ] |
| [ 1.48, 2.86 ] |
[ 1.35, 1.50 ] |
|
| [ 1.59, 1.90 ] |
[ 1.04, 1.06 ] |
| [ 1.59, 1.90 ] |
[ 1.04, 1.06 ] |
|
Document |
| Finance |
|
|
| [ 3.37, 3.39 ] |
[ 0.57, 0.57 ] |
|
| [ 2.95, 2.97 ] |
[ 1.06, 1.07 ] |
| [ 3.37, 3.39 ] |
[ 0.57, 0.57 ] |
|
| [ 2.54, 2.55 ] |
[ 0.85, 0.85 ] |
| [ 2.55, 2.56 ] |
[ 0.85, 0.85 ] |
|
| [ 3.12, 3.14 ] |
[ 1.15, 1.15 ] |
| [ 3.95, 3.97 ] |
[ 1.24, 1.25 ] |
|
| [ 2.95, 2.96 ] |
[ 1.06, 1.06 ] |
| [ 2.99, 3.00 ] |
[ 1.06, 1.07 ] |
|
| [ 4.05, 4.07 ] |
[ 1.31, 1.33 ] |
| [ 4.42, 4.45 ] |
[ 1.34, 1.36 ] |
|
| [ 2.87, 2.88 ] |
[ 1.04, 1.05 ] |
| [ 2.87, 2.88 ] |
[ 1.04, 1.05 ] |
|
Finance |
| Military |
|
|
| [ 1.73, 4.09 ] |
[ 0.16, 0.29 ] |
|
| [ 4.07, 4.41 ] |
[ 1.02, 1.23 ] |
| [ 1.73, 4.09 ] |
[ 0.16, 0.29 ] |
|
| [ 3.11, 3.57 ] |
[ 0.58, 0.86 ] |
| [ 3.11, 3.57 ] |
[ 0.58, 0.86 ] |
|
| [ 3.12, 3.55 ] |
[ 0.85, 1.23 ] |
| [ 4.22, 4.88 ] |
[ 0.92, 1.40 ] |
|
| [ 4.07, 4.40 ] |
[ 1.02, 1.22 ] |
| [ 3.49, 4.07 ] |
[ 0.84, 1.28 ] |
|
| [ 4.35, 5.14 ] |
[ 1.16, 1.71 ] |
| [ 6.08, 7.20 ] |
[ 1.32, 2.01 ] |
|
| [ 2.58, 2.97 ] |
[ 0.86, 1.26 ] |
| [ 2.58, 2.97 ] |
[ 0.86, 1.26 ] |
|
Military |
| Scientific |
|
|
| [ 2.99, 3.85 ] |
[ 0.07, 0.10 ] |
|
| [ 3.92, 4.75 ] |
[ 1.12, 1.29 ] |
| [ 2.99, 3.86 ] |
[ 0.07, 0.10 ] |
|
| [ 2.34, 3.06 ] |
[ 0.66, 0.77 ] |
| [ 2.34, 3.06 ] |
[ 0.66, 0.77 ] |
|
| [ 2.80, 3.70 ] |
[ 0.86, 1.05 ] |
| [ 2.77, 3.99 ] |
[ 0.89, 1.10 ] |
|
| [ 2.49, 3.41 ] |
[ 1.04, 1.18 ] |
| [ 2.45, 3.32 ] |
[ 1.04, 1.19 ] |
|
| [ 4.63, 6.05 ] |
[ 1.28, 1.48 ] |
| [ 4.65, 6.05 ] |
[ 1.36, 1.51 ] |
|
| [ 2.02, 2.87 ] |
[ 1.04, 1.17 ] |
| [ 2.02, 2.87 ] |
[ 1.04, 1.17 ] |
|
Scientific |
| Sensor |
|
|
| [ 0.74, 0.76 ] |
[ 0.34, 0.36 ] |
|
| [ 0.96, 1.03 ] |
[ 1.00, 1.00 ] |
| [ 0.72, 0.77 ] |
[ 0.35, 0.35 ] |
|
| [ 0.97, 1.02 ] |
[ 0.99, 0.99 ] |
| [ 0.97, 1.02 ] |