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.

N3995: A proposal to add shared_mutex (untimed) (Revision 2) -- Gor Nishanov

By Blog Staff | Jun 5, 2014 08:46 AM | Tags: None

A new WG21 paper is available. A copy is linked below, and the paper will also appear in the next normal WG21 mailing. If you are not a committee member, please use the comments section below or the std-proposals forum for public discussion.

Document number: N3995

Date: 2014-05-20

A proposal to add shared_mutex (untimed) (Revision 2)

by Gor Nishanov

Excerpt:

This revision is a minor edit of an earlier paper N3961 that clarifies that proposed modifications to the standard be incorporated into the Concurrency Technical Specification N3993.

CppCon Program Preview, 3 of N -- Boris Kolpackov

By Blog Staff | Jun 5, 2014 07:26 AM | Tags: None

More CppCon 2014 accepted talks have just been announced, below. For past announcements about the conference program, see also:

• CppCon Program Preview, 2 of N
• CppCon Program Preview, 1 of N 
• CppCon 2104: Initial Partial Topics and Speakers

Super Early Bird registration has sold out, but Early Bird registration is available until June 30.

CppCon Program Preview, 3 of N

by Boris Kolpackov

From the announcement:

Herb Sutter: “Standardization Update: C++14 and the Seven Dwarfs”
Stephan T. Lavavej: “STL Features And Implementation Techniques”
Jared Hoberock: “Parallelizing the Standard Algorithms Library”
Howard Hinnant: “Types Don’t Know #”
Lisa Lippincott: “How to call C libraries from C++”

 

Herb Sutter: “Standardization Update: C++14 and the Seven Dwarfs"

Standardization has accelerated: By the time we meet at CppCon, C++14 might already be ratified. But that’s only one of eight (so far) work items now in flight. In this session, the chair of the ISO C++ committee will give a brief summary of the new features coming in C++14 itself, and then a tour of the seven (7) near-term separate Technical Specifications already underway — think of these as the “C++14 wave” of deliverables. The ISO C++ committee has transitioned to a “decoupled” model where updated versions of the standard are published more frequently, while at the same time major pieces of work can progress and be published independently from the Standard itself and delivered asynchronously in the form of Technical Specifications (TS’s) that are separate from the main Standard and can later be incorporated into the Standard. Come to this session to see how this is helping both the standard and C++ compiler implementations near you stay current with the latest in C++.

Speaker’s bio: Herb Sutter is the author of several best-selling books about C++, chair of the ISO C++ standards committee, and a software architect at Microsoft.

 

Stephan T. Lavavej: “STL Features And Implementation Techniques"

This session will cover selected STL features from C++11/14, both explaining how to use them and delving into implementation techniques that could be useful outside the STL. I will avoid covering popular features you’re already using (e.g. make_shared, make_unique) and obscure features of limited use (e.g. forward_list). The focus will be on useful but underappreciated features like dual-range algorithms, minimal allocators, and heterogeneous associative lookup.

Speaker’s bio: Stephan T. Lavavej is a Senior Developer at Microsoft. Since 2007, he’s worked with Dinkumware to maintain Visual C++’s implementation of the C++ Standard Library. He also designed a couple of C++14 features: make_unique and the transparent operator functors. He likes his initials (which people can actually spell) and cats (although he doesn’t own any).

 

Jared Hoberock: “Parallelizing the Standard Algorithms Library"

Until recently, C++ programmers building parallel programs found little support for parallelism in the standard toolbox. That’s changing with the technical specification on Extensions for Parallelism in C++. This talk will explore how programmers can build portable parallel programs from high-level parallel algorithms which can execute on CPU threads, vector units, and even GPUs.

Speaker’s bio: Jared Hoberock is a research scientist at NVIDIA where he develops the Thrust parallel algorithms library and edits the Technical Specification on Extensions for Parallelism for C++.

 

Howard Hinnant: “Types Don’t Know #“

This presentation will be based on the C++ standards committee proposal of a new hashing infrastructure that completely decouples hashing algorithms from individual types that need to be hashed. This decoupling divides the hashing computation among 3 different programmers who need not coordinate with each other:

