Blog Archive for / 2017 / 03 /

Getting tuple elements with a runtime index

Tuesday, 28 March 2017

std::tuple is great. It provides a nice, generic way of holding a fixed-size set of data items of whatever types you need.

However, sometimes it has limitations that mean it doesn't quite work as you'd like. One of these is accessing an item based on a runtime index.

std::get needs a compile-time index

The way to get the nth item in a tuple is to use std::get: std::get<n>(my_tuple). This works nicely, as long as n is a compile-time constant. If you've got a value that is calculated at runtime, this doesn't work: you can't use a value that isn't known until runtime as a template parameter.

std::tuple<int,int,int> my_tuple=...;
size_t index;
std::cin>>index;
int val=std::get<index>(my_tuple); // won't compile

So, what can we do? We need a new function, which I'll call runtime_get, to retrieve the nth value, where n is a runtime value.

template<typename Tuple>
... runtime_get(Tuple&& t,size_t index){
  ...
}

The question is: how do we implement it?

Fixed return type

The return type is easy: our function must have a single return type for any given Tuple. That means that all the elements in the tuple must have the same type, so we can just use the type of the first element. std::tuple_element will tell us this, though we must first adjust our template parameter so it's not a reference.

template<typename Tuple>
typename std::tuple_element<
  0,typename std::remove_reference<Tuple>::type>::type&
runtime_get(Tuple&& t,size_t index){
  ...
}

Note: C++17 includes std::variant, so you might think we could use that to hold the return type, but that wouldn't actually help us: to get the value from a variant, you need to call std::get<n>(v), which requires n to be a constant (again)!

OK, so the return type is just a reference to the type of the first element. How do we get the element?

Retrieving the nth element

We can't do a straightforward switch, because that requires knowing all the cases in advance, and we want this to work for any size of tuple.

One way would be to have a recursive function that checked the runtime index against a compile-time index, and then called the function with the next compile-time index if they were different, but that would mean that the access time would depend on the index, and potentially end up with a deeply nested function call if we wanted the last element in a large tuple.

One thing we can do is use the index value as an array index. If we have an array of functions, each of which returns the corresponding element from the tuple, then we can call the appropriate function to return the relevant index.

The function we need is of course std::get; it's just a matter of getting the function signature right. Our overload of std::get has the following signature for const and non-const tuples:

template <size_t I, class... Types>
constexpr tuple_element_t<I, tuple<Types...>>&
get(tuple<Types...>&) noexcept;

template <size_t I, class... Types>
constexpr const tuple_element_t<I, tuple<Types...>>&
get(const tuple<Types...>&) noexcept;

so, we can capture the relevant instantiation of std::get for a given tuple type Tuple in a function pointer declared as:

using return_type=typename std::tuple_element<0,Tuple>::type&;
using get_func_ptr=return_type(*)(Tuple&) noexcept;

The signature is the same, regardless of the index, because we made the decision that we're only going to support tuples where all the elements are the same.

This makes it easy to build a function table: use a variadic pack expansion to supply a different index for each array element, and fill in std::get<N> for each entry:

template<
  typename Tuple,
  typename Indices=std::make_index_sequence<std::tuple_size<Tuple>::value>>
struct runtime_get_func_table;

template<typename Tuple,size_t ... Indices>
struct runtime_get_func_table<Tuple,std::index_sequence<Indices...>>{
    using return_type=typename std::tuple_element<0,Tuple>::type&;
    using get_func_ptr=return_type (*)(Tuple&) noexcept;
    static constexpr get_func_ptr table[std::tuple_size<Tuple>::value]={
        &std::get<Indices>...
    };
};

template<typename Tuple,size_t ... Indices>
constexpr typename
runtime_get_func_table<Tuple,std::index_sequence<Indices...>>::get_func_ptr
runtime_get_func_table<Tuple,std::index_sequence<Indices...>>::table[
  std::tuple_size<Tuple>::value];

