Home » Blog » 2012 » November

Compile Time Computations -- Andrzej Krzemieński

By Blair Davidson | Nov 30, 2012 02:38 PM | Tags: advanced

[Ed.: This is an old post but we feel it has valuable information about constexpr.]

This is a good article about constant expressions and computations at compile time. It gives good coverage of the new constexpr keyword for allowing compile-time and run-time evalution. constexpr is discussed rigorously with information on the rules required by the facility.

Compile-Time Computations

by Andrzej Krzemieński

[...] But now, consider the following example:
const int i = 2;

const char array[ i == 2 ? 64 : throw exception() ];
Throwing an exception (which is an expression) cannot be evaluated at compile-time, but since i == 2 is true, the third argument of conditional operator should not be evaluated; at least at run-time. So is the above a valid code? Not in C++03. It is valid however in C++11. Does this sound incredible? [...]

Applied Informatics C++ Libraries and Tools Release 2012.1 now available

By Blog Staff | Nov 30, 2012 12:21 PM | Tags: None

Release 2012.1 of Applied Informatics C++ Libraries and Tools is now available.

These libraries extend the POCO C++ Libraries with additional features, including:

Remoting for RPC/IPC and SOAP/WSDL web services, including SOAP 1.1 and 1.2
Open Service Platform for building modular, extensible applications
DNSSD/Zeroconf
Universal Plug and Play (UPnP)
Fast Infoset processing
Secure remote access to smart devices.

New in release 2012.1 are:

Support for C++ code generation from XML Schema and WSDL documents
Allowing Remoting to invoke SOAP 1.1/1.2 web services created using other middleware technologies such as Java JAX-WS or Microsoft .NET WCF
New Remoting featuers to support MTOM, HTTP Basic and Digest authentication and HTTP compression (gzip content encoding), as well as remote events with the new TCP transport

A free evaluation version is available for download.

Exception-Safe Coding in C++ -- Jon Kalb

By Blair Davidson | Nov 30, 2012 10:04 AM | Tags: intermediate

Jon Kalb from the C++ Now 2012 conference.

Exception-Safe Coding in C++

by Jon Kalb

Are you 100% confident that your code is exception-safe?

Safe usage of exceptions is a non-trivial problem that the industry has struggled with for the better part of two decades. If you have fear, uncertainty, or doubt about exception safety or just want to see the best practices for using exceptions in C++, this session is for you. We'll start with "What is the problem we are trying to solve?" and discuss alternatives, acknowledge the challenges associated with with exception usage, and cover some well-meaning but misguided attempts at safety. I will then present a set of guidelines that are the basis for safe exception usage and solid implementation techniques, including how to transition from an exception-unsafe legacy code base.

When we are finished you will know how to produce code that is easier to write, easier to understand, faster, and 100% robust in the face of exceptions.

This is a two part video series. Links:

Part 1: http://www.youtube.com/watch?v=N9bR0ztmmEQ
Part 2: http://www.youtube.com/watch?v=UiZfODgB-Oc

Enjoy!

Learn How to Capture by Move -- Marco Arena

By Marco Arena | Nov 30, 2012 08:05 AM | Tags: advanced

[Ed.: C++11 lambdas support capturing local variables by value and by reference... but not by move. This will likely be addressed in the next standard, but in the meantime we need workarounds, usually involving a shared_ptr, to get the right behavior. In this article, Marco Arena looks at the shared_ptr approach and offers another potential helper. Observing the tradeoffs in these workarounds can instructive.]

Learn How to Capture by Move

by Marco Arena

what if I want to capture by moving an object instead of both copying and referencing? Consider this plausible scenario:
function<void()> CreateLambda()

{

    vector<HugeObject> hugeObj;

    // ...preparation of hugeObj...


    auto toReturn = [hugeObj] { ...operate on hugeObj... };

    return toReturn;

}
This fragment of code prepares a vector of HugeObject (e.g. expensive to copy) and returns a lambda which uses this vector (the vector is captured by copy because it goes out of scope when the lambda is returned). Can we do better?

"Yes, of course we can!" – I heard. "We can use a shared_ptr to reference-count the vector and avoid copying it." ...

Introduction to Modern C++ Techniques -- Michael Caisse

By Blair Davidson | Nov 28, 2012 10:04 AM | Tags: intermediate advanced

Brilliant talk from Michael Caisse from C++ Now 2012.

