Home » Blog » Categories »

Faster Hash Maps, Binary Trees etc. Through Data Layout Modification -- Ivica Bogosavljević

By Blog Staff | Nov 14, 2023 03:18 PM | Tags: None

2023-10-02_15-20-11.pngIn this post we talk about how data structure data layout effects software performance and how, by modifying it, we can speed up the access and modification of the data structure.

Faster Hash Maps, Binary Trees etc. Through Data Layout Modification

By Ivica Bogosavljević

From the article:

This post is a logical continuation of the previous post about class layout and performance, where we talked about how class size and class layout influences software performance.

The basic premises of good memory performance hold in this case as well:

  • Everything that is accessed together should be stored together. Otherwise, the memory subsystem needs to more resources to fetch data.
  • Exploite the cache line organization of the memory subsystem. Since data is brought in blocks of 64 bytes from the memory to the data caches, our programs should consume all of it.
  • Keep data compact in memory speeds up access and modification. Smaller data more easily fits in the faster parts of the memory subsystem.

Techniques

Different techniques apply for different data structures. But in essence, all techniques revolve around the same idea of making the logically neighboring data physically close as well.

Polymorphism and Vectors of Pointers

In C++, to use polymorphism, you need to access the object through a pointer or a reference. And to access a collection of polymorphic objects, you need a vector of pointers (or some other data structure that holds pointers). As a data structure, a vector of pointers has two problems:

  • For each pointed object there needs to be a call to a system allocator to allocate the memory for the objects.
  • To access an object, a pointer needs to be dereferenced.

Trip report: Autumn ISO C++ standards meeting (Kona, HI, USA) -- Herb Sutter

By Blog Staff | Nov 11, 2023 05:39 PM | Tags: None

reflection.pngA report out from this week's ISO C++ standards committee meeting, which just ended:

Trip report: Autumn ISO C++ standards meeting (Kona, HI, USA)

by Herb Sutter

From the article:

This time, the committee adopted the next set of features for C++26. It also made significant progress on other features that are now expected to be complete in time for C++26 — including contracts and reflection.

2 Lines Of Code and 3 C++17 Features - The Overload Pattern -- Bartlomiej Filipek

By Blog Staff | Nov 10, 2023 03:14 PM | Tags: None

2023-10-02_15-16-38.pngLearn how the overload pattern works for std::variant visitation and how it changed with C++20 and C++23.

2 Lines Of Code and 3 C++17 Features - The Overload Pattern

By Bartlomiej Filipek

From the article:

While I was doing research for my book and blog posts about C++17 several times, I stumbled upon this pattern for visitation of std::variant:

template<class... Ts> struct overload : Ts... { using Ts::operator()...; }; 
template<class... Ts> overload(Ts...) -> overload<Ts...>;

With the above pattern, you can provide separate lambdas “in-place” for visitation.

It’s just two lines of compact C++ code but packs some exciting techniques.

Let’s see how this works and go through the three new C++17 features that make this pattern possible.

Changelog

  • Updated on 18th Septeber 2023: C++23 updates, and Compiler Explorer examples.
  • Updated on 13th January 2020: better description for the whole article and C++ 20 features were mentioned - CTAD for aggregates.
  • Initial version on 11th Feb 2019

Intro

The code mentioned at the top of the article forms a pattern called overload (or sometimes overloaded), and it’s primarily valid for std::variant visitation.

Intro to C++ Coroutines: Concept -- Ilya Doroshenko

By Blog Staff | Nov 8, 2023 03:06 PM | Tags: None

Coroutine.pngThe time has come, fellow devs. We are on our way to uncover the newest concept of C++ language – Coroutines.

Intro to C++ Coroutines: Concept

By Ilya Doroshenko

From the article:

The newest concept of C++ language, Coroutines, is already used by several programming languages, like

  • C# async tasks and yield iterables, forming LINQ base;
  • JS with awaitables, replacing the old way of making consecutive calls, that was hard to understand did a lot of code identation for cases that required a lot of async execution;
  • Python with synchronous generator
  • etc.

They were introduced in the recent C++20 standard. However, instead of handy classes such as Task<> and std::generator<> we received a complex and low-level toolkit to make our own promises and futures. Only C++23 gave us our first usable coroutine type (std::generator<>). It seems like the C++ committee followed the quote: “give a man a fish and you feed him for a day; teach a man to fish and you feed him for a lifetime”.

Today we will discuss what is needed to understand coroutines, and in the later chapters we will make our own little coroutine.

Beware of Unsafe Conversions from size_t to int -- Giovanni Dicanio

