Parsing XML at the Speed of Light (2012)

http://www.aosabook.org/en/posa/parsing-xml-at-the-speed-of-light.html

by Tomte • 4 years ago

53 52 4 years ago

xnacly• 4 years ago

I recently made a very stripped down XML to JSON parser, specifically for parsing RSS feeds, for a react native project:

https://xnacly.vercel.app/blog/2022_07_18_rss_parser

adenozine• 4 years ago

I remember reading this when it came out, it really informed and confirmed some of my data intuitions. Absolutely fascinating material.

The allocator section is particularly clever and shows just how precise and utilitarian the design is.

Ironically, I’ve only ever ended up parsing a handful of XML in my life, but it’s reassuring to me that people will look into these algorithms and see how beautifully crafted they had to be in order to go so fast.

sgtnoodle2• 4 years ago

I wrote an XML parser from scratch one time. It was fun! I just needed to read in an XML file into a C++ program, and pulling in a third party library wasn't a viable option.

planede3• 4 years ago

pulling in a third party library wasn't a viable option

How? I would violently object for implementing an in-house XML parser as opposed to just finding a way to include libxml2. It's under the MIT license, so I doubt that was an issue.

plugin-baby• 4 years ago

Do you have other objections beyond the wasted effort of re-writing the wheel?

maskros• 4 years ago

libxml2 can be massive overkill if you just want to parse XML data. Unless you need schema validation and namespaces and all that jazz, you can parse XML in C with a simple state machine of ~200 lines. Add another 200 to build a DOM-like structure.

https://github.com/ccxvii/snippets/blob/master/xml.c#L326

Or in lua with ~200 lines altogether:

https://github.com/ccxvii/snippets/blob/master/xml.lua

johannes1234321• 4 years ago

Yes, libxml2 is a widespread, thus mostly unproblematic choice. However pulling in a third party is not only about license.

