A previous post gave some examples to illustrate how to use regular expressions as defined by the upcoming C++0x standard. The new regex features are certainly easy to use but what about the performance of some of the current implementations?

To find out, I compared the performance of the Micirosoft Visual Studio 2008 implementation against the regex implementation from the Boost library v1.36, and also against the PCRE v7.7 library. Microsoft introduced C++0x regex support in Visual Studio 2008 feature pack #1 and subsequently improved regex performance in Visual Studio 2008 service pack #1. Both the fp1 and sp1 implementations were included in the comparison analysis. The Boost library was chosen for comparison since this was the initial C++ regex implementation that was the basis for the proposal for inclusion into C++0x. PCRE was chosen for comparison since this is a very popular and in many respects the defacto regular expression library for use in C/C++ applications.

Methodology
The regular expression patterns and data strings to use for comparison were taken from here. Three patterns of various complexity were selected and each of these was run against a set of five content strings. Each pattern/string search combination was run for 10000 iterations and the elapsed time was measured for each combination. The code used to perform the test is available here. Multiple runs were conducted to ensure that the results were consistent across each run. Once all the data was gathered, the results were normalized against libPcre - hence all the graphs show libPcre at a value of 1. By taking this normalization approach it is easier to compare the relative performance of each implementation.

Results
The results are shown for each of the three patterns in the graphs below - one per pattern. The numbers along x-axis in each graph corresponds to the strings numbered 1-5 from the table above.

RegEx Benchmark - Pattern #1

RegEx Benchmark - Pattern #2

RegEx Benchmark - Pattern #3

Based on the data shown in the graphs, a number of observations can be made:

1. libPCRE v7.7 has the best performance for all pattern / string combinations.
2. Performance varies significantly for different patterns. For example, for pattern #1, the boost implementation was faster than either of the Visual Studio 2008 (vc9) versions, but was slower for patterns #2 and #3. This seems to suggest that the Visual Studio 2008 implementations show relatively poor performance for patterns that contain alterations and a number of groups and nested groups.
3. Based on patterns #1 and #2 the Visual C++ regex implementation performance has improved as claimed between feature pack 1 (fp1) and service pack 1 (sp1) but this is not completely true as can be seen from the pattern #3 results.

Conclusion
While the C++0x regex library makes it easier to use regular expressions in C++ code, there are still some performance gaps between the Visual Studio 2008 implementation and the performance of existing regular expression libraries such as libPCRE.

Note: The data shown in this article is based on a small sample of regular expression patterns and content strings and so the results should be taken in that context.

RUBY
The standard C implementation of Ruby 1.x (current version: 1.9) implements threading as green threading, where all threads are serviced by a single OS level thread and the Ruby runtime has full control over the thread life cycle. As described in the Ruby wiki, Ruby’s thread scheduler is a simple cooperative timeslicing scheduler with control switching to another thread if certain well defined keywords or events are encountered. There is also a 10ms timeout period to prevent too many context switches occurring (i.e. in general a max of 1 context switch every 10ms).

This use of green threads imposes severe scaling restrictions for Ruby applications that are CPU bound since the use of a single native OS thread limits the Ruby application to run on a single CPU core. IO bound Ruby applications can employ threading to a certain extent to parallelize waiting on IO operations but even this is limited by the 10ms minimum context switch time which has the effect of limiting the number of threads that can run within a Ruby application. Due to this limitation, scalability of Ruby applications appears to be solved today by splitting the application and running it in multiple processes which can then be run on different cores.

There is some hope in store though in that using native OS threads instead of green threads is being considered for Ruby 2.0 and there are some implementations of Ruby such as JRubywhich currently implement Ruby threads using native OS threads (via Java though for JRuby).