1. Authors of hashable types (keys of type K) write their hashing support just once, using no specific hashing algorithm. This code resembles (and is approximately the same amount of work as) operator== and swap for a type.
2. Authors of hashing algorithms write a functor (e.g. H) that operates on a contiguous chunk of generic memory, represented by a void const* and a number of bytes. This code has no concept of a specific key type, only of bytes to be hashed.
3. Clients who want to hash keys of type K using hashing algorithm H will form a functor of type std::uhash<H> to give to an unordered container: unordered_set<K, uhash<H>>

Speaker’s bio: Howard Hinnant is a lead author of several C++11 features including: move semantics, unique_ptr, <mutex>, <condition_variable> and <chrono>. Coming in C++14: <shared_mutex>. Howard is also a lead author on two open source projects: a std::lib implementation and an Itanium ABI implementation.

 

Lisa Lippincott: “How to call C libraries from C++“

Many libraries used by C++ programs present C-like interfaces that are compatible with C++, but are not directly compatible with good C++ style. Using these libraries directly is error-prone in many of the ways C++ is designed to avoid. It is better to pass through an interface layer that presents good C++ style on the C++ side. But writing such an interface layer is daunting. Completing it may be an enormous task, as are documenting it and maintaining it as the underlying library evolves. To address this problem, I will present a style of writing such interfaces that can be used incrementally as needed, and that reduces documentation cost. I will also present a small library that supports the writing of interface layers in this style.

Speaker’s bio: Lisa Lippincott is a Chief Software Architect at Tanium, a bay-area startup. Her claim to fame is writing one phrase appearing in the C++ standard. In her spare time, she studies mathematical logic with a category-theoretic approach.

Schedule for Meeting C++ 2014 released

By Meeting C++ | Jun 5, 2014 02:57 AM | Tags: conference community c++

I have the honor to annouce the release of the schedule for this years Meeting C++ conference:

Meeting C++ 2014 Schedule

This years conference offers again few highlights and a lot of great C++ content. The keynotes will be given by Scott Meyers and Hartmut Kaiser. The conference will offer 21 Talks in 3 Tracks.

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.

Lang.NEXT Keynote: What -- If Anything -- Have We Learned from C++? -- Bjarne Stroustrup

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

Hot off the Channel 9 video press from last week's Lang.NEXT conference:

Lang.NEXT Keynote: What – if anything – have we learned from C++?

by Bjarne Stroustrup

What is the essence of C++? Why did it succeed despite its well-understood flaws? What lessons -- if any -- can be applied to newer languages?

Themes: Social and technical factors. Resource management. Generic programming. The importance of being inefficient. The importance of syntax. How (not) to specify a language. Standardization and compatibility. And no, I don't plan to condemn C++ -- it is still the best language around for a lot of things, and getting better. It just isn't anywhere near perfect (even of its kind) or the best at everything -- and was never claimed to be.

CppCon Program Preview, 2 of N -- Boris Kolpackov

By Blog Staff | Jun 2, 2014 08:40 AM | Tags: None

More CppCon 2014 accepted talks have just been announced, below. For past announcements about the conference program, see also CppCon Program Preview, 1 of N and CppCon 2104: Initial Partial Topics and Speakers.

Super Early Bird registration has sold out, but Early Bird registration is available until June 30.

CppCon Program Preview, 2 of N

by Boris Kolpackov

From the announcement:

Continuing with the program preview, the next set of accepted talks is below (summary first, abstracts following):

• Andrei Alexandrescu: “Mo’ Hustle Mo’ Problems”
• Andrew Sutton: “Generic Programming with Concepts Lite”
• Marshall Clow: “Hardening Your Code”
• Nate Kohl: “cppreference.com: Documenting C++ One Edit at a Time”
• Kate Gregory, James McNellis: “Modernizing Legacy C++ Code”

Andrei Alexandrescu: “Mo’ Hustle Mo’ Problems"

