Program Preview: Data Structures

We have a program! We received over 175 submissions for CppCon this year, and we accepted about 100 of them. In a few days, we’ll post the full six-track schedule. Until then, here’s a preview of some excellent talks about data structures:

High Performance Code 201: Hybrid Data Structures, Chandler Carruth
Colonies, Performance and Why You Should Care, Matt Bentley
The Details of std::string at Facebook, Nicholas Ormrod
tuple<>: What’s New, and How it Works, Stephan T. Lavavej
variant<>: Past, Present and Future, David Sankel

If you want to come join us for CppCon 2016, there’s still time to register!

— Bryce Adelstein Lelbach

High Performance Code 201: Hybrid Data Structures

Modern programs’ performance characteristics are often dictated by their data. Whether the cache locality of data access, the size of working set, or avoiding costly memory allocation overhead. Unfortunately, the standard C++ library data structures range from adequate to terrible at controlling these aspects, and they don’t provide any of the core mechanisms needed for extremely efficient data structure design.

This talk will present the core concepts of designing high performance data structures in C++. It is based on years of experience in the LLVM compiler as well as several other large code bases. From these principles, the talk will propose a suite of data structures that provide performance without loss of generality or functionality. As much as this talk will present specific data structure designs, its primary intent will be to give an understanding of what makes these structures have greater performance than more naive approaches.

Chandler Carruth leads the C++ platform team and LLVM team at Google. He is also an active contributor to the LLVM and Clang open source projects, and speaks at various C++ events where he tries to help spread knowledge about C++, compilers, tools, and optimization. Previously, he worked on several components of Google’s distributed build system. He received his M.S. and B.S. in Computer Science from Wake Forest University, but disavows all knowledge of the contents of his Master’s thesis. He can usually be found coding with the aid of Cherry Coke Zero in the daytime and pontificating over a single malt scotch in the evening.

Colonies, Performance and Why You Should Care

In game development and many other high-performance, highly-modular development architectures, maintaining valid references to container elements, regardless of erasure and insertion, is often crucial. Though there are many workarounds for this, typically using std::vector<> with various methods to avoid invalidation, to date there exist no generalized solutions to the problem which also provide strong cache performance.

plf::colony<>, a proposed unordered container class from the SG14 working group, is one attempt to remedy this situation, providing fast insertion, erasure and iteration performance while maintaining pointer/iterator stability to non-erased elements, which is unaffected by both insertion and erasure.

In this talk we’ll explore both the structure and comparative performance of plf::colony<>, contrasting it with other standard library containers and their potential modifications, showing how it can outperform many typical alternatives where large amounts of insertions and erasures are concerned. This will include details on:

The “jump-counting” skipfield pattern, a new numeric pattern which has better performance than its boolean counterpart.
plf::stack<>, a replacement for std::stack<> with stronger stack performance than other standard library containers.
The chained-group allocation pattern, common to both containers.

If you’re not interested in new containers, you will still pick up a few concepts to help you with improving your own implementations and high-performance C++ code. If you are interested in better containers, or better container usage, you should definitely attend this talk.

Matt Bentley was born in 1978 and never fully recovered from the experience. He started programming in 1986, completing a BSc Computer Science 1999, before spending three years working for a legal publishing firm, getting chronic fatigue syndrome, quitting, building a music studio, recovering, getting interested in programming again, building a game engine, and stumbling across some generalized solutions to some old problems. He lives in the New Zealand, which as you may know, is near the penguins.

The Details of std::string at Facebook

Standard strings are slowing you down. Strings are everywhere. Changing the performance of std::string has a measurable impact on the speed of real-world C++ programs. But how can you make strings better? In this talk, we’ll explore how Facebook optimizes strings, especially with our open-source std::string replacement, fbstring. We’ll dive into implementation tradeoffs, especially the storage of data in the struct; examine which standard rules can and cannot be flouted, such as copy-on-write semantics; and share some of the things we’ve learned along the way, like how hard it is to abolish the null-terminator. War stories will be provided

Nicholas Ormrod is an infrastructure engineer at Facebook. His focus is on developer efficiency – how to make coding in C++ easier for other engineers. He enjoys making massive codebase-wide changes, especially to deprecate old C++ features in favor of new ones.

tuple<>: What’s New, and How it Works

std::tuple<> has been gaining new abilities, like get-by-type in C++14 and conditionally-explicit constructors in C++17. This talk will begin by briefly summarizing what you can do with tuples in C++11 and C++14. Next, we’ll explore what’s new in C++17, and how it can improve your code. We’ll also delve into how this magic is implemented, with new metaprogramming tools like std::conjunction<>. Finally, we’ll look at active issues in tuple’s design, and what the Library Working Group is doing about them.

Stephan T. Lavavej is a Senior Developer at Microsoft, maintaining Visual C++’s implementation of the C++ Standard Library. He designed C++14’s std::make_unique() and transparent operator functors, C++17’s variable templates for type traits, and LibFunV2‘s uniform container erasure.

variant<>: Past, Present and Future

What are variants, why are they important, and how I use them? Once available to a developer, variants become one of the most commonly used tools in everyday programming. This talk will explore the venerable Boost.Variant library, discuss the improvements made by C++17’s std::variant<>, and close with a discussion of the exciting new language-based variant and pattern matching papers (proposed for C++20). This talk aims to be of practical utility in variant library usage and informative as to where things are heading.

David Sankel is a professional software developer/architect based in the USA and an active member of the C++ Standardization Committee. His prolific software developments have included CAD/CAM, computer graphics, visual programming languages, web applications, computer vision, and cryptography. He is a frequent speaker at the C++Now conferences and is especially well known for his advanced functional programming in C++ talks. David’s interests include large-scale development, dependently typed languages, semantic domains, EDSLs, and functional reactive programming.