PYTHON
In contrast to Ruby, Python threads are implemented using native OS threads and so it is possible for different Python threads within a single application to run on different cores on a multi-core processor under the control of the OS scheduler. However, Python threading has a serious limitation in the form of the Global Interpreter Lock(GIL). This is a global lock that must be held by the current thread before it can safely access Python objects and only the thread that has acquired the global interpreter lock may operate on Python objects or call Python/C API functions. In order to support multi-threaded python programs, the interpreter regularly releases and reacquires the lock - by default, every 100 bytecode instructions. C extensions can release and reacquire the lock using the Python API and so this offers some relief, but the lock must be acquired before the state of any Python object is accessed.

Similar to Ruby, this GIL effectively limits the performance of CPU bound Python applications to that of a single CPU core (since only one Python thread can run at a time). Scalability is available for IO bound applications as these can easily scale across cores and the “one at a time” model of the GIL does not significantly restrict the performance of threads that are highly IO bound. Some relief is available by being able to implement performance and lock optimized C extensions but this is very restrictive and cumbersome - certainly a lot harder than writing some Python code.

Given this serious restriction of the Python threading model, you would expect it to be possible to replace the GIL with more fine grained locking, but apparently it has been tried and there are some reasons why we can’t get rid of the global interpreter lock. When fine grained locking was tried as a patch to Python 1.5, a 2x slowdown was observed. The slowdown was attributed to the overhead of the acquiring/releasing the OS locks. This patch hasn’t been maintained for subsequent versions of Python. Another patch that is gaining popularity and actively being maintained is python-safethread. This is a set of Python extensions that is “intended to provide safe, easy, and scalable concurrency mechanisms. It focuses on local concurrency, not distributed or parallel programs.” While it is not yet part of the Python mainline but it is certainly a promising solution to the GIL issue.

Update: Thanks to Adam Olsen for pointing me towards python-safethread as a possible solution to the GIL.

Six regular expression grammars will be supported in C++0x. The default is based upon the ECMAScript grammar specified in ECMA-262. This syntax is based upon the PCRE syntax and is used by languages such as Perl, Python and Ruby which also provide built in regular expression support. Other supported grammars include the POSIX regex syntax, and the syntaxes used in tools such as awk, grep and egrep.

Here are some examples that illustrate how to perform some basic tasks with the new C++ regex component of the standard library.

Header files and namespaces:

#include <regex>

using namespace std::tr1;

Finding a match:

regex rgx("ello");
assert(regex_search("Hello World", rgx));

The above example illustrates the construction of a regex object, with the regex pattern being passed as a parameter to the regex constructor. The regex object is a specialization of the basic_regex template for working with regular expressions which are provided using sequences of chars. The regex_search()function template is then used to see if the “Hello world” string contains the “ello” pattern. This function returns true as soon as the first matching substring is found. The regex_search()function is also overloaded to provide versions that take sequence iterators as params (instead of a full string) and also versions that provide additional info on the match results.

Note: The use of assert() in the examples is used to highlight the “contract” provided by the api - e.g. to highlight if a function can be used in a conditional expression and if the function should return true or false for the particular example.

Finding an exact match:
The regex_match() function template is an alternative to regex_search() and is used when the target sequence must exactly match the regular expression.

regex rgx("ello");
assert(regex_match("Hello World", rgx) == false);
assert(regex_match("ello", rgx));

Finding the position of a match:
The sub_match or match_results template is used to receive search results from regex_search(). When searching char data, the library provides a ready made specialization of match_results called cmatch.

regex rgx("llo");
cmatch result;
regex_search("Hello World", result, rgx);
cout << "Matched \"" << result.str()
    << "\" after \"" << result.prefix()
    << "\" at offset: " << result.position()
    << " with length: " << result.length()
    << endl;

Working with capture groups:
Capture groups provide a means for capturing matched regions within a regular expression. Each captured region is represented by a sub_match template object. The smatch specialization of match_results is provided by the library for working with sequences of string sub-matches.

string seq = "foo@helloworld.com";
regex rgx("(.*)@(.*)");
smatch result;
regex_search(seq, result, rgx);
for(size_t i=0; i<result.size(); ++i)
{
cout << result[i] << endl;
}

