Masking a Class in Boost.Graph -- Vadim Androsov

By Blog Staff | Jun 9, 2014 12:02 PM | Tags: boost advanced

Here's an experience report about using Boost's graph support in an existing game app, with some notes about Boost Concepts:

Masking a Class in Boost Graph. Part 1: Let the Interface Be

Masking a Class in Boost Graph. Part 2: Completing the Implementation of Concept Support

by Vadim Androsov

From the articles:

I had to rebuild a pathfinding algorithm for our game recently. The previous one (Boost Concepts) was bad as any sidestep was dangerous. So I wanted to take a ready algorithm from a good source. That’s exactly when I remembered about boost as there’s functionality for working with graphs. Unfortunately “find a function, call it and everything will work” approach wasn’t meant to be realized. The library is focused on the maximum use flexibility which has badly affected its simplicity. But it’s better than creating it from scratch (then fixing it). I didn’t want to bother with other libraries, while boost has already been used in the project. ...

Are lists evil? -- Bjarne Stroustrup

By Blog Staff | Jun 6, 2014 06:50 AM | Tags: None

Recently added to Bjarne Stroustrup's FAQ:

Are lists evil?

by Bjarne Stroustrup

From the FAQ:

According to some corners of the Web, I am under the impression that vectors are always better than linked lists and that I don't know about other data structures, such as trees (e.g. std::set) and hash tables (e.g., std::unordered_map). Obviously, that's absurd.

The problem seems to be an interesting little exercise that John Bentley once proposed to me: Insert a sequence of random integers into a sorted sequence, then remove those elements one by one as determined by a random sequece of positions: Do you use a vector (a contiguously allocated sequence of elements) or a linked list? For example, see Software Development for Infrastructure. I use this example to illustrate some points, encourage thought about algorithms, data structures, and machine architecture, concluding:

• don't store data unnecessarily,
• keep data compact, and
• access memory in a predictable manner.

Note the absence of "list" and "vector" in the conclusion. Please don't confuse an example with what the example is meant to illustrate.

I used that example in several talks, notably:

• My 2012 "Going Native" Keynote.

This video has been popular: It has been downloaded more than 250K times (plus another 50K+ times at verious other sites). My impression is that many viewers failed to understand that the purpose of that example is to illustrate some general principles and to make people think. Initially, most people say ``List of course!'' (I have tried asking that question many times) because of the many insertions and deletions ``in the middle'' (lists are good at that). That answer is completely and dramatically wrong, so it is good to know why.

I have been using the example for years, and had graduate students implement and measure dozens of variants of this exercise and different exercises. Examples and measurements by others can be found on the Web. Of course,

