Home » Blog » Tags » advanced

« Prev Next »

advanced

Open and Efficient Type Switch for C++ -- Solodkyy, Dos Reis, and Stroustrup

By Blog Staff | Feb 13, 2013 06:41 PM | Tags: intermediate advanced

Here's a recent highlight from the pre-Portland mailing that you might have missed:

Open and Efficient Type Switch for C++

Yuriy Solodkyy, Gabriel Dos Reis, Bjarne Stroustrup

... we implement a type switch construct as an ISO C++11 library, called Mach7. This library-only implementation provides concise notation and outperforms the visitor design pattern. ... For closed sets of types, its performance roughly equals equivalent code in functional languages, such as OCaml and Haskell.

C++ is a powerful library-building language. Whenever possible, we prefer to add new functionality as a library rather than in the language. This is an excellent example of where a C++ library-only solution can get equivalent performance to the language support included in some popular functional languages.

C++ and Beyond 2013 dates and location finalized

By Blog Staff | Feb 11, 2013 10:41 AM | Tags: intermediate basics advanced

The final dates and location are now set for C++ and Beyond 2013 with Scott Meyers, Herb Sutter, and Andrei Alexandrescu:

December 9-12, 2013 in beautiful Snoqualmie, Washington, USA.

From Scott Meyers' announcement:

About a month ago, I posted tentative dates for C&B 2013. I cautioned that there was no contract yet, and I’m glad I did, because shortly thereafter we discovered an off-by-one scheduling snafu. As a result, the dates are not the ones I posted earlier, they’re a day later: Monday evening, December 9, through Thursday, December 12.
The inital C&B in 2010 was held at the Salish Lodge and Spa in Snoqualmie, Washington, USA. In 2011, we had a larger group in a larger venue, and last year we bumped up the numbers again. Growth was ours, it seemed, but we sensed that C&B was looking more like a conventional conference and less like the unique event we had originally envisioned. For 2013, we decided to return to our roots, both geographically and organizationally.

C&B 2013 will return to the Salish Lodge and Spa in Snoqualmie, Washington (not far from Seattle). Enrollment will again be limited to the capacity of the ballroom (~64 attendees). Scott will again lead lunchtime walks. Evenings will again feature free-form “hang out with the speakers” sessions. Hotel guestrooms will again boast fireplaces, whirlpool tubs for two, and one whopping big waterfall just steps from the front door. If you were part of C&B 2010, you know what I’m talking about. If you weren’t, ask around: you’ll wish you had been.

We’ll announce more details when they’ve been finalized, including when registration for C&B 2013 will begin. In the meantime, reserve December 9-12 for C++ and Beyond 2013 in Snoqualmie, Washington, USA.

Core C++, 7 and 8 of N: Loops, ODR, and variadic array sorter

By Blog Staff | Feb 5, 2013 11:31 AM | Tags: intermediate advanced

Two advanced talks by Stephan T. Lavavej (aka STL) are now available, the second being posted today:

Core C++, 7 of N

In Part 7, STL teaches us about Usual Arithmetic Conversions, Template Metaprogramming (TMP), and shares some of the Visual C++ STL internal implementation (some of it not yet released). Many of you have asked for some treatment of TMP and STL delivers!

Core C++, 8 of N

In part 8, STL digs into the do-while loop, casts, one definition rule (ODR), and his variadic template array sorter. There is a lot of information in this episode, so get comfortable, tune in, and learn.

HPX (High Performance ParalleX) 0.9.5 Released

By Eric Niebler | Jan 17, 2013 12:44 PM | Tags: intermediate advanced

The High Performance ParalleX (HPX) library has produced its 0.9.5 release. Here's a snippet about HPX from its release announcement.

HPX 0.9.5 Released

[...] HPX (High Performance ParalleX) is a general C++ runtime system for parallel and distributed applications of any scale. It is the first freely available, open source, feature-complete, modular, and performance oriented implementation of the ParalleX execution model. HPX is targeted at conventional architectures and, currently, Linux based systems, such as SMP nodes and conventional clusters. [...]

C++ Training at All Levels -- Leor Zolman

By Blog Staff | Jan 16, 2013 05:54 PM | Tags: intermediate basics advanced

On-Site C++ Training at All Levels

by industry veteran Leor Zolman

Note: For a limited time, any 4- or 5-day training includes the C++11 Overview.

Our C++ and C seminars have been designed by some of the best-known, most effective C++ educators practicing today. In addition to materials created by Leor our C++ training repertoire features courses licensed from and supported by industry leaders Dan Saks and Stephen C. Dewhurst.

A Whirlwind Overview of C++11 (1/2-day, author: Leor Zolman)