Reasonably-written C++ code will be naturally fast. This is due to C++’s excellent low-penalty abstractions and a memory model close to the machine. However, a large category of applications have no boundaries on desired speed, meaning there’s no point of diminishing returns in making code faster. Better speed means less power consumed for the same work, more workload with the same data center expense, better features for the end user, more features for machine learning, better analytics, and more. Optimizing has always been an art, and in particular optimizing C++ on contemporary hardware has become a task of formidable complexity. This is because modern hardware has a few peculiarities about it that are not sufficiently understood and explored. This talk discusses a few such effects, and guides the attendee on how to navigate design and implementation options in search for better performance.

Speaker’s bio: Andrei Alexandrescu is a researcher, software engineer, and author. He wrote three best-selling books on programming (Modern C++ Design, C++ Coding Standards, and The D Programming Language) and numerous articles and papers on wide-ranging topics from programming to language design to Machine Learning to Natural Language Processing. Andrei holds a PhD in Computer Science from the University of Washington and a BS in Electrical Engineering from University “Politehnica” Bucharest. He works as a Research Scientist for Facebook.

Andrew Sutton: “Generic Programming with Concepts Lite"

In this talk, I will give an overview of the Concepts Lite language extension for C++ and present examples of its use in design and implementation of real-world generic libraries. Concepts Lite provides the ability for programmers to directly state constraints on template arguments as part of the template declaration. These constraints are predicates which determine whether or not a template argument can be used with that template. Constraints are checked by the compiler at the point of use, meaning that that effectively constrained generic libraries will not suffer from the usual problems of insane diagnostics. Libraries written using concepts will be far more readable and maintainable than the status quo. This talk will focus on generic programming, proposed language features, and their use in building real-world libraries. Concepts Lite is a forthcoming ISO Technical Specification (TS) aimed at publication alongside C++14. Concepts Lite is implemented in a branch of GCC, which will be made available to the audience for experiments and experience.

Speaker’s bio: Andrew Sutton is an assistant professor at the University of Akron in Ohio where he teaches and conducts research at the intersection of Software Engineering and Programming Languages. Dr. Sutton helped design and implemented the Concepts Lite proposal for the C++ programming language. He is also the author of the Origin C++ Libraries, an experimental collection of generic libraries that supports ideas and research for generic programming. Dr. Sutton had previously worked as a postdoctoral researcher at Texas A&M University where he worked with Bjarne Stroustrup and Gabriel Dos Reis on the design and implementation of language support for generic programming (i.e., Concepts Lite). He is a member of the C++ Standards Committee and Project Editor for the Concepts Lite Technical Specification. He graduated with a PhD in computer science from Kent State University in Ohio in 2010.

Marshall Clow: “Hardening Your Code"

Ok, you’ve written some code, and it seems to work. How can you be sure that it works? It’s a busy, complicated, dangerous world out there, and software has to work in lots of different environments. How can you gain confidence about your code? How can you make your code more reliable? There are a lot of techniques available to developers today; I’ll talk about several of them: Unit tests, static analysis, runtime analysis, fuzzing, decoding compiler warnings and probably others.

Speaker’s bio: Marshall is a long-time Boost participant. He is one of the moderators of the Boost-Users mailing list, and helps keep the Trac system running. Marshall is a principal engineer at Qualcomm, Inc. in San Diego. He is the author of the Boost.Algorithm library, maintains Boost.Array and Boost.StringAlgo, and is the leader of the Boost Community Maintenance team.

Nate Kohl: “cppreference.com: Documenting C++ One Edit at a Time"

How do you convert hundreds of pages of C++ standardese into a resource that is accessible to software engineers around the world? This talk will describe the process of building a community-run website that documents all of the nooks and dark corners of the C++ programming language. I’ll look back at the history of how C++ was defined, cover the current state of documentation, examine the pros and cons of running a fairly high-profile publicly-editable wiki, and try to guess at what the future holds.

Speaker’s bio: Nate Kohl is a software engineer at Google who enjoys herding cats.

Kate Gregory, James McNellis: “Modernizing Legacy C++ Code"