Case insensitive searches:

regex rgx("ello", regex_constants::icase);
assert(regex_search("HELLO WORLD", rgx));

import thread

def someFunc():
    print "someFunc was called"

thread.start_new_thread(someFunc, ())

This approach has a limitation in that once the start_new_thread() function is called, it is not possible to find out when the thread has finished or to wait for completion of the thread. This may be acceptable for many applications but may be too restrictive for others. Note that function parameters can also be passed in a tuple (use an empty tuple if there are no parameters) as the second argument to start_new_thread().

Python also provides the threading module which implements a layer on top of the thread module. The threading module provides, among other things, a Thread class which contains a run() method. Typical usage is to subclass the Thread class and override the run() method in the subclass to implement the desired functionality. The Thread class also provides start() and join() methods to control the starting of a thread and to provide a mechanism for waiting until the thread has finished execution (i.e. the end of run() method is reached).

Without sub-classing, it is possible to pass a function or other callable object to the Thread class constructor to specify the target that the run() method will call. This is illustrated below.

import threading

t1 = threading.Thread(target=someFunc)
t1.start()
t1.join()

This approach works well for providing a mechanism for waiting for the thread to complete. A drawback to this approach though is that it is not possible to pass any arguments to the function supplied as the thread’s target.

If waiting for thread completion and argument passing is required it is necessary to provide a subclass of Thread. The function to execute and its arguments can be passed to the subclass constructor. This is illustrated below:

import threading

class FuncThread(threading.Thread):
    def __init__(self, target, *args):
        self._target = target
        self._args = args
        threading.Thread.__init__(self)

    def run(self):
        self._target(*self._args)

# Example usage
def someOtherFunc(data, key):
    print "someOtherFunc was called : data=%s; key=%s" % (str(data), str(key))

t1 = FuncThread(someOtherFunc, [1,2], 6)
t1.start()
t1.join()

The volatile keyword does a very simple job. When a variable is marked as volatile, the programmer is instructing the compiler not to cache this variable in a register but instead to read the value of the variable from memory each and every time the variable is used. That’s it - simple isn’t it?

To illustrate the use of the keyword, consider the following example:

volatile int* vp = SOME_REGISTER_ADDRESS;
for(int i=0; i<100; i++)
    foo(*vp);

In this simple example, the pointer vp points to a volatile int. The value of this int is read from memory for each loop iteration. If volatile was not specified then it is likely that the compiler would generate optimized code which would read the value of the int once, temporarily store this in a register and then use the register copy during each iteration.

Examples of where volatile is often used:

• When accessing hardware registers via pointers. It is necessary for the generated code to always access the hardware registers value and never a potentially out of date copy.
• When accessing a variable that is shared between two or more threads or between a thread and an ISR.

Common myths about the volatile keyword:

• A volatile variable will never reside in cache memory - e.g. within the L2 cache of a processor. This is not true. In the case where the volatile variable is shared between two software threads, it is highly likely that the variable will exist in cached memory and the cache coherency policy will ensure that the threads will see the correct and up-to-date value of the variable in the event that the threads are running on seperate cores that don’t share the same cache. When the volatile variable refers to a hardware register, it is likely that the memory map of the system will be setup such that this register is not cacheable in the processor cache, but this is setup and managed by the appropriate device driver and is not something that is provided by the volatile keyword.

Thats’ it. So the next time you hear somebody waxing lyrical about the super powers of the volatile keyword, please feel empowered to enlighten them!

Consider the following example:

memcpy((void* restrict) dst, (void* restrict) src, size);

This tells the compiler that neither the dst or src pointer paramters overlap and so the compiler is free to apply any optimizations - including optimizations that may result in out of order reads/writes.

Mainstream compilers have varying support for this feature.

