Boost tuple performance

Question

According to boost::tuple documentation, accessing a single element of a tuple has the same performance as accessing a member variable. For example, given the following declaration:

tuple<A, B, C> t1(A(), B(), C());
struct T { A a; B b; C c; }
T t2;

These two statements should have equal (or with negligible difference) performance:

t1.get<2>();
t2.c;

I looked into the sources of boost::tuple and, if I understood them correctly (I am not sure I did), get<N> function actually performs this action:

C get<2>(tuple<A, B, C>& t)
{
    return t.tail.tail.head;
    //Generally:  return t.tail. <<N times>> .head;
}

This is more similar to a look-up in a linked list than a direct access, and, as far as I undestand, has O(N) complexity instead of O(1), which is expected from a member access. From my past experiences with boost, I'd assume I got it wrongly; but what is my mistake? How does get really work?

Answer 1

You are correct about the list-like performance. However, it can be resolved at compile-time and hence boils down to O(1) at run-time. (Given a sufficiently good optimizing compiler.)

Answer 2

Remember, in C++, the dot operator is not a pointer deference, it is a direct offset computation. The general answer is yes, i1.i2.i3.in for all n is a constant time operation calculable at compile time.

If you want to learn a little about the compiler internals for this without digging very deep, look at LLVM getelementptr http://llvm.org/docs/LangRef.html#i_getelementptr This is exactly how a C++ compiler like CLANG would target LLVM when compiling a struct reference.