Dale Bruce Hopkins

Any time it is possible to reduce the coupling of code it is generally a good idea.  This makes the code more easily adapted to reuse and easier to maintain.  I wanted to take a minute to discuss how we used Events and Delegates to do just that and, perhaps as interesting, is how we did it using C++ which does not have built in support for Events and Delegates.

The Problem
This code was written for the LucidHelix Terrier project, which is an MPEG-2 diagnostic tool.  One of the common tasks in parsing MPEG-2 transport streams is parsing Service Information (SI) tables.  There are a number of higher level modules that have use for parsing these tables and thus the code for parsing them is used frequently.  When parsing SI tables out of a stream there are a number of events which may be note worth:

• An SI table was parsed
• A new version of the SI table was received
• There was an error parsing an SI table

The problem is that when writing the code to parse the SI table, we didn’t know all of the modules that would be interested in this information when we wrote it, and we really didn’t want the parsing code to care who or how many people were interested in the information.

Using Events and Delegates
The solution we decided to go with was for the SI table parsing objects to have public member ‘Events’ that would be raised upon note worthy conditions occurred while parsing the data.  Interested classes can then subscribe to the events by passing a delegate, which for simplicity can be though of as a specialized function pointer.  In the .NET framework there is built-in language support for raising events and delegates, but this is not the case in the C++ language.

Boost to the Rescue
As often is the case when C++ is missing a feature you want, we found that the Boost libraries offer a simple module to provide the functionality required!  The boost “signal2″ module is a header-only implementation of Event for C++.  They use slightly different terminology so if you are comparing a Boost “Slot” is what I am calling a delegate and a Boost “Signal” is what I am calling an event.

The next issue is that working with function pointers is difficult in C++ because of the distinction made between member function pointers and non-member function pointers.  Luckily Boost can help us again with the “bind” module.  This allows one to easily set functions (member or non-member) as the delegate for an event.

Final Thoughts
By using Events and Delegates we successfully decreased the coupling of the application.  The SI table processing code has no knowledge of who is listening to the events it raises, and thus it is not dependent on any particular module or group of modules to function.  It actually allowed us to change at run-time the group of listeners to match the functionality requested by the user.

It seems that XML data is everywhere these days.  A while back we had a project that involved processing streams of XML data.  Parsing XML data is a complex process, but luckily there is a huge number of XML parsing libraries for you to use (if you are a PHP user, then these libraries are even built in!).  These parsers can be divided into 2 groups based on the interface they provide to your applications: SAX and DOM.

DOM Parsing For Small XML Files
When the amount of XML data you want to parse is small (a few MB or less) then DOM parsing is often the easiest way to parse the file.  A DOM parser parses the XML document in its entirety and provides a Document Object Model (DOM) to your application.  This DOM is a tree data structure that contains all of the data for the XML document.  Once you have a DOM, you can use XPath queries to extract data from the DOM.

The DOM model also shines when you need to perform lots of queries on the data because regardless of the dependencies of those queries the XML file is only parsed once and the DOM is efficient to query.

The problem with DOM processing is the fact that the entire XML document has to be parsed at once, and a DOM representing the whole document needs to be created in memory.  This works great on a 1 MB XML document, but it is expensive with 100 MB XML file, and it is crazy with a 4 GB XML document!

SAX Parsing for Large XML Files
When parsing larger XML files a SAX parser is a better choice.  A SAX parser provides a tree iterator interface to the XML file.  This means that you get the following general operations.

• Iterate to next node (XML element)
• Read Attributes of current Node
• Read character data of current Node
• Read XML content of current Node

This means that parsing XML with a SAX parser is more involved than using XPath with a DOM object!  The key benefit is that this method can have extremely small memory requirements that do not depend on the size of the XML document.  In our case we needed to read XML data from a webservice to update a local database copy.  The SAX processor allowed us to process the > 1GB data files with less than 1MB of memory and over 100x faster than the original DOM implementation!