We need the separate redeclaration of the table to satisfy a pre-C++17 compiler; with C++17 inline variables it is no longer needed.

Our final function is then just a simple wrapper around a table lookup:

template<typename Tuple>
constexpr
typename std::tuple_element<0,typename std::remove_reference<Tuple>::type>::type&
runtime_get(Tuple&& t,size_t index){
    using tuple_type=typename std::remove_reference<Tuple>::type;
    if(index>=std::tuple_size<tuple_type>::value)
        throw std::runtime_error("Out of range");
    return runtime_get_func_table<tuple_type>::table[index](t);
}

It's constexpr safe, though in a constexpr context you could probably just use std::get directly anyway.

So, there you have it: a constant-time function for retrieving the nth element of a tuple where all the elements have the same type.

Final code

Here is the final code for a constant-time function to retrieve an item from a tuple based on a runtime index.

#include <tuple>
#include <utility>
#include <type_traits>
#include <stdexcept>

template<
  typename Tuple,
  typename Indices=std::make_index_sequence<std::tuple_size<Tuple>::value>>
struct runtime_get_func_table;

template<typename Tuple,size_t ... Indices>
struct runtime_get_func_table<Tuple,std::index_sequence<Indices...>>{
    using return_type=typename std::tuple_element<0,Tuple>::type&;
    using get_func_ptr=return_type (*)(Tuple&) noexcept;
    static constexpr get_func_ptr table[std::tuple_size<Tuple>::value]={
        &std::get<Indices>...
    };
};

template<typename Tuple,size_t ... Indices>
constexpr typename
runtime_get_func_table<Tuple,std::index_sequence<Indices...>>::get_func_ptr
runtime_get_func_table<Tuple,std::index_sequence<Indices...>>::table[std::tuple_size<Tuple>::value];

template<typename Tuple>
constexpr
typename std::tuple_element<0,typename std::remove_reference<Tuple>::type>::type&
runtime_get(Tuple&& t,size_t index){
    using tuple_type=typename std::remove_reference<Tuple>::type;
    if(index>=std::tuple_size<tuple_type>::value)
        throw std::runtime_error("Out of range");
    return runtime_get_func_table<tuple_type>::table[index](t);
}

Posted by Anthony Williams
[/ cplusplus /] permanent link
Tags: cplusplus, tuples
Stumble It! | Submit to Reddit | Submit to DZone

Comment on this post

If you liked this post, why not subscribe to the RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the left.

C++ Concurrency in Action 2nd edition Early Access

Wednesday, 22 March 2017

I am happy to announce that the second edition of my book, C++ Concurrency in Action, is now available under the Manning Early Access Program.

The second edition is being updated to cover C++14, C++17 and the Concurrency TS, along with general improvements throughout the book.

This includes full coverage of the library changes from C++14 and C++17:

• std::shared_mutex and std::shared_timed_mutex. These provide for multiple-reader/single-writer mutex locks.
• std::scoped_lock from C++17 for locking multiple mutexes together.
• Parallel overloads of many standard library algorithms include std::sort, std::for_each and std::transform_reduce.

Plus, full coverage of the library extensions from the concurrency TS:

• std::experimental::latch to allow waiting for a set number of events to occur
• std::experimental::barrier and std::experimental::flex_barrier to synchronize groups of threads
• std::experimental::atomic_shared_ptr to allow atomic accesses to a single shared_ptr instance from multiple threads, as a better alternative that the std::atomic_load and std::atomic_store free functions.
• Extended futures that allow continuations, so additional functions can be scheduled for when a future is ready.
• std::experimental::when_all and std::experimental::when_any to allow waiting for either all of a set of futures to be ready, or the first of a set of futures to be ready.

Only the first few chapters are available at the moment, but if you sign up now, then you will get those chapters in PDF form now, as well as updated PDFs including the later chapters as they become ready, along with updates for the earlier ones, and a final print copy of the book when it's done.

