ACE recursive mutexes vs. STL recursive mutexes

In the MADARA engine, we must use recursive mutexes to protect the underlying dictionary-based shared knowledge. Since 2008 or so, we have been using ACE_Recursive_Thread_Mutex to protect our critical sections, but I have been following the C++11 spec with especial interest. The goal of MADARA is portability and speed across platforms like Windows, Linux, ARM, Intel, Mac, Android, etc. and ACE was a natural choice because of its platform support but also because of its well-tested code base and community development. Over the past five years or so, the community that supports and uses ACE has dwindled, and there has been a push within the C++ community to use libraries like Boost and STL mutexes, which are basically Boost libraries that have been standardized.

But for a middleware like MADARA that is especially concerned with performance on low-powered processors for robotics systems, it's not just about how excited the C++ community is about a particular library, it's also about speed and efficiency. So, to make our own decision on whether or not the C++11 spec was ready for primetime in portable middleware, I incorporated new features into the MADARA build process to allow for null mutexes (essentially no-ops that do not actually protect multi-threaded access), STL recursive mutexes, and our current usage of ACE recursive mutex in an extensible way. After seeing the results, I retrofitted test_reasoning_throughput (one of our standard tests for performance measurements on a target platform) to include breakdowns of C++ STL mutex and recursive mutex against the ACE implementations of ACE_Thread_Mutex and ACE_Recursive_Thread_Mutex.

First, the results of the direct comparisons of ACE mutexes and STL mutexes for g++ and Visual Studio 2015.

Settings
CPU: Intel® Core™ i7-4810MQ CPU @ 2.80GHz × 4
Linux: Ubuntu 14.04
g++ -v:Version Info
Windows: 7, Sp 1
Visual Studio: 2015
Results are reported in average nanoseconds per operation in 100k operations performed.

As you can see from the above direct comparison, the g++ STL C++11 mutexes are roughly the same performance as the ACE Recursive Mutexes. The Visual Studio 2015 performance is supposedly much better than the Visual Studio 2013 performance, but I could not get my installation of Visual Studio 2013 to handle the STL mutex library correctly at runtime (it compiled fine but just seemed to stall for no reason). For completeness, I've included a bunch of C++ operations with no mutex usage in the breakdown as well. This is information also printed in our test_reasoning_throughput test.

Now, MADARA itself performs knowledge and reasoning operations for shared information in a distributed system. The test_reasoning_throughput tests many simple operations on the MADARA knowledge bases, using these recursive mutexes often in nested ways. It also enforces quality-of-service policies and various checks about knowledge consistency, time, and various other attributes. In short, it does useful things within the critical section.

The following table uses the same hardware, operating systems, and compilers to check performance of basic operations in MADARA.

Most of our current generation of MADARA software uses KaRL containers (the last line in the above check). Another thing we optimize for are large Knowledge and Reasoning Language (KaRL) programs, which fall into the 2nd and 4th row of the above table. From these metrics, the ACE Recursive Thread Mutex is still the way for us to go. However, the performance of std::recursive_mutex in g++ is promising. Hopefully, the performance of the Visual Studio STL mutex library will catch up. After all, they have 30 years of open source code to look to for inspiration ideas... if they care to open a web browser.

Performance Increase in MADARA KaRL

The new built-in features in KaRL have resulted in very noticeable performance increases. Below are the changes in performance. These are reported timing metrics from the test_reasoning_throughput test, available in the source code repo ran on a Intel Core Duo with 4 GB RAM, but only using ~330 KB of memory for the test.

BEFORE indicates timing values before providing compiled expressions that circumvented the std::map lookups for KaRL logics and the built-in changes to the variable indexing which were incurring the same type of std::map overhead with each variable lookup. The AFTER indicates timing values after providing the built-in variable lookups with constant time was implemented. The AFTER WITH COMPILED indicates the timing for both changes.

Execution times

BEFORE	for(1->10,000) ++var 997 ns ++var; x 10,000 502 ns for(1->10,000) true => ++var 1000 ns true => ++var; x 10,000 597 ns
AFTER	for(1->10,000) ++var 642 ns ++var; x 10,000 248 ns for(1->10,000) true => ++var 637 ns true => ++var; x 10,000 357 ns
AFTER WITH COMPILED	for(1->10,000) ++var 266 ns ++var; x 10,000 169 ns for(1->10,000) true => ++var 269 ns true => ++var; x 10,000 196 ns

What does this mean to you as a developer?
It means you can develop C++ applications that link to our library and evaluate knowledge operations at around 6 mhz before disseminating your knowledge updates across the network using DDS or whatever transport you want in microseconds. It means that knowledge and reasoning can be included in online, mission-critical real-time systems, and you no longer have to use reasoning engines that take milliseconds to evaluate rules, limiting you to hz and not khz or mhz, in our case.

This engine was already increasing the state-of-the-art speeds for knowledge evaluation in real-time systems before these changes, but we also have plans for hopefully blowing this out of the water by using templates instead of virtual functions in our current expression tree formation. This will require either rolling over to the boost::spirit template meta programming lexical parser approach or rolling our own. I'll keep you posted. Right now, updates to CID and KATS for automated, adaptive deployments are taking priority.

New Features in MADARA KaRL

