Event-level parallel methods and apparatus for XML parsing

• US 8,838,626 B2
• Filed: 12/17/2009
• Issued: 09/16/2014
• Est. Priority Date: 12/17/2009
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Yu, Zhiqiang, Fang, Yuejian, Zhai, Lei, Wang, Yun, Wu, Zhonghai, Dai, Mo
• Primary Examiner(s): Truong, Dennis
• Application Number:
  US12/641,234
• Publication Number:
  US 20110153604A1
• Time in Patent Office: 1,734 Days
• Field of Search: 707/602, 707/755, 715/236, 715/237, 717/143, 717/149
• US Class Current: 707/755
• 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 an events partitioning module of a computing device, the XML data into a plurality of XML chunks having a plurality of XML events contained therein, wherein partitioning includes determining a type of event associated with individual XML events of the plurality of XML events and ignoring character data contained within one or more XML events based, at least in part, on the type of event to prevent identification of character data contained within the one or more XML events from being identified as an XML event;

parsing, by a plurality of instances of an events parsing module of the computing device, the plurality of chunks in parallel into sub-event streams, wherein parsing includes creating structure metadata to identify unresolved items in the sub-event streams to avoid a parsing error based on the unresolved items, wherein the unresolved items include one or more of an identity of an unresolved start element, an identity of an unresolved end element, or an identity of an unresolved prefix; and

generating, by a post processing module of the computing device, a result event stream for the XML data from the sub-event streams, wherein generating the result event stream includes resolving an unresolved end element identified in the structure metadata with a preceding unresolved start element identified in the structure metadata or resolving an unresolved prefix identified in the structure metadata with a namespace of a preceding start element to avert the need to reparse the XML chunks that produced the unresolved item.

2. The method of claim 1, wherein generating the result event stream further includes:

post-processing the sub-event streams sequentially;

and

producing the result event stream by recombining the plurality of XML chunks and linking the post-processed sub-event streams together.

3. The method of claim 2, wherein partitioning the XML data into a plurality of XML chunks is based on a threshold indicated by a number of XML events to include in each XML chunk of the plurality of XML chunks.

4. The method of claim 2, wherein partitioning the XML data into a plurality of XML chunks is based on a pre-determined size variation of a threshold indicated by a preferred chunk size.

5. The method of claim 2, wherein partitioning the XML data into a plurality of XML chunks comprises at least one XML chunk that contains a matching start element and end element.

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

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

8. The method of claim 1, wherein partitioning includes:

identifying XML event boundaries by locating “

<

”

characters in the XML data, wherein determining a type of event associated with individual XML events of the plurality of XML events is

based on a character following the “

<

”

character;

and

forming the plurality of XML chunks from the identified XML events.

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

10. A system comprising:

storage memory configured to store an XML document;

one or more processors having a plurality of processor cores, coupled to the storage memory;

an events partitioning module which, upon execution by the processor, causes the processor to partition the XML document into a plurality of XML chunks having a plurality of XML events contained therein, wherein partition includes determination of a type of event associated with individual XML events of the plurality of XML events and exclusion of character data contained within one or more XML events based, at least in part, on the type of event to prevent identification of character data contained within the one or more XML events from being identified as an XML event;

a plurality of instances of an events parsing module which, upon execution by one or more of the plurality of processor cores, cause the one or more of the plurality of processor cores to perform, in parallel, events parsing of the plurality of XML chunks to produce respective sub-event streams and structure metadata, the structure metadata identifying unresolved items in the sub-event streams to avoid a parsing error based on the unresolved items, wherein the unresolved items include one or more of an identity of an unresolved start element, an identity of an unresolved end element, or an identity of an unresolved prefix; and

a post-processing module which, when executed by at least one processor of the one or more processors, causes the at least one processor to perform post-processing on the sub-event streams to produce a result event stream, wherein to produce the result event stream includes resolution of an unresolved end element identified in the structure metadata with a preceding unresolved start element identified in the structure metadata or resolution of an unresolved prefix identified in the structure metadata with a namespace of a preceding start element to avert the need to reparse the XML chunks that produced the unresolved item.

11. The system of claim 10, wherein the post-processing module, when executed by the at least one processor, causes the processor to:

process the sub-event streams sequentially; and

produce the result event stream through recombination of the plurality of XML chunks and linking of the processed sub-event streams.

12. The system of claim 11, wherein to partition the XML document includes:

identification of XML events by locating “

<

”

characters in the XML document wherein determination of a type of event associated with individual XML events of the plurality of XML events is based at least in part on a character following the “

<

”

character;

and

formation of the plurality of XML chunks from the identified XML events.

16. The system of claim 10, wherein to partition is performed at least partially in parallel through use of single instruction, multiple data (SIMD) instructions.

13. One or more non-transitory computer-readable storage media containing instructions which, upon execution by a processor having a plurality of cores, cause the processor to:

partition an XML document into a plurality of XML chunks containing a plurality of XML events, wherein partition includes determination of a type of event associated with individual XML events of the plurality of XML events and exclusion of character data contained within one or more XML events based, at least in part, on the type of event to prevent identification of character data contained within the one or more XML events from being identified as an XML event;

perform, in parallel on respective cores of the processor, events parsing of XML chunks to produce respective sub-event streams and structure metadata to identify unresolved items in the sub-event streams and avoid a parsing error based on the unresolved items, wherein the unresolved items include one or more of an identity of an unresolved start element, an identity of an unresolved end element, or an identity of an unresolved prefix; and

perform post-processing on the sub-event streams to produce a result event stream, wherein to produce the result event stream includes resolution of an unresolved end element identified in the structure metadata with a preceding unresolved start element identified in the structure metadata or resolving an unresolved prefix identified in the structure metadata with a namespace of a preceding start element to avert the need to reparse the XML chunks that produced the unresolved item.

14. The non-transitory computer-readable media of claim 13, wherein perform post-processing includes:

process the sub-event streams sequentially;

and

produce the result event stream through recombination of the plurality of XML chunks and linking together of the post-processed sub-event streams.

15. The non-transitory computer-readable media of claim 13, wherein partition includes:

identification of XML events through location of “

<

”

characters in the XML document, wherein determination of a type of event associated with individual XML events of the plurality of XML events is based at least in part on a character following the “

<

”

character;

and

formation of the plurality of XML chunks from the identified XML events.

17. The non-transitory computer-readable media of claim 13, wherein to partition is performed at least partially in parallel through use of single instruction, multiple data (SIMD) instructions.