50% Discount

If you use the code mlwilliams4 at the checkout when you sign up for the MEAP before 27th March 2017 then you'll get a 50% discount.

Posted by Anthony Williams
[/ news /] permanent link
Tags: C++, concurrency, multithreading, book
Stumble It! | Submit to Reddit | Submit to DZone

Comment on this post

If you liked this post, why not subscribe to the RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the left.

Just::Thread Pro v2.4.2 released with clang support

Thursday, 16 March 2017

I am pleased to announce that Just::Thread Pro v2.4.2 has been released with support for clang on linux.

Just::Thread Pro is our C++ concurrency extensions library which provides an Actor framework for easier concurrency, along with concurrent data structures: a thread-safe queue, and concurrent hash map, and a wrapper for ensuring synchronized access to single objects.

It also includes the new facilities from the Concurrency TS:

• Latches
• Barriers
• atomic_shared_ptr and atomic_weak_ptr
• future::then()
• when_any()
• when_all()

Clang support is finally here!

V2.4.2 adds the much-anticipated support for clang. clang 3.8 and 3.9 are supported on ubuntu 16.04 or later, clang 3.8 is supported on Fedora 24, and clang 3.9 on Fedora 25.

Just::Thread Pro is now fully supported on the following compiler/OS combinations (32-bit and 64-bit):

• Microsoft Visual Studio 2015 for Windows
• Microsoft Visual Studio 2017 for Windows
• gcc 5 for Ubuntu 14.04 or later
• gcc 6 for Ubuntu 14.04 or later
• clang 3.8 for Ubuntu 16.04 or later
• clang 3.9 for Ubuntu 16.04 or later
• gcc 5 for Fedora 22 and 23
• gcc 6 for Fedora 24 and 25
• clang 3.8 for Fedora 24
• clang 3.9 for Fedora 25

Just::Thread Pro v2.2 is also supported with the Just::Thread compatibility library on the following compiler/OS combinations:

• Microsoft Visual Studio 2005, 2008, 2010, 2012 and 2013 for Windows
• TDM gcc 4.5.2, 4.6.1 and 4.8.1 for Windows
• g++ 4.3 or later for Ubuntu 9.04 or later
• g++ 4.4 or later for Fedora 13 or later
• g++ 4.4 for Centos 6
• MacPorts g++ 4.3 to 4.8 on MacOSX Snow Leopard or later

All licences include a free upgrade to point releases, so if you purchase now you'll get a free upgrade to all 2.x releases of Just::Thread Pro. Purchasers of the older Just::Thread library (now called the compatibility library) may upgrade to Just::Thread Pro for a small fee.

Posted by Anthony Williams
[/ news /] permanent link
Tags: just::thread, release, concurrency, multithreading
Stumble It! | Submit to Reddit | Submit to DZone

Comment on this post

If you liked this post, why not subscribe to the RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the left.

Does const mean thread-safe?

Tuesday, 14 March 2017

There was a discussion recently on the cpplang slack about whether const meant thread-safe.

As with everything in life, it depends. In some ways, yes it does. In others, it does not. Read on for the details.

What do we mean by "thread-safe"?

If someone says something is "thread-safe", then it is important to define what that means. Here is an incomplete list of some things people might mean when they say something is "thread safe".

• Calling foo(x) on one thread and foo(y) on a second thread concurrently is OK.
• Calling foo(x_i) on any number of threads concurrently is OK, provided each x_i is different.
• Calling foo(x) on a specific number of threads concurrently is OK.
• Calling foo(x) on any number of threads concurrently is OK.
• Calling foo(x) on one thread and bar(x) on another thread concurrently is OK.
• Calling foo(x) on one thread and bar(x) on any number of threads concurrently is OK.