Advanced C++ (Author: Stephen C. Dewhurst)

Effective C++ (3-, 4- and 5-day versions of courseware by Scott Meyers based on his books)

An Effective Introduction to the Standard Template Library (STL) (Author: Scott Meyers)

C++ for Non-C Programmers (Author: Leor Zolman)

C++ and Object-Oriented Programming (a.k.a. C++ for C Programmers). (Author: Dan Saks)

A sample unit of any course is available upon request.

Constexpr Unions -- Andrzej Krzemieński

By Blog Staff | Dec 17, 2012 08:02 AM | Tags: advanced

On using constexpr and unions, with insights into the design of the currently-proposed std::optional<T>:

Constexpr Unions

by Andrzej Krzemieński

I assume you are already familiar with constexpr functions. (If not, see a short introduction here.) [Ed.: We linked to that article recently, so you've seen it if you've been following isocpp.org.]

In this post I wanted to share my experience with using unions in constant expressions. Unions are not very popular due to type-safety hole they open, but they offer some capabilities that I found priceless when working with Fernando Cacciola on std::optional proposal.

A C++11 Name-Lookup Problem: a Long-Term Solution and a Temporary Work-Around

By Eric Niebler | Dec 14, 2012 01:31 PM | Tags: advanced

A C++11 Name-Lookup Problem: a Long-Term Solution and a Temporary Work-Around

by Eric Niebler

[This article has been changed since it was first published. New information from the standardization committee, which is working to fix the issue, is included.]

[Disclaimer: This is an advanced article.]

Both beginner programmers and experienced library developers got new tools when C++11 came out. As a library developer, I was particularly excited by variadic templates, an advanced feature that makes it possible to write a function that takes an arbitrary number of arguments. As it turns out, the nature of the language feature, together with the existing name lookup rules of C++, can steer you down a dark alley of frustration. This article sheds some light on the issue and shows a light at the end of the tunnel in the form of a language simplification coming in C++14. Until then, there is a workaround. But first, a word about variadic templates.

Imagine you're trying to write a sum() function that takes an arbitrary number of arguments and adds them all together. In pseudo-code, you want something like this:

// pseudo-code
auto sum( t ) { return t; }
auto sum( t, ...u ) { return t + sum( u... ); }

You have two overloads: one that takes a single argument and returns it; and the other that takes multiple arguments and adds the first to the resulting of summing the rest. Simple enough, right? With variadic templates, this isn't too hard, although the syntax takes some getting used to. Let's assume we're summing ints for now:

// real code
int sum( int i )
{
  return i;
}

template< typename ...Ints >
int sum( int i, Ints ...is )
{
  return i + sum( is... );
}

OK, that wasn't so bad. It's a little strange that we had to parameterize all the arguments after the first. We would have preferred a signature like "int sum(int i, int... is)". Variadic templates don't let us do that, but it's not a huge deal.

The other thing we notice is that variadic templates can only ever expand into a comma-separated list of things. Above, we expand is... into the (comma-separated) argument list of a recursive invocation of sum(). If we could expand the argument pack into a list of things separated with '+', then we could have done all this in one shot. Instead, we're forced by the nature of variadic templates to implement sum() recursively. This may not seem like a big deal right now, but is.

Let's check to see that our sum() function works like we expect:

int i = sum( 1 );       // OK, i == 1
int j = sum( 1, 2 );    // OK, j == 3
int k = sum( 1, 2, 3 ); // OK, k == 6

Now we're feeling bold, and we'd like to generalize. Maybe we want to sum longs, or even concatenate std::strings! We need to make two changes: replace int with a template parameter, and automatically deduce the result type of the addition. We want to use type deduction so that if we, say, add an int and a long, the return type is long as it should be. C++11 makes this possible as well, although again the syntax takes some getting used to:

template< typename T >
T sum( T t )
{
  return t;
}

template< typename T, typename ...Us >
auto sum( T t, Us ...us ) -> decltype( t + sum( us... ) )
{
  return t + sum( us... );
}

Above, we use decltype to deduce the return type, and we use the new trailing return type declaration syntax. The code duplication in the trailing return type declaration is a code smell, but we can live with it for now. (FWIW, the standardization committee smells it too, and wants to clean this up. Read to the end for a glimpse of the smell-free future of C++.) Let's give it a test drive:

auto i = sum( 1 );                                     // OK, i == 1
auto j = sum( 1, 2 );                                  // OK, i == 3
auto greeting = sum( std::string("hello "), "world" ); // Cool! greeting == "hello world"
auto k = sum( 1, 2, 3 );                               // ERROR! Doesn't compile.

The last line gives us the following error on Clang:

