6 ms·

AsmXml: a fast XML parser/decoder in pure x86 assembler

132 points by gmac 16y ago

jasondavies 16y ago
The 10x speed difference is impressive, but they do list some caveats in the benchmark: * AsmXml does not copy attributes and text unless necessary (when it includes entity or char references), so, if you need a zero terminated string, you must copy the value first. * On the other hand, it does more work since it also decodes attributes (O(1) access time), saving a lot of time to the caller of the library. I'd be interested to know whether it would still be that much faster than a C library that had the same tradeoffs e.g. no copying of attributes/text unless necessary. I also wonder if it's worth it for existing C libraries to incorporate hand-optimised asm from this library (only when targeting x86 of course) if it provides much more benefit than the above tradeoffs.
- roel_v 16y ago
  "* On the other hand, it does more work since it also decodes attributes (O(1) access time), saving a lot of time to the caller of the library" This part I didn't understand. Does he mean transforming the document's encoding into the platform's native encoding? How can the access time of a list of attributes be in constant time? I mean, there needs to be some form of lookup from the name of the attribute to its value. And how do the two relate to each other?
  - Nitramp 16y ago
    The trick is that through their mapping, they have an array of "attributes" for every element, with a specific offset for each attribute with a certain name. During construction, they build that array according to the names, so they do the lookup once during construction.
    - roel_v 16y ago
      But then how do you reference the attributes? I get the code to parse my xml document, then afterward I want to access a certain attribute (by name). The library would still need to look up the index of that attribute, at O(n) complexity, right?
      - lincolnq 16y ago
        no, quoting from grandparent: "a specific offset for each attribute with a certain name" -- e.g., for all <image> element, 'width' is always at attributes[0] and 'height' is at attributes[1], presumably regardless of whether that particular image has a width and height attribute.
        roel_v 16y ago
        Oh I see, thanks.
- humbledrone 16y ago
  The RapidXml library is pretty similar to AsmXml, except that it's written in C++. Browsing around the "Links" section on the AsmXml website, I came across a site that performs speed comparisons between the various parsers out there. RapidXml does appear to come pretty close to AsmXml in terms of speed. Source: http://xmlbench.sourceforge.net/results/benchmark200910/index.html http://xmlbench.sourceforge.net/results/benchmark200910/inde...
  - yatsyk 16y ago
    Thank you for RapidXml information. From RepidXml site: It is an in-situ parser written in modern C++, with parsing speed approaching that of strlen function executed on the same data. bold statement :)
  - boris 16y ago
    Except that RapidXml is not a real XML parser. It is a parser that can only handle a subset of XML 1.0 language. See: http://www.codesynthesis.com/~boris/blog/2008/05/19/real-xml-parser/ http://www.codesynthesis.com/~boris/blog/2008/05/19/real-xml...
