The C++ Programming Language – Part 5

This post will be mostly for personal reference as I go through Bjarne Stroustrop’s “The C++ Programming Language” 4th edition textbook. Some of the notes will appear random.

Chapter 5 – Concurrency and Utilities (continued)

Threads sometimes need to wait on events to do their work. For example, threads can wait for time to pass, wait for other threads to fill data buffers, pretty much anything you can think of. The classic example is the producer/consumer model. One thread processes data from a shared queue, while the other thread puts data into the shared queue. All operations on the shared queue are protected by a unique lock, making sure that only one thread can use the queue at a time. In this example, there is also a condition variable that would indicate to the processing thread that data is ready in the queue. Condition variables have a wait() function which takes a mutex and a Predicate. A C++ Predicate is “a function object that takes a single iterator argument that is dereferenced and used to return a value testable as a bool.” In the example below, the consumer thread will not try to acquire the mutex until the predicate returns true aka the queue is not empty.

// g++ -pthread -std=c++11 -o cond_var cond_var.cpp
#include <thread>
#include <iostream>
#include <mutex>
#include <queue>
#include <cstdbool>
#include <chrono>
#include <condition_variable>

using namespace std;

// globals to allow threads to work together
queue<int> mqueue;
condition_variable mcond;
mutex mmutex;

void producer()
{
    for (int i = 100; i < 105; i++) {
        // Acquire the lock.
        unique_lock<mutex> lck {mmutex};
        mqueue.push(i);
        cout << "producer - Pushed data to shared queue." << endl;
        // Unblock waiting threads.
        mcond.notify_one();
        cout << "producer - Notifying consumer and sleeping." << endl;
        // Scoped unlocking wasn't working properly for me, so I 
        // explicity unlock before looping.
        lck.unlock();
        this_thread::sleep_for( chrono::milliseconds(1000) );
    }
}

void consumer()
{
    while(true) {
        // Acquire the lock. Example of RAII.
        unique_lock<mutex> lck {mmutex};
        // Waiting on condition variable releases the mutex and attempts to 
        // reacquire once the Predicate returns true.
        mcond.wait(lck, []() { return !mqueue.empty(); });
        auto m = mqueue.front();
        mqueue.pop();
        lck.unlock();
        cout << "consumer - Got " << m << " from shared queue." << endl;
        cout << "consumer - Waiting for notify." << endl;
    }
}

int main(int argc, char *argv[])
{
    thread prod(producer);
    thread cons(consumer);

    prod.join();
    cons.join();

    return 0;
}

Output:

user@ubuntu:~/cpp/part_1/chapter_5$ ./cond_var 
producer - Pushed data to shared queue.
producer - Notifying consumer and sleeping.
consumer - Got 100 from shared queue.
consumer - Waiting for notify.
producer - Pushed data to shared queue.
producer - Notifying consumer and sleeping.
consumer - Got 101 from shared queue.
consumer - Waiting for notify.
producer - Pushed data to shared queue.
producer - Notifying consumer and sleeping.
consumer - Got 102 from shared queue.
consumer - Waiting for notify.
producer - Pushed data to shared queue.
producer - Notifying consumer and sleeping.
consumer - Got 103 from shared queue.
consumer - Waiting for notify.
producer - Pushed data to shared queue.
producer - Notifying consumer and sleeping.
consumer - Got 104 from shared queue.
consumer - Waiting for notify.
^C

Type functions are functions that is evaluated at compile-time give a type as its argument or returning a type. For example, computing the smallest supported positive float on a system. Also it could be used to find the byte width of standard types. This is an example of metaprogramming.

// g++ -std=c++11 -o smallfloat smallfloat.cpp
#include <iostream>
#include <limits>

using namespace std;

int main()
{   
    constexpr float min = numeric_limits<float>::min();
    cout << "smallest float on this system at compile time: " << min << endl;

    constexpr int szi = sizeof(int);
    cout << "int width in bytes on this system at compile time: " << szi << endl;

    return 0;
}

Output:

user@ubuntu:~/cpp/part_1/chapter_5$ ./smallfloat 
smallest float on this system at compile time: 1.17549e-38
int width in bytes on this system at compile time: 4

Random numbers are useful in many contexts, such as testing, games, simulation, and security. The diversity of application areas is reflected in the wide selection of random number generators provided by the standard library in <random>.” There are two parts to a random number generator: engine and the distribution. The engine outputs the values while the distribution maps the values into a range. Some included distributions: uniform_int_distribution, normal_distribution, and exponential_distribution. There are all kinds of possibilities with this <random> library.