>  main.cpp:25:14: error: no matching function for call to 'sum'
>      auto k = sum( 1, 2, 3 ); // ERROR! Doesn't compile.
>               ^~~
>  main.cpp:16:6: note: candidate template ignored: substitution
>  failure [with T = int, Us = <int, int>]: call to function
>  'sum' that is neither visible in the template definition nor
>  found by argument-dependent lookup
>  auto sum( T t, Us ...us ) -> decltype( t + sum( us... ) )
>       ^                                     ~~~
>  main.cpp:11:3: note: candidate function template not viable:
>  requires single argument 't', but 3 arguments were provided
>  T sum( T t )
>    ^
>  1 error generated.

What's going on here? Calls to sum() work for one argument and two arguments, but fail for three. In the error message, we see that Clang really tried to call the variadic overload of sum() but failed because "'sum' ... is neither visible in the template definition nor found by argument-dependent lookup." Huh?

I'll skip to the chase and tell you what's going on (though you might take a moment to figure it out for yourself before reading further). Look again at the definition of the variadic sum() overload:

template< typename T, typename ...Us >
auto sum( T t, Us ...us ) -> decltype( t + sum( us... ) )
{
  return t + sum( us... );
}

sum() appears twice, once in the function declaration and once in the function body. It's the one in the function declaration that's causing the problem. Consider that the above is (roughly) equivalent to the following:

template< typename T, typename ...Us >
decltype( T() + sum( Us()... ) ) sum( T t, Us ...us )
{
  return t + sum( us... );
}

The main difference is that we moved the return type from the back to the front, but this makes it a little more clear that in the return type the second sum() overload hasn't been seen yet! Even in the trailing return type formulation, the compiler pretends like it hasn't seen the second overload of sum() yet. And if it hasn't seen it, it can't call it. Picky, picky.

Name Lookup for Dummies

Name lookup happens in two phases. Let's just consider what happens in the case of the non-qualified function call in the return type of sum(). The compiler builds a set of overloads by adding a dash of functions from lookup phase 1 and then another dash from lookup phase 2. In phase 1, which happens when sum() is first parsed, functions with the right name that are in scope are tossed in the overload bucket. In our case, that's the single-argument overload of sum(), since that's the only one that is currently in scope. This phase happens before the argument types are known. Phase 2 is the argument-dependent lookup (ADL) phase and happens when the argument types are known; we check the associated namespaces of the arguments and look for any sum() overloads in those namespaces. None are found, because the arguments are of type int which has no associated namespaces. Bummer, our bucket only has only one overload of sum() in it, and it's not the one we need.

If you want to see something interesting about the way ADL works, try this. Define "struct String : std::string {};" at global scope. Now do this:

auto k = sum( "", String(), "" ); // OK!

Why does it compile when one of the arguments is a String? Because now ADL is forced to look in String's associated namespaces. Since String is defined in the global scope, ADL must check the global scope during the phase 2, and presto! there's another overload of sum() hiding in plain sight.

What's curious about our case is that we're trying to use a function in the declaration of that same function. There's just no way to get a function in scope until after its declaration, so trying to get phase 1 lookup to find it is a lost cause.

Recall what we said earlier about variadic templates: recursive algorithms are pretty much the only way to get non-trivial things done with them. There's no way around it. If the return type depends on the type returned by the recursive invocation -- and it often does -- we will run into this name lookup problem. Every time. The committee is already on its way with a language simplification that will make this problem go away (more about that below). For now, we have to find a workaround. Help us, phase 2 lookup. You're our only hope.

Relax, It's Just a Phase

How do we get name lookup to cool its jets and wait for phase 2? Let's back up a second and ask ourselves why lookup is done in two phases in the first place. When the compiler first sees the definition of a function template, some things are known and some aren't. For instance, the name of the function is known, but not the types of the arguments. Anything that depends on the template parameters is called, er, dependent. Name lookup in dependent types and dependent expressions happens during phase 2. So, in order to make the sum() function call resolve correctly, we need to make it depend on a template parameter.

Once again skipping ahead a bit, here is the hackish workaround that I've found. Explanation to follow.

namespace detail
{
  // The implementation of sum() is in a function object,
  // which is really just a holder for overloads.
  struct sum_impl
  {
    template< typename T >
    T operator()( T t ) const
    {
      return t;
    }

    // Sneaky trick below to make the function call lookup
    // happen in phase 2 instead of phase 1:
    template< typename T, typename ...Us, typename Impl = sum_impl >
    auto operator()( T t, Us ...us ) const -> decltype( t + Impl()( us... ) )
    {
      return t + Impl()( us... );
    }
  };
}

constexpr detail::sum_impl sum{};