Which one we mean in a given circumstance is important. For example, a concurrent queue might be a Single-Producer, Single-Consumer queue (SPSC), in which case it is safe for one thread to push a value while another pops a value, but if two threads try and push values then things go wrong. Alternatively, it might be a Multi-Producer, Single-Consumer queue (MPSC), which allows multiple threads to push values, but only one to pop values. Both of these are "thread safe", but the meaning is subtly different.

Before we look at what sort of thread safety we're after, let's just define what it means to be "OK".

Data races

At the basic level, when we say an operation is "OK" from a thread-safety point of view, we mean it has defined behaviour, and there are no data races, since data races lead to undefined behaviour.

From the C++ Standard perspective, a data race is where there are 2 operations that access the same memory location, such that neither happens-before the other, at least one of them modifies that memory location, and at least one of them is not an atomic operation.

An operation is thus "thread safe" with respect to the set of threads we wish to perform the operation concurrently if:

• none of the threads modify a memory location accessed by any of the other threads, or
• all accesses performed by the threads to memory locations which are modified by one or more of the threads are atomic, or
• the threads use suitable synchronization to ensure that there are happens-before operations between all modifications, and any other accesses to the modified memory locations.

So: what sort of thread-safety are we looking for from const objects, and why?

Do as ints do

A good rule of thumb for choosing behaviour for a class in C++ is "do as ints do".

With regard to thread safety, ints are simple:

• Any number of threads may read a given int concurrently
• If any thread modifies a given int, no other threads may access that int for reading or writing concurrently.

This follows naturally from the definition of a data race, since ints cannot do anything special to provide synchronization or atomic operations.

If you have an int, and more than one thread that wants to access it, if any of those threads wants to modify it then you need external synchronization. Typically you'll use a mutex for the external synchronization, but other mechanisms can work too.

If your int is const, (or you have const int& that references it, or const int* that points to it) then you can't modify it.

What does that mean for your class? In a well-designed class, the const member functions do not modify the state of the object. It is "logically" immutable when accessed exclusively through const member functions. On the other hand, if you use a non-const member function then you are potentially modifying the state of the object. So far, so good: this is what ints do with regard to reading and modifying.

To do what ints do with respect to thread safety, we need to ensure that it is OK to call any const member functions concurrently on any number of threads. For many classes this is trivially achieved: if you don't modify the internal representation of the object in any way, you're home dry.

Consider an employee class that stores basic information about an employee, such as their name, employee ID and so forth. The natural implementation of const member functions will just read the members, perform some simple manipulation on the values, and return. Nothing is modified.

class employee{
    std::string first_name;
    std::string last_name;
    // other data
public:
    std::string get_full_name() const{
        return last_name + ", " + first_name;
    }
    // other member functions
}

Provided that reading from a const std::string and appending it to another string is OK, employee::get_full_name is OK to be called from any number of threads concurrently.

You only have to do something special to "do as ints do" if you modify the internal state in your const member function, e.g. to keep a tally of calls, or cache calculation values, or similar things which modify the internal state without modifying the externally-visible state. Of course, you would also need to add some synchronization if you were modifying externally-visible state in your const member function, but we've already decided that's not a good plan.

In employee::get_full_name, we're relying on the thread-safety of std::string to get us through. Is that OK? Can we rely on that?

Thread-safety in the C++ Standard Library

The C++ Standard Library itself sticks to the "do as ints do" rule. This is spelled out in the section on Data race avoidance (res.on.data.races). Specifically,

A C++ standard library function shall not directly or indirectly modify objects accessible by threads other than the current thread unless the objects are accessed directly or indirectly via the function's non-const arguments, including this.

and

Implementations may share their own internal objects between threads if the objects are not visible to users and are protected against data races.

This means that if you have a const std::string& referencing an object, then any calls to member functions on it must not modify the object, and any shared internal state must be protected against data races. The same applies if it is passed to any other function in the C++ Standard Library.

