EVENT-LEVEL PARALLEL METHODS AND APPARATUS FOR XML PARSING

• US 20110153604A1
• Filed: 12/17/2009
• Published: 06/23/2011
• Est. Priority Date: 12/17/2009
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Wang, Yun, Fang, Yuejian, Dai, Mo, Zhai, Lei, Wu, Zhonghai, Yu, Zhiqiang
• Granted Patent: US 8,838,626 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/221 Parsing markup language streams streaming G06F40/149

Abstract

Embodiments of techniques and systems for parallel XML parsing are described. An event-level XML parser may include a lightweight events partitioning stage, parallel events parsing stages, and a post-processing stage. The events partition may pick out event boundaries using single-instruction, multiple-data instructions to find occurrences of the “<” character, marking event boundaries. Subsequent checking may be performed to help identify other event boundaries, as well as non-boundary instances of the “<” character. During events parsing, unresolved items, such as namespace resolution or matching of start and end elements, may be recorded in structure metadata. This structure metadata may be used during the subsequent post-processing to perform a check of the XML data. If the XML data is well-formed, individual sub-event streams formed by the events parsing processes may be assembled into a flat result event stream structure. Other embodiments may be described and claimed.

Claims

1. A computer-implemented method for parsing XML data, the method comprising:

partitioning, by a computing device, the XML data into a plurality of XML chunks by a computing device;

parsing by the computing device, respective ones of the plurality of chunks in parallel into sub-event streams; and

generating by the computing device, a result event stream for the XML data from the sub-event streams.

2. The method of claim 1, wherein partitioning the XML data comprises:

marking boundaries of XML events by identifying locations of “

<

”

characters in the XML data; and

forming the XML chunks based at least in part on the boundaries of XML events.

3. The method of claim 2, wherein marking boundaries further comprises, for respective “

<

”

characters which are identified;

checking a character following the “

<

”

character; and

determining a type of event based at least in part on the character following the “

<

”

character.

4. The method of claim 3, wherein marking boundaries further comprises not identifying locations for “

<

”

characters which do not mark event boundaries in the XML data.

5. The method of claim 2, wherein forming XML chunks comprises forming at least one XML chunk which comprises more than one event.

6. The method of claim 2, wherein forming XML chunks comprises forming XML chunks within a pre-determined size variation.

7. The method of claim 2, wherein forming XML chunks comprises forming at least one XML chunk which contains a matching start element and end element.

8. The method of claim 2, wherein partitioning comprises partitioning at least partially in parallel using single instruction, multiple data instructions.

9. The method of claim 1, wherein parsing respective ones of the plurality of chunks in parallel comprises performing respective events parsing processes on respective XML chunks on respective ones of a plurality of cores on a multi-core or many-core computer processor.

10. The method of claim 9, wherein performing a respective events parsing process comprises maintaining structure metadata identifying unresolved items in the respective XML chunk.

11. The method of claim 10, wherein unresolved items comprise start elements, end elements, or prefixes in the XML chunk.

12. The method of claim 1, wherein generating an event stream comprises:

processing sub-event streams sequentially;

resolving unresolved prefixes using structure metadata created during parsing;

matching start and end elements together; and

producing a result event stream from parsed sub-event streams.

13. The method of claim 1, wherein parsing comprises parsing respective ones of the plurality of chunks in parallel into sub-event streams with no internal cross references or generating comprises generating a result event stream with no internal cross-references.

14. A system comprising:

storage memory configured to store an XML document; and

a computer processor having a plurality of processing cores, coupled to the storage memory;

an events partitioning module, executable by a first processor core and configured, upon execution by the at least one processor core to partition the XML document into a plurality of XML chunks;

one or more events parsing modules, executable in parallel by one or more respective processor cores and configured, upon execution by the one or more respective processor cores, to perform, in parallel, events parsing on respective XML chunks to produce respective sub-event streams and structure metadata; and

a post-processing module, executable by a second processor core, to perform post-processing on the sub-event streams based on the structure metadata to produce a result event stream.

15. The system of claim 14, wherein the events partitioning module is further configured, upon execution by the first processor core, to perform a partition of the XML document by, for respective XML events:

performing a first character check to identify a location of a “

<

”

character which indicates an event boundary; and

performing a second character check to identify a type for the event.

16. The system of claim 15, wherein:

the one or more events parsing modules are further configured, upon execution by the one or more processor cores, to perform events parsing on an XML chunk by;

identifying unresolved items resulting from the chunk having incomplete XML data; and

recording, for respective unresolved items in the chunk, structure metadata identifying the unresolved items; and

the post-processing module is further configured, upon execution by the second processor core, to perform post-processing by;

sequentially visiting structure metadata of respective sub-event streams;

resolving at least unresolved prefixes with the structure metadata; and

linking sub-event streams to form the result event stream.

17. One or more computer-readable storage media containing instructions which, upon execution by a computer processor comprising a plurality of cores, cause the computer processor to perform a method comprising:

partitioning the XML document into a plurality of XML chunks;

on respective cores of the computer processor, performing events parsing on respective XML chunks to produce respective sub-event streams and structure metadata; and

performing post-processing on the sub-event streams based on the structure metadata to produce a result event stream.

18. The computer-readable media of claim 17, wherein performing a partition of the XML document comprises, for respective XML events:

performing a first character check to identify a location of a “

<

”

character which indicates an event boundary; and

performing a second character check to identify the type of the event.

19. The computer-readable media of claim 17, wherein performing events parsing on an XML chunk comprises:

identifying unresolved items resulting from the chunk having incomplete XML data; and

recording, for respective unresolved items in the chunk, structure metadata identifying the unresolved items.

20. The computer-readable media of claim 17, wherein performing post-processing comprises:

sequentially visiting structure metadata for respective sub-event streams;

resolving at least unresolved prefixes with the structure metadata; and

linking sub-event streams to form the result event stream.