Toggle Menu

Miscellaneous


Concurrency & Multithreading

Concurrency and multithreading are powerful tools to take advantage of available hardware to make your program run faster. Multithreading can be used to improve responsiveness and performance.

Concurrency

Concurrency is the process by which 2 or more separate activities are happening simultaneously. Context switching is performed each time the computer switches from one task to another. It involves:
  1. Saving the CPU state and the instruction pointer of the currently running task
  2. Working out which task to switch to
  3. Reloading the CPU state from the task being switched to

Approaches To Concurrency

  1. Concurrency with multiple processes: divide app into multiple single threaded processes
    • pass msg to each other through interprocess communication channels
    • slow because OS provides protection to prevent one process to modify the data of other
    • processes communicate to each other through interprocess communication
    • easier to write safer concurrent code
    • can run processes on different machines
  2. Concurrency with multiple threads: each thread runs independently of each other
    • share same address space
    • most data can be accessed from all threads
    • less overhead because OS has less book-keeping to do
    • lack of protection
    • programmer must ensure data is consistent whenever accessed
    • relies on platform specific API

When Not To Use Concurrency

  1. When the benefit is not worth the cost
  2. Code is harder to understand, more bugs
  3. Unless potential performance gain is large enough
  4. Having too many threads consume OS resources and might make the system run slower as a whole
  5. Can exhaust available memory and address space because each thread requires a separate stack space
  6. More threads = more context switching (takes time)
// Non-concurrent
#include <iostream>
int main() {
  std::cout << "Hello World\n";
}

// Concurrent
#include <iostream>
#include <thread>
void hello() {
  std::cout << "Hello Concurrent World\n";
}
int main() {
  std::thread t(hello);
  t.join();
}
In concurrent version:
  1. Code is moved to a separate function because each thread needs an initial function to start an execution
  2. A thread object of type std::thread named t is created and the construtor is initialized with the hello function. Launches new thread (thread count = 2)
  3. Calling thread main() waits for new thread t to finish by calling join()

Launching A Thread With A Function Object

class background_task{
public:
  void operator() () const {
    do_something();
    do_something_else();
  }
};
background_task f;
// f is copied to storage of thread and invoked there
std::thread my_thread(f);
Note that if we want to use a temporary, unnnamed function object, we cannot use std::thread t(background_task()). This is interpreted as a a function t that takes in a pointer to a function with no parameters. Instead, we can:
  • enclose it in parenthesis: std::thread t((background_task()))
  • use uniform initialization with braces rather than parenthesis: std::thread t{background_task()}

Function Objects

A function object, known as a functor, is any object for which the function call operator is defined. An advantage of this is the ability to contain states. 
// this is a functor
class Add_x {
public:
  Add_x(int x) : x(x) {}
  int operator()(int y) const { return x + y; }
private:
  int x;
};

// Now you can use it like this:
// 1. Create an instance of the functor class
Add_x add42{42};

// 2. Call it
int i = add42(8);  // i == 50

// Alternatively,
std::vector in{ 2, 5, 8, 3 };
std::vector out(in.size());

// Pass a functor to std::transform, which calls the functor on every element
// in the input sequence, and stores the result to the output sequence
std::transform(in.begin(), in.end(), out.begin(), Add_x{1});
// out == { 3, 6, 9, 4 }

Lambdas

Lambdas allow us to construct an unnamed function object capable of capturing variables in scope.
Syntax: [ captures ]( params ){ body }

The captures is a comma-separated list of zero or more captures, optionally beginning with a capture-default.
Capture defaults:
  1. & - capture by reference
  2. = - capture by copy
The capture list can be passed as follows:
  • [a, &b] - a captured by copy, b captured by reference
  • [this] - captures current object by reference
  • [&] - captures all automatic (local) variables used in body of lambda by reference and current object by reference if it exists
  • [=] - captures all automatic (local) variables used in body of lambda by copy and current object by reference if it exists
  • [] - captures nothing

The params is a list of parameters, similar to named functions. 
auto foo(int& x) {
  return [&]{ std::cout << x << "\n"; };
  // since x is used, it captures x by reference
}

int main(){
  int i = 3;
  auto f = foo(i); // the use of x in f binds directly to i
  i = 5;
  f();// OK; prints 5
}

STL Algorithms

The <algorithm> library defines functions for a variety of purposes that operate on a range of elements, where range is [first, last).

for_each

Applies the given function object f to the result of dereferencing every iterator in the range [first, last), inorder. 
template <class InputIt, class UnaryFunction>
UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f)

std::vector<int> nums{ 1, 2, 3, 4, 5 };
auto print = [](const int& n){ std::cout << " " << n; };
std::for_each(nums.begin(), nums.end(), [](int& n){ n++; });
std::for_each(nums.begin(), nums.end(), print); // 2 3 4 5 6

find

Returns the first element in the range [first, last) that equals to value, otherwise, returns last. 
template <class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value)

std::vector<int> nums{ 1, 2, 3, 4, 5 };
int i = 3;
auto result = std::find(nums.begin(), nums.end(), i);
if (result != nums.end()) cout << "nums contains " << i << endl;
else cout << "nums does not contain " << i << endl;

count

Returns the number of elements in the range [first, last) equal to value. 
template <class InputIt, class T>
typename iterator_traits<InputIt>::difference_type count(InputIt first, InputIt last, const T& value)

std::vector<int> nums{ 1, 2, 3, 4, 5, 3, 3 };
int i = 3;
auto count = std::count(nums.begin(), nums.end(), i);
cout << "nums contains " << count << " counts of " << i << endl;
We can also use count_if to count the elements where the last argument returns true. 
int div3 = std::count_if(nums.begin(), nums.end(), [](int i){ return i % 3 == 0; });

copy

Copies the elements in the range [first, last) to another range beginning at d_first. 
template <class InputIt, class OutputIt>
OutputIt copy(InputIt first, InputIt last, OutputIt d_first)

std::vector<int> nums{ 1, 2, 3, 4, 5 };
std::copy(nums.begin(), nums.end(), std::ostream_iterator<int>(std::cout, " "));
// 1, 2, 3, 4, 5

transform

Applies unary_op to the range [first, last) and stores the result in another range beginning at d_first. 
template <class InputIt, class OutputIt, class UnaryOperation>
OutputIt transform(InputIt first, InputIt last, OutputIt d_first, UnaryOperation unary_op)

std::vector<int> nums{ 1, 2, 3, 4, 5 };
std::vector<int> mult;
std::transform(nums.begin(), nums.end(), mult.begin(), [](const int& n){ return n * 2; });
for (int n : mult) cout << n << " ";
// 2, 4, 6, 8, 10