Introduction to Modern C++ Techniques

by Michael Caisse

Topics include:

Policy Based Design

SFINAE

Tag Dispatching

Traits

Curious Recurring Template Pattern

This is a two part video series. Links:

Part 1: http://www.youtube.com/watch?v=9TFV2JxX7L0
Part 2: http://www.youtube.com/watch?v=urshrBatNo4

Enjoy!

C++ Benchmark: std::vector vs. std::list -- Baptiste Wicht

By Baptiste Wicht | Nov 27, 2012 10:04 AM | Tags: intermediate

[Ed.: Another reason why vector is the default (not only, but preferred) standard container.]

C++ Benchmark: std::vector vs. std::list

by Baptiste Wicht

In C++, two of the most used data structures are std::vector and std::list. In this article, their performance is compared in practice on several different workloads.

It is generally said that a list should be used when random insert and remove will be performed (performed in O(1) versus O(n) for a vector). If we look only at the complexity, search in both data structures should be roughly equivalent, complexity being in O(n). When random insert/replace operations are performed on a vector, all the subsequent data needs to be moved and so each element will be copied. That is why the size of the data type is an important factor when comparing those two data structures.

However, in practice, there is a huge difference, the usage of the memory caches. All the data in a vector is contiguous where the std::list allocates separately memory for each element. How does that change the results in practice ?

This article shows the difference in performance between these two data structures.

Modules: Update on work in progress -- Doug Gregor

By Blog Staff | Nov 26, 2012 11:56 AM | Tags: experimental

[Updated to add video link]

Earlier this month, Doug Gregor gave a presentation on Modules at the November 2012 LLVM Developers' Meeting. Doug is lead Clang developer at Apple, chairs the WG21 Study Group on Modules (SG2), and in this talk reports his design goals and partial progress to date on designing and implementing a module system for C++. This talk is an extended version of the presentation Doug made at the Feb 2012 ISO C++ meeting in Kona.

The talk slides and video recording is available via the 2012 DevMeeting page.

Standardization note: SG2 was formed in February and has been relatively quiet as a handful of experts (notably Doug with Clang) make further progress on proof-of-concept designs and implementations. As this prototyping work coalesces, SG2 is expected to become active early in the new year.

Modules (MP4 video) (PDF slides)

Doug Gregor -- Apple

The C preprocessor has long been a source of problems for programmers and tools alike.

Programmers must contend with widespread macro pollution and #include-ordering problems due to ill-behaved headers. Developers habitually employ various preprocessor workarounds, such as LONG_MACRO_PREFIXES, #include guards, and the occasional #undef of a library macro to mitigate these problems.

Tools, on the other hand, must cope with the inherent scalability problems associated with parsing the same headers repeatedly, because each different preprocessing context could effect how a header is interpreted -- even though the programmer rarely wants it.

Modules seeks to solve this problem by isolating the interface of a particular library and compiling it (once) into an efficient, serialized representation that can be efficiently imported whenever that library is used, improving both the programmer's experience and the scalability of the compilation process.

Podcast: Hanselminutes interviews Herb Sutter

By Blog Staff | Nov 24, 2012 05:20 PM | Tags: None

A few weeks ago at the Build conference, Scott Hanselman sat down to talk with Herb Sutter about C++ and modern UI/UX. The podcast is now live here:

The Hanselminutes Podcast, Show #346

“Why C++” with Herb Sutter

Topics Scott and Herb discuss include:

2:00 Scott mentions he has used C++ in the past. C++ has changed. We still call it C++, but it’s a very different language now.
5:30 (Why) do we care about performance any more?
10:00 What’s this GPGPU thing? Think of your GPU as your modern 80387.
13:45 C++ is having a resurgence. Where is C++ big?
18:00 Why not just use one language? or, What is C++ good at? Efficient abstraction and portability.
21:45 Programmers have a responsibility to support the business. Avoid the pitfall of speeds & feeds.
24:00 Herb's experience with his iPad, his iPhone, and his Slate 7 with Win8.
28:45 We’re in two election seasons – (a) political and (b) technology (Nexus, iPad Mini, Surface, ...). Everyone is wallpapering the media with ads (some of them attack ads), and vying for customer votes/$$, and seeing who’s going to be the winner.
35:00 Natural user interfaces – we get so easily used to touch that we paw all screen, and Scott’s son gets so used to saying “Xbox pause” that anything that doesn’t respond is “broken.”