// g++ -std=c++11 -o rando rando.cpp
#include <random>
#include <functional>
#include <chrono>
#include <iostream>

using namespace std;

int main()
{   
    default_random_engine engine {};
    // Seed the engine so it makes new numbers each time.
    engine.seed(std::chrono::system_clock::now().time_since_epoch().count());
    // Set the value map.
    uniform_int_distribution<> distro {1, 100};
    // Bind the engine and map together. Provided by <functional>
    // bind() makes a function object that will invoke its first argument
    // given its second argument as its argument. So, distro(engine);
    auto die = bind(distro, engine);
    for (int i = 0; i < 10; i++) {
        cout << die() << endl;
    }

    return 0;
}

It is necessary to seed the generator. Otherwise, it will output the same “random” numbers each run. Output:

user@ubuntu:~/cpp/part_1/chapter_5$ ./rando 
1
70
83
69
84
73
45
47
71
50
user@ubuntu:~/cpp/part_1/chapter_5$ ./rando 
67
99
64
61
93
62
94
82
29
49

 

The C++ Programming Language – Part 4

This post will be mostly for personal reference as I go through Bjarne Stroustrop’s “The C++ Programming Language” 4th edition textbook. Some of the notes will appear random.

Chapter 4 – Containers and Algorithms (continued)

A standard library map is a search tree data structure. It is a series of key, value pairs implemented as a balanced binary tree. This is also known as a dictionary, optimized for lookup providing O(logn) lookup performance. This fast lookup is possible because when searching a balanced binary tree, the search space is halved each time a node is traversed. This continued halving is essentially the reverse of exponential growth, which is the logarithm. The unordered map is a hashed lookup version of a map. A hash table maps keys to values using a hashing function, allowing the search space to be narrowed down very quickly even compared to a binary tree. “C++ standard library hashed containers are referred to as “unordered” because they don’t require an ordering function.” This graph from MICHAEL KAZAKOV’S QUIET CORNER shows the performance difference:

There are many useful containers in the standard library. The unordered ones are designed for fast key lookup.

vector<T> - variable sized vector
list<T> - doubly linked list
forward_list<T> - singly linked list
deque<T> - double ended queue
queue<T> - first in first out data structure
priority_queue<T> - queue in which the first element is always the greatest according to some criterion. this is implemented on top of another container
stack<T> - last in first out data structure
set<T> - stores unique elements in a specific order. elements are immutable
multiset<T> - set allowing recurring values
map<K,V> - associative array (key values aka dictionary)
multimap<K,V> - same as map with added ability to have one key with multiple values
unordered_map<K,V> - hashed lookup map vs binary tree lookup
unordered_multimap<K,V> - hashed multimap
unordered_set<T> - hashed set
unordered_multiset<T> - hashed multiset
bitset<N> - stores bits...
array<T, N> - fixed size sequence in strict linear sequence

Reinforcing the concept of iterators, we can use them to write to stdout! Constructing an ostream_iterator with the ostream_type reference as cout, whenever an assignment operator is used on the ostream_iterator, it inserts a new element into the stream. Of course, the stream in this case is stdout:

#include <iostream>
#include <iterator>

using namespace std;

int main()
{
    ostream_iterator<string> oo {cout};
    *oo = "Hello, ";
    ++oo; 
    *oo = "world.\n";
}

Another way to use iterators for input and output (thanks to a buddy for this code segment):

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

using namespace std;

int main()
{
    istream_iterator<int> ii {cin};
    ostream_iterator<int> oo {cout};

    /* Write a vector to cout via iterator */
    vector<int> v {1, 3, 5, 7, 9};
    copy(v.begin(), v.end(), oo);

    /* Read 5 elements into the vector via iterator */
    copy_n(ii, 5, back_inserter(v));

    /* Write it back out to cout */
    copy(v.begin(), v.end(), oo);
}

Output: (you must provide input before it prints anything):

user@ubuntu:~/cpp/part_1/chapter_4$ ./ostream_iterator 
1
135792
3
4
5
1357912345

Chapter 5 – A Tour of C++ Concurrency and Utilities

