DEV Community: Imaculate

Graph problems are not hard

Imaculate — Mon, 10 Jun 2024 23:45:43 +0000

Graph problems have a reputation for being hard and there is a good reason for that.

First off, graph algorithms are not very popular. In my day job I'm more likely to think about sorting algorithms than Dijkstra's.
Second, unlike sorting, many languages do not offer native implementation of graphs nor graph algorithms. Solutions to graph problems are tedious because they have to be implemented from scratch.
Third, even after mastering all graph algorithms, you come across problems that are not obviously graph-related. Problems like Longest subsequence repeated k times look like they could be solved with a Greedy algorithm or Dynamic Programming but the best solution is actually Dijkstra's.

So yes, they are hard. But you have an interview coming up, you're secretly dreading the 10% chance that your interviewer is a fan of graph algorithms. What can you do about it? Aside from trying your luck, you can try something else that is within your control: prepare.

Step 1. Learn

There is a lot to learn about graphs, it can feel overwhelming. It helps to have a map, some sort of decision tree to guide how you classify problems. Graph algorithms can be divided into 3 main categories.

Graph traversal
This class of algorithms traverses a graph for different purposes such as finding a path between nodes, detecting cycles, maximizing flow, performing topological sort etc. They include Breadth First Search (BFS) and Depth First Search (DFS).
Shortest Path
These algorithms aim to minimize the cost of going from one node to another. The cost could be a function of the number of hops or edge weights which can be positive or negative. This category includes popular algorithms such as BFS, Dijkstra's, Bellman Fords, Floyd-Warshall, Informed Search algorithms. Each of them is best suited for specific conditions.
Graph connectivity
This category includes algorithms that test for connectedness of a graph for instance how many connected components it has, the size of the largest component, the minimal spanning tree etc. This class of problems is best solved by Union-Find algorithm or DFS.

Step 2. Practice

Similar to body building, the muscle of problem solving is built from experience. Solve a bunch of problems and you start to see the pattern. You can easily distinguish a BFS problem from a Dijkstra's problem and a graph problem from a tree problem.

There are many resources for learning Graphs ranging to textbook references to interview guides. What will actually help depends on how much you already know and how much time you have. That said, allow me to give you a biased recommendation of my Leanpub book that will be published by the end of this month. A quick and thorough guide to get you interview ready in no time. You are also welcome to check my courses on bit manipulation and dynamic programming.

Till next time, happy coding!

How to actually prepare for Coding Interviews

Imaculate — Wed, 31 Jan 2024 17:06:48 +0000

The best way to prepare for coding interviews is really a function of two things:

Leetcode fitness
How much time you have

Ideally you want as much of each possible but we live in the real world where time is scarce and engineering expertise doesn't translate to leetcode fitness.

1. Basics

Say you have all the time in the world; you're not actively interviewing but you want to stay sharp. You want to master all the fundamentals. Read these books then solving as many as 500 leetcode questions, at least 100 hard.

2. Test

Having mastered the basics you should be comfortable testing your knowledge with the popularized 75 random questions like:

These lists have a good mix of easy, medium and hard questions that are likely to asked in interviews. You want to ace them within a month of your interview(s).

3. Refresh

After testing yourself, you may find gaps in your knowledge or techniques you haven't seen before. You want to double down on Dynamic Programming or Graph Algorithms. This is where focused courses come handy. There are many offerings out there, most of them touch each subtopic lightly. I have a better proposition; focused courses that actually develop your intuition.

Check out my courses on Dynamic Programming and Bit Manipulation (Btw, this is free!). I bet you'll complete them algorithmically fit, otherwise let me know I'll issue a refund.

Happy coding!

What's hard about Dynamic Programming

Imaculate — Fri, 19 Jan 2024 04:44:33 +0000

As far as coding interviews are concerned, dynamic Programming has become synonymous with hard. Candidates spend disproportionate amount of time cracking the code, secretly hoping they won't have to do it in an interview. I totally get it, there is a big jump from the familiar fibonacci problem to palindrome partitioning. Here is why I think its hard and what to do about it.

Detection
When encountering hard problems, solutions that come to mind are brute force, maybe a greedy algorithm. Greedy problems look eerily similar in that they are also trying to maximize or minimize a variable. For instance, a jumping frog scenario is a DP problem but a slight variation is a greedy problem. One way to distinguish the two is to question whether it is necessary to search the entire solution space versus accept a local solution.
Categorization
Dynamic Programing is a diverse algorithm. There are many types of problems to which it is applied. Prominent categories include Longest Increasing Subsequence, Longest Common Substring, Knapsack problems, Matrix Chain Multiplication among others. Sometimes it works alongside other techniques like Number Theory and Bit Manipulation. It definitely helps to be aware of these categories.
Recurrence relation
The premise of dynamic programming is that big problems can be broken into smaller subproblems. The recurrence relationship is the bread and butter of this supposition, a misstep here throws off the whole solution. It is important to get these steps right:
- Is the problem made of smaller subproblems?
- Knowing the solution to the subproblem, how does it tally up to the bigger problem?
- Pay close to problem wording even if you have seen the problem before. For instance given infinite number of coins, counting the number of combinations to make change will have a different formular from minimizing the number of coins needed.
Caching order
Even after successfully deriving the recurrence relation, there is still a chance the solution won't work. It has a lot to do with the order in which the cache is built which depends on the recurrence relation. For instance for the formular:

cache[i][j] = 1 + Min(cache[i-1][j] + cache[i][j-1])

The cache is filled from top to bottom, left to right, so when computing for cache[i][j], the prerequisites are known. On the other hand, this wouldn't work for the formular:

cache[i][j] = Max(cache[i + 1][j], cache[i][j - 1])

The reason being the value at cell cache[i][j] depends on diagonal neighbor cache[i+1][j] which has to be computed prior. The table has to be filled diagonally from bottom to top, left to right. This also means the base case at the bottom right corner has to be set beforehand.

That said, these are just some issues I've seen folks struggle with. After sitting on both sides of multiple interview loops I have reasonable confidence in the techniques that work. I have compiled these techniques in a short but comprehensive course now available on leanpub. Interviews aside, it is important to master algorithms because solving problems optimally is the essence of Software Engineering. You are also welcome to check my other course on bit manipulation which is completely free.

Till next time, happy coding!

Leetcode with ChatGPT

Imaculate — Sat, 06 Jan 2024 03:36:55 +0000

I asked ChatGPT to solve leetcode hard DP problems. The results were well, interesting ...

I started with Frog Jump and the results were promising. Frog Jump is a classic DP problem that is solved by memoization and backtracking. ChatGPT produced python code that could easily be ported into leetcode.

The solution had a trivial bug but passed most testcases. Given the signature of the helper recursive function, def canCrossHelper(position, jump) the initial call should have been canCrossHelper(0,0) and not canCrossHelper(0,1). After fixing the bug, the solution was faster than 90+% of Python solutions. Not bad.

I then tried something more convoluted, Count ways to make array with product. This is a complex problem that applies prime factorization and combinatorics on top of DP techniques. The results were less than stellar.

It produced a DP solution with recurrence relation


 = (dp[i - 1][j] + dp[i - 1][j - 1])

