OmegaMan's Musings

Most of the time one needs the power of the xml parser whether it is the XmlDocument or Linq to Xml to manipulate and extract data. But what if I told you that in some circumstances regular expressions might be faster?

Most conventional development thinking has branded regex processing as slow and the thought of using regex on xml might seem counter intuitive. In a continuation of articles I again want to dispel those thoughts and provide a real world example where Regular Expression parsing is not only on par with other tools in the .Net world but sometimes faster. The results of my speed test may surprise you;  and hopefully show that regular expressions are not as slow as believed, if not faster!

See: Are C# .Net Regular Expressions Fast Enough for You?

Real World Scenario

There was a developer on the MSDN forums who needed the ability to count URLs in multiple xml files. (See the actual post count the urls in xml file on Msdn) The poster received three distinct replies, one to use XMLDocument, another provided a Linq to XML solution and I chimed in with the regular expression method. The poster took the XMLDocument method and marked as the answer, but could he have done better?

I thought so…

So I took the three replies and distilled them down into their core processing and wrapped them in a similar IO extraction layer and proceeded to time them. I created 48 xml files with over one hundred thousand urls to find for a total of 13 meg on disk. I then proceeded to run the test all in release mode to get the results.  (See below section Setup to get a gist repository of the code).

Real World Result

Five tests, each test name is the technology and the user as found on the original msdn post. In red is the slowest and fastest time. Remember XmlDoc is the one the user choose as the answer.

Test 1
Regex           found 116736 urls in 00:00:00.1843576
XmlLinq_Link_FR found 116736 urls in 00:00:00.2662190
XmlDoc_Hasim()  found 116736 urls in 00:00:00.3534628

Test 2
Regex           found 116736 urls in 00:00:00.2317883
XmlLinq_Link_FR found 116736 urls in 00:00:00.2792730
XmlDoc_Hasim()  found 116736 urls in 00:00:00.2694969

Test 3
Regex           found 116736 urls in 00:00:00.1646719
XmlLinq_Link_FR found 116736 urls in 00:00:00.2333891
XmlDoc_Hasim()  found 116736 urls in 00:00:00.2625176

Test 4
Regex           found 116736 urls in 00:00:00.1677931
XmlLinq_Link_FR found 116736 urls in 00:00:00.2258825
XmlDoc_Hasim()  found 116736 urls in 00:00:00.2590841

Test 5
Regex           found 116736 urls in 00:00:00.1668231
XmlLinq_Link_FR found 116736 urls in 00:00:00.2278445
XmlDoc_Hasim()  found 116736 urls in 00:00:00.2649262

Wow! Regex consistently performed better, even when there was no caching of the files as found for the first run! Note that the time is Hours : Minutes : Seconds and regex’s is the fastest at 164 millseconds to parse 48 files! Regex worst time of 184 milleseconds is still better than the other two’s best times.

How was this all done? Let me show you.

Setup

Ok what magic or trickery have I played? All tests are run in a C# .Net 4 Console application in release mode. I have created a public Gist (Regex vs Xml) repository of the code and data which is actually valid Git repository for anyone how may want to add their tests, but let me detail what I did here on the blog as well.

The top level operation found in the Main looks like this where I run the tests 5 times