• GCC supports it in C99 mode  - specified via the “-std=c99″ option or for non-C99 code by specifying __restrict to enable the keyword as a GCC extension.
• Microsoft’s Visual Studio .NET 2005/2008 compiler doesn’t support this feature as specified in the C99 standard but does provide similar support using the __restrict specifier. Micorosft also allows this keyword to be specified for both C and C++ code. See the MSDN documentation for more details on Microsofts implementation and differences between it’s support and the C99 specification of restrict.

Finally, it should be noted that this keyword is specific to C and is not specified in the 1998 C++ specification nor is it currently planned for inclusion in the fothcoming C++ specification update.

References:

• MSDN documentation on restrict keyword
• Demystifying The Restrict Keyword

So why the move? The main reason was because I found the blogger interface a bit cumbersome for posts that involved source code. I was underwhelmed by the presentation of source code that resulted from <code> and <pre> tags. It was also a pain to have to remember to properly handle the angle brackets and ampersands in the code. I decided to move from blogger to WordPress so that I could take advantage of it’s syntax highlighting plugin which is based on the syntaxhighlighter Google Code project by Alex Gorbatchev. Check out the following snippet - cool or what?

#include <iostream>

using namespace std;

int main()
{
    cout << "Hello World" << endl;
    return 0;
}

Rather than moving the blog from stephendoyle.blogspot.com to something like stephendoyle.wordpress.com or softwareramblings.wordpress.com I decided to move the blog to it’s own domain. Since the blog was entitled “Software Ramblings” and the domain of the same name was miraculously free, my mind was made up.

However, I was very surprised to find that it does not appear to be possible to do this on OS X! 

OS X Leopard introduced a thread affinity API which provides the ability to provide affinity hints to the scheduler to improve data locality in caches. Unfortunately this API does not provide the ability to tie a thread to a core. This is a major gap, especially now that all new PCs and laptops are multi-core.

So why do I want to be able to tie a thread to a core? I want to benchmark a piece of code and one of the data points of interest is to benchmark this code on a single core. With the current Mac OS X thread affinity API, this is not possible!

I’m finding it hard to believe that this service does not exist on OS X - I mean surely somebody must have wanted to run a single core benchmark on OS X running on a multi-core system. But after a couple of hours of googling and reading through the OS X APIs I have been unable to find out how to do this.

After browsing through some of the blog entries on the site and from one of its user groups, I am reminded of the resonant style of the Pragmatic Programmer book. It has the same practical and pragmatic feel. 

Some entries / articles that I found interesting:

• What is a Software Architect?
• Role profile for software architects
• Sharing Architectures
• Software Architecture Document Guidelines

I am constantly amazed by the vast number of different applications for managing ToDo lists that have emerged. They range from very simple single list tools, to complex tools that are more suited towards project management than they are for keeping track of what to get during the next visit to the shops.

ToDo list applications need to feel right when you are using them. I have all too often had the experience of trying out a particular ToDo list application only to find that it constrains my usage model in some way. I then spend a couple of days/weeks trying to adapt my usage model to the constraints and model offered by the application. I eventually get too frustrated and give up. I am convinced at this stage that different people are tuned to different ToDo list application features and that there is no one “ToDo list model” that fits all. In spite of this, I believe that I have found the magic ToDo list application that seems to fit most usage models - or at least it doesn’t provide any constraints about how to manage your ToDo lists so you have the freedom to manage them whatever way you like.

After trying 20+ different applications over the past 10 or so years, I constantly return to Abstract Spoon’s ToDoList application. This is without doubt one of the most flexible ToDo list managers out there and it acquires new features at a fast pace. This application really defines the meaning of feature rich. I have used it successfully for managing simple lists, project scheduling, time tracking, and SCRUM backlogs, burndown charts and even for online SCRUM boards. It is difficult to describe its feature list in a simple blog post so I encourage you to download it and give it a twirl.

The only downside that I have encountered with this particular application is that it is Windows specific. I’m sure that ports of this application to different OSes will occur with time but for the moment the cost of its excellent flexibility is only being able to use it on your Windows box(es).