However, if you have a std::string& referencing the same object, then you must ensure that all accesses to that object must be synchronized externally, otherwise you may trigger a data race.

Our employee::get_full_name function is thus as thread-safe as an int: concurrent reads are OK, but any modifications will require external synchronization for all concurrent accesses.

There are two little words in the first paragraph quoted above which have a surprising consequence: "or indirectly".

Indirect Accesses

If you have two const std::vector<X>s, vx and vy, then calling standard library functions on those objects must not modify any objects accessible by other threads, otherwise we've violated the requirements from the "data race avoidance" section quoted above, since those objects would be "indirectly" modified by the function.

This means that any operations on the X objects within those containers that are performed by the operations we do on the vectors must also refrain from modifying any objects accessible by other threads. For example, the expression vx==vy compares each of the elements in turn. These comparisons must thus not modify any objects accessible by other threads. Likewise, std::for_each(vx.begin(),vx.end(),foo) must not modify any objects accessible by other threads.

This pretty much boils down to a requirement that if you use your class with the C++ Standard Library, then const operations on your class must be safe if called from multiple threads. There is no such requirement for non-const operations, or combinations of const and non-const operations.

You may of course decide that your class is going to allow concurrent modifications (even if that is by using a mutex to restrict accesses internally), but that is up to you. A class designed for concurrent access, such as a concurrent queue, will need to have the internal synchronization; a value class such as our employee is unlikely to need it.

Summary

Do as ints do: concurrent calls to const member functions on your class must be OK, but you are not required to ensure thread-safety if there are also concurrent calls to non-const member functions.

The C++ Standard Library sticks to this rule itself, and requires it of your code. In most cases, it's trivial to ensure; it's only classes with complex const member functions that modify internal state that may need synchronization added.

Posted by Anthony Williams
[/ cplusplus /] permanent link
Tags: cplusplus, const, concurrency
Stumble It! | Submit to Reddit | Submit to DZone

Comment on this post

If you liked this post, why not subscribe to the RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the left.

just::thread Pro adds Visual Studio 2017 support

Wednesday, 08 March 2017

I am pleased to announce that just::thread Pro now supports Microsoft Visual Studio 2017 on Microsoft Windows.

This adds to the support for Microsoft Visual Studio 2015, g++ 5 and g++ 6 for the just::thread Pro enhancements, which build on top of the platform-supplied version of the C++14 thread library. For older compilers, and for MacOSX, the just::thread compatibility library is still required.

The new build features all the same facilities as the previous release:

• A multiple-producer single-consumer FIFO queue, ideal for sending messages to a particular thread
• A synchronized_value class template for synchronizing access to a single object
• A thread-safe hash map
• An Actor framework for simplified design of multi-threaded applications
• A variadic jss::lock_guard class template to allow acquiring multiple locks at once, like the new C++17 std::lock_guard.
• New facilities from the Concurrency TS:
  • A lock-free implementation of atomic_shared_ptr and atomic_weak_ptr — see Anthony's earlier blog post on atomic_shared_ptr
  • Latches — signal waiting threads once a specified number of count-down events have occurred.
  • Barriers — block a group of threads until they are all ready to proceed.
  • future::then() — schedule a task to run when a future becomes ready.
  • when_any() — create a future that is ready when any of a set of futures is ready.
  • when_all() — create a future that is ready when all of a set of futures are ready.

Get your copy of just::thread Pro

Purchase your copy and get started now.

As usual, all customers with V2.x licenses of just::thread Pro will get a free upgrade to the new just::thread Pro Standalone edition.

Posted by Anthony Williams
[/ news /] permanent link
Tags: multithreading, concurrency, C++11
Stumble It! | Submit to Reddit | Submit to DZone

Comment on this post

If you liked this post, why not subscribe to the RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the left.

Previous Entries Later Entries

Design and Content Copyright © 2005-2025 Just Software Solutions Ltd. All rights reserved. | Privacy Policy