A high-performance interpretive approach to schema-directed parsing

ABSTRACT

XML delivers key advantages in interoperability due to its flexibility, expressiveness, and platform-neutrality. As XML has become a performance-critical aspect of the next generation of business computing infrastructure, however, it has become increasingly clear that XML parsing often carries a heavy performance penalty, and that current, widely-used parsing technologies are unable to meet the performance demands of an XML-based computing infrastructure. Several efforts have been made to address this performance gap through the use of grammar-based parser generation. While the performance of generated parsers has been significantly improved, adoption of the technology has been hindered by the complexity of compiling and deploying the generated parsers. Through careful analysis of the operations required for parsing and validation, we have devised a set of specialized byte codes, designed for the task of XML parsing and validation. These byte codes are designed to engender the benefits of fine-grained composition of parsing and validation that make existing compiled parsers fast, while being coarse-grained enough to minimize interpreter overhead. This technique of using an interpretive,validating parser balances the need for performance against the requirements of simple tooling and robust scalable infrastructure. Our approach is demonstrated with a specialized schema compiler, used to generate byte codes which in turn drive an interpretive parser. With almost as little tooling and deployment complexity as a traditional interpretive parser, the byte code-driven parser usually demonstrates performance within 20% of the fastest fully compiled solutions.

REFERENCES

• 1: The Apache Foundation. Xerces. http://xml.apache.org.
• 2: R. J. Bayardo , D. Gruhl , V. Josifovski , J. Myllymaki, An evaluation of binary xml encoding optimizations for fast stream based xml processing, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988719]
• 3: K. Chiu and W. Lu. A Compiler-Based Approach to Schema-Specific XML Parsing. In First International Workshop on High Performance XML Processing, May 2004.
• 4: J. Clark. Expat XML parser. http://expat.sourceforge.net/.
• 5: D. C. Fallside and P. Walmsley, editors. XML Schema Part 0: Primer Second Edition. W3C, second edition, Oct 2004. http://www.w3.org/TR/xmlschema-0.
• 6: The GNU Project. Flex. http://www.gnu.org/software/flex/.
• 7: Margaret G. Kostoulas , Morris Matsa , Noah Mendelsohn , Eric Perkins , Abraham Heifets , Martha Mercaldi, XML screamer: an integrated approach to high performance XML parsing, validation and deserialization, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135796]
• 8: J. K. Ousterhout. Tool Command Language. http://www.tcl.tk/
• 9: E. Perkins , M. Matsa , M. G. Kostoulas , A. Heifets , N. Mendelsohn, Generation of efficient parsers through direct compilation of XML schema grammars, IBM Systems Journal, v.45 n.2, p.225-244, January 2006
• 10: F. Reuter and N. Luttenberger. Cardinality constraint automata: A core technology for efficient XML schema-aware parsers. http://www.swarms.de/publications/cca.pdf, 2003.
• 11: Sarvega, Inc. XML Validation Benchmark. http://www.sarvega.com/xml-validation-benchmark.html
• 12: saxproject.org. SAX: Simple API For XML. http://www.saxproject.org/.
• 13: Sun Microsystems, Inc. Java Technology. http://java.sun.com/.
• 14: H. Thomson, D. Beech, M. Maloney, and N. Mendelsohn, editors. XML Schema Part 1: Structures. W3C, second edition, Oct 2004. http://www.w3.org/TR/REC-xmlschema
• 15: R. van Engelen. Constructing Finite State Automata for High-Performance XML Web Services. In International Conference on Internet Computing, 2004.
• 16: L. Wall. Practical Extraction and Report Language. http://www.perl.org/

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Retargetable compilers

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Parsing; Compilers; Optimization

General Terms:
Experimentation, Languages, Performance, Standardization

Keywords:
XML, compiler, interpreter, parsing, performance, schema