Dec 10-12, free online: CodeRage 7 C++ conference, with special guest Bjarne Stroustrup

By Blog Staff | Nov 23, 2012 10:46 AM | Tags: None

CodeRage 7 is a free C++-themed online developer conference by Embarcadero, running from December 10-12 (Mon-Wed). Many of the sessions are vendor-specific, focusing notably on C++Builder, but there are two notable sessions likely of interest to C++ developers on all platforms.

SPECIAL SESSION: A C++ Conversation with Bjarne Stroustrup

Bjarne Stroustrup and David Intersimone

Monday, December 10th - 8:00am - 8:45am PST (find your local time)

Bjarne Stroustrup will discuss the ISO C++11 standard, new language features, how C++11 builds on C++’s strengths, application portability, and C++’s ubiquitous presence in the markets.

The Resurgence of C++ for Application Development

John Thomas - Embarcadero

Tuesday, December 11th - 9:00am - 9:45am PST (find your local time)

Why C++ is back and coming on strong, and not just for "infrastructure." Believe it.

More information...

On vector<bool> -- Howard Hinnant

By Howard Hinnant | Nov 22, 2012 12:20 PM | Tags: advanced

On vector<bool>

by Howard Hinnant

vector<bool> has taken a lot of heat over the past decade, and not without reason. However I believe it is way past time to draw back some of the criticism and explore this area with a dispassionate scrutiny of detail.

There are really two issues here:

Is the data structure of an array of bits a good data structure?
Should the aforementioned data structure be named vector<bool>?

I have strong opinions on both of these questions. And to get this out of the way up front:

Yes.
No.

The array of bits data structure is a wonderful data structure. It is often both a space and speed optimization over the array of bools data structure if properly implemented. However it does not behave exactly as an array of bools, and so should not pretend to be one.

First, what's wrong with `vector<bool>`?

Because vector<bool> holds bits instead of bools, it can't return a bool& from its indexing operator or iterator dereference. This can play havoc on quite innocent looking generic code. For example:

template <class T>
void
process(T& t)
{
    // do something with t
}

template <class T, class A>
void
test(std::vector<T, A>& v)
{
    for (auto& t : v)
        process(t);
}

The above code works for all T except bool. When instantiated with bool, you will receive a compile time error along the lines of:

error: non-const lvalue reference to type 'std::__bit_reference<std::vector<bool, std::allocator<bool>>, true>' cannot bind to
      a temporary of type 'reference' (aka 'std::__bit_reference<std::vector<bool, std::allocator<bool>>, true>')
    for (auto& t : v)
               ^ ~
note: in instantiation of function template specialization 'test<bool, std::allocator<bool>>' requested here
    test(v);
    ^
vector:2124:14: note: selected 'begin' function
      with iterator type 'iterator' (aka '__bit_iterator<std::vector<bool, std::allocator<bool>>, false>')
    iterator begin()
             ^
1 error generated.

This is not a great error message. But it is about the best the compiler can do. The user is confronted with implementation details of vector and in a nutshell says that the vector is not working with a perfectly valid ranged-based for statement. The conclusion the client comes to here is that the implementation of vector is broken. And he would be at least partially correct.

But consider if instead of vector<bool> being a specialization instead there existed a separate class template std::bit_vector<A = std::allocator<bool>> and the coder had written:

template <class A>
void
test(bit_vector<A>& v)
{
    for (auto& t : v)
        process(t);
}

Now one gets a similar error message:

error: non-const lvalue reference to type 'std::__bit_reference<std::bit_vector<std::allocator<bool>>, true>' cannot bind to
      a temporary of type 'reference' (aka 'std::__bit_reference<std::bit_vector<std::allocator<bool>>, true>')
    for (auto& t : v)
               ^ ~
note: in instantiation of function template specialization 'test<std::allocator<bool>>' requested here
    test(v);
    ^
bit_vector:2124:14: note: selected 'begin' function
      with iterator type 'iterator' (aka '__bit_iterator<std::bit_vector<std::allocator<bool>>, false>')
    iterator begin()
             ^
1 error generated.

And although the error message is similar, the coder is far more likely to see that he is using a dynamic array of bits data structure and it is understandable that you can't form a reference to a bit.

I.e. names are important. And creating a specialization that has different behavior than the primary, when the primary template would have worked, is poor practice.

But what's right with `vector<bool>`?