``` which only sounds correct, but is infact wrong. Even after prompting to revise the solution, nothing fundamental changed.

These cases told me all I needed to know about interviewing with AI. Errors are to be expected since AI is only as good as the training data. ChatGPT already has the disclaimer in the footnote `ChatGPT can make mistakes. Consider checking important information.` Here is the [link](https://chat.openai.com/share/6ed19f25-3184-4e6c-90f8-10bf3df81860) to the full chat.

A candidate could have some success from asking ChatGPT in a live interview, essentially cheating. Or they could master algorithms with confidence. A resource I recommend to is [Ace the technical interviews courses](https://leanpub.com/c/acethetechnicalinterviewbitsedition2), DP course coming soon. They help you build intuition around algorithmic techniques and reduce time to optimal solution. I'm biased because I wrote them but they free at the moment and feedback is welcome.

Diving into C++ Iterators

Imaculate — Tue, 05 Jul 2022 23:34:25 +0000

Data structures have been covered extensively but iterators are often in their shadow. This article centers on iterators instead, specifically C++ iterators. We'll explore what they are, why we need them and their various types.

As the name suggests, iterators often come up when traversing through elements of a container. They are produced from C++ containers or streams through functions like begin() and end(). Some common use cases are illustrated in Listing 1.

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

int main()
{
    std::vector<int> v{46, 34, 97, 55};

    std::cout << "Initial order:";
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    std::sort(v.begin(), v.end());

    std::cout << "Final order:";
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

Listing 1: Vector Iterators

Observations:

An object of type vector<int>::iterator is generated from the vector.
It is dereferenced like a pointer in the body of the loop.
It is incremented to get to the next vector element.
It is compared with the iterator at the end of the vector to check for loop termination.
It is passed to standard functions like sort.

We can thus deduce that an iterator is a pointer-like object that can be incremented with ++, dereferenced with * and compared against another iterator with !=. That's a good start; iterators are in-fact wrappers around pointers. Why do we need a separate type for them? Couple reasons:

They abstract away containers hence enabling algorithms to be generic. In Listing 1, the vector was sorted with std::sort() which takes iterator arguments. The same function can sort any other container/array that generates the same kind of iterator; we'll later explore the various kinds of iterators. In addition to that, std::sort() can be used to sort a portion of the data structure by passing iterators from the interior.
Efficiency: Iterators are pointers, Functions that take Iterator arguments instead of containers avoid expensive copying of all elements. If std::sort() took vector instead, the vector would have to be copied on function call as well as on return (twice if the returned vector is assigned to another variable). Moreover, we'd need a different sort function for all the different data types.

As hinted above, there are different classes of iterators. They don't map to C++ classes but are based on the kinds of operations they support. These are:

Input Iterators
Output Iterators
Forward Iterators
Bidirectional Iterators
Random access Iterators

Some iterators are more powerful than others, you can think of them as classes derived from weaker ones as shown in the hierarchy below.

An iterator supports all operations for its kind as well as all above it. The kind of iterators a data structure generates determines the kind of operations it supports. Lets dive in, starting from the top.

1. Input iterators

Input iterators support the following operations.

Increment with iter++ and ++iter.
Comparison with other iterators using == and !=.
Pointer dereference to read data at the address but not store to it.

istream iterators for input streams are good examples of Input Iterators. Listing 2 demonstrates how they are used with standard input. Assigning to *iter would not compile since it is read-only.

#include <iostream>
#include <iterator>

int main()
{
    std::cout << "Enter a stream of numbers terminated by Ctrl+Z: ";

    std::istream_iterator<double> eos;           // end-of-stream iterator from default constructor
    std::istream_iterator<double> iter(std::cin); // stdin iterator

    double sum = 0;
    while (iter != eos)
    {
        sum += *iter;
        ++iter;
    }

    std::cout << "The sum of the numbers is: " << sum << '\n';

    return 0;
}

Listing 2: Input Iterators

2. Output iterators

Output iterators support the following operations.

Increment with iter++ and ++iter.
Comparison with other iterators using == and !=.
Pointer dereference to store data at the address but not read from it.

They are similar to Input Iterators but differ in that they are write-only instead of read-only. ostream iterators for output streams are good examples of output Iterators. Listing 3 samples how they are used. Reading from *iter would not compile since it is write-only.

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

int main()
{
    std::vector<int> v{46, 34, 97, 55};

    std::cout << "Printing vector contents: ";
    std::ostream_iterator<int> iter(std::cout, ", ");
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {
        *iter = *it;
        ++iter;
    }
    return 0;
}

Listing 3: Output Iterators

3. Forward iterators

Forward iterators support the following operations.

Increment with iter++ and ++iter.
Comparison with other iterators using == and !=.
Pointer dereference to read and store data at the address.

As the hierarchy suggests, they combine InputIterator and OutputIterator. As the name suggests, they can not be decremented. Forward list iterators are good examples of purely forward iterators. std::forward_list is implemented as a singly linked list hence allows traversing the elements only in forward direction. Listing 4 shows they work. They can read and store data but calling it-- to iterate in reverse would not compile.

#include<forward_list>
#include <iostream>
#include <iterator>

int main()
{
    std::forward_list<int> fl{46, 34, 97, 55};

    std::cout << "Before mutation: ";
    for (std::forward_list<int>::iterator it = fl.begin(); it != fl.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    for (std::forward_list<int>::iterator it = fl.begin(); it != fl.end(); ++it)
        *it = *it * 2;

    std::cout << "After mutation: ";
    for (std::forward_list<int>::iterator it = fl.begin(); it != fl.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

Listing 4: Forward Iterators

4. Bidirectional iterators

Bidirectional iterators support the following operations.

All forward iterator operations.
Decrement with iter-- and --iter.

They are similar to forward iterators but they can be decremented. std::list which is implemented as a doubly linked list generates bidirectional iterators. List iterators are good examples of purely bidirectional iterators as illustrated in Listing 4. The first two loops shows operations inherited from forward iterators. The last loop traverses the list in reverse. Since list::end() returns an invalid pointer past the last element, decrement operator is used to get the last element. It would be cleaner to simply subtract 1 but arithmetic operations are not supported. Similarly, the first element is printed after the loop because we can't get past the first element by subtracting from list::begin().

#include <list>
#include <iostream>
#include <iterator>

int main()
{
    std::list<int> l{46, 34, 97, 55};

    std::cout << "Before mutation: ";
    for (std::list<int>::iterator it = l.begin(); it != l.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    for (std::list<int>::iterator it = l.begin(); it != l.end(); ++it)
        *it = *it * 2;

    std::cout << "After mutation, in reverse order: ";
    std::list<int>::iterator it;
    for (it = --l.end(); it != l.begin(); --it)
        std::cout << ' ' << *it;
    std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

Listing 4: Bidirectional iterators

5. Random access iterators

Random access iterators support the following operations.

All bidirectional iterator operations.
Pointer arithmetic i.e addition or subtraction with a constant.
All comparisons i.e <, >, <=, >=

They are the most powerful iterators. They are generated by array based data structures such as array, std::vector and std::string. Listing 5 demonstrates these operations using vector iterators.
The first two loops shows the operations inherited from bidirectional iterators. The third loop traverses the list in reverse, but more elegantly than list iterators as a result of the following:

We can subtract 1 from list::end() to get the last element.
We can make the loop go all the way to the first element by using >= operator.

Moreover, the vector can be sorted std::sort() which only takes random access iterators.

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

int main()
{
    std::vector<int> v{46, 34, 97, 55};

    std::cout << "Before mutation: ";
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        *it = *it * 2;

    std::cout << "After mutation in reverse order: ";
    std::vector<int>::iterator it;
    for (it = v.end() - 1; it >= v.begin(); --it)
        std::cout << ' ' << *it;

    std::cout << '\n';

    std::sort(v.begin(), v.end());

    std::cout << "After sorting:";
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

Listing 5: Random access iterators

And that friends, is iterators in a nutshell. Since the kind of iterators generated by a data structures determines the operations they support, Iterator knowledge comes handy when choosing data structures. Happy hacking!

The tale of the triathlete and C++ performance

Imaculate — Tue, 05 Apr 2022 13:27:45 +0000

Let's solve the problem of the triathlete who wants to get a rough idea of their training efforts using C++. Given that running is twice as hard as biking and swimming is four times as hard as running, she wants the weighted sum of all her activities' provided as a list where an activity is made of distance and type. There is enough clarity to the problem so lets get to it.

V1

The most straight forward solution looks like the function below:

double calculateTriathleteEffortV1(vector<int> distances, vector<string> types)
{
     double result = 0.0;
    for (int i = 0; i < distances.size(); i++)
    {
        int distance = distances[i];
        string type = types[i];
        if (type == "swim")
        {
            result += (distance * 8);
        }
        else if (type == "run")
        {
            result += (distance * 2);
        }
        else if (type == "bike")
        {
            result += distance;
        }
    }
    return result;
}

It sums up the activities' distances weighted by respective factors. It works just fine and runs in an average of 0.44 microseconds per run over 10 million runs. If we have to calculate this for billions of athletes, it will not scale.

V2: Bit Manipulation

An easy way to optimize this is by using replacing multiplication with bit shift operations. This is possible because the factors are multiples of 2 and bit shifts are generally faster than arithmetic operations.

double calculateTriathleteEffortV2(vector<int> distances, vector<string> types)
{
     double result = 0.0;
    for (int i = 0; i < distances.size(); i++)
    {
        int distance = distances[i];
        string type = types[i];
        if (type == "swim")
        {
            result += (distance << 3);
        }
        else if (type == "run")
        {
            result += (distance << 1);
        }
        else if (type == "bike")
        {
            result += distance;
        }
    }
    return result;
}

The V2 function above runs in 0.47 microseconds. Surprisingly this 'optimization' has made things worse. The explanation lies somewhere in the assembly output. The compile command below saves the intermediate files including the assembly file which we should examine.

g++ -save-temps -fverbose-asm test_athlete.cpp -o test_athlete.exe

The instructions from V1 and V2 are practically the same so it looks like the compiler does a better job at this optimization than us.

 # test_athlete.cpp:29:             result += (distance * 8);
    movl    -64(%rbp), %eax  # distance, tmp112
    sall    $3, %eax     #, _7
 # test_athlete.cpp:29:             result += (distance * 8);
    cvtsi2sd    %eax, %xmm0  # _7, _8
    movsd   -56(%rbp), %xmm1     # result, tmp114
    addsd   %xmm1, %xmm0     # tmp114, tmp113
    movsd   %xmm0, -56(%rbp)     # tmp113, result
    jmp .L9  #


.
.
.


 # test_athlete.cpp:52:             result += (distance << 3);
    movl    -64(%rbp), %eax  # distance, tmp112
    sall    $3, %eax     #, _7
 # test_athlete.cpp:52:             result += (distance << 3);
    cvtsi2sd    %eax, %xmm0  # _7, _8
    movsd   -56(%rbp), %xmm1     # result, tmp114
    addsd   %xmm1, %xmm0     # tmp114, tmp113
    movsd   %xmm0, -56(%rbp)     # tmp113, result
    jmp .L16     #

We are therefore better off with multiplication so we have to look for the gains elsewhere.

V3: Branches

V2 branches between activity types using if-else-if statements where each if statement is processed in the arbitrary order we have set (swim -> run -> bike) even though each case is independent of the others. Using switch case statements allows the compiler to generate jump tables which are faster. We will attempt that and to do that we have to change the data type of activity type to enum because strings can't be used in switch-case statements.

typedef enum
{
    RUN,
    BIKE,
    SWIM,
} Type;

.
.
.

double calculateTriathleteEffortV3(vector<int> distances, vector<Type> types)
{
    double result = 0.0;
    for (int i = 0; i < distances.size(); i++)
    {
        int distance = distances[i];
        Type type = types[i];
        switch (type)
        {
            case SWIM:
                result += (distance * 8);
                break;
            case RUN:
                result += (distance * 2);
                break;
            case BIKE:
                result += distance;
                break;
        }
    }
    return result;
}

This not only eliminates expensive if-else-if jumps also but string comparison of activity types and the results do speak for themselves. V3 runs in an average of 0.27 microseconds per run, almost twice as fast!
This is definitely an optimization we want to keep. Can we do better? Probably, lets try eliminating jumps altogether.

V3: Branches

We can eliminate branches by using a look up table to translate activity types to multiplication factors.

typedef enum
{
    RUN,
    BIKE,
    SWIM,
} Type;

int factors[] = {2, 1, 8};

.
.
.

double calculateTriathleteEffortV4(vector<int> distances, vector<Type> types)
{
    double  result = 0;
    for (int i = 0; i < distances.size(); i++)
    {
        int distance = distances[i];
        Type type = types[i];
        result += (distance * factors[type]);

    }
    return result;
}

V4 runs in an average of 0.25 microseconds per run, marginally better than V3. The cost of jumps is replaced by array access which is only borderline faster. Although marginal, it is still faster, we'll therefore carry it forward as we continue to look for more performance opportunities. We have gone as far as we can to optimize the algorithm, lets try tweaking the data structures.

V5: Constant vector references

We didn't give a lot of thought into the function API, it accepts vectors which are passed by value even though they are only read in the function. We can correct that by
a) Passing the vectors by reference; this should shave some time that is spent copying all elements.
b) Marking the vectors as constant to ensure the function doesn't change the original vectors.

double calculateTriathleteEffortV5(const vector<int>& distances, const vector<Type>& types)
{
    double  result = 0;
    for (int i = 0; i < distances.size(); i++)
    {
        int distance = distances[i];
        Type type = types[i];
         switch (type)
        {
            case SWIM:
                result += (distance << 3);
                break;
            case RUN:
                result += (distance << 1);
                break;
            case BIKE:
                result += distance;
                break;
        }
    }
    return result;
}

V5 runs in an average of 0.025 microseconds per run, almost 10x faster than V4!!! It might be hard to hard to top that but lets try changing the parameters from vectors to static arrays.

V6: Array parameters

There is no need to pass dynamically sized vectors when the size never changes. Vector elements reside in the heap which makes access slower. Alternatively accessing static arrays elements is faster because they are on the stack. Arrays are passed to functions as pointers therefore we need not worry about copying on passing by value.

double calculateTriathleteEffortV6(int distances[], Type types[], int size)
{
    double result = 0;
    for (int i = 0; i < size; i++)
    {
        int distance = distances[i];
        Type type = types[i];
         switch (type)
        {
            case SWIM:
                result += (distance << 3);
                break;
            case RUN:
                result += (distance << 1);
                break;
            case BIKE:
                result += distance;
                break;
        }
    }
    return result;
}

V6 above runs in an average of 0.012 microseconds per run, almost twice as fast V5 and significantly faster than V1. We can probably do better but we'll stop here. The table summarizes the gains (or losses) each version brought,

Function	Time (us)	Delta from previous (%)	Delta from V1 (%)
V1	0.44
V2	0.47	-6.38	-6.38
V3	0.27	74.07	62.96
V4	0.25	8	76
V5	0.025	900	1660
V6	0.012	108.33	3567

We have witnessed a speedup of almost 3567% in our function, applying very practical tweaks some of which didn't work. It is therefore very important to measure if attempted optimizations are working. The journey to performance doesn't end here, there is probably more ways to make it run faster, and a lot more ways to reduce the memory footprint. Benchmarks and profiling should guide these decisions. In the meantime, our triathletes will definitely appreciate the runtime improvements.

Arrays and pointers

Imaculate — Tue, 24 Nov 2020 23:41:46 +0000

In C/C++ it is common to assume that arrays are identical to pointers. The assumption holds true for most practical scenarios: we can assign arrays to pointers, substitute pointers for arrays, and even traverse arrays with pointers. For this reason, code similar to Listing 1 below is valid and very common.

#include <iostream>
using namespace std;

void print_arr(int *p, int arr_size)
{
    cout << "Printing array of size" << size << endl;
    for (int *iter = p; iter != (p + arr_size); ++iter)
        cout << *iter << endl;
}

int main()
{
    int arr[] = {5, 6, 7, 8, 9};
    int *p = arr;
    cout << "P points to " << *p << endl;
    int arr_size = sizeof(arr) / sizeof(int);
    print_arr(arr, arr_size);
}

Listing 1: Arrays and pointers used interchangeably

Output:

Looking at the output, it is reasonable to conclude that an array is equivalent to the pointer to its first element. Does this assumption hold for array functions and multidimensional arrays? Let's find out in Listing 2.

#include <iostream>
using namespace std;

int main()
{
    int arr[] = {5, 6, 7, 8, 9};
    int *p = arr;
    cout << "Size of arr: " << sizeof(arr) << endl;
    cout << "Size of p: " << sizeof(p) << endl;

    int arr2d[2][2] = {{5, 6}, {7, 8}};
    int **p2 = arr2d;
}

Listing 2: Arrays and pointers not interchangeable

Before all else, the listing doesn't compile. The compiler doesn't like the assignment of double pointer p2 to a 2D array.

On uncommenting the problematic assignment, we see somewhat unexpected results of sizeof(). We expected the size of the array to be a multiple of the number of elements and that is true for array arr but not the equivalent pointer.

Why is that? Even though it appears so, the assumption we made is not entirely true. What's true is that there is a subset of cases where arrays are equivalent to pointers but otherwise they are entirely different types. In this article, we'll examine all the various cases, starting from the basics.

Pointers

A pointer is a variable that holds the address of another variable, the pointed-to variable can be any type including function or other pointers. Pointers can be obtained using the address-of (&) operator or dynamically assigned memory with new/malloc. The dereference operator () is used to get the value at the pointer address. They can be assigned to other pointers, and the dynamic memory they point to can be resized. **Listing 3* shows different ways pointers can be manipulated.

int num = 4;
int *p1 = &num;
int *p2 = (int *)malloc(sizeof(int));
p1 = p2;
p2 = (int *)realloc((void *)p2, 2 * sizeof(int));

Listing 3: Pointers

In the listing, p1 is declared and assigned to the address of the integer num and later assigned to another addressp2; for that reason dereferencing it won't return 4. As demonstrated in the figure below, p1 points to the same location as p2 which has been resized to double its initial size.

Arrays

An array is a data structure that holds a fixed number of elements of the same type that can be accessed by indexing. Unlike pointers, arrays can't be initialized with or assigned to other arrays, nor can they be resized. They sacrifice flexibility for runtime performance. Listing 4 shows some operations that would be valid on pointers but do not compile with arrays; these operations have been commented out.

#include <iostream>
using namespace std;

int main()
{
    int arr1[3] = {0, 1, 2};
    // int arr2[] = arr1;
    int arr3[3] = {5, 6, 7};
    //arr3 = arr1;
    cout << "First array: " << arr1 << endl;
    cout << "Third array: " << arr3 << endl;
}

Listing 4: Arrays

On running the listing, we observe interesting output on printing the arrays.

Instead of array elements, we got pointers. We have hit one of the cases where pointers and arrays are equivalent. When does the equivalence rule apply? Let's find out.

Arrays can be pointers

With a few exceptions, whenever an array appears in an expression, the compiler substitutes it with a pointer to its first element. The exceptions being address-of(&) operator, sizeof() and some cases of character arrays. This explains why in listing 2, sizeof() returned the size of a pointer rather than size of the array and the arrays in listing 4 were displayed as pointers. Let's look at different scenarios where the equivalence rule may or may not apply.

1. Address-of operator

Listing 5 demonstrates how the rule works with this operator.

int arr[4] = {0, 1, 2, 3};
int *p = arr;
//int *p2 = &arr;
int (*pa)[4] = &arr;

Listing 5: Address-of operator

arr is a array variable which when referenced in the second statement, decays to a pointer to its first element, making it valid to assign to int pointer type p. arr decays into &arr[0] which is different from &arr, pointer to the array. This distinction is better represented visually below. While pa points to the whole array, p pointes to the first element.

Uncommenting the statement that assigns p2 to &arr will cause compile-time error due to type mismatch.

2. Subscript operator

The subscript ([]) operater commonly used on arrays also works on pointers. On a pointer, it dereferences a pointer that is index steps from the input pointer, that is p[index] is equivalent to *(p + index). When used on array, the equivalence rule applies, resulting in pointer subscripting. Incrementing a pointer moves it in steps of size of the type the pointer points to. For instance in the print_arr() loop in Listing 1 above, iter++ advances iter by the size of one int since it is of type int*. Likewise incrementing pa in Listing 5 will advance it by one int array of size 4, skipping over arr into undefined territory. Caution must be exercised when subscripting pointers to ensure they are not accessing undefined memory. Buffer overflow bugs are tricky to debug since they surface as unexpected results at runtime.

3. String literals

Since strings are collections of characters, it comes as no surprise that string literals can be used to initialize character arrays. With this initialization, the array has one extra character for null termination. A noteworthy fact about string literals is that unless they are assigned to character array, they turn into unnamed read-only array of characters. Therefore although it is correct to initialize a character pointer with string literals, the contents at the location can not be modified. These concepts have been illustrated in Listing 6 below.

#include <iostream>
using namespace std;

int main()
{
    char arr[] = "Coasts";
    cout << "Null terminating char leads to length: " << sizeof(arr) << endl;

    char *p1 = arr; // decay
    cout << "p1 can modify arr since it wasn't initialized with literals" << endl;
    p1[0] = 'T';
    printf("Updated array: %s\n", arr);

    char *p2 = "Coasts";
    cout << "p2 can't modify array since it was initialized with literals" << endl;
    p2[0] = 'T';
    printf("Updated array: %s\n", p2);
}

Listing 6: Character arrays

As expected, the output shows segmentation fault when we modify p2.

4. Passing arrays to functions

Since arrays decay to pointers when passed to functions, they are effectively passed by reference. As a result, arrays can be passed to functions where the expected parameter is an array or pointer of element type. This is demonstrated in Listing 7 below.

#include <iostream>
using namespace std;

void func1(char a[])
{
    cout << "The size of array is: " << sizeof(a) << endl;
}

void func2(char *a)
{
    cout << "First character is: " << *a << endl;
}

int main()
{
    char a[] = "A sentence";
    func1(a);
    func2(a);
}

Listing 7: Arrays in functions

Array a can be passed to func2() which expects a char pointer. The listing compiles but runs with a relevant warning about func1() and which displays unexpected result for the array size.

The compiler assumes the array parameter is a pointer because that is how arrays are passed. sizeof() returns size of the pointer which can be confusing since we expected the size of the array. As a result, array size has to be passed separately to array functions.

5. Multidimensional array

Knowing what we know, its fair to assume that multidimensional arrays decay into respective multilevel pointers (e.g 2D array to double pointer) but that is not the case. The equivalence rule is not recursive; the outer array decays to a pointer to its first element which is another array. Therefore a multidimensional array decays to a pointer to array with one less dimensions. In listing 8 below, arr2d can be passed to func3() which expects pointer to int array. Extra conversion is required to pass it to func4() which takes a double pointer.

#include <iostream>
using namespace std;

void func3(int (*a)[3])
{
    cout << "Size of outer array: " << sizeof(a) << endl;
    cout << "Size of inner array: " << sizeof(*a) << endl;
    cout << "First array: " << *a << endl;
}

void func4(int **p)
{
    cout << "Derefenced element: " << **p << endl;
}

int main()
{
    int arr2d[2][3] = {{1, 2, 3}, {4, 5, 6}};
    func3(arr2d);

    int *p_to_last = &arr2d[1][2];
    func4(&p_to_last);
}

Listing 8: 2-dimensional array

The output from func3() reveals that even though the outer array became a pointer, the inner array was preserved. When the pointer is dereferenced, an int array is returned which is displayed as int pointer.

Although the equivalence is not recursive, multilevel pointers are used to dynamically allocate multidimensional arrays. Dynamic memory is allocated at runtime when it cannot be determined at compile time. The catch is the programmer has to be disciplined enough to deallocate it when no longer need. In C++, this is done with new and delete keywords or C variations of malloc and free. Below we will explore different ways of allocating dynamic multidimensional arrays modeled with 2D arrays; these methods can be translated to more dimensions with more levels of indirection.

5.1 Multi level pointers

Through arrays of pointers, multilevel pointers can create multidimensional arrays. An array of pointers is not to be confused with pointer to array. They are different types with different implications. Listing 9 highlights the syntax difference in declaration and assignment.

const int LEN = 4;
int arr[LEN] = {0, 1, 2, 3};
int (*pa)[LEN] = &arr; //pointer to array of ints
int *ap[LEN];          // array of pointers to int

for (i = 0; i < LEN; i++)
{
    ap[i] = &arr[i]; /* assign the address of integer. */
}
int **pp = ap;

Listing 9: Arrays and Pointers

More illustration in the figure below.

In a 2D array the pointers in the array to the first element(s) of respective columns. Due to equivalence rule, an array of pointers decays to a pointer to pointer i.e a multilevel pointer. Similar to single pointers outlined in Subcripting section, multilevel pointers can also be accessed with subscript operators, depending on the number of dimensions. Multidimensional arrays can be allocated in a single contiguous block or non-contiguous blocks.

5.1.1 Non-contiguous block

With this method of allocation, each column can be on a different block in memory. This is advantageous when memory is limited and its hard to get space for all rows and columns. Listing 10 shows they are allocated, manipulated and deleted. On deletion, each of the columns has to be deallocated before freeing the double pointer.

const int rows = 3;
const int cols = 4;
// array of pointers
int **arr1 = new int *[rows];
for (size_t i = 0; i < rows; i++)
    arr1[i] = new int[cols];
cout << "Array 1:" << endl;
for (size_t i = 0; i < rows; i++)
{
    for (size_t j = 0; j < cols; j++)
        cout << arr1[i][j] << " ";
    cout << endl;
}

for (size_t i = 0; i < rows; i++)
    delete arr1[i];
delete arr1;

Listing 10: Non-contigous 2D array

arr1 can be visualized as follows:

5.1.2 Contiguous block

As the title suggests, here all the array elements are allocated in one contiguous block. Since the array is allocated in one go, it has the advantage of easier cleanup but it may not be possible to find a continuous block big enough for the whole array. Listing 11 shows how such an array is manipulated. Elements can be accessed by subscripting and deletion is simply done by deallocating the block, then the array of pointers.

const int rows = 3;
const int cols = 4;
// array of pointers, continous
int **arr2 = new int *[rows];
arr2[0] = new int[rows * cols];
for(size_t i = 1; i < rows; i++)
     arr2[i] = arr2[0] + i * cols;

cout << "Array 2:" << endl;
for (size_t i = 0; i < rows; i++)
{
   for (size_t j = 0; j< cols; j++)
      cout << arr2[i][j] << " ";
   cout << endl;
}
delete arr2[0];
delete arr2;

Listing 11: Contiguous 2D array

arr2 can be visualized as follows.

Multilevel pointers provide an intuitive way of thinking about multidimensional arrays but it can be hard to visualize with higher dimensions. In such cases, it is recommended to
avoid three star programmership by using type aliases.

5.2 Pointers to arrays

Since multidimensional arrays decay to pointers to arrays, they can be declared as such. They can be declared as pointers to outer or inner arrays. Similar to multilevel pointers, elements can be accessed with subscript operators.

5.2.1 Pointer to inner array

In listing 12, a 2D array is allocated and assigned to pointer to inner array (columns).

const int rows = 3;
const int cols = 4;
int (*arr3)[cols] = new int[rows][cols];
cout << "Array 3:" << endl;
for (size_t i = 0; i < rows; i++)
{
    for (size_t j = 0; j < cols; j++)
        cout << arr3[i][j] << " ";
    cout << endl;
}
delete arr3;

Listing 12: Pointer to inner array

arr3 can be visualized as follows.

There are rows number of pointers starting from arr3 pointing to arrays. Note that these pointers point to arrays, not int elements. With more dimensions, the pointers will point to higher dimensional arrays though they made harder to visualize. The disadvantage to this is that the length of outer array (rows in above case) can not derived from the pointer, it has to be stored separately.

5.2.2 Pointer to outer array

This method is used if we need to preserve the sizes of all dimensions in the pointers. It is achieved by adding one dimension of size 1 to desired array. The additional dimension requires dereference or one more subscript operator when accessing array elements. arr4 shows one such example in Listing 13.

const int rows = 3;
const int cols = 4;
int (*arr4)[rows][cols] = new int[1][rows][cols];
cout << "Array 4:" << endl;
for (size_t i = 0; i < rows; i++)
{
    for (size_t j = 0; j < cols; j++)
        cout << (*arr4)[i][j] << " "; // or arr4[0][i][j]
    cout << endl;
}

cout << "Number of rows: " << sizeof(*arr4) << endl;
cout << "Number of columns: " << sizeof((*arr4)[0]) << endl;
delete arr4;

Listing 13: Pointer to outer array

arr4 can be visualized as follows:

5.3 Single level pointer

Although a single level pointer allocates one dimensional array, it can simulate a multidimensional array. Such arrays are also known as flattened arrays. They have the advantage of being easier to visualize and deallocate. On the other hand, since it is a 1D array, multidimensional subscript syntax can not used to access the elements; the pointer to each elements has to be manually calculated. Listing 14 illustrates how that is done. In addition to that, it requires availability of a contiguous block to fit it all and the pointer doesn't preserve dimension size information.

const int rows = 3;
const int cols = 4;
int *arr5 = new int[rows * cols];
cout << "Array 5:" << endl;
for (size_t i = 0; i < rows; i++)
{
    for (size_t j = 0; j < cols; j++)
        cout << arr5[i * cols + j] << " ";
    cout << endl;
}
delete arr5;

Listing 14: Flattened array

arr5 can be visualized as follows:

Pointers are not arrays

Having seen these scenarios, we can confidently conclude that although arrays and pointers can be equivalent, they are very different. Arrays can be pointers but pointers are not necessarily arrays. And that, friends, is the knotty relationship between arrays and pointers.

That's so Rusty! Fearless concurrency

Imaculate — Mon, 12 Oct 2020 17:08:34 +0000

A concurrent program is one which multitasks (or appears to be), that is two or more tasks run in overlapping time spans. These tasks are executed by threads, the smallest executable unit of a process. Under the hood, is not exactly multitasking but context switching between threads very rapidly that our mortal senses can't detect. Many modern applications rely on this illusion; for instance a server can wait for other requests while processing other requests. A lot could go wrong when threads share data, the most common are two kinds of bugs: race conditions and deadlock.

Race conditions happens when shared data is accessed and/or mutated by threads in an inconsistent order. This has serious repercussions for transactions that must be atomic. It is essential that only one thread accesses shared data at a time, and that the program works irrespective of the order in which threads will run.
Deadlock happens when two threads or more are waiting for each other to take action, due to a lock on resource that neither will attain, resulting in infinite hang. For instance it can happen with two threads when thread1 needs two resources, it has acquired one lock on resource1 and is waiting for thread2 to release resource2 but then thread2 is also waiting on thread1 to release resource1. This situation is known as circular wait. If the threads can hold the resources while waiting to acquire locks and pre-emption is not supported, deadlock becomes irrecoverable.

Avoiding these bugs in any language requires a great deal of discipline. When they do trickle in, they can be cumbersome to detect. In the best case these bugs manifest in crashes and hangs, in the worst case, programs runs unpredictably. That said, guarantee of fearless concurrency is not to be taken lightly. As it so happens, Rust claims to provide just that, or does it?

Rust Concurrency

The building blocks of Rust Concurrency are threads and closures.

1. Closures

Closures are anonymous functions that can access variables from the scope they were defined in. They are one of the functional paradigm features of Rust; they can be assigned to variables, passed as arguments and returned from functions. Their scope is limited to local variables, therefore not exposed beyond the crate. Syntactically, they are very similar to functions except they are unnamed, parameters are passed in vertical bar brackets (||) and type annotations are optional. Unlike functions, closures can access variables from the scope in which they are defined. The variables captured can be borrowed or moved into the closure depending on variable type and how it is used in the closure. Below is an example of a closure (assigned to print_greeting) with one parameter and captures variable generic_greeting.

fn main() {
    let generic_greeting = String::from("Good day,");
    let print_greeting = |name| println!("{} {}!", generic_greeting, name);
    let person = String::from("Crab");
    print_greeting(person);
    // println!("Can I use generic greeting? {}", generic_greeting);
    // println!("Can I use person {}", person);
}

In this example, both variables person and generic_greeting are moved into the closure, therefore they can't be used after calling the closure. The program won't compile on uncommenting the last two print statements.

2. Threads

Rust concurrency is achieved by spawning multiple threads to run different tasks wrapped in parameter-less closures. When a thread is spawned, the return type is JoinHandle type, the main thread doesn't wait for JoinHandle to complete unless it is joined. For this reason, closures passed to threads must take ownership of captured variables to ensure they are still valid when the thread eventually executes. This is demonstrated in the following example.

use std::thread;
use std::time::Duration;

fn main() {
    let t1 = thread::spawn(|| {
        for i in 1..10 {
            println!("Greeting {} from other thread!", i);
            thread::sleep(Duration::from_millis(1));
        }
    });

    for i in 1..5 {
        println!("Greeting {} from main thread!", i);
        thread::sleep(Duration::from_millis(1));
    }
    t1.join().unwrap();
}

We get full output from both threads, 9 greetings from spawned thread and 4 greetings from main thread.

When t1.join().unwrap() is commented out, the program exits when the main thread completes. You can try it on the Rust playground.

It is also worth noting that the output may vary on multiple runs of the program. Such non-determinism is characteristic of concurrency and as we'll eventually see, a source of many bugs.

As far as multitasking goes, it is crucial that threads share information. Through the standard library, Rust supports communication through two methods: Message Passing and Shared-State.

1. Message passing

Rust supports channels, through which threads can send and receive messages. An example is the Multiple Producers Single Consumers(shortened as mpsc) channel. This channel allows multiple transmitters to communicate with a single receiver, where these components may be in different threads. The channel takes ownership of variables at transmitter end and gives it up at the receiver end. The example below shows how messages are passed in a channel with two transmitters and one receiver.

use std::sync::mpsc;
use std::thread;

fn main() {
    let (tx1, rx) = mpsc::channel();
    let tx2 = mpsc::Sender::clone(&tx1);

    thread::spawn(move || {
        println!("Sending message from thread 1");
        tx1.send(String::from("Greeting from thread 1")).unwrap();
    });

    thread::spawn(move || {
        println!("Sending message from thread 2");
        tx2.send(String::from("Greeting from thread 2")).unwrap();
    });

    for recvd in rx {
        println!("Received: {}", recvd);
    }
}

A second transmitter is made by cloning the original one. There is no need to join the threads since the receiver blocks until all the channel messages are received, there by waits for thread execution to complete.

2. Shared state

Another means of communication is by sharing memory. Message passing is great but it has the limitation of single ownership; objects have to be moved/cloned to be transmitted to another thread, if the object is moved it is rendered unusable, if it is cloned any updates to it will have to be communicated by message passing. The workaround to this is multiple ownership, which you may recall from smartpointers post is achievable with reference counted smartpointers Rc<T>. We saw how combined with RefCell<T>, we created mutable shared pointers. Why not use them in a multithreaded program? One attempt is shown below:

fn main() {
    let counter = Rc::new(RefCell::new(0));
    let mut threads = vec![];

    for _ in 0..5 {
        let counter = Rc::clone(&counter);
        let handle = thread::spawn(move || {
            let mut num = (*counter).borrow_mut();
            *num += 1;
        });
        threads.push(handle);
    }

    for thread in threads {
        thread.join().unwrap();
    }

    println!("Result: {}", *counter.borrow());
}

A shared pointer to a counter is sent to 5 threads, each of which increments it by 1. The number is then printed after the threads complete. Will this work?

It doesn't compile but the error message is on to something. The type Rc<RefCell<T>> can not be sent between threads safely. Further down is the reason; it doesn't implement the Send trait.
Looks like the intent has been correctly expressed but we need thread safe versions of the pointer(s). Do safe alternatives exist? Indeed, the alternative to Rc<T> is the atomic reference counted type Arc<T>. In addition to properties of Rc<T> (shared ownership) it can be safely shared between threads by implementing the Send trait. Making a substitution in the program should get us closer to working state. Does the below snippet compile?

use std::cell::RefCell;
use std::thread;
use std::sync::Arc;

fn main() {
    let counter = Arc::new(RefCell::new(0));
    let mut threads = vec![];

    for _ in 0..5 {
        let counter = Arc::clone(&counter);
        let handle = thread::spawn(move || {
            let mut num = (*counter).borrow_mut();
            *num += 1;
        });
        threads.push(handle);
    }

    for thread in threads {
        thread.join().unwrap();
    }

    println!("Result: {}", *counter.borrow());
}

No, We have a similar but slightly different error now. RefCell<T> can't be shared among threads, doesn't implement Send and Sync traits.

If RefCell<T> is not suitable for concurrency, there has to be a thread safe alternative. In fact, the Mutex (Mutex<T>) is just that; in addition to providing interior mutability, mutexes can be shared between threads. A thread must acquire a lock before accessing mutex object, ensuring single thread access at a time. Locking a mutex returns LockResult<MutexGuard<T>> type of smartpointer. A LockResult is an enum that can be Ok<T> or Error. For simplicity, we extract it by calling unwrap() which returns the inner object (MutexGuard in this case) if its Ok and panics on error. A MutexGuard is another smartpointer that can be dereferenced to access the inner object, the lock is released when thr LockResult goes out of scope. For our program, we substitute Mutex<T> for RefCell<T> and update the way it is manipulated as shown below:

use std::sync::{Arc, Mutex};
use std::thread;

fn main() {
    let counter = Arc::new(Mutex::new(0));
    let mut threads = vec![];

    for _ in 0..5 {
        let counter = Arc::clone(&counter);
        let handle = thread::spawn(move || {
            let mut num_guard = (*counter).lock().unwrap();
            *num_guard += 1;
        });
        threads.push(handle);
    }

    for thread in threads {
        thread.join().unwrap();
    }

    println!("Result: {}", *counter.lock().unwrap());
}

Much to our delight, it works!

It is worth noting that the atomicity of Arc<T> and Mutex<T> comes with performance penalty. It is possible but not wise to use them in single threaded programs.

Knowing what we know, is Rust concurrency as fearless as claimed? The answer lies in the way it handles the most common concurrency pitfalls some of which were introduced above.

1. Race conditions

We established in Mutables that data races/inconsistency happens when two or more pointers access the same data at the same time, at least one of the pointers is being used to write to the data and access to the data is not synchronized. By ensuring a mutex is always associated with an object, access to the object is always synchronized. This is unlike C++ where a mutex is a separate entity and the programmer has to manually ensure a lock is acquired before accessing a resource. Below is an example of how incorrect use of mutex can cause inconsistencies.

#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>
using namespace std;

mutex mtx;
int counter = 0;

void increment_to_5(int id)
{
    cout << "Executing from thread: " << id << endl;
    if (counter < 5)
    {
        lock_guard<mutex> lck(mtx);
        counter++;
    }
}

int main()
{
    thread threads[10];
    for (int i = 0; i < 10; ++i)
        threads[i] = thread(increment_to_5, i);

    for (auto &thread : threads)
        thread.join();

    cout << "Final result: " << counter << endl;
    return 0;
}

The function increment_to_5() is called in different threads and it is supposed to increment counter variable until it gets to 5.
Although it is reasonable to only lock the mutex before the critical section (incrementing it), the lock should have been acquired before accessing comparing counter to 5. Otherwise, multiple threads may read a stale value, and increase it beyond the desired 5. This consequence is made clear on adding a small delay before lock acquisition as shown below.

cout << "Executing from thread: " << id << endl;
    if (counter < 5)
    {
        this_thread::sleep_for(chrono::milliseconds(1));
        lock_guard<mutex> lck(mtx);
        counter++;
    }
}

The final value of counter will vary on different runs. The Rust translation of this program won't encounter this problem because counter is a mutex type and has lock has to be acquired before any access. Different runs of below program will produce the same result.

use std::sync::{Arc, Mutex};
use std::thread;
use std::time::Duration;

fn main() {
    let counter = Arc::new(Mutex::new(0));
    let mut threads = vec![];

    for i in 0..10 {
        let counter = Arc::clone(&counter);
        let handle = thread::spawn(move || {
            println!("Executing from thread: {}", i);
            let mut num_guard = (*counter).lock().unwrap();
            if *num_guard < 5 {
                thread::sleep(Duration::from_millis(1));
                *num_guard += 1;
            }
        });
        threads.push(handle);
    }

    for thread in threads {
        thread.join().unwrap();
    }

    println!("Result: {}", *counter.lock().unwrap());
}

2. Deadlock

Although Rust mitigates some concurrency risks, it is not capable of detecting deadlock at compile time. The example below shows how two threads can end up in a deadlock on two mutexes.

use std::sync::{Arc, Mutex};
use std::thread;
use std::time::Duration;
fn main() {
    let v1 = Arc::new(Mutex::new(0));
    let v2 = Arc::new(Mutex::new(0));

    let v11 = Arc::clone(&v1);
    let v21 = Arc::clone(&v2);
    let t1 = thread::spawn(move ||
        {
            println!("t1 attempting to lock v1");
            let v1_guard = (*v11).lock().unwrap();
            println!("t1 acquired v1");

            println!("t1 waiting ...");
            thread::sleep(Duration::from_secs(5));

            println!("t1 attempting to lock v2");
            let v2_guard = (*v21).lock().unwrap();

            println!("t1 acquired both locks");
        }
    );

    let v12 = Arc::clone(&v1);
    let v22 = Arc::clone(&v2);
    let t2 = thread::spawn(move ||
        {
            println!("t2 attempting to lock v2");
            let v1_guard = (*v22).lock().unwrap();
            println!("t2 acquired v2");

            println!("t2 waiting ...");
            thread::sleep(Duration::from_secs(5));

            println!("t2 attempting to lock v1");
            let v2_guard = (*v12).lock().unwrap();

            println!("t2 acquired both locks");
        }
    );

    t1.join().unwrap();
    t2.join().unwrap();
}

From the output, the program hangs after each thread has acquired its first lock.

In a similar fashion, deadlock can also happen with message passing as in below example.

use std::sync::mpsc;
use std::thread;

fn main() {
    let (tx1, rx1) = mpsc::channel();
    let (tx2, rx2) = mpsc::channel();

    thread::spawn(move || {
        println!("Waiting for item 1");
        rx1.recv().unwrap();

        println!("Sending item 2");
        tx2.send(()).unwrap();
    });

    println!("Waiting for item 2");
    rx2.recv().unwrap();

    println!("Sending item 1");
    tx1.send(()).unwrap();
}

Since each channel waits for an item before sending, both channels are left waiting forever.

3. Reference cycles

From smart pointers post, we saw how Rc pointers can cause reference cycles. Arc pointers are also not immune to them but they can be similarly mitigated with Atomic Weak pointers.

From above observation, its safe to say that Rust concurrency is not 100% flawless. It prevents race conditions at compile time but can't guarantee the same for deadlocks or reference cycles. In retrospect, these problems are not unique to Rust, and compared to most languages Rust performs much better. Concurrency in Rust is not necessarily fearless but it is less fearful.

That's so Rusty!: Smart pointers

Imaculate — Sat, 03 Oct 2020 04:15:48 +0000

If you've been following this series, the post about Ownership probably gave you the impression that Rust is a no-brainer and C++ should never be used in production. Smart pointers may change your mind. In modern terms, Smart pointers are pointers which are a little (um ...) extra. They are essentially memory addresses that manage the object they point to and automatically clean up when the object is no longer in use. This eliminates lots of bugs caused by memory mismanagement and makes programming a lot less tedious. While C++ smart pointers provide a safe alternative to raw pointers, Rust smart pointers extend the language capabilities while maintaining safety.

Smart pointers are dereferenced like regular pointers but exhibit varying behavior on assignment and deallocation. As a result, there are different kinds of smart pointers. In this post we'll explore how they are used to implement variations of Linked Lists namely:
1) A singly linked list
2) A shared linked list
3) A doubly linked list

1. Simple linked list

A linked list is a linear collection of nodes in which each node points to the next. In a singly linked list, each Node has its own data and a pointer to the next Node, the last Node points to NULL indicating end of list.

A. Rust

In Rust a Singly Linked List Node could be defined as below:

struct Node {
    value: i32,
    next: Node,
}

But it won't compile for various reasons. First, since next can be NULL, next should be an Option<Node>, the NULL equivalent in Rust. Moreover, a Rust struct must have known size at compile time. If Option<Node> is a field of Node, the size of Node can be as long as the length of list, potentially infinite. To workaround that, pointers are used since they have finite size, they are afterall just addresses. The most straight forward smart pointer is the Box (Box<T>). It allocates data on the heap and when it goes out of scope both the pointer and data it points to are dropped. On assignment, Boxes follow Rust ownership rules; on assignment, ownership of both data and pointer is moved. Changing the type of next to Box<Option<T>> precisely captures the essence of a node.

Below example shows how two nodes are singly linked to a list.

struct Node {
    value: i32,
    next: Box<Option<Node>>,
}

fn main() {
    let a = Node {
        value: 5,
        next: Box::new(None),
    };
    let b = Node {
        value: 10,
        next: Box::new(Some(a)),
    };
    println!("b is {:?}", b);
    // println!("a is {:?}", a);
}

It runs successfully but uncommenting last print statement leads to compile error since a was moved when it was assigned to b.next.

B. C++

The C++ equivalent to Boxes are unique pointers. As the name implies, unique pointers own objects explicitly, when deallocation conditions are met it deletes the managed object irrespective of other pointers pointing to it. For this reason, there should be only one unique pointer managing an object. To assign the object to another unique pointer, it has to be moved; ownership is transferred and the previous pointer is nullified. Sound familiar? It should, because Rust ownership system behaves similarly. C++ unique pointers have similar benefits but they don't provide compile-time guarantee of memory safety; dereferencing a nullified pointer will error-out at runtime. Below is an example of how a linked list node can be implemented with unique pointers.

#include <iostream>
#include <memory>
#include <utility>
using namespace std;

struct Node
{
    int value;
    unique_ptr<Node> next;
};

void printNode(unique_ptr<Node> n)
{
    if (n != nullptr)
    {
        cout << "value: " << n->value << ", ";
        printNode(move(n->next));
    }
    cout << '\n';
}

int main()
{
    Node a{5, nullptr};
    unique_ptr<Node> upA(&a);
    Node b{10, move(upA)};
    unique_ptr<Node> upB(&b);
    printNode(move(upB));
    // printNode(move(upA));
}

printNode() has been implemented since C++ doesn't generate toString() implementation like Rust. Unique pointer upA is moved to be assigned to next of node b, the pointers also have to be moved to be passed to functions. Uncommenting the last print statement results in segmentation fault since the upA is null.

2. Shared linked list

A shared linked list is one in which two or more lists share one or more segments. The diagram below shows an example where segment C-D is shared by two lists that start at A and B respectively.

A. Rust

To support shared lists, nodes have to be able to have multiple owners. Can we use Boxes for this type of lists?

#[derive(Debug)]
struct Node {
    value: i32,
    next: Box<Option<Node>>,
}

fn main() {
    let a = Node {
        value: 5,
        next: Box::new(None),
    };
    let b = Node {
        value: 10,
        next: Box::new(Some(a)),
    };
    println!("b is {:?}", b);
    let c = Node {
        value: 20,
        next: Box::new(Some(a)),
    };
}

The compiler disagrees because boxes can only have one owner.

To support multiple ownership Rust has Reference Counted smart pointers, shortened as Rc<T>.Rc<T> pointers are shared by cloning which creates a copy that points to the same data and increments the reference count. This count is decremented when the pointers become invalid.

To make the node shareable, the type is next is changed to Rc<Option<Node>> in place of Box<Option<Node>>. This change justifies defining another struct, SharedNode to distingush from the simple Node. The node in a is shared by b and c by cloning its smartpointer. This time around, the compiler is satisfied.

#[derive(Debug)]
struct SharedNode {
    value: i32,
    next: Rc<Option<SharedNode>>,
}

use std::rc::Rc;

fn main() {
    let a = Rc::new(Some(SharedNode {
        value: 5,
        next: Rc::new(None),
    }));
    let b = SharedNode {
        value: 10,
        next: Rc::clone(&a),
    };
    let c = SharedNode {
        value: 20,
        next: Rc::clone(&a),
    };
    println!("a is {:?}", a);
    println!("b is {:?}", b);
    println!("c is {:?}", c);
}

Reference counts

It is also possible to trace how the reference count is updated using the function Rc::strong_count(). In the example below, reference count of SharedNode managed by a increases on cloning it to link to nodes b and c. The count decreases when c goes out of scope.

let a = Rc::new(Some(SharedNode {
    value: 5,
    next: Rc::new(None),
}));
println!("Rc count of a after creating a = {}", Rc::strong_count(&a));
let b = SharedNode {
    value: 10,
    next: Rc::clone(&a),
};
println!("Rc count of a after creating b = {}", Rc::strong_count(&a));
{
    let c = SharedNode {
        value: 20,
        next: Rc::clone(&a),
    };
    println!("Rc count of a after creating c = {}", Rc::strong_count(&a));
}
println!(
    "Rc count of a after c goes out of scope = {}",
    Rc::strong_count(&a)
);

Mutation

We established in mutables post that Rust doesn't prefer default mutability partly because multiple mutable references lead to data races and race conditions. It is crucial that smart pointers are mutable, otherwise they would have limited functionality. To bridge the gap, Rust offers RefCell<T>, another type of smart pointer pointer which offers interior mutability: a way to mutate immutable references by deferring borrowing rules enforcement to runtime. Interior mutability is useful but since references are analyzed at runtime vs compile time, it can allow unsafe code to blow-up at runtime and also cause performance regression.

The example below demonstrates how Rc<T> and Box<T> types can be mutated. RefCell<T> has borrow_mut() function which returns a mutable smart pointer RefMut<T>, the pointer can be dereferenced (with * operator) and mutated. Borrowing rules still apply therefore if more than one RefCell<T> is used in same scope, the program will panic at runtime.

#[derive(Debug)]
struct Node {
    value: i32,
    next: Box<RefCell<Option<Node>>>,
}

#[derive(Debug)]
struct SharedNode {
    value: i32,
    next: Rc<RefCell<Option<SharedNode>>>,
}
use crate::List::{Cons, Nil};
use std::cell::RefCell;
use std::rc::Rc;

fn main() {
    println!("Mutating node");
    let node_a = Node {
        value: 5,
        next: Box::new(RefCell::new(None)),
    };
    let a = Box::new(RefCell::new(Some(node_a)));
    let b = Node { value: 10, next: a };
    println!("Before mutation b is {:?}", b);

    if let Some(ref mut x) = *b.next.borrow_mut() {
        (*x).value += 10;
    }
    println!("After mutation b is {:?}", b);

    println!("Mutating shared node ...");
    let node_a = SharedNode {
        value: 5,
        next: Rc::new(RefCell::new(None)),
    };
    let a = Rc::new(RefCell::new(Some(node_a)));

    let b = SharedNode {
        value: 10,
        next: Rc::clone(&a),
    };
    let c = SharedNode {
        value: 20,
        next: Rc::clone(&a),
    };
    println!("Before mutation a is {:?}", a);
    println!("Before mutation b is {:?}", b);
    println!("Before mutation c is {:?}", c);

    if let Some(ref mut x) = *a.borrow_mut() {
        (*x).value += 10;
    }

    println!("After mutation a = {:?}", a);
    println!("After mutation b = {:?}", b);
    println!("After mutation c = {:?}", c);
}

B. C++

The C++ equivalent to Rc<T> is the shared pointer. It exhibits similar reference counting behaviour and has the advantage of easier mutation. The snippet below shows how it is used to create a shared linked list.

#include <iostream>
#include <memory>
#include <utility>
using namespace std;

struct SharedNode
{
    int value;
    shared_ptr<SharedNode> next;
};

void printSharedNode(shared_ptr<SharedNode> n)
{
    if (n != nullptr)
    {
        cout << "value: " << n->value << " -> ";
        printSharedNode(n->next);
    }
    cout << '\n';
}

int main()
{
    SharedNode node_a{5, nullptr};
    shared_ptr<SharedNode> a(&node_a);
    cout << "Reference count of a: " << a.use_count() << endl;
    SharedNode node_b{10, a};
    shared_ptr<SharedNode> b(&node_b);
    cout << "Reference count of a, after linking to b: " << a.use_count() << endl;
    SharedNode node_c{20, a};
    shared_ptr<SharedNode> c(&node_c);
    cout << "Reference count of a, after linking to c: " << a.use_count() << endl;

    // mutation
    a->value = 2;

    printSharedNode(a);
    printSharedNode(b);
    printSharedNode(c);

    a.reset();
    cout << "Reference count of a on reset: " << a.use_count() << endl;
    // cout << " a is " << a->value << endl;
}

The output looks like:

Although shared pointers are easier to work with, they are not immune to C++ safety concerns. Uncommenting the last print statement above results in seg-fault at runtime.

3. Doubly linked list

In a doubly linked list, each node has pointer to the next as well previous node in the list. Therefore, a doubly linked Node has prev field that is of the same type as next.

A. Rust

Using the pointers we've used so far we can create doubly linked node named DoubleNode. Setting and updating prev and next fields requires interior mutability hence the need for RefCell<T>. To allow the DoubleNode to be owned by next and previous node we'll use Rc<T>. The prev and next fields of border nodes are nullable we'll use Option<DoubleNode>. Therefore, the type of prev and next fields becomes Rc<RefCell<Option<DoubleNode>>>.

For simplicity, we create a list of two nodes node_a and node_b and their corresponding pointers a and b. node_b is created with a clone of a as its next element and using interior mutability, the prev element of node_a is made to point to node_b. This is done in the snippet below which prints node information and reference count before and after linking the nodes.

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
struct DoubleNode {
    value: i32,
    next: Rc<RefCell<Option<DoubleNode>>>,
    prev: Rc<RefCell<Option<DoubleNode>>>,
}

fn main() {
    let node_a = DoubleNode {
        value: 5,
        next: Rc::new(RefCell::new(None)),
        prev: Rc::new(RefCell::new(None)),
    };
    let a = Rc::new(RefCell::new(Some(node_a)));
    let node_b = DoubleNode {
        value: 10,
        next: Rc::clone(&a),
        prev: Rc::new(RefCell::new(None)),
    };
    let b = Rc::new(RefCell::new(Some(node_b)));

    println!(
        "Before linking a is {:?}, rc count is {}",
        a,
        Rc::strong_count(&a)
    );
    println!(
        "Before linking b is {:?}, rc count is {}",
        b,
        Rc::strong_count(&b)
    );

    if let Some(ref mut x) = *a.borrow_mut() {
        (*x).prev = Rc::clone(&b);
    }

    println!("After linking a rc count is {}", Rc::strong_count(&a));
    //println!("After linking a is {:?}", a);
    println!("After linking b rc count is {}", Rc::strong_count(&b));
    //println!("After linking b is {:?}", b);
}

It compiles and runs just fine but the output gets interesting when the last two commented print statements are uncommented.

Printing any node goes infinitely in cycles, resulting in stack overflow. This is because to extract the string representation of a node, we have expand all its fields. To print node_a, we print its fields: value (5), next (None) and prev(node_b), prev points to a DoubleNode therefore we print it in a similar fashion: value (10), next (node_a) and prev(None), next points to DoubleNode so we expand on it, returning us to printing node_a again, the cycle continues infinitely. This is an example reference cycle which has manifested in stack overflow.

Another consequence of reference cycles is memory leak which happens when memory is not released. On successfully running the snippet above, it is observed that both pointers a and b have a reference count of 2. At the end of main, Rust will attempt to drop b, this leaves 1 reference to node_b, the prev pointer of node_a. This reference count will remain 1 indefinitely, preventing the node_b from being dropped. As a result, both nodes will not be dropped, leading to memory leak. Since the program above exits shortly, the OS cleans the memory. Memory leaks are more severe in long running programs like servers. This is one of the few bugs that can slip past the Rust compiler.

Does this mean it is impossible to implement doubly linked lists in Rust? No. It is possible with another kind of pointer called weak pointer. A weak pointer is a smart pointer that holds a non-owning reference to an object that is managed by a shared pointer.
Denoted as Weak<T>, weak pointers are similar to Rc<T> in that they can share ownership, but they don't weigh against deallocation. The example below shows how they solve our Doubly Linked List mystery.

use std::cell::RefCell;
use std::rc::{Rc, Weak};

#[derive(Debug)]
struct DoubleNode {
    value: i32,
    next: Rc<RefCell<Option<DoubleNode>>>,
    prev: Weak<RefCell<Option<DoubleNode>>>,
}

fn main() {
    let node_a = DoubleNode {
        value: 5,
        next: Rc::new(RefCell::new(None)),
        prev: Weak::new(),
    };
    let a = Rc::new(RefCell::new(Some(node_a)));
    let node_b = DoubleNode {
        value: 10,
        next: Rc::clone(&a),
        prev: Weak::new(),
    };
    let b = Rc::new(RefCell::new(Some(node_b)));

    println!(
        "Before cycle a is {:?}, rc count is {}",
        a,
        Rc::strong_count(&a)
    );
    println!(
        "Before cycle b is {:?}, rc count is {}",
        b,
        Rc::strong_count(&b)
    );

    if let Some(ref mut x) = *a.borrow_mut() {
        (*x).prev = Rc::downgrade(&b);
    }

    println!(
        "After cycle a rc count is {}, weak count is {}",
        Rc::strong_count(&a),
        Rc::weak_count(&a)
    );
    println!("After cycle a is {:?}", a);
    println!(
        "After cycle b rc count is {}, weak count is {}",
        Rc::strong_count(&b),
        Rc::weak_count(&b)
    );
    println!("After cycle b is {:?}", b);
}

The absence of stack overflow on printing the node is a sign reference cycles have been removed.

This has been achieved by making the prev pointer a weak pointer. A weak pointer is made by downgrading a shared pointer instead of cloning it and doesn't affect the effective reference count.

By tracing reference counts we can see how reference cycles are prevented. After doubly linking the nodes, a has strong count of 2 and b has strong count of 1 and weak count of 1. At the end of main, Rust will attempt to drop b, leaving node_b with weak count of 1. Since weak pointers have no bearing on deallocation, the node is dropped. After node_b is dropped, its link to a is removed, reducing node_a's strong count to 1. When a goes out of scope, node_a's strong count becomes 0, allowing it to be dropped. Essentially, reference cycles have been solved by reducing the importance of some references. This is also evident in the output where weak pointers are not expanded but simply annotated as (Weak).

B. C++

The equivalent of Rust weak pointers in C++ are well, weak pointers. They are used in a similar way to prevent reference cycles. They can be used to implement doubly linked list as shown below.

#include <iostream>
#include <memory>
#include <utility>
using namespace std;

struct DoubleNode
{
    int value;
    shared_ptr<DoubleNode> next;
    weak_ptr<DoubleNode> prev;
};


void printDoubleNode(shared_ptr<DoubleNode> n)
{
    if (n != nullptr)
    {
        cout << "value: " << n->value << ", prev: (Weak) ->";
        printDoubleNode(n->next);
    }
    cout << '\n';
}

int main()
{
    DoubleNode node_a{5, nullptr, weak_ptr<DoubleNode>()};
    shared_ptr<DoubleNode> a(&node_a);
    DoubleNode node_b{10, a, weak_ptr<DoubleNode>()};
    shared_ptr<DoubleNode> b(&node_b);
    cout << "Before linking, rc count of a: " << a.use_count() << endl;
    cout << "Before linking, rc count of b: " << b.use_count() << endl;
    printDoubleNode(a);
    printDoubleNode(b);

    a->prev = b;
    cout << "After linking, rc count of a: " << a.use_count() << endl;
    cout << "After linking, rc count of b: " << b.use_count() << endl;
    printDoubleNode(a);
    printDoubleNode(b);
}

The output confirms that weak pointers do not affect reference counts.

Apart from syntactical differences, it looks like Rust smart pointers are very similar to C++. They were designed to address similar problems. While Rust smart pointers maintain compile time guarantees (except for reference cycles), C++ smart pointers are easier to manipulate and reference count operations are thread safe. Which ones do you prefer?

That's so Rusty: Metaprogramming

Imaculate — Thu, 17 Sep 2020 16:41:08 +0000

I'm writing this post while recovering from writer's cramp from all the keystrokes I've been striking. I've read Hanselman's concept of limited keystrokes in a lifetime before but this is the probably the first time it hit home. Ideally I would like a programming language that rids zero of boiler plate. I'm in luck because that is something Rust has done a fairly good job at. The simplest demonstration is when declaring variables. Although Rust is strongly typed, declaring a variable type is optional since it can be inferred. Declaring the type is still an option but not required. Below are two valid ways of declaring an integer.

let x = 9;
let x: i32 = 9;

In addition to that, Rust allows you to write code that generates code, a concept known as metaprogramming. As advanced as it sounds, metaprogramming has practical applications that can tremendously improve the quality of code and life. We will explore how with two problems.

How would you implement a function that takes a variable number of arguments i.e variadic function?
How would you implement a function that returns true if a struct has at least one vector field i.e has_vector_field()?

1. Variadic functions

Variadic functions are functions that can be passed with different number of arguments that may or not be of the same type. An example is a function that calculates the sum of numbers. The example below shows how sum_of_numbers() can calculate sum of 3 or 6 numbers that can be integers or floating point numbers.

fn main() {
    println!("Sum of three numbers is: {}", sum_of_numbers(1, 4.2, 5));
    println!(
        "Sum of six numbers is: {}",
        sum_of_numbers(-6, 8, 10, 12, 67, 90)
    );
}

One way to achieve this would be to define a function for each possible way arguments will be passed. Lets find out how feasible that is. We need to factor in the number of arguments a function can have, which is limitless but we can limit it to 100 for simplicity. These arguments could be integers or floating point numbers of varying widths hence various types, we can limit the types to 20. The number of functions to define is equal of unique permutations of upto 100 elements that can be of 10 different kinds. This problem is now a matter of combinatorics mathematics.
We can get a sense of the magnitude procedurally as follows:

Pick n starting from 1.
Find all possible type combination (up to 10 types) for chosen n.
For each of combination, find all possible arrangements (permutations) of the elements, sum the counts.
Sum the counts of all combinations for n to the total count.
Advance n by 1, repeat 1-4 till n is 100.

Even without knowledge of combinatorics, its easy how fast the total count will grow, even with simplified numbers. Given that this is the number of functions to be defined, a lot of code will be duplicated making it impossible to maintain, not to mention the pain of keystrokes. Although this option is possible, it is not feasible.

Another alternative would be to make the function take array argument instead. This has limitations for strongly typed languages where array elements can be only one type and Rust is one such language. To workaround that, we can make the array to be of floating point numbers since all numbers can be converted to floats. This adds overhead of creating an array and populating it with floating points versions of the arguments before calling the function. Although this option is feasible, it is not the most elegant.

Metaprogramming can give us both feasible and elegant solution to our problem through macros. Macros are similar to functions except their input and output is Rust code, not data. Rust supports two kinds of macros: Declarative and Procedural. Procedural macros allow you to extract patterns and generate appropriate code for each pattern. They were designed for this type of problem.

Here is a macro definition that solves the problem:

macro_rules! sum_of_numbers
{
    ( $( $x:expr ),* ) => {
        {
            let mut result = 0.0;
            $(
                result += $x as f64;
            )*
            result as i64
        }
    };
}

The definition is prepended with macro_rules! similar to fn for functions. The body syntax is similar to match guard, the Rust equivalent to switch-case statement. This guard is slightly different since it is matching against Rust code. It has one arm in parenthesis ( $( $x:expr),* ) which represents a pattern. If the pattern matches, the code after => will be executed.

In the inner parenthesis is ($x:expr), which matches a Rust expression and assigns it to x. Following that is a comma which represents a separator, the star next stands for the cardinality of 0 or more. This pattern therefore matches comma-separated Rust expressions. For each expression, the code in $() is generated, manipulating the expression as x.

When the macro is called with arguments like sum_of_numbers!(1, 4.2, 5), it effectively expands to:

{
    let mut result = 0.0;
    result += 1 as f64;
    result += 4.2 as f64;
    result += 5 as f64;
    result
}

This is as accurate as the function we would have hard-coded had we gone with the naive approach.

2. `has_vector_field()` function for structs

As the name suggests, we want has_vector_field() to examine all fields of a struct and return true if any of them is a vector. Other than demonstration it may be hard to imagine the practicality of this function but it may prove useful for assessing and optimizing runtime performance. For instance, it may be used to for assessment to avoid cloning large objects like below.

struct Book {
    title: String,
    publication_year: u32,
    authors: Vec<String>,
}

fn main() {
    let b = Book {...}
    if (!Book::has_vector_field()) {
        let b_clone = b.clone();
    }
}

Lets start with the most straight forward solution. Can we implement has_vector_field() for Book struct? Yes and No.

impl Book {
    fn has_vector_field() -> bool {
        // ....
    }
}

Yes, we can hardcode the result of the function because we know that Book has one vector field; authors. To maintain correctness, this function will have to be evaluated (and possibly updated), every-time the struct fields change. This becomes tedious when all structs in the program require the same attention. Maintaining this code will not feasible even for a highly disciplined team. The best option would be to dynamically introspect the struct fields in the function but Rust doesn't support reflection.

There has got to be a better way, this is Rust, after all, it is bound to have an elegant solution. First off, since we want has_vector_field() to be available to multiple structs, in other languages we would put it behind an interface to enforce all types to implement it. Rust has traits in place of interfaces. For our example we can implement the trait VectorField for Book as below:

pub trait VectorField {
    fn has_vector_field() -> bool;
}

impl VectorField for Book {
    fn has_vector_field() -> bool {
        // ...
    }
}

We still have to implement the function and this is where macros come to the rescue. In addition to declarative macros described in previous example, Rust supports another kind of macros called procedural macros. Procedural macros take Rust code as input and return Rust code. There are three kinds of procedural macros.

a. Function-like macros
b. Custom Derive macros
c. Attribute macros.

With derive macros we can generate trait implementations for types. Simply annotating a type with #[derive(<TraitName>)], makes the trait functions available. Snippet below shows barebones definition of the macro and how it can be used with Book struct.

// vectorfield_derive.rs
#[proc_macro_derive(VectorField)]
pub fn derive_vector_fields(input: TokenStream) -> TokenStream {
    TokenStream::new()
}

// main.rs
#[derive(VectorField)]
struct Book {
    title: String,
    publication_year: u32,
    authors: Vec<String>,
}

The input TokenStream can be parsed into an Abstract Syntax Tree (AST) for further processing.

#[proc_macro_derive(VectorField)]
pub fn derive_vector_fields(input: TokenStream) -> TokenStream {
    let ast = parse_macro_input!(input as DeriveInput);
    TokenStream::new()
}

To manipulate the AST, we need to figure out its structure. It is possible to print it on enabling full or extra-traits Rust features on the project. Doing so reveals the tree structure and how to extract field information from it. A truncated version of the AST for Book struct looks like:

ident: Ident {
        ident: "Book",
        span: #0 bytes(277..281),
    },
    ...
    data: Struct(
        ...
        Field {
               ...
                ident: "title",
                ...
                type:
                   ...
                   ident: "String"
        },
...

Of interest are the field type identifiers and the code below shows how to extract them from the AST.

#[proc_macro_derive(VectorField)]
pub fn derive_vector_fields(input: TokenStream) -> TokenStream {
    let ast = parse_macro_input!(input as DeriveInput);
    let mut vec_field = false;
    let fields = match &ast.data {
        Data::Struct(DataStruct {
            fields: Fields::Named(fields),
            ..
        }) => &fields.named,
        _ => panic!("expected a struct with named fields"),
    };

    for field in fields {
        if let Type::Path(tp) = &field.ty {
            if tp.path.segments[0].ident.to_string() == "Vec" {
                vec_field = true;
                break;
            }
        }
    }
    TokenStream::new()
}

For struct types, the data field of the AST is a Data::Struct Enum variant. Since we are implementing has_vector_field() for structs with named fields for simplicity, the match statement panics (throws exception in other languages) if another variant is found or fields are unnamed. Panicking is generally not a good idea, but its practical for our simple example. We then iterate through the fields, extracting each field type to get the identifier and compare it to the vector identifier Vec. We shortcircuit the loop on finding the first vector.

After dynamically determining the return value of has_vector_field(), the next step is to create a TokenStream of the function definition. This is done with the quote! macro as shown below.

extern crate proc_macro;

use proc_macro::TokenStream;
use quote::quote;
use syn;

#[proc_macro_derive(VectorField)]
pub fn derive_vector_fields(input: TokenStream) -> TokenStream {
    let ast = parse_macro_input!(input as DeriveInput);
    let name = &ast.ident;
    let mut vec_field = false;

    let fields = match &ast.data {
        Data::Struct(DataStruct {
            fields: Fields::Named(fields),
            ..
        }) => &fields.named,
        _ => panic!("expected a struct with named fields"),
    };

    for field in fields {
        if let Type::Path(tp) = &field.ty {
            vec_field = tp.path.segments[0].ident.to_string() == "Vec";
            if vec_field {
                break;
            }
        }
    }

    let output = quote! {
        impl VectorField for #name {
            fn has_vector_field() -> bool {
                #vec_field
            }
        }
    };
    TokenStream::from(output)
}

And with that, we can call has_vector_field() on any Struct with named fields as long as it derives the VectorField trait. Snippet below shows how Book makes use of it.

#[derive(VectorField)]
pub struct Book {
    title: String,
    publication_year: u32,
    authors: Vec<String>,
}

fn main() {
    println!("Do Books have vector fields? {}", Book::has_vector_field());
}

With metaprogramming we have gotten rid of code duplication and hard coding, freeing up headspace for actual business logic. Moreover this comes at no runtime performance penalty since the code is generated at compile time. The two examples above are just one of the many ways macros sprinkles magic. The need for code deduplication has opened doors for some very cool macros. Unlike C macros, Rust macros are hygienic in that they don't interfere with outer scope and local variables, hence preventing interesting compiler errors. This is indeed very Rusty.

That's so Rusty: Mutables

Imaculate — Sun, 06 Sep 2020 16:37:07 +0000

Given its unique nature, a lot of people are curious to know if Rust is functional.

Is it? Let's find out.
For a programming language to be considered strictly functional it has to adhere to functional paradigm where functions are first class citizens and shared state, mutable data, and side-effects are not allowed. For that reason, a pure function will always return the same result for the same arguments. Rust supports Object Oriented Programming, which means it allows shared state. That disqualifies it from being a purely functional language. However, it borrows some functional concepts such as immutability.

All Rust variables are immutable ... by default.
There are a few ways to mutate them as shown below.

1. Mut keyword

fn main()
{
  let mut vec = vec![1, 5, 10, 2, 15];
  println!("The vector is: {:?}", vec);
  vec = vec![16, 2, 7, 5];
  println!("The vector is: {:?}", vec);
}

Above, the vector vec is declared mutable with the mut keyword, making it possible to change its contents.

2. Shadowing

fn main()
{  
  let s = String::from("Hello from");
  let s = String::from("A shadow");
}

Although it looks like s has been mutated, it hasn't. The let keyword declares another variable that happens to have the same name as existing one. This declaration overwrites the previous variable, effectively shadowing it.

So, you can still mutate things but it takes some effort. Its natural to think that this is an unnecessary complication but it has its merits that probably outweigh the cons. With default immutability the compiler guarantees that when a value is declared, it won't change; it can be accessed from various contexts and won't be updated. This not only makes code easier to read and write but also eliminates classes of bugs such as race condition and undefined behavior. These bugs rise from the following conditions:

Two or more pointers access the same data at the same time.
At least one of the pointers is being used to write to the data.
Access to the data is not synchronized.

Since we established that all values have exactly one owner in previous post, what are the ways multiple pointers can access the same data? The answer is borrowing; accessing data without necessarily taking ownership. Borrowing provides references which are similar to C++ pointers.

References are especially useful when passing values to functions. If all functions took ownership of arguments, we'd have to return arguments from the function so that they can be reused in the original scope. The example below illustrates how cumbersome it would be to use a function that calculate the length of a vector.

fn main()
{
  let vec = vec![16, 2, 7, 5];
  let (len, vec) = calculate_length_take(vec);
  println!("The vector {:?} has length {}", vec, len);
}

fn calculate_length_take(v : Vec<i32>) -> (usize, Vec<i32>)
{
    println!("Calculating the length of {:?}", v);
    return (v.len(), v);
}

The function calculate_length() gets a whole lot better with references. We can create a reference that borrows from vec and pass it to the function. The function can access the data without moving ownership so the vector remains valid after the function call.

fn main()
{
  let vec = vec![16, 2, 7, 5];
  let v_ref = &vec;
  println!("The vector size is {:?}", calculate_length(v_ref));
  println!("The vector is still: {:?}", vec);
}

fn calculate_length(v : &Vec<i32>) -> usize
{
    println!("Calculating the length of {:?}", v);
    return v.len();
}

As you might expect, references are immutable by default. Mutable references are allowed as long as they point to mutable data. Mutable references are by definition the perfect recipe for race conditions and bugs. To prevent that, Rust compiler enforces that that at any given scope, there is either one mutable reference or any number of immutable references to the same data.

For illustration, Let's look at C++ and Rust program that essentially do the same thing: print the smallest number in array of integers. The C++ version below is totally valid, it compiles and runs without warning.

#include <iostream>
#include <algorithm>    
#include <vector>
using namespace std;

int smallest_element(int *p)
{
    int size = sizeof(p)/ sizeof(int);
    sort(p, p+size);
    return p[0];
}

int main () {  
  int arr[] = {16, 2, 7, 5};
  cout << "The first element is: " << arr[0] << endl;
  cout << "The smallest element is: " << smallest_element(arr) << endl;
  cout << "The first element is: " << arr[0] << endl;
}

The function smallest_element looks completely harmless, it simply returns smallest element in the array, but it does so with side-effect of sorting it. Reusing arr blindly will result incorrect behavior which will be hard to debug especially if the function is imported from external library.

Let's try translating that to Rust. The snippet below is as close as we can get, you can interactively run it on Rust Playground.

fn main()
{
  let vec = vec![16, 2, 7, 5];
  let vec_ref = &vec;
  println!("The first element is: {:?}", vec_ref[0]);
  let vec_ref_2 = &vec;
  println!("The smallest element is: {:?}", smallest_element(vec_ref_2));
  println!("The first element is: {:?}", vec_ref[0]);
}

fn smallest_element(v : &Vec<i32>) -> i32
{
    v.sort();
    return v[0];
}

Does it compile?

No, but the error message seems straight forward. The vector sort function changes the vector, so requires it to be mutable. Let's see what happens after changing the signature of smallest_element() to take mutable reference instead.

fn smallest_element(v : &mut Vec<i32>) -> i32
{
    v.sort();
    return v[0];
}

Is the compiler satisfied?

Not yet, but the error message is actionable. Since smallest_element() now takes a mutable reference, we can't pass immutable reference. Making vec_ref_2 mutable, should easily fix it.

 let vec_ref_2 = &mut vec;

Well, not quite.

Makes sense that we can't have mutable reference to immutable data. The error message recommendations have been pretty spot on so far, making vec mutable should get us closer to compilation.

  let mut vec = vec![16, 2, 7, 5];

Or not.

The problem is we are using an immutable reference to data after declaring mutable reference to it. This reference is invalid since the mutable ref may have changed the data; in this case, it did. Since vec_ref is unsafe to use, we can work around it by commenting out the last print statement.

// println!("The first element is: {:?}", vec_ref[0]);

Hooray! A working program finally 🍻.

Isn't it nice that we have caught a potentially nasty bug at compile time? Isn't it awesome that we can rely on error messages for guidance? Turns out default immutability is useful afterall. It may take some time to get used to but I'm starting to like the Rusty way.

That's so Rusty: Ownership

Imaculate — Tue, 01 Sep 2020 04:07:12 +0000

To some extent Rust is interesting because of unpopular design choices that achieve the same and sometimes better outcome than other languages. A good example is memory management, specifically heap memory management. Memory management can be achieved in two ways: explicitly or automatically.

Explicit memory management is supported in systems programming languages such as C and C++. With explicit management the programmer has more autonomy, but with great power comes great responsibility. Heap memory can be dynamically allocated and should be deallocated when no longer needed. The timing of deallocation matters; early deallocation may lead to using invalid references, late deallocation causes memory waste. The programmer should also be careful not to free memory more than once. If these requirements are not met, the following bugs can result.

1. Memory leak

Memory leak happens when memory is freed too late. Below is example where memory is not freed at all. new allocates memory on the heap and p points to address of the array. Ideally it should be freed when it is no longer needed but in this case it is not. It is eventually freed as the OS cleans up resources after program terminates. Performance cost would be evident if the pattern is repeated in long running programs or limited memory devices.

#include <iostream>
using namespace std;

int main()
{
    cout << "Before allocate" << endl;
    int * p = new int[10];
    // ... other program logic
    cout << "After allocate" << endl;
    // delete (p); p is not deleted
}

2. Dangling pointer

Dangling pointers are invalid references to memory that has already been released. In the snippet below, returns_pointer() returns pointer to local variable c. Since c is a stack-allocated local variable, following RAII idiom, it is released when it goes out of scope at the end of the function. The pointer returned is therefore invalid and causes a crash. Dangling pointers can also cause unpredictable behavior and security loopholes. These bugs are usually expensive to debug and fix.

// Example program
#include <iostream>
using namespace std;

char * returns_pointer()
{
   char c = 'a';
   return &c;
}

int main()
{
   char * cp = returns_pointer();
   cout << "Result: " << *cp << endl;
}

3. Memory corruption due to double free

Similar to dangling pointers, double free is harmful due to utilizing invalid references. The example below shows how it can cause unpredictability. Since the memory for B is allocated soon after A is released for the same size, B is assigned to same address as A. The second attempt at freeing A has no consequences since it effectively frees B. The program crashes on freeing B since it was already deallocated. Debugging this can be tricky.

#include <iostream>
using namespace std;

int main()
{
   int *A = new int[10];
   cout << "After delete A: " << A << endl;
   delete(A);
   int *B = new int[10];
   delete(A);
   cout << "After second delete A: " << A << endl;
   delete(B);
   cout << "After delete B: " << B << endl;
}

It can be very hard to detect these bugs even with due diligence, code reviews and countless tests, hence the need for automatic memory management.

Automatic memory management abstracts away memory business to let programmer focus on logic. In most languages this is done using a garbage collector. At runtime the garbage collector pauses program execution to clean up objects no longer in use. This eliminates the bugs demonstrated above but at a cost. The most significant cost is performance since program execution is paused periodically, moreover cleanup is non-deterministic and there is less opportunity to customize destructors. This is tolerable for high level languages like C# and Java.

The win win situation would be a middle ground that is both and safe and that is the case for Rust. Rust does automatic memory management without a garbage collector through Ownership.The simple yet powerful principles of ownership are:

All objects on the heap are owned by exactly one owning variable.
When the variable goes out of scope, the object will be dropped.
When objects are assigned to other variables, ownership is moved.

Below snippets illustrates it best.

fn main()
{
    let s1 = String::from("hello");
    let s2  = s1;
    // println!("s1 is: {}, s2 is: {}", s1, s2);

    let s3 = s2.clone();
    println!("s2 is: {}, s3 is: {}", s2, s3);

    print_if_not_empty(s3);
    // println!("is s3 still valid? {}",s3);

    let s4 = returns_string();
    println!("Is s4 valid? {}", s4);
}

fn print_if_not_empty(s : String)
{
    if !s.is_empty()
    {
        println!("String s: {}", s)
    }
}

fn returns_string() -> String
{
    String::from("hello world!")
}

This snippet runs correctly but it won't compile upon uncommenting the print statements. Here is why:

When s2 is assigned to s1, the value of s1 has effectively been moved to s2. s2 points to the heap address of s1 and s1 is no longer a valid variable. Accesing s1 like in the first print statement results in compile error.
s3 demonstrates how to make deep copies without having to move ownership. s3 is a clone of s2 but lives in a different heap location. Ownership is not moved so both s2 and s3 will be valid. Most languages make deep copies by default on assignment which can be expensive for large objects. Making this behavior non-default makes it a little harder to regress performance.
Similar to assignment, ownership is moved on passing objects to functions. When s3 is passed to print_if_not_empty(), its value is moved to local variable s, when s goes of out of scope at the end of the function it is dropped. As you might expect, printing s3 results in compiler error. If s3 is needed after the function call there are alternatives that are out of scope here otherwise, unnecessary clone was avoided here.
Same rules apply to return values from functions. Returning a value, moves its ownership out of local function scope, it is therefore not dropped at end of function. In the example above the string "hello world!" is moved to s4.

At the end of the program only s2 and s4 will be dropped; s1, s3 and s will have been moved. With the guarantee of exactly one owner, all values are deterministically cleaned as soon as they are no longer needed. This also comes with bonus of surfacing errors at compile time.

When I first learned about Ownership, I thought it was overkill. If function calls move objects then coding in Rust must be a lot complicated than necessary. I was also suspicious that no pointers were involved for memory management. Those were of course valid concerns that were addressed with references, a topic for another blogpost. Otherwise, it was clearer to me that Rust embodies safety, performance and error surfacing at every turn. What do you think?

DEV Community: Imaculate

Graph problems are not hard

Step 1. Learn

Step 2. Practice

How to actually prepare for Coding Interviews

1. Basics

2. Test

3. Refresh

What's hard about Dynamic Programming

Leetcode with ChatGPT

Diving into C++ Iterators

1. Input iterators

2. Output iterators

3. Forward iterators

4. Bidirectional iterators

5. Random access iterators

The tale of the triathlete and C++ performance

V1

V2: Bit Manipulation

V3: Branches

V3: Branches

V5: Constant vector references

V6: Array parameters

Arrays and pointers

Pointers

Arrays

Arrays can be pointers

1. Address-of operator

2. Subscript operator

3. String literals

4. Passing arrays to functions

5. Multidimensional array

5.1 Multi level pointers

5.1.1 Non-contiguous block

5.1.2 Contiguous block

5.2 Pointers to arrays

5.2.1 Pointer to inner array

5.2.2 Pointer to outer array

5.3 Single level pointer

Pointers are not arrays

That's so Rusty! Fearless concurrency

Rust Concurrency

1. Closures

2. Threads

1. Message passing

2. Shared state

1. Race conditions

2. Deadlock

3. Reference cycles

That's so Rusty!: Smart pointers

1. Simple linked list

A. Rust

B. C++

2. Shared linked list

A. Rust

Reference counts

Mutation

B. C++

3. Doubly linked list

A. Rust

B. C++

That's so Rusty: Metaprogramming

1. Variadic functions

2. has_vector_field() function for structs

That's so Rusty: Mutables

1. Mut keyword

2. Shadowing

That's so Rusty: Ownership

1. Memory leak

2. Dangling pointer

3. Memory corruption due to double free

2. `has_vector_field()` function for structs