Using My STM Library

As promised yes­ter­day, I’d like to show off a few bits of my STM library. Of course it’s far from done, and is still miss­ing sev­eral key fea­tures, but the core library is in pretty good shape. So as they say on the inter­nets, “my STM library, let me show you it”

In the fol­low­ing, I’ll show a slightly mod­i­fied ver­sion of one of my test cases. It shows how to call and use my library, from the user’s point of view. The test spawns a num­ber of threads, which each wait on a bar­rier (because if one thread was allowed to run while another was being con­structed, I’d get fewer con­cur­rent trans­ac­tions, and my test would be less likely to uncover race con­di­tions), and then per­form a fixed num­ber of trans­ac­tions. In each trans­ac­tion, two trans­ac­tional vari­ables are opened for writ­ing, one is decre­mented and the other incre­mented. If the sum of these vari­ables is nonzero in any iter­a­tion, the thread reg­is­ters a failure.

And if, after all the threads have ter­mi­nated, the value of each of these vari­ables is not what was expected, a fail­ure is reg­is­tered as well.

So from a test­ing point of view, there should be plenty of oppor­tu­nity for things to go wrong. Just a sin­gle small race con­di­tion some­where, and one of the many mil­lions of reads would be incon­sis­tent and the test would fail.

#include <stm.hpp> // my STM library

#include <boost/test/unit_test.hpp> // Boost.Test is used to supply a unit-testing framework
#include <boost/thread.hpp> // Boost.Thread is used as a threading API

// define the number of threads to run, and the number of iterations for each
enum { thread_count = 8, iterations = 200000 }; 

// The following are transactional variables. The shared template ensures that the contained value
// can only be accessed as part of a transaction, and provides the necessary metadata
// for checking validity and consistency
// Two such integers are created, both initialized to zero
stm::shared<int> val1(0);
stm::shared<int> val2(0); 

BOOST_AUTO_TEST_SUITE( threads ) // define a test suite named "threads"

// this function defines the body of our transaction. 
// We're passed a transaction, which can be used to open any "shared" variables
bool tx_func(stm::transaction& tx){
    // open both variables for writing
    int& a = val1.open_rw(tx);
    int& b = val2.open_rw(tx);

    // modify the variables freely
    --a;
    ++b;

    return a + b == 0; // Our transaction returns a bool. Other return types (or void) are also supported
}

// this class defines a thread. operator() is called as the thread's entry point
struct thread_functor{
    // In the constructor, the thread object is given a barrier it can synchronize on,
    // and a reference where it can write the its result (success/failure)
    thread_functor(boost::barrier& bar, int& res) : bar(bar), res(res) {}

    void operator()(){
        // when the thread is first created, we wait for the barrier
        // This ensures that no transactions are running until all threads have been constructed
        bar.wait(); 
        for (int i = 0; i < iterations; ++i){
            // for each iteration, pass our transaction function to the "atomic" function, which executes it atomically.
            // To get a non-void return type, we have to specify the template parameter explicitly 
            // (this can be avoided in C++0x using the return_of template to deduce the return type implicitly)

            // depending on the return value of the transaction, write success or failure back
            res = (res != 0) && stm::atomic<bool>(tx_func) ? 1 : 0;
        }
    }

    boost::barrier& bar;
    int& res;
};

// another transaction, to be executed after our helper threads terminate, 
// to verify that the right number of modifications have occurred
// note that here variables are opened for reading only
void verify(stm::transaction& tx) {
    const int& a = val1.open_r(tx);
    const int& b = val2.open_r(tx);

    BOOST_CHECK_EQUAL(-a, thread_count * iterations);
    BOOST_CHECK_EQUAL(b, thread_count * iterations);
}

// finally, we get to our test case itself
BOOST_AUTO_TEST_CASE ( short_concurrent_transactions )
{
    boost::barrier bar(thread_count);
    boost::thread_group gr;
    int res[thread_count]; // array of results
    // set all the results to an initial true/1 value (since each iteration "and"'s it together with the current result
    std::fill(res, res+thread_count, 1); 

    for (int i = 0; i < thread_count; ++i){
        gr.create_thread(thread_functor(bar, res[i])); // create the threads, passing the necessary parameters to each
    }

    gr.join_all(); // wait for all threads to terminate

    // verify that each thread return success
    for (int i = 0; i < thread_count; ++i){
        BOOST_CHECK_EQUAL(res[i], 1);
    }

    // run a final transaction to access both variables and check their final values
    stm::atomic(verify);
}

BOOST_AUTO_TEST_SUITE_END()

In the above, I used a func­tion object to rep­re­sent threads, and a reg­u­lar func­tion to rep­re­sent trans­ac­tions. Of course in both cases, either would work — a func­tion object would poten­tially be more effi­cient as it is eas­ier for the com­piler to inline, but I used a func­tion for brevity.

In C++0x, of course, lamb­das could also have been used in both cases.

One of my design goals has been to make basic usage as sim­ple and intu­itive as pos­si­ble, and I think I’ve suc­ceeded so far. Any C++ pro­gram­mer who is famil­iar with the STL algo­rithms or the Boost libraries, should find my library’s inter­face very straight­for­ward. Note espe­cially that all the trans­ac­tion “magic”, of ver­i­fy­ing valid­ity and retry­ing trans­ac­tions as needed, is com­pletely invis­i­ble to the user. You sim­ply define a func­tion express­ing what your trans­ac­tion should do, and pass it to the atomic function.

In its cur­rent ver­sion, this test is able to exe­cute around 1,800,000 trans­ac­tions per sec­ond on my Core Duo 2GHz lap­top. (Of course, with trans­ac­tions as small as these, open­ing only two vari­ables each, per­for­mance is a lot bet­ter than it would be in real-world transactions.

So that’s it for now. Of course I’ve got a few more user-facing fea­tures in the pipeline¹, and a lot of back­end changes, but the basic func­tion­al­ity is there, and I’m pretty happy with it so far.

Tags: c++, stm, thesis, transactional-memory

Programming | RSS 2.0 | Respond | Trackback |