For the rest of this article assume that we did indeed have a std::bit_vector<A = std::allocator<bool>> and that vector was not specialized on bool. bit_vector<> can be much more than simply a space optimization over vector<bool>, it can also be a very significant performance optimization. But to achieve this higher performance, your vendor has to adapt many of the std::algorithms to have specialized code (optimizations) when processing sequences defined by bit_vector<>::iterators.

`find`

For example consider this code:

template <class C>
typename C::iterator
test()
{
    C c(100000);
    c[95000] = true;
    return std::find(c.begin(), c.end(), true);
}

How long does std::find take in the above example for:

A hypothetical non-specialized vector<bool>?
A hypothetical bit_vector<> using an optimized find?
A hypothetical bit_vector<> using the unoptimized generic find?

I'm testing on an Intel Core i5 in 64 bit mode. I am normalizing all answers such that the speed of A is 1 (smaller is faster):

1.0
0.013
1.6

An array of bits can be a very fast data structure for a sequential search! The optimized find is inspecting 64 bits at a time. And due to the space optimization, it is much less likely to cause a cache miss. However if the implementation fails to do this, and naively checks one bit at a time, then this giant 75X optimization turns into a significant pessimization.

`count`

std::count can be optimized much like std::find to process a word of bits at a time:

template <class C>
typename C::difference_type
test()
{
    C c(100000);
    c[95000] = true;
    return std::count(c.begin(), c.end(), true);
}

My results are:

1.0
0.044
1.02

Here the results are not quite as dramatic as for the std::find case. However any time you can speed up your code by a factor of 20, one should do so!

`fill`

std::fill is yet another example:

template <class C>
void
test()
{
    C c(100000);
    std::fill(c.begin(), c.end(), true);
}

My results are:

1.0
0.40
38.

The optimized fill is over twice as fast as the non-specialized vector<bool>. But if the vendor neglects to specialize fill for bit-iterators the results are disastrous! Naturally the results are identical for the closely related fill_n.

`copy`

std::copy is yet another example:

template <class C>
void
test()
{
    C c1(100000);
    C c2(100000);
    std::copy(c1.begin(), c1.end(), c2.begin());
}

My results are:

1.0
0.36
34.

The optimized copy is approaches three times as fast as the non-specialized vector<bool>. But if the vendor neglects to specialize fill for bit-iterators the results are not good. If the copy is not aligned on word boundaries (as in the above example), then the optimized copy slows down to the same speed as the copy for A. Results for copy_backward, move and move_backward are similar.

`swap_ranges`

std::swap_ranges is yet another example:

template <class C>
void
test()
{
    C c1(100000);
    C c2(100000);
    std::swap_ranges(c1.begin(), c1.end(), c2.begin());
}

My results are:

1.0
0.065
4.0

Here bit_vector<> is 15 times faster than an array of bools, and over 60 times as fast as working a bit at a time.

`rotate`

std::rotate is yet another example:

template <class C>
void
test()
{
    C c(100000);
    std::rotate(c.begin(), c.begin()+c.size()/4, c.end());
}

My results are:

1.0
0.59
17.9

Yet another example of good results with an optimized algorithm and very poor results without this extra attention.

`equal`

std::equal is yet another example:

template <class C>
bool
test()
{
    C c1(100000);
    C c2(100000);
    return std::equal(c1.begin(), c1.end(), c2.begin());
}

My results are:

1.0
0.016
3.33

If you're going to compare a bunch of bools, it is much, much faster to pack them into bits and compare a word of bits at a time, rather than compare individual bools, or individual bits!

Summary

The dynamic array of bits is a very good data structure if attention is paid to optimizing algorithms that can process up to a word of bits at a time. In this case it becomes not only a space optimization but a very significant speed optimization. If such attention to detail is not given, then the space optimization leads to a very significant speed pessimization.

But it is a shame that the C++ committee gave this excellent data structure the name vector<bool> and that it gives no guidance nor encouragement on the critical generic algorithms that need to be optimized for this data structure. Consequently, few std::lib implementations go to this trouble.

The Resurgence of C++ for Application Development

On vector<bool>

First, what's wrong with vector<bool>?

But what's right with vector<bool>?

find

count

fill

copy

swap_ranges

rotate

equal

Summary

First, what's wrong with `vector<bool>`?

But what's right with `vector<bool>`?

`find`

`count`

`fill`

`copy`

`swap_ranges`

`rotate`

`equal`