Title: Const and Concurrency (Part 1)

Author: Martin Moene

Date: 07 November 2014 15:36:22 +00:00 or Fri, 07 November 2014 15:36:22 +00:00

Summary: Ralph McArdell comments on comments to Herb Sutter’s updated GotW #6b solution.

Body: 

I have been following Herb Sutter on his Sutter’s Mill [1] website and while reading, in 2013, GotW #6b Solution: Const-Correctness, Part 2 [2] and the comments subsequently posted, some thoughts popped into my head.

For those in need of a reminder or enlightenment, GotW is the commonly used short-form term for Herb Sutter’s ‘Guru of the Week’ C++ posers. The ‘GotW #6b Solution: Const-Correctness, Part 2’ article is Herb’s posted solution to the GotW #6b poser which concerns consistent usage of const and mutable in C++ to write safer code. The posed task for which the article provides Herb’s solution is to add or remove const to/from the shown polygon class which caches the result of area calculations, with bonus points awarded if you could point out undefined results or uncompilable code caused by the erroneous use of const. The solution includes concurrency and synchronisation concerns including whether to protect the cached, double, area member by a mutex or make it std::atomic<double> (which is where mutable makes an appearance).

The first comments to catch my eye were about the overhead that may be incurred by std::atomic being only to do with what liberties the compiler can take with respect to optimising writes. This raised an eyebrow as I was under the impression that the need to force atomic operation effects to be globally and consistently visible has more of an effect on performance than reordering write restrictions. Even where a processor has atomic memory update support there is still a cost [3, 4] – although that cost is significantly lower in modern processors.

However, the main focus of my thoughts has to do with various comments noting that modifying the set of points added to objects of the problem’s polygon class is not synchronised and performing such changes concurrently with other operations without external synchronisation will end in tears and confusion! One suggestion was to do all the updates on a single thread then allow shared concurrent read access to the finalised polygon. This got me speculating as to how to enforce such a usage pattern, rather than just arrange for violations to such usage to not occur by convention and hope everyone plays along.

What follows is the result of me following up on these initial thoughts, along the lines of “let’s see where this goes…”, and as such is not intended to necessarily solve any real world problems or even to produce any workable solutions. It is assumed that the types involved, like the GotW 6B polygon class, do not have immutable instances so any thread could potentially modify an instance at any time. If nothing else maybe these musing will serve as an example as to why immutability can be a good thing.

So, the pattern is:

1. Create an object – e.g. a polygon as per GotW 6b; this occurs on a single thread.
2. On this thread perform updates to this object (e.g. add points to the polygon).
3. Having performed all updates share the polygon for read-only access from potentially many threads concurrently.

The above omits what to do when we wish to delete the object – which of course should be considered a mutating operation! The simplest option might be:

4. When all threads using the object have died the object may be deleted.

Although this seems somewhat restrictive.

During the initial updating phase read-access will, in general, also need to be restricted to access by a single thread. Step 2 could be relaxed to allow access on different threads so long as access only occurred on one thread at a time. It would be nice to relax step 4 to allow the object to be safely deleted without all the reader threads having to terminate first.

Thus mutating and non-mutating (or const in C++ terms) operations have different usage restrictions:

• Mutating operations are allowed to be used initially from a single thread then disallowed.
• Non-mutating operations are allowed to be used initially from a single thread then from multiple threads.

Let’s consider restricting multithread access first. An obvious lock-based approach would be to create an object in a locked, mutable, state and then change the state to being immutable and release the lock. This does not help with the deletion problem though. Using a readers-writer or readers-upgrade-writer lock could potentially solve this issue: create in mutable, write-locked state, when done setting up the object’s state move to the immutable readers-locking state, when wanting to destroy the object obtain a writer lock, possibly via an upgrade lock.

Such locking strategies allow for more flexible usage patterns than we require here. Because multithread access is forbidden when in the initial mutable state we can just treat such accesses as errors when in this state. It would be nice to be able to prevent such usage by failing compilation – possibly restricting usage patterns such as use as stack objects only – but (I am fairly certain) this is not attainable. Hence we should look to detecting and raising such misuse as errors at runtime.