• I have tried maps (they are much better than lists, but still slower than vectors)
• I have tried much larger elements sizes (eventually lists come into their own)
• I have used binary search and direct insertion for vectors (yes, they speed up even further)
• I checked my theory (no I'm not violating any big-O complexity rule; it is just that some operations can be dramatically more expensive for one data structure compared to another)
• I have preallocated links (that's better than std::list but the traversal still kills performance)
• I have used singly-linked lists, forward_lists, (that doesn't make much difference, but makes it a bit harder to ensure that the user code is 100% equivalent)
• I know (and say) that 500K lists are not common (but that doesn't matter for my main point). We use many structures (large and small) where there is a choice between linked and contiguous reprentation.
• I know that for insertion push_front() is faster for std::lists and push_back()s is faster for vectors. You can construct examples to illustrate that, but this example is not one of those.

My point is not about lists as such. They have their uses, but this example isn't one of them. Please don't confuse the example with what the example is used to illustrate. This example is about use of memory: We very often create a data structure, do some computation on it requiring access (often, traversal), and then delete it. The ordered sequence is simply an example of such use and the example is presented to get people to think about what matters in such cases. My suggestion is:

• don't store data unnecessarily,
• keep data compact, and
• access memory in a predictable manner.

I emphasize the importance of cache effects. In my experience, all but true experts tend to forget those when algorithms are discussed.

And, yes, my recomendation is to use std::vector by default. More generally, use a contiguous representation unless there is a good reason not to. Like C, C++ is designed to do that by default.

Also, please don't make statements about performance without measurements. I have seen a case where changing a zero-to-two-element list to a zero-to-two-element vector made a factor-of-two difference to an algorithm. I didn't expect that. Nor did other experts looking at the code.

Lightweight HTTP Server in less than 40 Lines on libevent and C++11 -- NYM

By Blog Staff | Jun 3, 2014 11:18 AM | Tags: intermediate concurrency

Fresh on Kukuruku:

Lightweight HTTP Server in less than 40 Lines on libevent and C++11

by NYM

From the article:

Looking through programming articles sometimes I see posts about creating your own HTTP server. I am most interested in C++ so I often read blogs about it. After looking them through you could easily write you own web server “on sockets” using boost.asio or something else. I also examined libevent and libev. Each of them has its advantages. Libevent is of great interest to me for developing a small HTTP server. Considering some innovations in C++11 the code becomes much more space-efficient and allows for the creation of a basic HTTP server in less than 40 lines.

Ref-qualifiers -- Andrzej Krzemieński

By Blog Staff | Jun 3, 2014 06:40 AM | Tags: intermediate

The latest from the desk of Andrzej:

Ref-qualifiers

by Andrzej Krzemieński

From the article:

In this post I want to describe a small language feature added in C++11 that, although essential for full value semantics support, is often neglected in tutorials and in compiler implementations....

Overload 121 is now available

By Blog Staff | Jun 3, 2014 05:39 AM | Tags: None

Overload 121 is now available. It contains the following C++-related articles, and more:

Overload 121

Stop the Constant Shouting

CONSTANTS often shout. Jonathan Wakely considers why this happens in C and what the alternatives are in C++.

Minimal Overhead for Multiple Interfaces

Using multiple interfaces can slow things down. Daniel Gutson and Pablo Oliva present an alternative.

Writing min function, part 1: The rise of Concepts -- Fernando Pelliccioni

By Fernando Pelliccioni | May 28, 2014 07:32 PM | Tags: intermediate

[Ed: Note that this article series is not (yet) about C++ code, but it promises to go there and it has an interesting pedigree in its generic programming design analysis (Alex Stepanov) and reviewers (several ISO C++ participants including Andrzej Krzemienski and Dean Michael Berris.]

Writing min function, part 1: The rise of Concepts

by Fernando Pelliccioni

From the article:

This is the first in a series of articles in which I want to transmit what I learned (or what I think I learned) from the books, papers, lectures of Alexander Stepanov.

These are the lessons that Alex gives us, and I want to show them in this series:

• Specify our algorithms correctly
• Programming must be based on a solid mathematical foundation
• Designing our API’s consistently
• Not always the library implementations provided by the programming languages we use are correct, even though they are designed by “experts”.
• The concept of Stability
• Generic programming, of course!

Ref-qualified member functions -- Alexander Kulikov

By Blog Staff | May 28, 2014 07:23 PM | Tags: intermediate basics

Today on Kukuruku:

Ref-qualified member functions

by Alexander Kulikov

From the article:

Today I’m going to tell you about a new and a little known (to my mind) C++ feature — reference-qualified member functions. I’ll tell about the rules of such functions overloading and, as an example of use, I’ll show you that with the help of ref-qualified you can try to improve the resource management scheme, which is implemented with the help of another C++ idiom — RAII.

How Dropbox Uses C++ for Cross-Platform iOS and Android Development -- Ole Begemann

By Blog Staff | May 27, 2014 08:37 AM | Tags: None

Did you know that C++ is a hot language for mobile development? This seems to be widely known among C++ developers, but surprisingly widely unknown in the non-C++ programming community at large. Two of the major reasons why C++ is currently experiencing this surge in mobile interest are:

• C++'s efficiency and determinism help create power-sipping apps -- ones that not only use fewer CPU cycles, but use them in battery-friendly "bursty" ways that let the CPU sleep frequently, and deterministically let go of expensive resources like sensors immediately when they're not needed.
• C++'s portability makes it the only cross-platform language that can target every major and minor mobile phone and tablet platform -- including iOS, Android, Windows and Windows Phone, and Blackberry -- never mind of course as usual also targeting every other platform and environment too, from desktops to servers to datacenters where it's already the language of choice in companies from Google to Facebook.

In that vein, here's a post from just before the U.S. long weekend about using C++ for cross-platform mobile development.

Expect to see more news like this. Also, expect to see talks on using C++ for modern cross-platform mobile development as one of the hot topics at CppCon this September.

How Dropbox Uses C++ for Cross-Platform iOS and Android Development

by Ole Begemann

From the article:

When work started on the Mailbox app for Android, the team made the choice to write a large portion of the non-UI code in C++ — rather than rewriting the entire app in Java — with the goal of sharing that common C++ layer between iOS and Android. The iOS app used Core Data at the time, so migrating it off of Core Data to the shared C++ library was also part of the process. C++ seemed like an obvious choice because it is available on every platform and team members preferred the language over Java.

The Carousel team made the same choice since launching simultaneously on iOS and Android was an important goal from the start.

Quick Q: Why can't a data member be in a lamba capture list -- StackOverflow

By Blog Staff | May 22, 2014 12:01 PM | Tags: basics

Quick A: Because you can only capture local (stack) objects, including function parameters, and to access a data member in a member function you capture the local variable this.

Today on SO:

Why can't a data member be in a lamba capture list

I have a class foo that has bar as a member variable.

In another member function of the class, I'm writing a lambda function:

[bar](void){}

But I can't include bar in the capture list. Why is that?

Vector of Objects vs Vector of Pointers Updated -- Bartlomiej Filipek

By Blog Staff | May 22, 2014 07:30 AM | Tags: performance memory intermediate efficiency

More in the "contiguous enables fast" department:

Vector of Objects vs Vector of Pointers Updated

by Bartlomiej Filipek

From the article:

For 1000 particles we need on the average 2000 cache line reads! This is 78% more cache line reads than the first case! Additionally Hardware Prefetcher cannot figure out the pattern -- it is random -- so there will be a lot of cache misses and stalls.

In our experiment the pointer code for 80k of particles was more 266% slower than the continuous case.