By Giovanni Dicanio | Nov 8, 2023 11:49 AM | Tags: None

When you have a size_t value and need to convert it to an int (for example: to pass it to a function expecting an int parameter), your C++ compiler may emit a warning message, and you may quickly silence it with a static_cast<int>. But, is that really safe? Or could that hide some subtle and "interesting" bugs?

Beware of Unsafe Conversions from size_t to int

by Giovanni Dicanio

From the article:

You can have some fun experimenting with these kinds of bugs with this simple C++ code [...]

So, these conversions from size_t to int can be dangerous and bug-prone, in both 32-bit and 64-bit builds.

 

Promise-Cpp with Boost.Beast -- Richard Thomson

By Legalize Adulthood | Nov 8, 2023 11:40 AM | Tags: None

Utah C++ Programmers has released a new video:

Promise-Cpp with Boost.Beast

by Richard Thomson

From the video description:

Over the past few months, we've looked at asynchronous I/O and network programming using Boost.Asio and Boost.Beast. Those libraries connect to your application through the use of callbacks. When orchestrating a sequence of asynchronous operations, it is up to the application to ensure that the callbacks are invoked in the proper sequence.

This "callback hell" problem has long been recognized in the JavaScript world, as all I/O operations in JavaScript (timers or XML HTTP Requests) are asynchronous. In the JavaScript world this lead to promise oriented APIs that allowed for a more linear notation in expressing a sequence of asynchronous operations. This led to the Promises/A+ specification for JavaScript promises.

Promise-cpp is an implementation of the Promises/A+ specification for C++. It can integrate with Boost.Asio and Boost.Beast for asynchronous network programming support for low-level I/O as well as HTTP and WebSocket APIs.

https://www.youtube.com/watch?v=YnTaumB5HVM

On Writing Loops in Continuation-passing Style, Part 4 -- Raymond Chen

By Blog Staff | Nov 6, 2023 03:00 PM | Tags: None

RaymondChen_5in-150x150.jpgIn this article, we delve into the equivalent helper functions for C# and JavaScript, which are simpler due to the inherent behavior of references in these languages, eliminating the need for explicit shared pointer conversions. 

On Writing Loops in Continuation-passing Style, Part 4

By Raymond Chen

From the article:

So far, we’ve been look at writing loops in PPL and continuation-passing style, and a lot of the complications came from creating shared_ptrs to manage shared state without copying, and trying to reduce the number of such pointers we had to make. The equivalent helper functions in C# and JavaScript are simpler because in those languages, references act like shared_ptr already; there’s no need to convert them into shared pointers explicitly.

class TaskHelpers
{
    public static Task DoWhileTask(Func<Task<bool>> callable)
    {
        return callable().ContinueWith(t =>
            t.Result ? DoWhileTask(callable)
                     : Task.CompletedTask).Unwrap();
    }
}

The C# Task Parallel Library’s ContinueWith method is the equivalent to the PPL then() method: You give it a Func<Task<T>, Result> which is called with the preceding task. In our case, we are given a Task<bool>: We check the result, and if it is true, then we recurse back and do the whole thing again.

The gotcha is that ContinueWith returns a task whose result type matches the return value of the Func you passed in. In our case, that Func returns a Task, so the return value of ContinueWith is a rather confusing Task<Task>. You need to follow up with the Unwrap() method to unwrap one layer and get a Task back. (More generally, the Unwrap method converts a Task<Task<T>> to a Task<T>.)

Optional Polymorphism by Delegation -- Daniel Lindner

By Blog Staff | Nov 2, 2023 02:55 PM | Tags: None

softwareschmiede_logo-1-300x138.pngA code design pattern I’ve used a lot in recent times is the “optional-based polymorphism” that looks like a delegation to another type that might not be available. It might be an implementation of the FCoI-principle (Favour Composition over Inheritance).

Optional Polymorphism by Delegation

By Daniel Lindner

From the article:

Let’s look at an example: An application has several different engines that move stuff around. Some engines are based on limit switches. They move until they are stopped by a physical switch. The application can make these engines move from one predefined position to the next, but not anywhere in between. Another type of engines is based on a relative position. You give the engine the new target position and it positions itself there, without any limit switches or predefined positions.

Traditional approach

A typical implementation using inheritance would be a common supertype “Engine” that provides the functionality both engine types exhibit. From there, we would define two subtypes that extend the functionality in their desired way. One subtype would be the “LimitSwitchEngine”, the other one the “PositionableEngine”.

Our client code that wants to use a particular engine has two possibilities: It only requires the common functionality of an engine and can work with the supertype. Or it needs to perform a downcast after checking the actual type of the engine.