The MADARA Knowledge and Reasoning Language (KaRL) has undergone some major changes recently that should provide developers with a faster, more flexible reasoning engine. In this post, we’ll outline features like explicit compilation of KaRL logics and implicit compilation of variable references, and the timed wait operation. Along the way, we'll show how to use the atomic pre- and post- prints for evaluations or wait statements.

Originally, the KaRL engine created an expression tree and then cached the expression tree in an STL string to expression tree map. This feature still exists, but we noticed that the string lookups were taking quite a bit of time. In the worst case, such string lookups can take O(m log n), where m is the length of the string and n is the number of compiled logics. This is quite a long time to grab a cached tree.

The same search complexity was limiting the execution of our KaRL interpreter logic as well. With each variable lookup, we perform a lookup in an STL string to long long tree map. Depending on the length of the variable and the number of variables, this could again take a while.

Not anymore.

Developers may now compile KaRL logics directly with a call to the compile function, the result of which can be used to directly reference the expression tree. Additionally, underneath the hood, we have rewritten the variable node in the expression tree so that it directly manipulates the underlying Knowledge Record in the Thread Safe Context (and does so without entering or leaving the mutex). This resulted in increasing the speed of the engine by a factor of 3-4x, depending on how the logics were being processed. Keep in mind that this speed up factor was achieved on an already state-of-the-art reasoned that was capable of 2 million knowledge operations per second (~500 ns per operation).

When using a C++ for loop to call the reasoning engine, these changes improved our performance from ~1us per operation to ~250ns. Larger logics, where internal optimizations are possible, have been improved from ~500ns per operation to ~190ns. This means that the KaRL engine can now processes knowledge operations at over 5mhz—5 million operations per second.

The implicit compilation is included in all knowledge calls, but the explicit compilation can be done via the following:

---


// Initiate knowledge base with no transport
Madara::Knowledge_Engine::Knowledge_Base knowledge;

// new classes for evaluation settings and compiled expressions
Madara::Knowledge_Engine::Eval_Settings settings;
Madara::Knowledge_Engine::Compiled_Expression compiled;

// compile the expression and save it into compiled
compiled = knowledge.compile ("invariant => (++.count ; someother.condition => status = 5)");

// evaluate the expression with the default settings
knowledge.evaluate (compiled, settings);


---

You can see other examples of using these new features in the test for reasoning throughput.

We’ve also added the ability to do timed waits instead of indefinite blocking waits on knowledge expressions. This allows for a calling C++ program to wait for a specific time interval for the knowledge expression or KaRL logic to become non-zero, and if the time interval passes, returning control back to the caller. The underlying mechanisms are similar. The KaRL engine aggregates any changes to variables within the logic evaluation and sends updates to other interested network entities over the DDS transport.

You can find examples of how to use this in the timed wait tests. I include an example below:

---


// Initiate knowledge base with no transport
Madara::Knowledge_Engine::Knowledge_Base knowledge;

// new classes for wait settings and compiled expressions
Madara::Knowledge_Engine::Compiled_Expression compiled;
Madara::Knowledge_Engine::Wait_Settings wait_settings;

// simple expression that will always evaluate to zero
std::string logic = "++.count && 0";

// set the wait settings to a polling frequency of once
// a millisecond and a maximum wait time of 10 seconds
wait_settings.poll_frequency = .001;
wait_settings.max_wait_time = 10.0;

// create atomic pre and post print statement
wait_settings.pre_print_statement =
"WAIT STARTED: Waiting for 10 seconds.\n";
wait_settings.post_print_statement =
"WAIT ENDED: Number of executed waits was {.count}.\n";

// compile the simple zero logic
compiled= knowledge.compile (logic);

// wait on the expression with the timed wait semantics
knowledge.wait (compiled, wait_settings);


---

The implications of the time-based waiting mechanism are pretty big, and these changes will eventually make their way into the KATS framework to allow for even more flexibility with automated tests and deployments in the form of fail and success condition executions of deployment elements. Combined with the new redeployment framework changes, the MADARA suite of tools should help a lot of distributed, real-time and embedded developers better reach their project goals. If you have any questions or comments about the implementations of these features or how you can use them in your projects, please let me know. MADARA is completely open source under a BSD license.

The KaRL Automated Testing Suite

So, we've submitted our first paper highlighting the KaRL Automated Testing Suite (KATS) to GPCE 2011, and the features of the toolset have really blossomed in the past month. KATS is a suite of tools that automate distributed deployment and testing in a cross platform way. This means that you can use KATS on a hybrid test bed with Windows and POSIX machines, and each of the machines will work together to accomplish distributed, automated testing.

The core of the KATS system is the KaRL reasoning engine, which provides the testing suite with a distributed knowledge and reasoning engine based on the anonymous publish/subscribe paradigm. The infrastructure is consequently host-agnostic, resulting in the ability to move tests between hosts without much difficulty. Tests can be started via cron jobs, and they will barrier and synchronize if needed.

One of the more interesting parts to the KATS system is the Generic Modeling Environment (GME) paradigm for visually modeling tests. You can read more about how to obtain and use KATS and its GME paradigm at the following links.

Links:

• Installation Guide for Linux and Windows
• Tutorial for modeling KATS tests in the KATS GME paradigm
• Advanced KaRL Automated Testing Suite (KATS) features

We're currently using KATS to model and execute distributed tests for smart phones and C++ services connected to and running on various host platforms. You can find out more at the links above.