The standard library aims to serve the intersection of needs rather than the union. The result of this decision is a generally useful set of well-designed tools. C++ resource management covers the allocation and deallocation of things that are acquired at runtime. In the standard library, resources follow the “Resource Acquisition Is Initialization” also called RAII. Defined so eloquently on cppreference.com, RAII “binds the lifecycle of a resource that must be acquired before use to the lifetime of the object.” This is fundamental to the design of C++. It guarantees that having access to an object means that the necessary associated resources are also ready to be used. Additionally, when the object is released (either manually or by some other mechanism like going out of function scope), all associated resources are also released. Objects, in this sense, come in an “all or nothing” package.

unique_ptr and shared_ptr are smart pointers that help manage objects on the heap. When the unique or shared pointer is forgotten about by a careless programmer, C++ covers his butt and frees all the necessary resources before going out of scope. This is essentially programming training wheels. Unique_ptr can also be returned from functions since its a handle to an individual object. Unique_ptrs are moved, they are atomic. This is in contrast to shared_ptrs, which are copied. The object pointed to by multiple shared_ptrs will only be deallocated once the reference count hits zero. For example:

// g++ -std=c++11 -o cpp_ptrs cpp_ptrs.cpp

#include <iostream>
#include <memory> // unique_ptr and shared_ptr

using namespace std;

int main(int argc, char **argv)
{
    shared_ptr<float> sample_a (new float(5.4551));

    cout << "shared_ptr sample_a ref count " << sample_a.use_count() << endl;

    shared_ptr<float> sample_b(sample_a);

    cout << "shared_ptr sample_a ref count " << sample_a.use_count() << endl;
    cout << "shared_ptr sample_b ref count " << sample_b.use_count() << endl;
    // The pointers now share the same raw pointer.
    // Thus each has ref count of 2 since they point to same place.

    // Delete managed object sample_b.
    sample_b.reset();
    // The raw pointer will not yet be deallocated, since there is still a ref to it by sample_a
    cout << "shared_ptr sample_a ref count " << sample_a.use_count() << endl;
    cout << "shared_ptr sample_b ref count " << sample_b.use_count() << endl;
    // Delete managed object sample_a.
    sample_a.reset();

    // All memory is freed since ref count is zero.
    cout << "shared_ptr sample_a ref count " << sample_a.use_count() << endl;
    cout << "shared_ptr sample_b ref count " << sample_b.use_count() << endl;

    return 0;
}

Output:

user@ubuntu:~/cpp/part_1/chapter_5$ ./cpp_ptrs 
shared_ptr sample_a ref count 1
shared_ptr sample_a ref count 2
shared_ptr sample_b ref count 2
shared_ptr sample_a ref count 1
shared_ptr sample_b ref count 0
shared_ptr sample_a ref count 0
shared_ptr sample_b ref count 0

Smart pointers are a form of destructor-based garbage collection and relieves the programmer from many memory leaks.

Concurrency is the execution of several tasks simultaneously. This is a bit of a fallacy on uniprocessor systems (and in Python, due to the GIL aka Global Interpreter Lock). Instructions are interleaved on single processors, not actually executed in parallel. Multiprocessor systems are a different game and do offer true concurrency. If those concurrently executing threads operate on the same data, beware. The C++ standard library directly supports concurrent execution in multiple threads in a single address space. These threads have their own stack, but share a heap. Threads are the most commonly used concurrency tool. For example:

#include <thread>
#include <iostream>

using namespace std;

void func(int x)
{
    for (int i = 0; i < 50; i++) {
        // There is a bad mistake here. 
        // Access to the stdout ostream is not controlled.
        // Output will be erratic.
        cout << "Thread " << x << endl;
        // Take a thread nap.
        this_thread::sleep_for(chrono::milliseconds(50));
    }
}

int main(int argc, char *argv[])
{
    // Create two threads.
    // Thread constructor takes the callback function, followed by args to that function.
    thread t1( func, 1 );
    thread t2( func, 2 );
    thread t3( func, 3 );
    thread t4( func, 4 );

    // Wait for threads to finish execution before leaving the main() thread.
    t1.join();
    t2.join();
    t3.join();
    t4.join();

    return 0;
}

Output:

...
Thread 2
Thread 3
Thread Thread 4
Thread 1
2
Thread 3
Thread 1
Thread 4
Thread 3
Thread 2
Thread 4
...

Can you spot the bug? This code contains a synchronization issue with the cout ostream. Nugget fact: “cout” stands for “console out”. In this case, if the goal is to write cleanly to console, each thread should globally lock on the output stream before writing.