Home » Blog » Tags » efficiency

efficiency

Sometimes you get things wrong--Marshall Clow

By Adrien Hamelin | Feb 8, 2016 06:11 AM | Tags: intermediate efficiency

What is the best thing to return?

Sometimes you get things wrong

by Marshall Clow

From the article:

A few years ago, Sean Parent challenged me to provide an implementation of Boyer-Moore searching in C++. I did that, first in boost and then, later as part of the proposed Library Fundamentals Technical Specification.

The idea here is that you have a searcher object, which encapsulates the actual searching. You construct it with the pattern that you want to search for, and then you call the searchers operator() with the corpus that you want to search, and it will return to you the start of the pattern in the corpus, if it exists, and the end of the corpus, if it does not (this is the same set of rules that std::search follows).

But this weekend I realized that this is not the right thing to return. The searcher (and std::search for that matter) should return a “range” (ok, a pair of iterators) denoting the beginning and end of the pattern in the corpus. (Yes, you can get the end of the pattern by incrementing the returned iterator by the length of the pattern, but that’s an O(N) operation if you only have forward iterators...

Raw loops vs STL algorithms

By Meeting C++ | Feb 4, 2016 10:00 AM | Tags: intermediate efficiency c++14 c++11 basics

A new post on the Meeting C++ blog, this time on <algorithm>

Raw loops vs. STL algorithms

by Jens Weller

From the article:

Since last week I am working on my CMS for static HTML pages again, and so the series about Building applications with Qt and boost continues. Today its about using STL algorithms, or how Sean Parent once said "no raw loops!". Now, I am not Sean Parent, and not event the implementers of the STL are perfect. Most code which I write is application code, which then powers Meeting C++. Also, I don't know all STL algorithms, and some times its just to tempting to write a little loop instead of searching the STL for the specific algorithm. Yesterday I had such a case.

Both keynotes from Meeting C++ 2015 are now online!

By Meeting C++ | Dec 21, 2015 08:47 AM | Tags: video performance keynote intermediate efficiency basics advanced

See Chandler Carruth and Lars Knoll giving the keynotes at Meeting C++ this year:

Both Keynotes from Meeting C++ 2015 are online!

by Jens Weller

From the article:

Great news: Since yesterday, both of the keynotes from this years Meeting C++ conference are on youtube! Both keynote speakers chose to speak on a specific topic, and delivered very well. There is also a playlist for Meeting C++ 2015.

All Meeting C++ Lightning Talk videos are online

By Meeting C++ | Dec 11, 2015 09:03 AM | Tags: performance intermediate efficiency c++14 c++11 boost basics advanced

Meeting C++ just started a week ago, and I already managed to edit and upload all lightning talks:

Meeting C++ 2015 - all lightning talks are now online at youtube

by Jens Weller

From the article:

This year for the very first time we had lightning talks at the Meeting C++ conference. Two sessions with each 5 lightning talks were held...

The Variant Saga: A happy ending?

By Axel | Nov 6, 2015 04:32 PM | Tags: intermediate experimental efficiency

Variant is like a union, only it tells you what it currently contains, and it will barf if you try to get something out of it that is does not currently contain. It's the type safe sibling of the union:

variant<double, string> v = 42.;
double d = get<double>(v);

I had proposed a variant many moons ago (N4218). After many discussions it seemed that the committee cannot agree on what the ideal C++ variant would look like. I will resolve this cliffhanger -- but before doing that let me introduce you to some of the key discussion points.

An ideal variant will always contain one of its alternative types. But look at this code snippet:

variant<string, MyClass> v = "ABC";
v = MyClass();

The second line will destroy the old value contained in the variant and construct the new value of a different type. Now suppose that the MyClass construction threw: what will the variant contain? What happens when you call get<1>(v)? What happens when the variant gets destroyed?

We either provide the strong exception guarantee (the variant would still contain the string) -- but this requires double buffering, as for instance boost::variant does. Or we could restrict the alternative types to only those that are nothrow_move_constructible. Or we make this a new state -- "invalid, because the variant has been derailed due to an exception thrown during type changing assignment". Or we say "you shouldn't write code that behaves like this; if you do you're on your own", i.e. undefined behavior. The committee was discussing what to do, and so was The Internet. There are other design decisions -- default construction, visitation etc -- but they are all insignificant compared to how to deal with the throwing, type-changing assignment.

I have tried to present the options and their pros and cons in P0086. In short: it's incredibly difficult and fragile to predict whether a type is_nothrow_move_constructible. And double buffering -- required for a strong exception guarantee -- kills the quest for an efficient variant. But efficiency is one of the main motivations for using a discriminated union.

After the second Library Evolution Working Group (LEWG) review in Lenexa, we got P0088R0: a design that was making this invalid state extremely rare. But if it happened, access to the value would result in undefined behavior. This caused a vivid reaction from the committee members. And from The Internet. Hundreds of emails on the committee email lists. Many many smart and convincing blog posts.

In the end, different parts of the committee strongly supported different designs -- and vetoing other designs. Massive disagreement. So when we came to our C++ Standards Meeting in Kona, it was immediately clear that we needed to expose this to the full committee (and not just LEWG). The expectation was that we would declare variant dead, and keep it locked away for the next five years. At least. (An I would have time to water my fishes again.)

So back to the cliffhanger. On the full committee, Monday evening stage in Kona were David Sankel and I. We presented (and represented) the different design options. While we were discussing with the committee members, live and uncut and on stage, David and I realized that we could make it happen. "The Kona Kompromise": similar to P0088R0, but instead of undefined behavior when extracting the value of such a zombie variant it would just throw!

The Kona Kompromise means that we don't pay any efficiency for the extremely rare case of a throwing move. The interface stays nice and clean. A variant of n alternatives is a "mostly" an n-state type. It offers the basic exception guarantee at no relevant performance loss. It is a safe vocabulary type for every-day use, also for novices. The vast majority of the committee was convinced by this idea. Almost everyone in the room was happy!

Do we have a std::variant now? Not yet. But we are a giant leap closer: variant is now under wording review with the Library Working Group (LWG); I will publish a new revision in the Kona post-mailing (P0088R1). This will get re-reviewed in Jacksonville, first week of March. Once LWG gives the green light, the full committee can vote variant into a Technical Specification (TS) as std::experimental::variant. Now that a large fraction of the committee has expressed its consent (happiness, even!), I expect that this will be in the TS called Library Fundamentals, v3. It might or might not make it into C++17 -- that depends mostly on how quickly I manage to bring P0088 into an acceptable state, and how quickly we will gain use experience with variant.

So there is one thing I'd really appreciate your help with: std::experimental::variant will show up in library implementations near you, likely in their first releases next year. It would be fantastic if you could try it out, and as importantly: give feedback, on the public forums or by contacting me directly (axel@cern.ch). Your feedback will tell us whether the design decisions we took are the right ones, for instance regarding default construction, visitation, performance, and especially converting construction and assignment. As they say here: Mahalo!

Axel Naumann, CERN (axel@cern.ch)

 

Random Acts of Optimization --Tony Albrecht

By Mantosh Kumar | Oct 29, 2015 01:16 AM | Tags: performance efficiency

Discussion regarding systematic approach to go about optimization of logic.

Random Acts of Optimization

by Tony Albrecht

From the article:

The three stages mentioned here, while seemingly obvious, are all too often overlooked when programmers seek to optimize. Just to reiterate:

    1. Identification: profile the application and identify the worst performing parts.
    2. Comprehension: understand what the code is trying to achieve and why it is slow.
    3. Iteration: change the code based on step 2 and then re-profile. Repeat until fast enough.

The solution above is not the fastest possible version, but it is a step in the right direction—the safest path to performance gains is via iterative improvements.

Video available: Chandler Carruth, "Tuning C++: Benchmarks, and CPUs, and Compilers!" -- CppCon

By Felix Petriconi | Sep 29, 2015 06:20 AM | Tags: performance efficiency advanced

Chandler's talk about benchmarking, cheating the compiler's optimizer and optimizing code from the recent CppCon is online.

Tuning C++: Benchmarks, and CPUs, and Compilers! Oh My! (YouTube)

by Chandler Carruth, CppCon 2015

From the talk's outline:

A primary use case for C++ is low latency, low overhead, high performance code. But C++ does not give you these things for free, it gives you the tools to control these things and achieve them where needed. How do you realize this potential of the language? How do you tune your C++ code and achieve the necessary performance metrics?

This talk will walk through the process of tuning C++ code from benchmarking to performance analysis. It will focus on small scale performance problems ranging from loop kernels to data structures and algorithms. It will show you how to write benchmarks that effectively measure different aspects of performance even in the face of advanced compiler optimizations and bedeviling modern CPUs. It will also show how to analyze the performance of your benchmark, understand its behavior as well as the CPUs behavior, and use a wide array of tools available to isolate and pinpoint performance problems. The tools and some processor details will be Linux and x86 specific, but the techniques and concepts should be broadly applicable.

CppCon 2014 Costless Software Abstractions for Parallel Architectures--Joel Falcou

By Adrien Hamelin | Jul 22, 2015 08:00 AM | Tags: experimental efficiency

Have you registered for CppCon 2015 in September? Don’t delay – Registration is open now.

While we wait for this year’s event, we’re featuring videos of some of the 100+ talks from CppCon 2014 for you to enjoy. Here is today’s feature:

Costless Software Abstractions for Parallel Architectures

by Joel Falcou

(watch on YouTube) (watch on Channel 9)

Summary of the talk:

Performing large, intensive or non-trivial computing on array like data structures is one of the most common task in scientific computing, video game development and other fields. This matter of fact is backed up by the large number of tools, languages and libraries to perform such tasks. If we restrict ourselves to C++ based solutions, more than a dozen such libraries exists from BLAS/LAPACK C++ binding to template meta-programming based Blitz++ or Eigen. If all of these libraries provide good performance or good abstraction, none of them seems to fit the need of so many different user types.

Moreover, as parallel system complexity grows, the need to maintain all those components quickly become unwieldy. This talk explores various software design techniques - like Generative Programming, MetaProgramming and Generic Programming - and their application to the implementation of a parallel computing librariy in such a way that:

- abstraction and expressiveness are maximized - cost over efficiency is minimized

We'll skim over various applications and see how they can benefit from such tools. We will conclude by discussing what lessons were learnt from this kind of implementation and how those lessons can translate into new directions for the language itself.