One obvious approach would be to use a std::atomic<bool> flag instance member that is tested, set and reset around each mutating operation. An exception is thrown if testing the flag indicates the method is currently being used by some other thread (see Listing 1).

void the_type::mutating_operation()
{
    bool expect_false {false};
    if (!in_use.compare_exchange_strong(expect_false, true))
    {
        throw std::runtime_error{"!!Concurrent access: illegal usage!!"};
    }
    // Do state changing stuff…
    in_use = false;
}

This will be monotonous to do repeatedly but the logic could be centralised – for example bundled up into a functor using execute-around to plumb in the boilerplate code around the actual work passed as a lambda function. A rough bare bones implementation might look like Listing 2.

class enforced_exclusive_executor
{
    std::atomic<bool> in_use;
public:
    enforced_exclusive_executor() : in_use {false}
    {}
    template <class WkFnT>
    void operator()(WkFnT do_work)
    {
        bool expect_false {false};
        if (!in_use.compare_exchange_strong(expect_false, true))
        {
            throw std::runtime_error{"!!Concurrent access: illegal usage!!"};
        }
        do_work();
        in_use = false;
    }
};

Which reduces the mutating operation implementation to:

void the_type::mutating_operation()
{
    exclusive_exec([&]()
    {
        /*Do state changing stuff…*/;
    });
}

In which exclusive_exec is an instance member of the_type of type enforced_exclusive_executor.

Other than the various overheads incurred this technique’s main problem is not necessarily detecting access by multiple threads immediately, if at all. This means that pattern-misuse exceptions are raised indeterminably. Then of course there is the question of what to do about non-mutating operations that do not alter the object’s state.

A better approach may be to work with a token: if the token matches the current valid token then updates are OK otherwise it is erroneous usage. A convenient token would seem to be a thread id, represented in C++11 by the std::thread::id type (see Listing 3).

void the_type::mutating_operation()
{
    if (std::this_thread::get_id()!=update_id)
    {
        throw std::runtime_error{"!!Concurrent access: illegal usage!!"};
    }
// Do state changing stuff…
}

update_id is an instance member of the_type of type std::thread::id which is initialised to the thread id of the thread creating the object. Of course the check logic can be pulled out – for example into a private instance method maybe called something like validate_call_context() (see Listing 4).

void the_type::validate_call_context()
{
    if (std::this_thread::get_id()!=update_id)
    {
        throw std::runtime_error{"!!Concurrent access: illegal usage!!"};
    }
}
void the_type::mutating_operation()
{
    validate_call_context();
    // Do state changing stuff…
}

This scheme will throw an exception any time any thread other than that the object expected to be called on calls any instance member function that validates its call context – which should be most if not all operations. The scheme has potential to be extended. Transferring the call context to another thread is simply a matter of updating the value of the object’s update_id to the id of the new calling thread. As such a transfer only makes sense during the initial updating stage of the object, like all such operations during this stage, it would be restricted to being performed only by the current calling context. As a bonus when moving to the shared, immutable state the calling context can be ‘transferred’ to the single distinct std::thread::id value that does not represent a thread – as produced by default constructing a std::thread::id object – which would ensure that all operations that validate their call context will fail.

A concern is that as std::this_thread_get_id() is called for each validation it should be a cheap – preferably very cheap – operation which may not be the case for all implementations.

I shall pause here and defer developing my musings further for a later article.

References

[1] http://herbsutter.com/

[2] http://herbsutter.com/2013/05/28/gotw-6b-solution-const-correctness-part-2/

[3] ‘Is Parallel Programming Hard, And, If So, What Can You Do About It?’ v2013.01.13a especially sections 2.1.3, 2.21, 2.2.3https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html

[4] What Every Programmer Should Know About Memory, section 6.4.2 http://www.akkadia.org/drepper/cpumemory.pdf

Notes: 

More fields may be available via dynamicdata ..