High performance XML parsing using parallel bit stream technology

ABSTRACT

Parabix (parallel bit streams for XML) is an open-source XML parser that employs the SIMD (single-instruction multiple-data) capabilities of modern-day commodity processors to deliver dramatic performance improvements over traditional byte-at-a-time parsing technology. Byte-oriented character data is first transformed to a set of 8 parallel bit streams, each stream comprising one bit per character code unit. Character validation, transcoding and lexical item stream formation are all then carried out in parallel using bitwise logic and shifting operations. Byte-at-a-time scanning loops in the parser are replaced by bit scan loops that can advance by as many as 64 positions with a single instruction.

A performance study comparing Parabix with the open-source Expat and Xerces parsers is carried out using the PAPI toolkit. Total CPU cycle counts, level 2 data cache misses and branch mispredictions are measured and compared for each parser. The performance of Parabix is further studied with a breakdown of the cycle counts across the core components of the parser. Prospects for further performance improvements are also outlined, with a particular emphasis on leveraging the intraregister parallelism of SIMD processing to enable intrachip parallelism on multicore architectures.

REFERENCES

• 1: Performance Application Programming Interface. http://icl.cs.utk.edu/papi/.
• 2: Xerces C++ Parser. http://xerces.apache.org/xerces-c/.
• 3: Cameron, Robert D. u8u16 -- A High-Speed UTF-8 to UTF-16 Transcoder Using Parallel Bit Streams. Technical Report TR 2007-18, Simon Fraser University, Burnaby, BC, Canada, 2007.
• 4: Robert D. Cameron, A case study in SIMD text processing with parallel bit streams: UTF-8 to UTF-16 transcoding, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345222]
• 5: Clark, James. The Expat XML Parser. http://expat.sourceforge.net/.
• 6: DuCharme, Bob. Documents vs. data, schemas vs. schemas. In XML 2004, Washington D.C., 2004.
• 7: Intel Corporation. IA-32 Intel Architecture Optimization Reference Manual, 2005.
• 8: 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]
• 9: Matthias Nicola , Jasmi John, XML parsing: a threat to database performance, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956898]
• 10: Perkins, E., Kostoulas, M., Heifets, A., Matsa, M., and Mendelsohn, N. Performance Analysis of XML APIs. In XML 2005, Atlanta, Georgia, November 2005.
• 11: Pettersson, Michael. Linux x86 Performance-Monitoring Counters Driver. http://user.it.uu.se/mikpe/linux/perfctr.
• 12: Giuseppe Psaila, On the Problem of Coupling Java Algorithms and XML Parsers (Invited Paper), Proceedings of the 17th International Conference on Database and Expert Systems Applications, p.487-491, September 04-08, 2006 [doi>10.1109/DEXA.2006.102]
• 13: Ron Lake , David Burggraf , Milan Trninic , Laurie Rae, Geography Mark-Up Language: Foundation for the Geo-Web, John Wiley & Sons, 2004
• 14: Ross, Kenneth A. Efficient Hash Probes on Modern Processors. In Proceedings of the 23rd International Conference on Data Engineering (ICDE 2007), Istanbul, Turkey, 2007.
• 15: Zhao, Li Laxmi Bhuyan. Performance Evaluation and Acceleration for XML Data Parsing. In 9th Workshop on Computer Architecture Evaluation using Commercial Workloads (CAECW), Austin, Texas, 2006.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Experimentation, Languages, Performance