Home » Blog » Categories »

Efficiency with Algorithms, Performance with Data Structures -- Chandler Carruth

By George Ryan | Dec 2, 2014 08:38 AM | Tags: performance c++14 c++11

carruth-cppcon2014.PNGAt the recent CppCon 2014, Chandler Carruth gave a great talk on using Modern C++ for writing high-performance applications. 

Efficiency with Algorithms, Performance with Data Structures

by Chandler Carruth

From the video introduction:

C++ programmers throughout the industry have an insatiable desire for writing high performance code. Unfortunately, even with C++, this can be really challenging. Over the past twenty years processors, memory, software libraries, and even compilers have radically changed what makes C++ code fast. Even measuring the performance of your code can be a daunting task. This talk will dig into how modern processors work, what makes them fast, and how to exploit them effectively with modern C++ code.

Quick Q: How do I add elements to a 2D vector of ints?--StackOverflow

By Jared Mulconry | Dec 2, 2014 03:56 AM | Tags: basics

Quick A: Index into the desired sub-vector and call push_back.

Recently on SO:

Inserting elements into 2D vector

So I'm creating a class that implements an adjacency list. Currently in my class definition I initialized two vectors:

vector<vector<int>> adjList;
vector<int> neighbors;

and I declared two functions that I plan to use to make it:

bool constructAdjList();
bool insertIntoAdjList(int, int);

It's getting difficult wrapping my head around 2D vectors. I understand that it is essentially a vector of vectors, but I'm confused about how to insert a new value into one of the "subvectors". For example, I am able to create an adjacency list in createAdjList that is empty with the following loop:

for (int i = 0; i < numOfValues; i++){
    neighbors.push_back(0);
    adjList.push_back(neighbors);
    neighbors.clear();
}

But how can I say, push_back the value 5 to the 4th vector in adjList, which would be represented in my insertIntoAdjList function as

insertIntoAdjList(4, 5);

I know I can access a specific value in a 2D vector by saying adjList[4][1], but how can I push one onto it?

Thanks!

A quick poll about order of evaluation -- Herb Sutter

By Blog Staff | Dec 1, 2014 01:48 PM | Tags: None

A quick Monday poll:

A quick poll about order of evaluation...

by Herb Sutter

From the article:

Consider this program fragment:

std::vector<int> v = { 0, 0 };
int i = 0;
v[i++] = i++;
std::cout << v[0] << v[1] << endl;

My question is not what it might print under today’s C++ rules. The third line runs afoul of two different categories of undefined and unspecified behavior.

Rather, my question is what you would like the result to be. Please let me know... [click for poll]

New optimizations for X86 in upcoming GCC 5.0 -- Evgeny Stupachenko

By Razvan Pascalau | Dec 1, 2014 07:11 AM | Tags: performance gcc efficiency compiler advanced

Fresh on the Intel Developer Zone blog:

New optimizations for X86 in upcoming GCC 5.0

by Evgeny Stupachenko

From the article:

Part 1. Vectorization of loads/stores group.

GCC 5.0 significantly improves vector code quality for load groups and store groups. By loads/stores group I mean iterated consecutive sequence of loads/stores. For example:

x = a[i], y = a[i + 1], z = a[i + 2] iterated by “i” is loads group of size 3

...

The most frequent case where loads/stores groups are applicable is array of structures.
  1. Image conversion (RGB structure to some other) ...
  2. N-dimentional coordinates. (Normalize array of XYZ points) ...
  3. Multiplication of vectors by constant matrix: ...

... GCC 5.0:

  1. Introduces vectorization of load/store groups of size 3
  2. Improves load groups vectorization for all supported sizes
  3. Maximizes load/store groups performance by generating code that is more optimal for particular x86 CPU...

 

Facebook Flint: Public domain C++ lint

By Felix Petriconi | Dec 1, 2014 02:02 AM | Tags: intermediate

Some months ago Facebook brought their C/C++ Facebook-Lint (Flint) analyzer into public domain and made it available on github.com/facebook/flint. Flint provides a lint framework and a number of C++11/14 style rules that we have found useful in our company.

This static code analyzer is not based on a C++ parser, but works with a tokenizer, completely written in D. (The previous C++ version of the program is still part of the repository.) 

Andrei Alexandescu gives detailed information in his blog entry:

Under the Hood: Building and open-sourcing flint

by Andrei Alexandrescu

... Writing a C++ linter in particular is not for the faint of heart because of C++'s high barrier to entry for parsing. That said, there are now dozens of C++ lint programs with a variety of features, some open sourced. So the natural question is why we chose to write our own instead of using a pre-existing one.

When we started this project, the lint programs we tried were too slow and most didn't support the C++11 features that our codebase had already started to use. Clang, which today would be logical starting point for a C++ analysis tool, offered too little support back then...

The distributed makefile is designed to work on Mac OS and Linux. But it is pretty easy to build a working flint.exe for Windows with Visual Studio and an installed D compiler and the corresponding plugin.

