Getting tuple elements with a runtime index

Anthony Williams from Just Software Solutions Blog

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: ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

Follow me on Twitter

C++ Concurrency in Action 2nd edition Early Access

Anthony Williams from Just Software Solutions Blog

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: , , ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

Follow me on Twitter

Siddhartha

Jon Jagger from less code, more software

is an excellent book by Herman Hesse. As usual I'm going to quote from a few pages.

He learned more from the river than Vasudeva could teach him. He learned from it continually. Above all, he learned from it how to listen, to listen with a still heart, with a waiting, open soul, without passion, without desire, without judgement, without opinions.
It also happened that curious people came along, who had been told that two wise men, magicians or holy men lived at the ferry. The curious ones asked many questions but they received no replies, and they found neither magicians nor wise men. They only found two friendly old men, who appeared to be mute, rather odd and stupid. And the curious ones laughed and said how foolish and credible people were to spread such wild rumours.
Is it not perhaps a mistake on your part not to be strict with him, not to punish him? Do you not chain him with your love? Do you not shame him daily with your goodness and patience and make it still more difficult for him?
Within Siddhartha there slowly grew and ripened the knowledge of what wisdom really was and the goal of his long seeking. It was nothing but a preparation of the soul, a secret art of thinking, feeling and breathing thoughts of unity at every moment of life.
From that hour Siddhartha ceased to fight against his destiny. There shone in his face the serenity of knowledge, of one who is no longer confronted with conflict of desires, who has found salvation, who is in harmony with the streams of events, with the stream of life, full of sympathy and compassion, surrendering himself to the stream, belonging to the unity of all things.
In every truth the opposite is equally true. For example, a truth can only be expressed and enveloped in words if it is one-sided. Everything that is thought and expressed in words is one-sided, only half the truth; it lacks totality, completeness, unity.
The sinner is not on the way to a Buddha-like state; he is not evolving, although our thinking cannot conceive things otherwise. No, the potential Buddha already exists in the sinner; his future is already there. The potential Buddha must be recognized in him, in you, in everybody. The world, Govinda, is not imperfect or slowly evolving along a path to perfection. No, it is perfect at every moment; every sin already carries grace within it, all small children are potential old men, all sucklings have death within them, all dying people - eternal life.
In order to learn to love the world, and no longer compare it with some kind of desired imaginary world, some imaginary vision of perfection, but to leave it as it is, to love it and be glad to belong to it.
It may be a thought, but I confess, my friend, that I do not differentiate very much between thoughts and words. Quite frankly, I do no attach great importance to thoughts either. I attach more importance to things.
I think it is only important to love the world, not to despise it, not for us to hate others, but to be able to regard the world and ourselves and all beings with love, admiration and respect.
The thing to me is of greater importance than the words; his deeds and life and more important to me than his opinions. Not in speech or thought do I regard him as a great man, but in his deeds and life.
Uncontrollable tears trickled down his old face. He was overwhelmed by a feeling of great love, of the most humble veneration.


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

Anthony Williams from Just Software Solutions Blog

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:

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: , , ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

Follow me on Twitter

Does const mean thread-safe?

Anthony Williams from Just Software Solutions Blog

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: , ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

Follow me on Twitter

The Hidden Life of Trees

Jon Jagger from less code, more software

is an excellent book by Peter Wohlleben (isbn 1771642483). As usual I'm going to quote from a few pages.

In forked trees, at a certain point, two main shoots form, they continue to grow alongside each other. Each side of the fork creates its own crown, so in a heavy wind, both sides sway back and forth in different directions, putting a great strain on the trunk where the two parted company. ... The fork always breaks at its narrowest point, where the two sides diverge.
The process of learning stability is triggered by painful micro-tears that occur when the trees bend way over in the wind, first in one direction and then in the other. Wherever it hurts, that's where the tree must strengthen its support structure. ... The thickness and stability of the trunk, therefore, builds up as the tree responds to a series of aches and pains.
There is a honey fungus in Switzerland that covers almost 120 acres and is about a thousand years old. Another in Oregon is estimated to be 2,400 years old, extends for 2,000 acres, and weighs 660 tons. That makes fungi the largest known living organism in the world.
You find twice the amount of life-giving nitrogen and phosphorus in plants that cooperate with fungal partners than in plants that tap the soil with the roots alone.
Diversity provides security for ancient forests.
There are more life-forms in a handful of forest soil than there are people on the planet.
As foresters like to say, the forest creates its own ideal habitat.
Commercial forest monocultures also encourage the mass reproduction of butterflies and moths, such as nun moths and pine loopers. What usually happens is that viral illnesses crop up towards the end of the cycle and populations crash.
The storms pummel mature trunks with forces equivalent to a weight of approximately 220 tons. Any tree unprepared for the onslaught can't withstand the pressure and falls over. But deciduous trees are well prepared. To be more aerodynamic they cast off all their solar panels. And so a huge surface area of 1,200 square yards disappears and sinks to the forest floor. This is the equivalent of a sailboat with a 130-foot mast dropping a 100-by-130 foot mainsail.
Why do tree grow into pipes in the first place?... What was attracting them was loose soil that had not been fully compacted after construction. Here the roots found room to breathe and grow. It was only incidentally that they penetrated the seals between individual sections of pipe and eventually ran riot inside them.
Sometimes, especially in cold winters, the old wounds can act up again. Then a crack like a rifle shot echoes through the forest and the trunk splits open along the old injury. This is caused by differences in tension in the frozen wood, because the wood in trees with a history of injury varies greatly in density.