C++ is a programming language with a long, storied history spanning over three decades–four if one includes its C ancestry. The C++ language has undergone many changes during that time, compiler technology has advanced substantially, and computers today are very different from the computers of decades past. But despite all of these advances, there’s an awful lot of C++ code in use today that looks like it was written in the 1980s. In C++ some cases, the code was written in the 1980s and it’s still in use; in other cases, it’s recently-written code that just doesn’t use modern style. In this talk, we’ll discuss some of the problems with legacy code, and review some practical techniques for applying principles of modern C++ to gradually improve the quality of legacy code and improve maintainability and debuggability. We’ll show how some very small changes to code can yield huge benefits.

Speakers’ bio: Kate Gregory has been using C++ since before Microsoft had a C++ compiler. She writes, mentors, codes, and leads projects, in both C++ and .NET, especially for Windows 7 and 8. Kate is a Microsoft Regional Director, a Visual C++ MVP, and has written over a dozen books (the most recent on C++ AMP for Microsoft Press) and speaks at conferences and user groups around the world. Kate develops courses on C++, Visual Studio, and Windows programming for Pluralsight, founded the East of Toronto .NET Users group, and is a member of adjunct faculty at Trent University in Peterborough.

James McNellis is a senior engineer on the Microsoft Visual C++ team, where he is responsible for the Visual C++ C Runtime (CRT) and C Standard Library implementation. He was previously a member of the Microsoft Expression Blend team, developing the XAML designer tools for Windows 8 apps. Prior to joining Microsoft in 2010, he spent several years working on real-time 3-D simulation and robotics projects in the defense industry. James is a prolific contributor on the Stack Overflow programming Q&A website and occasionally writes for the Visual C++ Team Blog.

CppCon Program Preview, 1 of N -- Boris Kolpackov

By Blog Staff | May 29, 2014 08:38 AM | Tags: None

The countdown continues: Today we are exactly 100 days out from CppCon 2014.

This morning, the organizers announced that CppCon will have some 100 talks, which going by the size of the program likely makes this the biggest C++ event in... ever. Also, we now have the first set of accepted talks.

CppCon Program Preview, 1 of N

by Boris Kolpackov

From the announcement:

Good news: Due to the large number of submissions (we got over 140), the conference will have 6 tracks instead of the planned 5. This means there will be approximately 100 talks, and that’s not counting keynotes, plenary sessions, and lightning talks (more on those soon). As far as we know no other conference has ever had this number of C++-related presentations which will make CppCon 2014 the biggest event in the history of the language.

Understandably, many of you would like to see the conference program before registering. However, due to a greater than expected number of submissions, the final program is still some weeks away. So to help you make up your mind (or convince your boss) we are going to start publishing the talks as they are accepted. So here is the first chunk (summary first, abstracts following):

Scott Meyers: “Type Deduction and Why You Care”

John JT Thomas: “Embarcadero Case Study: Bringing CLANG/LLVM to Windows”

Rachel Cheng, Michael VanLoon: “Boost: A Bridge from C++98 to C++11; An Introduction to Using More Boost”

Titus Winters: “The Philosophy of Google’s C++ Code”

James McNellis: “Unicode in C++”

 

Scott Meyers: "Type Deduction and Why You Care"

C++98 had template type deduction, and it worked so intuitively, there was little need to understand what took place under the covers. C++11 extends type deduction to include universal references, applies it to auto variables and lambda expressions, then throws in a special auto-only deduction rule. C++14 pushes the boundary further, adding two forms of function return type deduction (auto and decltype(auto)) for arbitrary functions and offering auto parameters for lambdas. The result is that what could be treated as a black box in C++98 has become a topic that practicing C++ developers really need to understand. This talk will give you the information you need to do that.

Speaker’s bio: Scott Meyers is one of the world’s foremost experts on C++ software development. He wrote the best-selling Effective C++ series (Effective C++, More Effective C++, and Effective STL) and is also author of Overview of the New C++ (C++11/14) and Effective C++ in an Embedded Environment.

John JT Thomas: "Embarcadero Case Study: Bringing CLANG/LLVM to Windows"

