Articles & Books

Is boyer_moore_horspool faster then std::string::find?

The last blog post by Julien Jorge made me wonder if the string searchers could be faster here.

Is boyer_moore_horspool faster then std::string::find?

by Jens Weller

From the article:

On Wednesday I've read an interesting blog post by Julien Jorge on Effortful Performance Improvements, where it is shown how to improve an replace function which runs replacements on a string. Its part of a series on performance and improving a code base, you should go read all of them!

When reading the post, and seeing the two implementations, one short and simple and the other longer and more complicated - but faster - I wondered is there a faster way? Julien already has shown that his newer function beats his old function which uses std::string::find in performance. I've veryfied that, and then started to refactor a copy of that slower function with a different approach using the string search algorithm boyer_moore_horspool...


What do number conversions cost?

Exploring how much number conversions from string cost you and how caching helps

What do number conversions cost?

by Jens Weller

From the article:

And so the devil said: "what if there is an easier design AND implementation?"

In the last two blog posts I've been exploring some of the ways to implement a certain type that has a string_view and holds a conversion to a type in a variant or any. And my last blog post touched on conversions. And that made me wonder, what if I did not have a cache in the type for conversions? The memory foot print would be much smaller, and implementation could be simple to convert in a toType function on demand. This then would essentially be a type that holds a string_view, but offers ways to convert this view to a type. Adding a cache to hold the converted value is in this case not necessary, as this is done on demand.

C++20 Formatting Library, Parts 1. 2 and 3 -- Gajendra Gulgulia

1*YoSAmfIDl_BLrT70dHAe5Q.pngThe first three parts are live:

C++20 Formatting Library

by Gajendra Gulgulia

Part 1: Setup and Basics

Part 2: Width, Fill and Alignment

Part 3: Sign Specification

From the lead article:

At the time of writing this series, the header format is not yet integrated into latest gcc or clang compiler. According to reference the only two compilers that have so far implemented the standard text formatting libraries are clang-14* and msvc 19.29. Due to limitations in my personal computer, I’ll therefore be using the fmt library on which the standard string formatting library is based. When the compiler support is released, the token fmt::format can be replaced with std::format and the examples in the series should work as it is. ...

Effortless Performance Improvements in C++: std::vector -- Julien Jorge

Screenshot_2023-03-09_070806.jpgPart the third:

Effortless Performance Improvements in C++: std::vector

by Julien Jorge

From the article:

This is the third post in the series about effortless performance improvements in C++. Check the first post to get the full story!

Last time we switched from std::map to std::unordered_map and got 30% performance improvements. After these changes we observed that the tokenize function was a top hotspot, mostly due to std::vector::push_back. How can we improve the performance of this function? ...

Merging intervals in next-gen C++--Marco Arena

Revisiting a classical programming puzzle in next generation C++:

Merging intervals in next-gen C++

by Marco Arena

From the article:

A few weeks ago, I set this problem at Coding Gym: given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input...

Effortless Performance Improvements in C++: Parts 1& 2 -- Julien Jorge

And nary a drop to drink:

Effortless Performance Improvements in C++

Part 1: Analyzing a program

Part 2: std::unordered_map

by Julien Jorge

From the articles:

In this series of blog posts we are going to explore the implications on processing time for typical C++ way-of-doing by implementing a non-trivial task using idiomatic C++. Then we will benchmark this program and improve its performance.

Optimization is a never-ending quest that can lead to huge sacrifices in terms of code readability. ... In these blog posts we will restrict ourselves into transformations that do not diminish the expressiveness of the existing interfaces, and we will stay withing the scope of the standard library. We will see that even within these limits one can easily reduce processing times by a factor of two, and maybe three with some compromises. ...

Decreasing the Number of Memory Accesses, 1.2 -- Johnny's Software Lab

Screenshot_2023-03-07_130055.jpgLess (memory access) is more (speed):

Decreasing the Number of Memory Accesses, 1.2

by Johnny's Software Lab

From the article:

When we are trying to speed up a memory-bound loop, there are several different paths. We could try decreasing the dataset size. We could try increasing available instruction level parallelism. We could try modifying the way we access data. Some of these techniques are very advanced. But sometimes we should start with the basics.

One of the ways to improve on memory boundness of a certain piece of code is the old-fashioned way: decrease the total number of memory accesses (loads or stores). Once a piece of data is in the register, using it is very cheap, to the point of being free (due to CPU’s ability to execute up to 4 instructions in a single cycle and their out-of-order nature). So all techniques that try to lower the total number of loads and stores should result in speedups. ...

Fun with printing tables with std::format and C++20 -- Bartlomiej Filipek


Fun with <format>, with a dash of <chrono> sauce:

Fun with printing tables with std::format and C++20

by Bartlomiej Filipek

From the article:

Today’s experiment went from a simple table printing code using C++17 into a fancier version from C++20. The improved code was “nicer” and easier to write and maintain. Additionally, we got working date-time handling capabilities in just a couple of lines of code! Which wasn’t possible until C++20. ...

The Iterator Protocol -- Rainer Grimm

A C++ story, as-if ghostwritten by Frederick Forsyth...

The Iterator Protocol

by Rainer Grimm

From the article:

Here is the question I want to answer: What interface must a user-defined type support to be usable in a range-based for-loop. ...