Enumerable.Range( 1, 5 )
            .ToList()
            .ForEach( tstNumber =>
            {
                Console.WriteLine( "Test " + tstNumber );
                Time( "Regex", RegexFindXml );
                Time( "XmlLinq_Link_FR", XmlLinq_Link_FR );
                Time( "XmlDoc_Hasim()", XmlDoc_Hasim );
                Console.WriteLine( Environment.NewLine );
            }

while the Time generic method looks like this and dutifully runs the target work and reports the results in “Test X found Y Urls in X [time]”:

public static void Time<T>( string what, Func<T> work )
{
    var sw = Stopwatch.StartNew();
    var result = work();
    sw.Stop();
    Console.WriteLine( "\t{0,-15} found {1} urls in {2}", what, result, sw.Elapsed );
}

Now in the msdn post the different methods had differing ways of finding each xml file and opening it, I made them all adhere to the way I open and sum the ULR counts. Here is its snippet:

return Directory.EnumerateFiles( @"D:\temp", "*.xml" )
            .ToList()
            .Sum( fl =>
            {

            } );

Contender  –  XML Document

This is one which the poster marked as the chosen one he used and I dutifully copied it to the best of my ability.

public static int XmlDoc_Hasim()
{
    return Directory.EnumerateFiles( @"D:\temp", "*.xml" )
                .ToList()
                .Sum( fl =>
                {
                    XmlDocument doc = new XmlDocument();
                    doc.LoadXml( System.IO.File.ReadAllText( fl ) );

                    if (doc.ChildNodes.Count > 0)
                        if (doc.ChildNodes[1].HasChildNodes)
                            return doc.ChildNodes[1].ChildNodes.Count;

                    return 0;

                } );

}

I used the sum extension method which is a little different from the original sum operation used, but it brings the tests closer in line by using the Extension.

Contender – Linq to Xml

Of the other two attempts, this one I felt was the more robust of the two, because it actually handled the xml namespace. Sadly it appeared to be ignored by the original poster. Here is his code

public static int XmlLinq_Link_FR()
{
    XNamespace xn = "http://www.sitemaps.org/schemas/sitemap/0.9";

    return Directory.EnumerateFiles( @"D:\temp", "*.xml" )
                    .Sum( fl => XElement.Load( fl ).Descendants( xn + "loc" ).Count() );

}

Contender – Regular Expression

Finally here is the speed test winner. I came up with the pattern design Upon by looking at the xml and it appeared one didn’t need to match the actual url, but just the two preceding  tags and any possible space between. That is the key to regex, using good patterns can achieve fast results.

public static int RegexFindXml()
{
    string pattern = @"(<url>\s*<loc>)";

    return Directory.EnumerateFiles( @"D:\temp", "*.xml" )
                    .Sum( fl => Regex.Matches( File.ReadAllText( fl ), pattern ).OfType<Match>().Count() );

}

XML1 (Shortened)

<?xml version="1.0" encoding="UTF-8"?>
<urlset xmlns="http://www.sitemaps.org/schemas/sitemap/0.9">
<url><loc>http://www.linkedin.com/directory/companies/internet-web2.0-startups-social-networking/barcelona.html</loc><changefreq>weekly</changefreq></url>
<url><loc>http://www.linkedin.com/directory/companies/internet-web2.0-startups-social-networking/basel.html</loc><changefreq>weekly</changefreq></url>
<url><loc>http://www.linkedin.com/directory/companies/internet-web2.0-startups-social-networking/bath.html</loc><changefreq>weekly</changefreq></url>
<url><loc>http://www.linkedin.com/directory/companies/computer-networking/sheffield.html</loc><changefreq>weekly</changefreq></url>
<url><loc>http://www.linkedin.com/directory/companies/computer-networking/singapore.html</loc><changefreq>weekly</changefreq></url>
<url><loc>http://www.linkedin.com/directory/companies/computer-networking/slough.html</loc><changefreq>weekly</changefreq></url>
<url><loc>http://www.linkedin.com/directory/companies/computer-networking/slovak-republic.html</loc><changefreq>weekly</changefreq></url>
</urlset>

Xml2 Shortened

<?xml version="1.0" encoding="UTF-8"?>
<urlset xmlns="http://www.sitemaps.org/schemas/sitemap/0.9">
<url><loc>http://www.linkedin.com/groups/gid-2431604</loc><changefreq>monthly</changefreq></url>
<url><loc>http://www.linkedin.com/groups/gid-2430868</loc><changefreq>monthly</changefreq></url>
<url><loc>http://www.linkedin.com/groups/Wireless-Carrier-Reps-Past-Present-2430807</loc><changefreq>monthly</changefreq></url>
<url><loc>http://www.linkedin.com/groups/gid-2430694</loc><changefreq>monthly</changefreq></url>
<url><loc>http://www.linkedin.com/groups/gid-2430575</loc><changefreq>monthly</changefreq></url>
<url><loc>http://www.linkedin.com/groups/gid-2431452</loc><changefreq>monthly</changefreq></url>
<url><loc>http://www.linkedin.com/groups/gid-2432377</loc><changefreq>monthly</changefreq></url>
<url><loc>http://www.linkedin.com/groups/gid-2428508</loc><changefreq>monthly</changefreq></url>
<url><loc>http://www.linkedin.com/groups/gid-2432379</loc><changefreq>monthly</changefreq></url>
<url><loc>http://www.linkedin.com/groups/gid-2432380</loc><changefreq>monthly</changefreq></url>
<url><loc>http://www.linkedin.com/groups/gid-2432381</loc><changefreq>monthly</changefreq></url>
<url><loc>http://www.linkedin.com/groups/gid-2432383</loc><changefreq>monthly</changefreq></url>
<url><loc>http://www.linkedin.com/groups/gid-2432384</loc><changefreq>monthly</changefreq></url>
</urlset>

Summary

It really comes down to the right tool for the right situation and this one regex really did well. But Regex is not good at most xml parsing needs, but for certain scenarios it really shines. If the xml has malformed or the namespace was wrong, then the parser has its own unique problems which would lead to a bad count. All the technologies had to do some upfront loading and that is key to how they performed. Regex is optimized to handle large data efficiently and as long as the pattern is spot on, it can really be quick.

My thought is don’t dismiss regular expression parsing out of hand, while the learning of it can pay off in some unique text parsing situations.

There are situations where the data within nodes of Xml need to be handled due to special characters or html type tags. To handle that one must place data into CData sections. This artcle shows one how to do that in .Net using C# for both the XMLDocument as well as the XDocument.

XMLDocument Example

string myXml =
@"<?xml version='1.0' encoding='utf-8'?>
<WorkingSet>
 <Data>
 </Data>
</WorkingSet>";

XmlDocument doc1 = new XmlDocument();
doc1.LoadXml( myXml );

XmlNode target = doc1.SelectSingleNode( "WorkingSet/Data" );

if (target != null)
    target.AppendChild( doc1.CreateCDataSection( "<h1>Hello</h1>" ) );

XDocument Example

XDocument doc = XDocument.Parse( myXml, LoadOptions.SetLineInfo );

XElement dataNode = doc.Descendants( "Data" ).First();

dataNode.Add ( new XCData( "<h1>Hello</h1>" ));

Console.WriteLine( doc.ToString() );

Results

<?xml version="1.0" encoding="utf-8"?>
<WorkingSet>
 <Data><![CDATA[<h1>Hello</h1>]]></Data>
</WorkingSet>

Here is an example of adding an attribute to an XmlDocument in C# and .Net. The below code reads in Xml. Where there are nodes that do not contain and ID attribute, we will add that attribute using the name as the value.

 1: public static string xmlAcct =

 2: @"<?xml version='1.0' encoding='utf-8'?>

 3: <Accounts>

 4: <acct acct='aex113' country_code='us' name='abcde' />

 5: <acct acct='aex114' name='eeaad' country_code='us' />

 6: <acct acct='aex115' country_code='us' name='eoo' id='eoo9' />

 7: </Accounts>

 8: ";

 9:

 10: public static void AddAttribute()

 11: {

 12:

 13:     XmlDocument originalXml = new XmlDocument();

 14:

 15:

 16:     originalXml.LoadXml(xmlAcct);

 17:

 18:     XmlNodeList accts

 19:        = originalXml.SelectNodes("descendant::*[name(.) ='acct']");

 20:     XmlNode temp;

 21:     XmlNode name;

 22:     XmlAttribute attr;

 23:

 24:     foreach (XmlNode current in accts)

 25:     {

 26:         temp = current.SelectSingleNode("@id");

 27:         if (temp == null)

 28:         {

 29:             name = current.SelectSingleNode("@name");

 30:             if (name != null)

 31:             {

 32:                 attr = originalXml.CreateAttribute("id");

 33:                 attr.InnerText = name.InnerText;

 34:                 current.Attributes.Append(attr);

 35:             }

 36:         }

 37:

 38:     }

 39:

 40:     Console.WriteLine(originalXml.OuterXml);

 41:

 42:

 43: }

• Line 01: Create Test XMl
• Line 16: Load the test Xml.
• Line 19: Get all the account nodes using Xpath.
• Line 24: Work through each account node to add an attribute if ID does not exist.
• Line 27: When null we need to add the ID node.
• Line 29: We will use the name as the ID.
• Line 32: We have to create the attribute off of the current node. Very important, for we can’t just slap any old node on. It has to be from the current branch/node.
• Line 40: Display the changes.

This is a quick example of loading data into and XmlDocument and then extracting data using XPath. Each of those topics have books written on them and one can surely use this sample as a starting point for that learning.

Note the Xpath used does not demonstate the full capabilities of Xpath such as one can extract attributes off of nodes using the @ sign.

 1: XmlDocument xd = new XmlDocument();

 2:

 3: xd.LoadXml(

 4: @"<?xml version='1.0'?>

 5:     <Wrapper>

 6:         <myData>some stuff</myData>

 7:         <level access='t'>4</level>

 8:         <size>medium</size>

 9:    </Wrapper>");

 10:

 11: XmlNode node

 12:     = xd.SelectSingleNode(

 13:         "descendant::*[name(.) ='myData']");

 14:

 15: Console.WriteLine("Inner Text ({0}) Outer Xml {1}",

 16:                   node.InnerText,

 17:                   node.OuterXml);

 18:

• Line 1 Create a new XmlDocument.
• Line 3 Load the Xml from a string, other ways one could load from a file.
• Line 11-13 We are interested in getting the first node encountered thats name is myData. By using the SelectSingleNode we can get just one.
• Line 13 This is a generic Xpath that I like to use which can get information from the current node looked being looked at. What it is saying is, Looking at all the decendants of the current node, give me the node where the name found is myData.
• Line 15 We are not checking to see if node is null. In normal code this is a no-no, check before usage!
• Line 16 The actual data is store in the InnerText of the node, which we will extract.
• Line 17 Sometimes we need the xml along with it, see below.

This is what the output looks like:

Inner Text (some stuff) Outer Xml <myData>some stuff</myData>

The tribal knowledge in dealing with XmlDocument in C# is that it takes the reference to a tree and its branches too literally. When pruning or adding to the tree, one must always take from the branch (node) from which it comes to do any operation.  Here are a few examples to work with the XmlDocument

Add Node With Attributes

string xml = @"<?xml version='1.0' encoding='utf-8'?>
   <menu>
    <sub name='A' value='p1.aspx'/>
    <sub name='B' value='p2.aspx'/>
    <sub name='C' value='p3.aspx'/>
   </menu>";'

XmlDocument originalXml = new XmlDocument();
originalXml.LoadXml(xml);

XmlNode menu = originalXml.SelectSingleNode("menu");

XmlNode newSub = originalXml.CreateNode(XmlNodeType.Element, "sub", null);

XmlAttribute xa = originalXml.CreateAttribute("Name");
xa.Value = "D";

XmlAttribute xb = originalXml.CreateAttribute("value");
xb.Value = "p4.aspx";

newSub.Attributes.Append(xa);
newSub.Attributes.Append(xb);

menu.AppendChild(newSub);

Console.WriteLine(originalXml.OuterXml.ToString());

The above code we had a static set of Xml, and added a node with two attributes. Here is the output (pretty printed after the fact and not by the code)

<?xml version="1.0" encoding="utf-8"?>

    <menu>

        <sub name="A" value="p1.aspx" />

        <sub name="B" value="p2.aspx" />

        <sub name="C" value="p3.aspx" />

        <sub Name="D" value="p4.aspx" />

     </menu>

Remove Node

Using the above snippet to remove the “B” node we will search for it then remove it

XmlNode bNode = originalXml.SelectSingleNode("descendant::sub[@name='B']");

if (bNode != null)

    menu.RemoveChild(bNode);

Console.WriteLine(originalXml.OuterXml.ToString());

Which produces this Output

<?xml version="1.0" encoding="utf-8"?>

    <menu>

        <sub name="A" value="p1.aspx" />

        <sub name="C" value="p3.aspx" />

        <sub Name="D" value="p4.aspx" />

    </menu>

Replace Xml Snippet

In this example we will simulate a user making a changes to an xml node say within an editor. All we know is that it has been changed, but we don’t know what. It could be either additions or subtractions of attributes and nodes; regardless it needs to replace an original item.

string xmlInitial =
@"<?xml version='1.0'?>
 <Rules>
  <OpenBalances function='ReOrderFifo'>
   <column name='SecurityID' used='True'/>
   <column name='COL2' used='False'>#@#</column>
   <column name='COL3' used='False'>#@#</column>
  </OpenBalances>
 <ClosedBalances/>
 </Rules>";

string xmlUser =
@"<OpenBalances function='ReOrderFifo' iAmNew='true'>
  <column name='SecurityID' used='True'/>
  <column name='COL3' used='True'>New Item</column>
  <column name='COL5' used='True'>Other Item</column>
 </OpenBalances>";

XmlDocument originalXml = new XmlDocument();
string targetNode = "descendant::*[name(.) ='OpenBalances']";

originalXml.LoadXml( xmlInitial );

// Simulate the selection of the subnode
// for the user to edit in the first nodes
// Rules.
XmlNode editNode = originalXml.SelectSingleNode(targetNode);

// Get a fragment and slide the changed data into it.
XmlDocumentFragment fragment = originalXml.CreateDocumentFragment();
fragment.InnerXml = xmlUser;

// Replace the contents of the editNode with the user fragment.
editNode.ParentNode.ReplaceChild(fragment, editNode);

Console.WriteLine(originalXml.OuterXml);

Here is the resulting output

<?xml version="1.0"?>
 <Rules>
  <OpenBalances function="ReOrderFifo" iAmNew="true">
   <column name="SecurityID" used="True" />
   <column name="COL3" used="True">New Item</column>
   <column name="COL5" used="True">Other Item</column>
  </OpenBalances>
 <ClosedBalances />
 </Rules>