CLANG/LLVM delivers a highly conforming C++ compiler and architecture for targeting multiple CPUs, and, as such, has seen success in iOS and other operating systems. Embarcadero has successfully delivered the first commercial compiler for Windows based on CLANG/LLVM. This session describes the benefits of CLANG/LLVM as well as the challenges in bringing it to the Windows operating system. Particular emphasis is placed on the managing the changes in CLANG as well as the additional features added to enable Windows development.

Speaker’s bio: John “JT” Thomas, Director of Product Management at Embarcadero Technologies, has more than 15 years of product management and product development experience including hands-on experience with the early versions of Delphi and C++Builder at Borland Software. While at Borland he was a delegate on the ANSI/ISO C++ standards committee. He earned his Computer Science degree from University of California, Santa Cruz and his MBA and MSE from San Jose State University.

Rachel Cheng and Michael VanLoon: "Boost: A Bridge from C++98 to C++11; An Introduction to Using More Boost"

Part one is for those who are stuck with a C++98/03 compiler, but are interested in using more advanced C++11-like strategies. We will discuss some of the differences between C++98 and C++11 while demonstrating how strategic use of Boost libraries can bridge the gap, allowing more modern programming paradigms in many cases.  Part two is a deeper dive into some interesting Boost libraries for those who may be new to Boost usage. We will explore how C++98 and C++11 can be enhanced and extended by the additional richness of Boost libraries. We will use as example some of the boost libraries used in the F5 Networks code base. If there is time leftover, we will discuss our experience upgrading GCC.

Speakers’ bio: Rachel Cheng is a recent graduate from The Evergreen State College is currently employed at F5 Networks. Michael VanLoon is a Senior Software Engineer at F5 Networks, is a member of the Northwest C++ Users group, and has attended ISO C++ Standards Committee meetings. He has benefited from time at Microsoft, Yahoo!, and VMware, among others, before joining F5. He is fascinated with crafting code and is dismayed at code that falls short of its potential.

Titus Winters: "The Philosophy of Google’s C++ Code"

The Google C++ Style Guide is a fairly popular guide for C++ coding practices, both at Google and externally, but some of its recommendations often seem dated and have created controversy and perceived tension with more modern C++ In this talk we will focus on the core philosophies underlying that guide, ranging from the common (be consistent) to the unusual (leave an explicit trace for the reader), and debunk the idea that Google’s C++ is anything less than modern. We’ll discuss how these core ideas inform contentious rules like “No non-const references” and “Don’t use exceptions,” and how the application of those rules has worked for us in practice, both as developers and reliability engineers (SREs).

Speaker’s bio: Titus Winters has spent the past three years working on Google’s core C++ libraries. He’s particularly interested in issues of large scale software engineering and codebase maintenance: How do we keep a codebase of over 100M lines of code consistent and flexible for the next decade? Along the way he has helped Google teams pioneer techniques to perform automated code transformations on a massive scale, and helps maintain the Google C++ Style Guide.

James McNellis: "Unicode in C++"

In some programming languages, text processing is easy. Unfortunately, C++ is not one of those languages. C++ lacks good, built-in support for Unicode, though the situation is starting to improve. This session will begin with a brief overview of text encodings, and an introduction to Unicode and the various Unicode encodings. We’ll look at the woeful state of Unicode support in C++98 (or, really, lack thereof), then take a look at the improvements that were made in C++11 and other improvements that have recently been proposed for standardization. We’ll finish up with a discussion of several libraries designed to make it easier to work with Unicode in C++, including the widely-used, open-source International Components for Unicode (ICU) library.

Speaker’s bio: James McNellis is a senior engineer on the Microsoft Visual C++ team, where he is responsible for the Visual C++ C Runtime (CRT) and C Standard Library implementation. He was previously a member of the Microsoft Expression Blend team, developing the XAML designer tools for Windows 8 apps. Prior to joining Microsoft in 2010, he spent several years working on real-time 3-D simulation and robotics projects in the defense industry. James is a prolific contributor on the Stack Overflow programming Q&A website and occasionally writes for the Visual C++ Team Blog.