The Best of Both Worlds?
Sometimes the situation arises where you have a large XML file containing a large number of small items.  You would like to perform XPath queries on the individual items rather than writing custom SAX code.  The solution to this problem can be to use a SAX parser to extract XML nodes from the document (Read XML content of current Node) and to then use a DOM parser on those small elements!

This particular approach only works if you have a large XML document that is comprised of a large number of smaller objects that you want to deal with in isolation.  If you have a large XML file that you want to query large sections, you are often stuck choosing between DOM and SAX parsing.

Multithreaded programming is difficult.  The problem is that as soon as you introduce multiple threads, the flow of your program is no longer linear.  Race conditions arising from multithreaded programming are also some of the toughest bugs to find, reproduce, and fix.  No wonder most people avoid multithreaded programming!  Some people even suggest avoiding this practice all together [reference].  Don’t worry, I’m not here to talk about problems, I’m here to talk about solutions

The most common reason I’ve had for doing multithreaded programming is to deal with truly parallel data.  In my case, I have dealt with processing multiple live MPEG-2 Transport streams and providing access to the resulting data over a webservice.  This problem was encountered when developing the Terrier product at LucidHelix Solutions.

Synchronize with Mutexes?
In order to syncrhonize all of these threads we started by using Mutexes to protect shared resources.  This worked well until the volume of data increased and the number of mutex operations started to get into the 1000′s of locking and unlocking operations per second.  At that point everything ground to a halt because everytime you use a mutex a context switch is required to access the underlying kernel synchronization construct!

We quickly discovered that we could not use mutex lock acquisition to protect the resources, but we needed some way to synchronize the data.

FIFOs and Spin locks to the Rescue!
At this point we decided that it was necessary to take a more intelligent look at how the data was being processed and see if we could avoid the need for synchronization.  Having worked with FPGAs in the past, we realized that the multithreading problem is similar to the problem of crossing clock-domains in FPGAs.  The standard solution to the clock-domain crossing problem is a FIFO.  The FIFO is divided into 2 pieces, allowing one thread or clock-domain to feed the input and read the free space available and one thread tor clock-domain to pull the output and read the amount of data in the FIFO.  The key to this working is that no locking is required to write into the FIFO when there is free space, and no locking is requried to read data from the FIFO when there is data in it.

This turned out to be a great way to pass data from the multiple threads reading data to the threads processing that data.  Because the data was continuous the threads processing data use a spinlock to wait for data to come available, which turned out to be significantly less overhead than any kernel-level synchronization

What about the Webservice?
The other synchronization issue came with the need to access the data being processed from the multiple webservice threads.  This problem was different because data being synchronized was not a continuous stream of data, but rather a set of changing data structures.  The webservice would only ever have 10′s of requests per second so the overhead of synchronization on those threads was much lower.  The solution involves a few instance variables on the data processing thread:

• shouldCopy – indicates whether or not the live data should be copied to a buffer for the webservice thread if an update happens, or if we should wait
• updateAvailable – indicates whether the latest data available is newer than the copy made available to the webservice
• currentlyCopying – set (if shouldCopy is 1) before copying data to the webservice buffer and cleared afterward

The webservice threads then simply do the following to ensure the copy available to the webservice threads is never overwritten while being read:

1. Wait on a mutex shared by all webservice threads so only one thread at a time can be accessing the mutex.
2. Set shouldCopy to 0
3. SpinLock until currentlyCopying is 0
4. Use the data
5. Set shouldCopy to 1
6. Release the mutex

This means that the data processing thread, which accesses the data 1000′s of times per second, never uses any kernel-level synchronization constructs.  Meanwhile the webservice thread, which accesses the data at most 10′s of times per second, uses a single Mutex to synchronize access between itself and other webservice threads.

Conclusion
The lesson learned from all of this for us was that multithreading is a problem that needs to be carefully approached and that with some careful planning one can minimize the amount of synchronization overhead.  By minimizing synchronization you maximize the speed of your software as we see the number of cores and processors in machines increasing, while clock speeds remain stationary.