points 16y ago
Using good (asm) to do evil (xml). Not cool :(
- pjscott 16y ago
  You think that programming a significant bit of code in assembly is a Good Thing? If you can possibly avoid it? As for XML, it's excessively heavyweight and kind of awkward, but don't underestimate what a big improvement it was over the incompatible, non-human-readable binary formats that it was meant to replace. No, this isn't using good to go evil. This is an elaborate, properly functioning, potentially useful joke. I'm awed by the combination of technical acumen and perversity, but I'm not going to actually use it.
kia 16y ago
Modern compilers can generate very good ASM (much better than most programmers can write by hand). I think parser with similar architecture in C should be as fast as written in pure ASM.
- twp 16y ago
  Revealing quote from the bottom of the benchmarks page: > I've performed other tests on different machines and observed that, on a Pentium 4, the difference between AsmXml and Expat is smaller (next generation processors seem to be more profitable to C programs). I also did tests with my Arch Linux but I couldn't build xerces-c so I don't publish results, but Expat was faster, may be because of 686 optimizations. Says it all, really.
  - yatsyk 16y ago
    As far as I remember expat is event based parser (it emits events when next attribute, tag etc ready) but it seems that this parser creates some sort of DOM. DOM based parsers usually much slower.
    - mfukar 16y ago
      ..and more useful as well.
- melling 16y ago
  Can you supply references to compilers producing faster code than assembler written by hand? I'm under the impression that the programmer can still do better, if she's willing to put in the effort.
  - StavrosK 16y ago
    The compiler does a million things to speed up your code, which are mostly lost when you write pure assembly. I wouldn't be surprised if a c program was noticeably faster than the same thing in assembly...
yatsyk 16y ago
PugXML (http://www.codeproject.com/KB/cpp/pugxml.aspx http://www.codeproject.com/KB/cpp/pugxml.aspx) uses similar approach but very portable.
- corysama 16y ago
  I have used pugixml (based on PugXML) for very fast parsing of very simple XML and I can highly recommend it. The speed and (IMO) interface improvements are very large. http://code.google.com/p/pugixml/ http://code.google.com/p/pugixml/ In AsmXML's benchmark, ASM was 14x faster than Xerces (http://tibleiz.net/asm-xml/benchmark.html http://tibleiz.net/asm-xml/benchmark.html). In pugixml's benchmark, pugi was 11x faster than Xerces (http://zeux.mooo.com/pub/pugixml/table.html http://zeux.mooo.com/pub/pugixml/table.html). Not bad for ASM vs C++. Both systems only support a limited subset of XML features.
Nitramp 16y ago
They are missing the most important thing: AsmXml builds a specialized structure for a specific kind of XML. Regular parsers like Xerces-C build a generic, mutable DOM tree. That is obviously _way_ more work, with different lists for attributes and children, different node types etc. Looking at the schemata they support, it doesn't look like they support all possible XML structures. A better comparison might have been one of the XML binding tools vs AsmXml, that's much closer in functionality. I'd also be careful wrt the XML-ness of this tool. Does it properly handle all Unicode obscurities? Does it handle all DTD obscurities? Is it robust against documents not matching the schema, malformed documents, or even malicious documents?
- boris 16y ago
  Those are exactly the questions I ask myself every time I hear about a new, super-fast XML parser. Is it a real XML parser[1] or can it only handle a "simple" subset of XML? I am surprised that more people don't seem to share the same skepticism as you and me. Probably because most people don't realize that implementing a conforming XML 1.0 parser is not a trivial task. And you are right about the XML data binding tools. In most cases parsing XML itself is not what takes the bulk of the time. It is validation (against DTD, XML Schema, or ad-hoc), data conversion (e.g., from "123" string to 123 integer) and perhaps construction of some in-memory representation (with memory allocations that it involves) that take the bulk of the time. There are existing tools[2] that can performs the above tasks an order of magnitude faster than a general-purpose XML parsers by generating the tailor-made validation and data extraction code as well as data structures from XML Schema. [1] http://www.codesynthesis.com/~boris/blog/2008/05/19/real-xml-parser/ http://www.codesynthesis.com/~boris/blog/2008/05/19/real-xml... [2] http://www.codesynthesis.com/products/xsde/ http://www.codesynthesis.com/products/xsde/
  - alan 16y ago
    A number of years ago, I wrote a XML/C binding tool atop the gnome SAX parser. It's able to handle anything in a DTD and a lot of things from XML Schema. I stopped working on it as it could do everything I had use for. http://xmel.sourceforge.net/ http://xmel.sourceforge.net/ It does O(1) access to attributes as well, since it does binding.
revjx 16y ago
For some reason, I'm impressed whenever anyone does anything clever in ASM, even if the performance benefits don't add up to much these days.
- BrandonM 16y ago
  I know that at the least, NES, Super NES, and Sega Genesis games were nearly all programmed in assembler. I don't know much about the next generation of game systems. Whenever you want to feel impressed, go back and play some old school classics.
  - corysama 16y ago
    Modern games are written in huge swaths of C++, tiny bits of SIMD compiler intrinsics and individual pieces of very special-purpose assembly. If you want to feel impressed, check this out http://benfry.com/distellamap/ http://benfry.com/distellamap/
    - scott_s 16y ago
      This is brilliant. So brilliant I'm submitting it to the main page.
    - Ogre 16y ago
      You're more likely to find lua or sometimes python in modern games than assembly. Scripting has become a big part of many games, and lua has found its niche by virtue of being relatively light weight and quite easy to interface with from C/C++. I don't think I've seen any assembly that was actually enabled in the games I've worked on in the last five years, though I do know where there's a tiny bit in my current project that's #if'd for older environments. That's just stuff like atomic operations that every modern compiler provides built-ins for now. The link is great, thanks!
    - revjx 16y ago
      That is superb.
8ren 16y ago
This was for fun (as he says.) > Remember: if you really need speed, do not use XML. He defines his own schema language, in XML (not XML Schema), which the parser needs. Nothing wrong with that. You could even transform (some subset of) XSD's to it using XSLT. (see "2. defining the schema" http://tibleiz.net/asm-xml/tutorial.html http://tibleiz.net/asm-xml/tutorial.html and "defining the schema" http://tibleiz.net/asm-xml/documentation.html http://tibleiz.net/asm-xml/documentation.html) He stores attributes in an array, to give O(1) access (... if you assume attribute order is significant, which it isn't according to the XML spec and most tools... even though humans find them more readable if in an expected order. So, to find a specific attribute, you'll have to step through them.) XML parsers are unbelievably inefficient.. (but c'mon... it's XML... all other sins pall to insignificance before the big one, as fireflies at dawn.) He makes the nice point that once you have the XML parsed, you can just use those strings directly instead of copying them again. IBM research came out with a this idea a while back, of combining the two, but it doesn't seem to have gone anywhere. I'd guess they patented it like crazy, because, after all, they are IBM. http://portal.acm.org/citation.cfm?id=1135777.1135796 http://portal.acm.org/citation.cfm?id=1135777.1135796 (that's just the abstract - sorry, couldn't find the pdf.) But again, all this cleverness wouldn't matter except that it's fun (if you really need speed, do not use XML.). Oh... and except in "XML appliances": http://en.wikipedia.org/wiki/XML_appliance http://en.wikipedia.org/wiki/XML_appliance DISCLAIMER: despite my tone, I am pro-XML. It's very useful. Some of its limitations facilitate some parsing ideas that escaped everyone else because of their cost in terms of performance and expressiveness. Just as some people are so obsessed with performance that they miss modular elegance, some people are analogously obsessed with expressiveness. There! I think I've insulted everybody.
- marcinw 16y ago
  Oh my, that IBM research probably went into their DataPower appliances >> http://www-01.ibm.com/software/integration/datapower/performance.html http://www-01.ibm.com/software/integration/datapower/perform... My biggest gripe with XML is namespaces followed by XSLT. Working with XML at that point just leaves me feeling disgusted. edit: here's the full text >> http://www2006.org/programme/files/xhtml/5011/p5011-mendelsohn.html http://www2006.org/programme/files/xhtml/5011/p5011-mendelso...
adw 16y ago
One of my cofounders committed this crime against nature: http://github.com/tow/fox http://github.com/tow/fox Yes, an XML parser in Fortran. Seriously, for data exchange between solid-state physics codes, writing this was the best option available. Occasionally people ask us why we founded a startup. Seriously?!
scotth 16y ago
Why was this written? Seems like it would have an interesting story behind it.
mkramlich 16y ago
now I want to see someone write a COBOL interpreter in Fortran

132 points by gmac 16y ago

The 10x speed difference is impressive, but they do list some caveats in the benchmark: * AsmXml does not copy attributes and text unless necessary (when it includes entity or char references), so, if you need a zero terminated string, you must copy the value first. * On the other hand, it does more work since it also decodes attributes (O(1) access time), saving a lot of time to the caller of the library. I'd be interested to know whether it would still be that much faster than a C library that had the same tradeoffs e.g. no copying of attributes/text unless necessary. I also wonder if it's worth it for existing C libraries to incorporate hand-optimised asm from this library (only when targeting x86 of course) if it provides much more benefit than the above tradeoffs.

roel_v 16y ago
"* On the other hand, it does more work since it also decodes attributes (O(1) access time), saving a lot of time to the caller of the library" This part I didn't understand. Does he mean transforming the document's encoding into the platform's native encoding? How can the access time of a list of attributes be in constant time? I mean, there needs to be some form of lookup from the name of the attribute to its value. And how do the two relate to each other?
- Nitramp 16y ago
  The trick is that through their mapping, they have an array of "attributes" for every element, with a specific offset for each attribute with a certain name. During construction, they build that array according to the names, so they do the lookup once during construction.
  - roel_v 16y ago
    But then how do you reference the attributes? I get the code to parse my xml document, then afterward I want to access a certain attribute (by name). The library would still need to look up the index of that attribute, at O(n) complexity, right?
    - lincolnq 16y ago
      no, quoting from grandparent: "a specific offset for each attribute with a certain name" -- e.g., for all <image> element, 'width' is always at attributes[0] and 'height' is at attributes[1], presumably regardless of whether that particular image has a width and height attribute.
      - roel_v 16y ago
        Oh I see, thanks.
humbledrone 16y ago
The RapidXml library is pretty similar to AsmXml, except that it's written in C++. Browsing around the "Links" section on the AsmXml website, I came across a site that performs speed comparisons between the various parsers out there. RapidXml does appear to come pretty close to AsmXml in terms of speed. Source: http://xmlbench.sourceforge.net/results/benchmark200910/index.html http://xmlbench.sourceforge.net/results/benchmark200910/inde...
- yatsyk 16y ago
  Thank you for RapidXml information. From RepidXml site: It is an in-situ parser written in modern C++, with parsing speed approaching that of strlen function executed on the same data. bold statement :)
- boris 16y ago
  Except that RapidXml is not a real XML parser. It is a parser that can only handle a subset of XML 1.0 language. See: http://www.codesynthesis.com/~boris/blog/2008/05/19/real-xml-parser/ http://www.codesynthesis.com/~boris/blog/2008/05/19/real-xml...

points 16y ago

Using good (asm) to do evil (xml). Not cool :(

pjscott 16y ago
You think that programming a significant bit of code in assembly is a Good Thing? If you can possibly avoid it? As for XML, it's excessively heavyweight and kind of awkward, but don't underestimate what a big improvement it was over the incompatible, non-human-readable binary formats that it was meant to replace. No, this isn't using good to go evil. This is an elaborate, properly functioning, potentially useful joke. I'm awed by the combination of technical acumen and perversity, but I'm not going to actually use it.

kia 16y ago

Modern compilers can generate very good ASM (much better than most programmers can write by hand). I think parser with similar architecture in C should be as fast as written in pure ASM.

twp 16y ago
Revealing quote from the bottom of the benchmarks page: > I've performed other tests on different machines and observed that, on a Pentium 4, the difference between AsmXml and Expat is smaller (next generation processors seem to be more profitable to C programs). I also did tests with my Arch Linux but I couldn't build xerces-c so I don't publish results, but Expat was faster, may be because of 686 optimizations. Says it all, really.
- yatsyk 16y ago
  As far as I remember expat is event based parser (it emits events when next attribute, tag etc ready) but it seems that this parser creates some sort of DOM. DOM based parsers usually much slower.
  - mfukar 16y ago
    ..and more useful as well.
melling 16y ago
Can you supply references to compilers producing faster code than assembler written by hand? I'm under the impression that the programmer can still do better, if she's willing to put in the effort.
- StavrosK 16y ago
  The compiler does a million things to speed up your code, which are mostly lost when you write pure assembly. I wouldn't be surprised if a c program was noticeably faster than the same thing in assembly...

yatsyk 16y ago

PugXML (http://www.codeproject.com/KB/cpp/pugxml.aspx http://www.codeproject.com/KB/cpp/pugxml.aspx) uses similar approach but very portable.

corysama 16y ago
I have used pugixml (based on PugXML) for very fast parsing of very simple XML and I can highly recommend it. The speed and (IMO) interface improvements are very large. http://code.google.com/p/pugixml/ http://code.google.com/p/pugixml/ In AsmXML's benchmark, ASM was 14x faster than Xerces (http://tibleiz.net/asm-xml/benchmark.html http://tibleiz.net/asm-xml/benchmark.html). In pugixml's benchmark, pugi was 11x faster than Xerces (http://zeux.mooo.com/pub/pugixml/table.html http://zeux.mooo.com/pub/pugixml/table.html). Not bad for ASM vs C++. Both systems only support a limited subset of XML features.

Nitramp 16y ago

They are missing the most important thing: AsmXml builds a specialized structure for a specific kind of XML. Regular parsers like Xerces-C build a generic, mutable DOM tree. That is obviously _way_ more work, with different lists for attributes and children, different node types etc. Looking at the schemata they support, it doesn't look like they support all possible XML structures. A better comparison might have been one of the XML binding tools vs AsmXml, that's much closer in functionality. I'd also be careful wrt the XML-ness of this tool. Does it properly handle all Unicode obscurities? Does it handle all DTD obscurities? Is it robust against documents not matching the schema, malformed documents, or even malicious documents?

boris 16y ago
Those are exactly the questions I ask myself every time I hear about a new, super-fast XML parser. Is it a real XML parser[1] or can it only handle a "simple" subset of XML? I am surprised that more people don't seem to share the same skepticism as you and me. Probably because most people don't realize that implementing a conforming XML 1.0 parser is not a trivial task. And you are right about the XML data binding tools. In most cases parsing XML itself is not what takes the bulk of the time. It is validation (against DTD, XML Schema, or ad-hoc), data conversion (e.g., from "123" string to 123 integer) and perhaps construction of some in-memory representation (with memory allocations that it involves) that take the bulk of the time. There are existing tools[2] that can performs the above tasks an order of magnitude faster than a general-purpose XML parsers by generating the tailor-made validation and data extraction code as well as data structures from XML Schema. [1] http://www.codesynthesis.com/~boris/blog/2008/05/19/real-xml-parser/ http://www.codesynthesis.com/~boris/blog/2008/05/19/real-xml... [2] http://www.codesynthesis.com/products/xsde/ http://www.codesynthesis.com/products/xsde/
- alan 16y ago
  A number of years ago, I wrote a XML/C binding tool atop the gnome SAX parser. It's able to handle anything in a DTD and a lot of things from XML Schema. I stopped working on it as it could do everything I had use for. http://xmel.sourceforge.net/ http://xmel.sourceforge.net/ It does O(1) access to attributes as well, since it does binding.

revjx 16y ago

For some reason, I'm impressed whenever anyone does anything clever in ASM, even if the performance benefits don't add up to much these days.

BrandonM 16y ago
I know that at the least, NES, Super NES, and Sega Genesis games were nearly all programmed in assembler. I don't know much about the next generation of game systems. Whenever you want to feel impressed, go back and play some old school classics.
- corysama 16y ago
  Modern games are written in huge swaths of C++, tiny bits of SIMD compiler intrinsics and individual pieces of very special-purpose assembly. If you want to feel impressed, check this out http://benfry.com/distellamap/ http://benfry.com/distellamap/
  - scott_s 16y ago
    This is brilliant. So brilliant I'm submitting it to the main page.
  - Ogre 16y ago
    You're more likely to find lua or sometimes python in modern games than assembly. Scripting has become a big part of many games, and lua has found its niche by virtue of being relatively light weight and quite easy to interface with from C/C++. I don't think I've seen any assembly that was actually enabled in the games I've worked on in the last five years, though I do know where there's a tiny bit in my current project that's #if'd for older environments. That's just stuff like atomic operations that every modern compiler provides built-ins for now. The link is great, thanks!
  - revjx 16y ago
    That is superb.

8ren 16y ago

This was for fun (as he says.) > Remember: if you really need speed, do not use XML. He defines his own schema language, in XML (not XML Schema), which the parser needs. Nothing wrong with that. You could even transform (some subset of) XSD's to it using XSLT. (see "2. defining the schema" http://tibleiz.net/asm-xml/tutorial.html http://tibleiz.net/asm-xml/tutorial.html and "defining the schema" http://tibleiz.net/asm-xml/documentation.html http://tibleiz.net/asm-xml/documentation.html) He stores attributes in an array, to give O(1) access (... if you assume attribute order is significant, which it isn't according to the XML spec and most tools... even though humans find them more readable if in an expected order. So, to find a specific attribute, you'll have to step through them.) XML parsers are unbelievably inefficient.. (but c'mon... it's XML... all other sins pall to insignificance before the big one, as fireflies at dawn.) He makes the nice point that once you have the XML parsed, you can just use those strings directly instead of copying them again. IBM research came out with a this idea a while back, of combining the two, but it doesn't seem to have gone anywhere. I'd guess they patented it like crazy, because, after all, they are IBM. http://portal.acm.org/citation.cfm?id=1135777.1135796 http://portal.acm.org/citation.cfm?id=1135777.1135796 (that's just the abstract - sorry, couldn't find the pdf.) But again, all this cleverness wouldn't matter except that it's fun (if you really need speed, do not use XML.). Oh... and except in "XML appliances": http://en.wikipedia.org/wiki/XML_appliance http://en.wikipedia.org/wiki/XML_appliance DISCLAIMER: despite my tone, I am pro-XML. It's very useful. Some of its limitations facilitate some parsing ideas that escaped everyone else because of their cost in terms of performance and expressiveness. Just as some people are so obsessed with performance that they miss modular elegance, some people are analogously obsessed with expressiveness. There! I think I've insulted everybody.

marcinw 16y ago
Oh my, that IBM research probably went into their DataPower appliances >> http://www-01.ibm.com/software/integration/datapower/performance.html http://www-01.ibm.com/software/integration/datapower/perform... My biggest gripe with XML is namespaces followed by XSLT. Working with XML at that point just leaves me feeling disgusted. edit: here's the full text >> http://www2006.org/programme/files/xhtml/5011/p5011-mendelsohn.html http://www2006.org/programme/files/xhtml/5011/p5011-mendelso...

adw 16y ago

One of my cofounders committed this crime against nature: http://github.com/tow/fox http://github.com/tow/fox Yes, an XML parser in Fortran. Seriously, for data exchange between solid-state physics codes, writing this was the best option available. Occasionally people ask us why we founded a startup. Seriously?!

scotth 16y ago

Why was this written? Seems like it would have an interesting story behind it.

mkramlich 16y ago

now I want to see someone write a COBOL interpreter in Fortran