In the above code, it looks like we simply moved the implementation of the sum() function into a sum_impl function object. But look closely, because there's more going on here than at first glance. The magic happens here:

template< typename T, typename ...Us, typename Impl = sum_impl >
// ----------------------- MAGIC HERE ^^^^^^^^^^^^^^^^^^^^^^^^
auto operator()( T t, Us ...us ) const -> decltype( t + Impl()( us... ) )

The "typename Impl = sum_impl" is a default function template parameter, new in C++11. If you don't specify it explicitly, Impl defaults to sum_impl. We won't specify it explicitly, but when the compiler first sees this code (in phase 1), it doesn't know that. Instead, when the compiler sees this...

decltype( t + Impl()( us... ) )

... the compiler must be patient and wait until phase 2, when it knows what Impl is, before it can resolve the function call. And that's precisely the point.

Sum-mary

With the above trick, our sum() function now compiles for three or more arguments. In short, when the compiler isn't finding the thing it should be finding, and you're yelling at the computer, "BUT IT'S RIGHT THERE!!!", pause and consider that maybe you too have been bitten by the phases of name lookup. Try the default function template parameter trick to make your expressions dependent.

A Look to C++14

The good news is that the problem described above is about to disappear. The C++ committee is in the process of approving return type deduction for regular functions the same way as it already works for lambdas, with the happy result that you won't even have to bother to write sum's return type at all (including not having to write decltype) because it will be deduced from the return statement in the body, at which point everything is happily in scope and Just Works.

In particular, the variadic sum() will be simply:

template< typename T, typename ...Us >
auto sum( T t, Us ...us )         // look ma, no "->"
{
  return t + sum( us... );
}

See Jason Merrill's paper N3386 for details. This proposal is on track to be adopted for C++14, and has already been implemented in the current development branch of GCC; to try it out, get the current development snapshot of GCC (or wait for GCC 4.8 in a few months) and compile with the -std=c++1y switch.

Automatic return type deduction, already becoming available in GCC and soon other compilers, is another example of how C++ continues to become simpler and remove the need for knowing about old-C++ corner cases. As simpler alternatives are added, we can just stop using the older complex ways in our new code, even while enjoying C++'s great backward compatibility for our older existing code.

C++ Optimization Manuals -- Agner Fog

By Bartosz Bielecki | Dec 13, 2012 10:51 AM | Tags: advanced

[Ed.: Many thanks to reader Bartosz Bielecki for directing our attention to a good resource for all the performance tweak-heads out there. You know who you are.]

Agner Fog's C++ Optimization Manuals

submitted by Bartosz Bielecki

Agner Fog's site is one of the most important pages related to software optimization (also for the C++). You will find following guides there:

C++ optimization,

assembly optimization,

CPU instructions choice,

C++ calling conventions,

and various other links/tools.

If you have not been there, it is high time you did it!

Value Semantics and Concepts-Based Polymorphism -- Sean Parent

By Eric Niebler | Dec 13, 2012 10:50 AM | Tags: advanced

This past year at C++Now, Sean Parent gave a talk about Value Types that blew the room away. It will deepen your understanding of the design of the STL and change the way you think about and write code. He'll also show you some lean-and-mean image-processing demos that will drop your jaw. This is why we do C++.

Value Semantics and Concepts-Based Polymorphism

by Sean Parent

Sean will further develop the Value Semantics and Concepts-based Polymorphism concepts covered in his keynote, "Now What? A vignette in 3 parts."

Note: The audio is soft. Turn your volume up. The slides, the Keynote presentation, and the source code can be found in C++Now's GitHub repo here.

Watch the video...

Use CRTP for Polymorphic Chaining -- Marco Arena

By Marco Arena | Dec 10, 2012 01:27 PM | Tags: advanced

Use CRTP for Polymorphic Chaining

by Marco Arena

This suggested video reminded me another use of CRTP I described some months ago. It was about how to support method chaining when inheritance is involved.

Consider this simple scenario:

struct Printer
{
   Printer(ostream& stream) : m_stream(stream) {}

   template<typename T>
   Printer& println(T&& message)
   {
      cout << message << endl;
      return *this;
   }

protected:
   ostream& m_stream;
};

struct CoutPrinter : public Printer
{
   CoutPrinter() : Printer(cout) {}

   CoutPrinter& color(Color c) 
   {
      // change console color
      return *this;
   }
}

//...

CoutPrinter printer;
printer.color(red).println("Hello").color( // OOPS

println("Hello") returns a Printer& and not a CoutPrinter&, so color is no longer available.

In this post I wrote a very simple approach based on CRTP to maintain the chaining relationship when inheritance is involved. I also propose a complicated-at-first-sight way to avoid duplication employing a bit of metaprogramming.