We prefer in our company either pairing or code reviews to ensure a high code quality. But we decided to use Flint as an additional safety-net and since the speed of the analyzer is so amazingly high, we were able to integrate it into the pre-commit hook of our Mercurial repository without any noticable performance drawbacks. So all to be committed C++ files are checked against a subset of all rules, that Flint supports.

(We disabled some Flint rules in the source code, because of missing C++11 capabilities of Visual Studio 2012/2013 and certain checks that does not make sence in our context.)

Consider automatically applying a lint tool in your project build. Whether you pick this or another one, it's worth checking out.

Quick Q: Are "++a" and "a = a.load() + 1" equivalent if 'a' is "atomic<int>"?--StackOverflow

By Jared Mulconry | Dec 1, 2014 01:57 AM | Tags: intermediate c++11

Quick A: No. Between a.load() and the addition and store to a is a window in which other threads can change the value of a, causing updates to be lost.

Recently on SO:

c++ atomic read/write misunderstanding

Why program with this code sometimes prints "2"?

int main() {
    std::atomic<int> a;
    a = 0;

    std::thread t1([&]{++a;});
    std::thread t2([&]{a++;});
    std::thread t3([&]{
        a = a.load() + 1;
    });

    t1.join();
    t2.join();
    t3.join();

    if (a != 3) {
        std::cout << "a: " << a << std::endl;
    }
}

I've thought std::atomic guarantees that all operations will be done atomically so writing here(incrementing) will use a memory barrier and we will have always "3" at the end of threads work. I've explored the code and found out that the problem thread is t3 but I can't understand why it is wrong.

C++ User Group Meetings in December

By Meeting C++ | Nov 30, 2014 08:39 AM | Tags: user group community

Its again the time to list the monthly meetings, this time its for December:

C++ User Group Meetings in December

by Jens Weller

From the Article

Three years ago, my own user group had its first meeting in December, being the second active C++ user group in Europe back in 2011. Since then a lot has changed, this December there are a lot more user groups meeting, and also we'll have the last premier C++ Event of the year: Meeting C++ is next week!

Meetings in December

    1.12 C++ UG Hungary - Template Metaprogramming With Better Tools
    2.12 C++ UG Chicago - The Bash Bug And The OpenSSL Bug
    3.12 C++ UG Saint Louis - Next meeting
    3.12 C++ UG Austin - Double Feature
    4.12 C++ UG Dublin - std::begin
    9.12 C++ UG San Francisco/ Bay area - C++11's New Pointer Types
    10.12 C++ UG Utah - Iterators\, Containers and Algorithms in the Standard Library
    10.12 C++ UG San Francisco/ Bay area - Presentation and Q&A
    11.12 C++ UG Dresden - Dezember Treffen
    13.12 C++ UG Pune, India - Introduction to C++ Template Metaprogramming and Domain Specific
    15.12 C++ UG Denver - Denver Tech Center C++ Developers
    15.12 C++ UG Austin - North Austin Monthly C/C++ Pub Social
    17.12 C++ UG Düsseldorf - Christmas special!
    18.12 C++ UG Paris - C++ FRUG #5 - L'asynchronisme en deux talks
    18.12 C++ UG Amsterdam - Let's have a meetup in December
    18.12 C++ UG Hamburg - Qt DevDays & Meeting C++

ODE simulations with Boost.odeint and Boost.SIMD

By Meeting C++ | Nov 30, 2014 08:36 AM | Tags: intermediate boost advanced

A very nice article on how to use boost::odeint and SIMD:

Boosting ODE simulations with Boost.odeint and Boost.SIMD

by Mario Mulansky

From the article:

Ordinary Differential Equations appear in numerous applications and finding their solution is a fundamental problem in science and engineering. Often one has to rely on numerical methods to approximate such solutions as in the presence of nonlinearities, no analytic solution can be found. Being such a frequent problem...

Design Patterns Revisited -- Bob Nystrom

By Mantosh Kumar | Nov 28, 2014 10:01 AM | Tags: intermediate

Walk through (with practical examples) a handful of the original patterns the Gang of Four documented in C++.

Design Patterns Revisited

Design Patterns: Elements of Reusable Object-Oriented Software is nearly twenty years old by my watch. Unless you’re looking over my shoulder, there’s a good chance Design Patterns will be old enough to drink by the time you read this. For an industry as quickly moving as software, that’s practically ancient. The enduring popularity of the book says something about how timeless design is compared to many frameworks and methodologies.

While I think Design Patterns is still relevant, we’ve learned a lot in the past couple of decades. In this section, we’ll walk through a handful of the original patterns the Gang of Four documented. For each pattern, I hope to have something useful or interesting to say.

I think some patterns are overused (Singleton), while others are underappreciated (Command). A couple are in here because I want to explore their relevance specifically to games (Flyweight and Observer). Finally, sometimes I just think it’s fun to see how patterns are enmeshed in the larger field of programming (Prototype and State).