With a thirdparty library you have to follow security updates (also to parts you don't need), may have build issues on some platforms you want to support (something embedded?) and so on.

If you don't need XML, but just a few xml-like tags a custom parser can be done quickly. But yes then you get to the NHI problems and what if your assumptions about XML subset were wrong ...

Personally I would lean on an XML lib (maybe libyml2, maybe qxml, maybe windows API, ... depending on context) as XML is complex, but generally adding libraries introduce their costs.

sgtnoodle2• 4 years ago

I didn't need to parse any XML file, but rather a specific XML file. It was inside an ITAR restricted codebase, and lawyers are conservative about open source in that context. In terms of security, it wasn't internet facing, and was written to the same standard as safety critical embedded software.

Cthulhu_• 4 years ago

Part of me wishes XML was still in vogue, it and related technologies solved a lot of problems that alternatives like JSON and YAML are still trying to solve.

I mean the last thing I heard from XML was EXI, a new way to transfer XML documents; instead of encoding it into an ASCII representation and gzipping it, it instead (iirc) turns an XML document into a binary representation or stream containing events similar to SAX as mentioned in this article. That could then be reshuffled and compressed for further efficiency. It was a way to improve transfer performance by a lot at the cost of human readability on the line, but, nobody should read XML documents on the line and they would probably use a client (that understands EXI) anyway.

guiriduro2• 4 years ago

Never understood the typical all/nothing hivemind developer view around XML and JSON/YAML. It is and should always have been a case of horses for courses - XML absolutely has its uses (structured markup, mixed human readable/data islands, schema validation and multi-schema markup), yes it was bad to try to use it for everything and it is poor and long-winded for short repeated key/value item markup, but its equally bad today to treat it as passe and useless, it excels in several areas where YAML manifestly fails. Outside key/value markup of fairly shallow tree structures where schemas are singular, absent or in flux (in nosql style) or for machine consumption only, JSON/YAML is also the wrong tool to reach for.

pydry4• 4 years ago

It was an overcomplicated design-by-committee mess.

The only cases where XML tech has survived is where it got in early and inertia has kept it there and because it was "good enough".

I genuinely dont know of anybody building new technology on a foundation of XML. There's always something simpler, with a lower bug surface that will handle the job better - even in its originally intended domain of document markup.

paskozdilar• 4 years ago

EXI, a new way to transfer XML documents; instead of encoding it into an ASCII representation and gzipping it, it instead (iirc) turns an XML document into a binary representation or stream containing events similar to SAX as mentioned in this article. That could then be reshuffled and compressed for further efficiency

How would this compare to protobuf, in terms of efficiency?

miffy9004• 4 years ago

I don't think anyone's tried benchmarking protobuf against EXI yet, but I've played around with a .NET implementation (Nagasena: http://openexi.sourceforge.net/) and it does outperform Gzip both for compression efficiency and decompression/runtime performance, so long as you use a schema-accelerated parser. It can infer a schema (turning it into a 'grammar' to use the EXI-specific term), but a properly constructed XML Schema will always be fastest/most efficient, especially in low memory systems.

brightball• 4 years ago

The only thing I really liked about XML was schemas (XSD I think?).

The ability to design a schema that could be passed around to let people validate the data and structure of an XML file before sending it was really slick. The schema designer tools were easy to use.

I actually enjoyed using WSDL based web services specifically because of this. You could take the file, which was just a schema and generate all the code and data structures you needed to interface with the API from any language…and you got the ability to validate your data client side before even bothering to send it.

It definitely had some pain points, but overall these were the good points that I remember.

GraphQL is probably the closest next evolution.

LAC-Tech2• 4 years ago

JSON Schema is a thing

pjmlp• 4 years ago

Come to the Java and .NET world, still used a lot.

LAC-Tech2• 4 years ago

What problem did XML solve that JSON is still trying to?

cxr2• 4 years ago

Mixed content: <https://news.ycombinator.com/item?id=21397111>

TedDoesntTalk4• 4 years ago

Comments. And before you mention JSON5, so you know anyone who uses it?

dragonwriter2• 4 years ago

Part of me wishes XML was still in vogue, it and related technologies solved a lot of problems that alternatives like JSON and YAML are still trying to solve.

If you have a problem solved by XML and not other technologies, you can still use XML.

TedDoesntTalk4• 4 years ago

you can still use XML

Make sure you have thick skin. Your peers will laugh at you. And your colleagues may veto your choice.

niros_valtos• 4 years ago

If I had to parse XMLs in my job today, I’d quit. It is equivalent to writing code in VB6 for me.

zasdffaa• 4 years ago

var dom := XMLparse(<some xml doc>);

What's the problem?

Edit: if you mean be in the extremely rare state of having to write an XML parser, it's very straightforward.

miffy9004• 4 years ago

I have a similar sentiment, but generalised to any file format. No one should be hand writing parsers or parsing code for XML, JSON or any other format for that matter. It’s 2022; data needs to come in a structured format with a schema. And preferably with tooling to generate code or parsers for said schemas.

TedDoesntTalk4• 4 years ago

data needs to come in a structured format with a schema. And preferably with tooling to generate code or parsers for said schemas

Where is your engineering, inventor spirit? This seems snowflakish to me. You want everything handed to you on a silver platter. But the reality is there’s lots of data out there that has no schema and never will. And if you don’t have proper tooling, you’d quit? Why not MAKE your own tooling?

ThePadawan• 4 years ago

My POV:

Until 2020 I worked in data exchange between an online retail company (think Amazon in the good old days) and its suppliers.

I wish people used XML more. Not because it's cool or practical or any of those reasons.

It's because 90% of non-tech-savvy people still do their IT work by someone manually filling in cells in an Excel worksheet.

I do understand your attitude - but I think the world would be served a lot better if we accepted formats that were viable, just not en vogue, if it at least got rid of all the crap we are using instead.

jarym2• 4 years ago

XML was and remains amazing - I write XSLT for bulk data transforms every now and then and it is super performant. Even querying JSON is fast via XPath - https://www.defiantjs.com/

It’s downfall was really how broad it ended up being with way too many ways to represent data structures - JSON was refreshing with it’s limited vocabulary.

planede3• 4 years ago

What do you use to evaluate XSLT to perceive it as "super performant"? I had the misfortune to deal with XSLT and I failed to perceive it as fast. In fact we had a lot of performance issues with XSLT processing. I wouldn't describe XPath as fast either.

jarym2• 4 years ago

The last time I used XSLT was in a Microsoft SSIS package to decode XML payloads into database rows that could be merged into SQL server tables.

Before I did this the previous engineer had written a bunch of stored procedures to do this that was both brittle and slow (processing time was 11 hours) but the SQL was fairly decent.

Once I used XSLT to do this the task ran in under 90 minutes and it was far easier to maintain (new fields, changing columns, etc).

yobbo• 4 years ago

Rather, it's your computer that is performant.

miga• 4 years ago

It is known that "speed of light" PugiXML can be replaced by fast processing in higher level language like Haskell: https://arxiv.org/pdf/2011.03536.pdf

herodotus• 4 years ago

Ah memories: parsing XML fast is what lead me to work for Apple. I gave a talk about it (based on https://webhome.cs.uvic.ca/~nigelh/Publications/IDEAL02.pdf: Expeditious XML processing, Yeow, Horspool, Levy) to the Vancouver XML group. That led me to be approached by the chair of the XML Vancover group who happened also to be the director of a Vancouver software company. They hired me and about a year later the company was acquired by Apple. And so that part of my adventure began.

(The fundamental idea of the parser was to use ideas taken from Warren's Abstract Machine for Prolog)

jhallenworld• 4 years ago

I worked on a hardware XML accelerator. It would deposit the parsed and validated XML tree into CPU memory, ready for use by software.

https://patents.google.com/patent/US9110875B2

The hardware was an FPGA-based PCIe board, but the design also ended up in a custom CPU.

Here's one thing I remember: namespace prefix declarations are applied retroactively within XML elements. This is not easy to deal with when trying to design streaming hardware..

Mikhail_Edoshin• 4 years ago

Yes, this complicates the parsing quite a bit: you have to read the element header with attributes into a buffer and keep them there until you're sure there's no changes in the default namespace or namespace prefixes. And when you start reading a name character-by-character you have no idea whether what you're reading is a namespace prefix or the local name, which affects the construction of the lookup table.

The added complexity is in a stark contrast with the namespaceless XML core, where all parsing decisions require a single character lookahead and you can report items as soon as their data is ready. It's interesting to think that a slightly different syntax for namespaces would make these problems non-existent. E.g. if namespace prefixes were at the end of a name (template:xsl) and namespace declarations were standalone elements enclosing the rest of the XML, it could be much simpler.

menotyou• 4 years ago

Abandonig XML would help the climate immensly.

Parsing XML at the Speed of Light (2012)

Related Stories