Category: C/Cpp

How To: Argument Dependent Lookup in C++ and Templates

September 1st, 2024
Introduction

This post aims to provide some hidden quirks on using the keyword friend in Cpp templates. I will be referencing and unraveling some of the text from the book “C++ Templates: The Complete Guide”. It’s quite an amazing read. Recommend you to get your hands on it to level up your C++ game.
Before jumping into using friend function, I want to discuss about the Argument Dependent Lookup in C++ (ADL) with respect to templates and how compilers tackle some of the issues that templates poses.

What is ADL?

To get a sense of what Argument-Dependent Lookup is, let’s take a look at following snippet (paraphrased from the book)
```
// My Templated Max() function
template<typename T>
const T& Max(const T& a, const T& b)
{
	return a < b ? b : a;
}
// A class in new namespsace
namespace BigStuff
{
	class BigNum
	{
	public:
		BigNum(int pNum)
		: num(pNum)
		{}
		int num;
	};
	bool operator<(const BigNum& a, const BigNum& b)
	{
		return a.num < b.num;
	}
}
// Usage
int main()
{
	BigStuff::BigNum bignum1(10);
	BigStuff::BigNum bignum2(10);

	std::cout << "Namespace Test1: " << (Max(bignum1, bignum2)).num;
}
```
In the snippet above, I have a templated Max() function that takes two arguments of generic type.
Next, I declared a new namespace “BigStuff” with a class “BigNum”. This namespace also has an overridden ‘<‘ operator to handle comparison against objects of type “BigNum”
Finally, in main(), we create two objects of type BigStuff:BigNum and call our templated Max() on them.

Now, here’s the question. Going by the usual rules, how does the compiler know the existence of the overridden ‘<‘ operator for BigNum types?
If we go with simple Unqualified-Name Lookup, it only checks the current and subsequent parent namespaces and wouldn’t be able to find the required overridden operator. Here’s where ADL comes to save the day.

If the name is unqualified (not preceded by :: or any other name, e.g., Base::<name> ), the scope of arguments is also considered for the Lookup.
In our case, the scope of “BigNum”(class scope) is checked. Since there’s no operator found, it again searches for the enclosing namespace “BigStuff” which contains our overridden ‘<‘ operator. Since it found a matching name, no further scopes are examined and the lookup stops here.
That is reason we are auto-magically able to access something defined in a different scope from where the function is called.

Back to the Original Topic

Now that we have enough context at hand, lets examine another snippet and try to analyze the behavior of the code:
```
namespace Injection
{
	template<typename T>
	class FriendInj;

	void injFuncNoparam()
	{
		std::cout << "Inside friendInjection No Param function\n";
	}

	void injFuncExternal(const FriendInj<int>& t)
	{
		std::cout << "Inside friend injection function\n";
	}

	template<typename T>
	class FriendInj
	{
	public:
		friend void injFunc()
		{
			std::cout << "Internal injected functon. No Params\n";
		}
	
		friend void injFuncNoparam();
		friend void injFuncExternal(const FriendInj<T>&);
		friend void injFuncInternal(const FriendInj<T>&)
		{
			std::cout << "Inernal injected function\n";
		}

		int a = 5;
		int b = 10;
	};
}
```
Here’s what we have in the code above:
- injFuncNoparam in namespace Injection that has no parameters
- injFuncExternal in namespace Injection that takes Injection::FriendInj& as a parameter
- Templated class FriendInj with 3 friend functions.
  injFuncInternal is interesting as it’s declared and defined within the class, but it’s not a member function of FriendInj.
Now that we have established the components, lets try to use the friend functions. The code in the snippet below is written in global namespace.
```
//Usage
void CallFunc()
{
	const Injection::FriendInj<int> inj;

	//injFuncNoparam(); // Cannot find the defined-friend function. Throws an error
	injFuncInternal(inj); // Visible due to ADL
	injFuncExternal(inj); // Visible due to ADL

	//injFunc(); // Cannot find. So, throws an error
}

int main()
{
	CallFunc();
    return 0;
}
```
It is valid to call injFuncInternal or injFuncExternal (declared and defined in namespace Injection) by passing the proper object as an argument.
BUT, when trying to access injFuncNoparam (again, declared and defined in namespace Injection), the compiler throws an error.
In the first place, it’s strange that we are able to find injFuncInternal and injFuncInternal defined in a different scope, without any additional syntax.

This bizarre behavior is thanks to Argument-Dependent lookup.
The function names injFuncInternal and injFuncInternal are “Unqualified-Names” and they fulfill the requirements to perform ADL. Since we are passing object of type Injection::FriendInj, the scopes of class FriendInj and Injection are lookup to find the required functions.
We could remove friend keyword on injFuncInternal and still find the class, but removing friend on injFuncInternal will throw an error as it becomes a regular member function in this case.
Defining a friend function in a class injects that function in the class’s scope!! So, it’s valid to call it as follows:
Injection::FriendInj::injFuncInternal(t);

Conclusion

That is all I’ve got or this post. Please let me know if something not right and hope that this is informative.
Do visit again!
Constructing: Compile Time String Objects

July 18th, 2024
Introduction

This post is going to demo an approach of storing string into an object and creating compile time string objects which can be evaluated at compile time in C++.
The usual approach of creating a hard-coded string in C++ is to create it as a pointer or as an array, like so:
char str* = “Test String 1”;
char str[] = “Test String2”;
This approach doesn’t really encapsulate the string into an object, and I’d be really happy if there’s a way to put this information into an object.
I’m going to use template meta-programming to achieve what I’ve planned for. By the end, we would’ve created an object that can successfully store strings and perform simple operations like compare on them. All during compilation!!!

Step-By-Step

I’m going to call my class “QCTString” and it’s going to have non-type template argument: int.
I also want a helper function to quickly create this string.
```
template<int N>
    class QCTString
    {
    public:
        template<int ... INDICES>
        constexpr QCTString(const char* c, <INDICES>)
        : buffer { c[INDICES]... }
        {
        }
        const char* getBuffer() const { return buffer; }
    private:
        const char buffer[N] = { '\0' };
    };
    
    template<int SZ>
    constexpr const QCTString<SZ> createCTString(const char(&str)[SZ])
    {
        return QCTString<SZ>(str, <Pass Indices somehow>);
    }
```
Couple of things to note in the snippet above:
- Non-Type template parameter N represents the size of the string that’ll be stored.
- Member variable buffer is an array of size N, with all entries initialized to ‘\0’.
- The mysterious part in the code above is, how are we going to pass the indices? This is necessary to extract characters from the char* pointer we are passing to the constructor.
  This is what enables us to inject strings into the member variable “buffer”
- Helper function “createCTString” does lot of work for us. The only thing we need to figure out is a way to pass indices from 0 – N(last character being \0) so that that char array we’ve passed is completely read.
To store these indices, I’m creating a proxy object that we’ll need to generate, which will have the sequence of indices. The type of this object would have variadic non-type template arguments.
```
template<int ... ARGS>
struct ArgsPack
{};
```
Once our indices are generated into ARGS, we can modify the constructor of QCTString class as follows:
```
template<int ... ARGS>
constexpr QCTString(const char* c, const ArgsPack<ARGS...>)
: buffer { c[ARGS]... }
{}
```
With this, we have simplified the problem to generating the ArgsPack<ARGS…> object.
The following snippet demonstrates how to generate the ARGS…
```
template<int N, int ITR, int ... ARGS>
struct IndexExtractor
{
    typedef typename IndexExtractor<N - 1, ITR + 1, ARGS..., ITR>::res res;
};

template<int ITR, int ... ARGS>
struct IndexExtractor<0, ITR, ARGS...>
{
    typedef typename ArgsPack<ARGS...> res;
};

template<int N>
struct GetIndices
{
    typedef typename IndexExtractor<N, 0>::res res;
};
```
This seems complicated, but is actually pretty simple. Let’s dissect the code now.
- GetIndices is the function that will be our entry-point and which will give the final type from which we can create our ArgsPack object from.
  This initiates the type generation by initializing IndexExtractor with N and 0 and initial parameters, which represent the size left to process and current iteration respectively
- IndexExtractor keeps calling itself, each time adding value in ITR to ARGS…, which will be passed to the next iteration.
- We have a template specialization for IndexExtractor once N hits 0. Now, we simply return ArgsPack<ARGS…>.
  All the indices(0 – N) are nicely extracted and stored in ARGS
Conclusion

Final code would look something like this.
If you notice, I also added a compare function, which lets us compare strings at compile time!!!
How neat is that!!
```
/* A light-weight class that carries indices 0 - (Size - 1) individually*/
    template<int ... ARGS>
    struct ArgsPack
    {};
    
    template<int N, int ITR, int ... ARGS>
    struct IndexExtractor
    {
        typedef typename IndexExtractor<N - 1, ITR + 1, ARGS..., ITR>::res res;
    };

    template<int ITR, int ... ARGS>
    struct IndexExtractor<0, ITR, ARGS...>
    {
        typedef typename ArgsPack<ARGS...> res;
    };

    template<int N>
    struct GetIndices
    {
        typedef typename IndexExtractor<N, 0>::res res;
    };

    //TODO: Improve upon this
    /* Compile-Time string */
    template<int N>
    class QCTString
    {
    public:
        template<int ... ARGS>
        constexpr QCTString(const char* c, const ArgsPack<ARGS...>)
        : buffer { c[ARGS]... }
        {
        }

        const char* getBuffer() const { return buffer; }

        template<int M>
        constexpr bool compare(const QCTString<M>& other) const
        {
            if(N != M) return false;
            for(int i = 0; i < N; ++i)
            {
                if(buffer[i] != other.buffer[i])
                {
                    return false;
                }
            }
            return true;
        }
    private:
        const char buffer[N] = { '\0' };
    };
    
    /* Helper to create a compile-time object with given sequence of characters from input const array */
    /* Should ideally only use helpers to create QCTString Objects */
    template<int SZ>
    constexpr const QCTString<SZ> createCTString(const char(&str)[SZ])
    {
        return QCTString<SZ>(str, GetIndices<SZ>::res());
    }
```
This should provide you with a pretty neat abstraction for simple string operations you want to perform during compilation time.
One down-side however, is that larger and complicated strings in a large number would increase compilation time.

Hope this has been insightful.
Will see you in the next one!
Dive into Static Variable in C++: A Comprehensive Study

April 17th, 2024
Introduction

I’ve often found myself using static variables a lot during my journey as a programmer. They are a convenient tool to have under your belt if you want a variable that should be shared across multiple objects or functions and rarely changes. Of course, like anything in C++, there might be some pitfalls when using these static variables and functions. The purpose of this post is to take a deep-dive into the world of static variable in C++.
This post will be iterative. I’ll keep updating here whenever I come across anything interesting related to static variables and functions.
For code demonstration, I’ll be using VSCode and MSVC compiler.

Organization of static variables and functions in code

To make the best of this section, I suggest downloading the Code Listing file for the code snippet below. This is generated by MSVC by giving compiler flags “/FAcsu”.

Main_CodeListing Download

To make the best of this section, I suggest downloading the Code Listing file for the code snippet below. This is generated by MSVC by giving compiler flags “/FAcsu”.
The code for the code listing above is as follows:
```
#include<iostream>
// 1. Initialized static variable
static const int a = 100;
// 2. Un-Initialized static variable
static int unB;

// 3. Normal function with static variable
int* getFunctionStaticValRef()
{
    static int c = 300;
    return &c;
}

//4. Static function with static variable
static int* staticFunctionWithStaticVar()
{
    static int staticValInStaticFunc = 700;
    return &staticValInStaticFunc;
}

//5. Static function with normal variable
static int* staticFuncWithNormalVar()
{
    int normalVar = 800;
    return &normalVar; // This is just wrong! Please don't do this.
}


class ClassA
{
public:
    //6. 
    static int m_a;

    //7. 
    int* staticInNonStaticClassFunc()
    {
        static int unInitstaticVar;
        return &unInitstaticVar;
    }
    //8. 
    static int* staticInStaticClassFunc()
    {
        static int staticVar = 900;
        return &staticVar;
    }
};
int ClassA::m_a = 400;

template<typename T>
class TemplateClass
{
public:
    //9. 
    static int m_t_a;

    //10. 
    int* staticInNonStaticTemplateClassFunc()
    {
        static int staticVar = 1000;
        return &staticVar;
    }
    //11. 
    static int* staticInStaticTemplateClassFunc()
    {
        static int staticVar = 1100;
        return &staticVar;
    }
};
int TemplateClass<int>::m_t_a = 1100;

int main()
{
    //Static tests
    const int* refA = &a;
    int* refB = &unB;

    int* heapAlloc1 = new int(10);
    int* heapAlloc2 = new int(10);

    int* refC = getFunctionStaticValRef();
    
    int* heapAlloc3 = new int(10);
    int* heapAlloc4 = new int(10);
    
    const int* ref_staticValInStaticFunc = staticFunctionWithStaticVar();
    
    const int* ref_staticWithNormalVar = staticFuncWithNormalVar();

    ClassA* heapObj = new ClassA();
    int* ref_mA = &ClassA::m_a;

    const int* ref_staticInNonStaticClassFunc = heapObj->staticInNonStaticClassFunc();
    const int* ref_staticInStaticClassFunc = ClassA::staticInStaticClassFunc();

    TemplateClass<int>* heapObj2 = new TemplateClass<int>();
    int* ref_t_mA = &TemplateClass<int>::m_t_a;

    const int* ref_t_staticInNonStaticClassFunc = heapObj2->staticInNonStaticTemplateClassFunc();
    const int* ref_t_staticInStaticClassFunc = TemplateClass<int>::staticInStaticTemplateClassFunc();

    return 0;
}
```
Let’s first establish a couple of things. Static variables are basically global variables and have their memory allocated during their declaration.
- An Un-Initialized static variable is created in the DATA_SEGMENT of the assembly code.
- An Initialized static variable is created in the BSS_SEGMENT of the assembly code.
- Since program stack grows from lower to higher memory address, static variables ALWAYS occupy a lower memory address than any heap allocated variable. For a quick overview of the Data segment, please refer to this wiki post
Let’s break apart the code snippet and how the code is arranged for static functions and variables. To make the best of this, refer to the CodeList file provided and check how the code is arranged:
1. This is an initialized static variable and occupies DATA segment. DATA segment is usually setup before the CODE/TEXT segment starts.
2. An un-initialized static variable and this occupies BSS segment.
3. Static variable in a normal function also gets created in the DATA segment if it’s initialized or in BSS if it’s uninitialized.
4. This is identical to 3. Since the function is global, marking it as static doesn’t really make much of a difference.
5. Returning address of a temporary variable is always bad. Even if that’s inside a static function. NEVER DO THIS!
6. Now, this one’s a static variable inside a class. Now, if you see the code listing file, you can notice that this sits right in the DATA segment and basically has a global scope (with the class name and any additional namespaces considered, of course).
7. This one’s a static variable inside a non-static member function. The variable still occupies the DATA segment as expected.
8. We now have a static variable inside a static member function.
  The difference between static and normal member functions is that, normal member functions must obtain the pointer to the object that’s calling it. While, static functions doesn’t have to do that.
  In the code lists file, we can see that the normal member function has these additional instructions to store the object that’s calling the function:
  push ecx
  mov DWORD PTR _this$[ebp], ecx
9. This one’s a static variable inside the template class. Now, I have not initialized this variable, just defined it so that the linker doesn’t complain. As expected, this variable occupies the BSS segment.
10. Behavior is identical to 7.
11. Behavior is identical to 8.
Declaring and Defining A Static variable

Still working on this section. Please check back later.

That is all for this post and I hope this has been useful.
Please do visit again 🙂
How To: Parse Bits From Stream In C++

October 20th, 2023
Introduction

When parsing data from a file, you might have some variables whose values doesn’t span the entire region of a byte. For example, you could have a sequence of flags all packed into a stream. There might be an unsigned integer that might just be 10 bits long. Let’s see how we can parse bits from stream.

I’ve been working on learning about h.264 codec and the data is very tightly packed when trying to decode. There are unsigned integers that are defined to occupy as few as 3 bits. Well, it’s an involved learning process and we come out just slightly wiser than yesterday going through it.

To read the byte stream as bits, we first calculate the number of bits in the stream (numBytes * 8) and use a variable to keep track of current position in the bit stream. Let’s name this variable as “m_bitPos“.
To work with bit stream, we need to be able to retrieve the value of each of the bits in the byte. This helper function gives us a mask for the bit index requested, which we can apply on the bit stream to retrieve it’s value.
```
const char myByte = 'c';
inline uint8_t getMaskForBit(uint8_t bit)
{
    return 1 << (7 - bit); 
}
Usage: uint8_t res = myByte & getMaskForBit(0..7); //This masks the respective bit requested and retrieves the value of the corresponding bit of the byte in our buffer.
```
Parsing IT!

To parse a bit, we need to know which byte it belongs to. We can find the byte our current bit belongs to simply dividing current bit position by 8:
currentByte = m_bitPos >> 3;

Here, I’m assuming the most significant bit always appears first in out bit stream. The process to retrieve a value by reading bits is as follows:
– Loop over the requested number of bits
– Get the byte that represents current bit position.
– Get the mask for current bit position. The purpose of this mask to check whether the corresponding bit is set in current byte.
– Left shift the current result to make room for appending the result of our test.
– Perform AND op on the byte to check if the corresponding bit is set. If it’s set, we add 1 to the result.

As we are doing a left shift on every iteration of the loop, all the values fall in place by the time loop terminates and the value stored in the bits is neatly embedded into uint32_t.
```
uint32_t readBits(uint8_t n)
    {
        uint32_t res = 0;
        while(n != 0)
        {
            uint32_t currentByte = (uint32_t)(bitPos >> 3);
            uint8_t mask = getMaskForBit(bitPos % 8);
            res <<= 1;
            res += (buffer[currentByte] & mask) ? 1 : 0;
            --n; ++bitPos;
        }
        return res;
    }
```
Wrapping it up

This one’s a quickie and I feel like it’s a good tool to have at your disposal, so I decided to write about it. As always, hope this helped someone! 🙂
A Take on how to perform Matrix Multiplication with Intrinsics

June 17th, 2023
Introduction

When working on a performance critical application, you want to do as much as possible in as few CPU clock cycles as possible. Intrinsics are platform specific features that compiler can replace with a single assembly instruction most of the time.
In this blog, I’m gonna walk through a couple of ways to perform matrix multiplication with intrinsics(specifically, Intel’s SIMD SSE instrinsics).
Let’s work with the following 4×4 matrix. Each of it’s rows(or columns, if we are implementing a column major matrix) can snugly fit in a single MMX register. The traditional approach of computing matrix multiplication is to multiply Row ‘i’ with Column ‘j’ to get element ‘E_ij‘.

This is basically implementing a dot product on i^th row and j^th column. This approach is implemented using intrinsics by first implementing a dot product and then using that when multiplying elements of matrix. Here’s how this can be implementation.
In the following implementations, “pack” is just a variable of type “__m128” packed within a union.
```
float dot_vf(const QVec4& a, const QVec3& b)
    {
        __m128 tmp = _mm_mul_ps(a.pack, b.pack); //(x1*x2, y1*y2, z1*z2, ?*?)
        __m128 shuff = _mm_shuffle_ps(tmp, tmp, _MM_SHUFFLE(0, 2, 0, 1)); //(y1*y2, x1*x2, z1*z2, ?*?)

        tmp = _mm_add_ps(tmp, shuff); //(x1*x2 + y1*y2, x1*x2+x1*x2, z1*z2+z1*z2, ?);
        shuff = _mm_shuffle_ps(shuff, shuff, _MM_SHUFFLE(0, 0, 0, 2)); //(z1*z2, ?*?, x1*x2, y1*y2)
        return _mm_cvtss_f32(_mm_add_ps(shuff, tmp)); //(x1*x2 + y1*y2 + z1*z2, ?, ? ,?)
    }

QMat4x4 mul1(const QMat4x4& a, const QMat4x4& b)
    {
        QMat4x4 transposed(b);
        transposed.transpose();
        return QMat4x4(
            QVec4( dot_vf(a.col0, transposed.col0), dot_vf(a.col0, transposed.col1), 
            dot_vf(a.col1, transposed.col2),dot_vf(a.col0, transposed.col3)),

            QVec4( dot_vf(a.col1, transposed.col0), dot_vf(a.col1, transposed.col1), 
            dot_vf(a.col1, transposed.col2),dot_vf(a.col1, transposed.col3)),

            QVec4( dot_vf(a.col2, transposed.col0), dot_vf(a.col2, transposed.col1), 
            dot_vf(a.col2, transposed.col2),dot_vf(a.col2, transposed.col3)),

            QVec4( dot_vf(a.col3, transposed.col0), dot_vf(a.col3, transposed.col1), 
            dot_vf(a.col3, transposed.col2),dot_vf(a.col3, transposed.col3))
        );
    }
```
Multiplication with a row view

The above implementation works perfectly, but dot product does a horizontal add and we are not really utilizing parallel hardware completely with subsequent calls to _mm_add_ps in dot product.
An alternate approach to multiplying matrices is by taking a closer look at how elements in the multiplication are distributed in the resultant matrix. Here’s a great resource that could help you solidify the intuition behind matrix multiplication.
The idea behind the row view of matrix multiplication is that each row in matrix “B” is a linear combination of rows of matrix B, with weights from matrix A.

Let’s try to compute Row-1 as an example:
1. All elements of Row-1 of Matrix B must be multiplied by a₁₁.
2. All elements of Row-2 of Matrix B must be multiplied by a₁₂.
3. All elements of Row-3 of Matrix B must be multiplied by a₁₃.
4. All elements of Row-4 of Matrix B must be multiplied by a₁₄.
The results of 1, 2, 3, 4 are added to get Row-1 of resultant matrix.

Here’s how this can be implemented using intrinsics.
```
QMat4x4 out;
        
//Col 0
__m128 T0 = _mm_mul_ps(b.pack[0], _mm_set_ps1(a.row0.x));
__m128 T1 = _mm_mul_ps(b.pack[1], _mm_set_ps1(a.row0.y));
out.pack[0] = _mm_add_ps(T0, T1);
T0 = _mm_mul_ps(b.pack[2], _mm_set_ps1(a.row0.z));
out.pack[0] = _mm_add_ps(out.pack[0], T0);
T0 = _mm_mul_ps(b.pack[3], _mm_set_ps1(a.row0.w));
out.pack[0] = _mm_add_ps(out.pack[0], T0);
```
Multiplication with a Column view

What if you have a column-major matrix? Would it be possible to implement a similar logic?
Of course, yes! You just have to approach the problem from the opposite direction.
In this case, each element of column of matrix B must be multiplied with a respective column in matrix A.

Let’s try to compute Column-1 as an example:
1. All elements of Column-1 of Matrix A must be multiplied by b₁₁.
2. All elements of Column-2 of Matrix A must be multiplied by b₂₁.
3. All elements of Column-3 of Matrix A must be multiplied by b₃₁.
4. All elements of Column-4 of Matrix A must be multiplied by b₄₁.
The results of 1, 2, 3, 4 are added to get Column-1 of resultant matrix.

Here’s how this can be implemented using intrinsics.
```
QMat3x3 out;

//Col 0
__m128 T0 = _mm_mul_ps(a.pack[0], _mm_set_ps1(b.col0.x));
__m128 T1 = _mm_mul_ps(a.pack[1], _mm_set_ps1(b.col0.y));
out.pack[0] = _mm_add_ps(T0, T1);
T0 = _mm_mul_ps(a.pack[2], _mm_set_ps1(b.col0.z));
out.pack[0] = _mm_add_ps(out.pack[0], T0);
T0 = _mm_mul_ps(a.pack[3], _mm_set_ps1(b.col0.w));
out.pack[0] = _mm_add_ps(out.pack[0], T0);

//Similar logic for the rest of the rows
```
That is all for this post.
Hope this taught you folks something 🙂
How To Bind Lambda To Function Pointer

April 28th, 2023
If you’ve ever tried to implement your own custom delegates, this amazing article must’ve crossed your path. If it didn’t, I can’t recommend enough that you read it’s contents entirely. It provides an extremely detailed and well structured information about member function pointers.
What the article seems to be missing is the support for lambda expressions. It’s understandable as Lambdas weren’t introduced into C++ when the article was written.
Therefore, in this article, I try to extend on the “Member Function Pointers and the Fastest Possible C++ Delegates” by Don Clugston and try to bind lambda to function pointer.

The basis of the implementation is to be able to bind/store a member function pointer as a variable of a generic member function pointer as follows:
```
class GenericClass{};

typedef void(GenericClass::*GenericMemberFuncType)(); //We want to be able to convert our lambda invocation to type &amp;amp;quot;GenericMemberFuncType&amp;amp;quot;
```
To achieve that, there must first be a way to bind invocation of lambda to a pointer of it’s own type. It’s pretty straight forward for Lambdas with no captured parameters and a little convoluted for Lambdas with capture parameters.

lambda with no Capture

It’s pretty straight forward to bind a lambda with no parameters to a function pointer. You can treat lambda as any other global or static function and assign it to a function pointer and invoke it.
```
auto noCapture =
    [](int res) -> float
    {
        std::cout << "No capture lambda called with " << res << "\n";
        return 99.9f;
    };

typedef float(*NormalFuncType)(int);
NormalFuncType noCaptureLambdaPtr = noCapture; //----------- (1)
float res = noCaptureLambdaPtr(100); //----------- (2)
std::cout << "No capture lambda returned: " << res << "\n";
```
When we break at (1) and go into disassembler, there’s a curious “explicit conversion” happening under the hood. The next instruction then stores the contents of register eax into [noCaptureLambdaPtr]. If we go into this call by pressing F11 in disassembler, we see these sets of instructions.

It has regular stack push and pop instructions, but the instruction that’s highlighted is vital to have a lambda with no captures passable to a regular function pointer. It pushed a “lambda_invoker” into eax, which is eventually stored inside [noCaptureLambdaPtr]. So, calling this lambda_invoker should call out lambda.
Let’s try and make sense of this by emulating the same behavior in pure C++.
```
struct NoCaptureLambdaRep
{
    static void Invoker() //....(@)
    {
        std::cout << "Called\n";    
    }

    typedef void(*VoidType)();
    operator VoidType() //.... (#) Explicit conversion to void(*)()
    {
        return &Invoker;
    }
};

int main()
{
    NoCaptureLambdaRep lambdaRep;
    typedef void(*TestFunc)();
    TestFunc testFunc = lambdaRep;
    testFunc();
...
}
```
“NoCaptureLambdaRep” is analogous to the dynamic class generated by compiler for our lambda and “lambdaRep” is the lambda object that we are going to be working with.
In out first disassembly view, there’s an explicit conversion to a function pointer that’s allowing us to bind the returned value to a generic function pointer. (#) should emulate that behavior.
Next, the address of a Lambda_Invoker is stored inside eax, which is eventually passed to us. This is emulated as a static function at (@). The implementation logic of lambda would reside inside this function. Since it’s a static function, it can be safely converted to VoidType. Finally, calling “testFunc” will most definitely call NoCaptureLambdaRep::Invoker.

lambda with Capture

One thing is very pristine from the previous section. Lambdas are glorified objects generated by compilers. So, what happens when lambda has a capture list? Simple, they become members of our lambda class through shallow copy.
Since our Lambda now has member variables and we might be using them inside implementation logic, there’s would be no way to convert lambda’s invocation into a generic function pointer. Now more than ever, we must treat lambda the way it’s supposed to be. Like an object.

The only option in our arsenal to bind lambda to an external pointer is therefore, to bind to operator() (a member function) of type lambda to an external pointer of same type. This is how it could be implemented.
```
auto capture =
    [p, q, r](int res) -> float
    {
        std::cout << "Capture lambda called with " << res << "\n";
        std::cout << "Captured values: " << p << " " << q << " " << r << "\n";
        return 101.1f;
    };

    typedef decltype(capture) CaptureLambdaType;
    typedef float(CaptureLambdaType::*CaptureFuncType)(int) const;
    CaptureFuncType captureLambda = &CaptureLambdaType::operator();

    res = (capture.*captureLambda)(999);
    std::cout << "Capture lambda returned: " << res << "\n";
```
When we break at (1) and look at disassembly, we see that it’s invoking the constructor of lambda and no clever type conversions take place and does exactly what we ask it to.

The same method of binding to a member function ptr of type lambda can also be used to bind lambdas with no captures.
This therefore, thins the line quite a lot between regular objects and lambdas. Therefore, with a few additional lines of code, we can easily extend Don Clugston’s article to include lambdas too.

One sneaky thing that crept up on me when implementing this was the realization that lambdas are designed to be short lived. So, when create lambda as a temporary inside function parameter, the original object could be destroyed. This makes all the original capture parameter data invalid.
```
auto del = QFastDelegate1<void, int>();
    del.BindLambda(
        [outerValue](int param)
        {    
            std::cout << outerValue << " Called Delegate " << param << "\n"; 
        }
    );
```
We must therefore rely on heaps if we want to properly support lambda. Lambda is then copied to a structure maintained by our delegate. If delegate is copied, the data holding lambda should be deep copied. When delegate is destroyed, care must be taken to properly free the data if the callback stored is a Lambda!!
This is a slight overhead, but quite worth the trouble.

Well, that is all folks! Hope you got to learn something.
C++ Memory Model and Memory order Semantics

April 2nd, 2023
Introduction

From C++11, Memory Model and Memory order semantics were introduced that makes it possible to run concurrent code using features of the standard library. This memory model is built on amalgamation of structural and concurrent aspects.
Structural aspects deal with how the data is laid out in memory and concurrent aspects of memory model specifies the aspects that are important for concurrent code, especially when performing low-level atomic operations.
- As per this new model, all data can be viewed as objects(even the primitive built-in types). An object can be stored in one or more memory locations.
- Primitive types of any size occupy exactly one memory location.
- Adjacent bit-fields are part of the same memory location.
To get a sense of how troublesome things can get, let’s study a relatively simple piece of code that uses relaxed ordering to store and load 2 atomic variables in 2 functions that are run on separate threads.
```
void funcA()
{
	flag2.store(true, std::memory_order_relaxed);//(A)Thread-1
	flag1.store(true, std::memory_order_relaxed);//(B)Thread-1
}
void funcB()
{
	while(!flag1.load(std::memory_order_relaxed));//(C)Thread-2

	bool res = flag2.load(std::memory_order_relaxed);//(D)Thread-2
	assert(res);
}
```
In the snippet above, funcB waits for flag1 to be set which is done in funcA that’s running in thread-1. Common sense dictates that since flag2 will also be set since it is ordered before flag1 in funcA and the assert in funcB will never get fired. But, Alas! that intuitive behaviour is not guaranteed by the memory model and the assertion could theoretically fire in a multi-core system!
To understand why this happens, let’s first try and get familiar with some of the terms you come across when working with synchronisation and atomics.

Definitions

Inter-Thread Synchronization

This is used to determine a synchronisation relationship between two or more threads. In the snippet above, funcB does not guarantee inter-thread synchronisation with funcA due to relaxed ordering of memory and instructions.

happens-before

This is as intuitive as it sounds in single threaded applications, but not so much in multi-threaded applications. It models the behaviour of instruction that happened before the current instruction. In funcA, (A) happens before (B) and (C) happens before (D) on their respective threads. Order across threads is not guaranteed without explicit synchronisation.

Synchronizes-with

This is used to establish a synchronisation relationship between a pair of threads.
Dependency-Ordered before

Consider this piece of code:

atomic<int> result = 0; void func() { int a = 10;(A) int b = a + 10;(B) result.store(b);(C) }

Here, on a single threaded application B depends on C and C depends on A. Therefore C depends on A. Therefore C has a dependency-ordered before relationship with B and A. The concept is similar when extending to multiple threads and we will study it a little closer when talking about various memory orderings.
Acquire

This is an atomic load operation with memory ordering stronger than memory_order_acquire.

Release

This is an atomic store operation with memory ordering stronger than memory_order_release.

Consume

This is an atomic store operation with memory ordering stronger than memory_order_consume.
Memory Ordering

The standard supplies us with following options for ordering memory. These hint compiler at the availability for optimisation and define memory can be re-ordered by the processors in the operating system.
- memory_order_seq_cst
- memory_order_relaxed
- memory_order_acquire
- memory_order_release
- memory_order_acq_rel
- memory_order_consume
Sequentially consistent ordering

This is represented by memory_order_seq_cst. This is the easiest ordering operation to reason about. Every thread has a sequentially consistent view of data and all modifications done to an atomic variable are observed in the same order.
In the snippet below, funcB on Thread-2 waits for flag1 from Thread-1. Because we mentioned sequentially consistent ordering, it is guaranteed that flag2’s store operation synchronises with (C) and by the time control reaches (D) in Thread-2, the thread’s storage would be updated to reflect flag2 correctly and the assert will never get triggered. Therefore, funcB Inter-Thread synchronises with funcA and following identities can be established:
(A) happens-before (B)
(B) inter-thread synchronises happens-before (C)
(C) happens-before (D)
(A) inter-thread happens-before (D) [By Transitive property]
Note that if a different thread is modifying A, depending on the scheduling, the value of A may take on this latest value. All the synchronisation guarantees is that no value older than store at (A) will be retrieved.
```
void funcA()
{
	flag2.store(true, std::memory_order_seq_cst);//(A)Thread-1
	flag1.store(true, std::memory_order_seq_cst);//(B)Thread-1
}
void funcB()
{
	while(!flag1.load(std::memory_order_seq_cst));//(C)Thread-2

	bool res = flag2.load(std::memory_order_seq_cst);//(D)Thread-2
	assert(res);
}
```
Relaxed Ordering

This is represented by memory_order_relaxed. Relaxed ordering is the least restrictive among all and allows for maximum optimisation. The initial code snippet uses a relaxed ordering and the standard makes no guarantee that the assertion wont trigger. Relaxed ordering lets compiler re-order instructions and lets the processor re-order memory as it sees fit and there’s no inter-thread synchronisation happening here at all! But, atomics are still guaranteed to execute without any data races though.
Having said that, the initial snippet runs perfectly fine on an x86 machines. Intel x86 machines’ store instruction supports synchronisation at the lowest level and guarantees that reads and writes are not reordered with older reads. Here what the developer’s manual says and if you want to read more, you can access it here.

Acquire-Release ordering

This ordering allows us to achieve some synchronisation using memory_order_acquire, memory_order_release and memory_order_acq_rel. This still doesn’t guarantee the total order of operations, but gives us ability to synchronise acquire(atomic load) and release(atomic store) operations. Atomic operations such as fetch_add are read-modify-write operations and they can be acquire, release or both(memory_order_acq_rel).
In the snippet below, store(B) is tagged as a release operation and load(C) is marked as a release operation. Therefore, the store(B) a inter-thread synchronises with store(C).
Following identities can be established:
(A) happens-before (B)
(B) inter-thread synchronises happens-before (C)
(C) happens-before (D)
(A) inter-thread happens-before (D) [By Transitive property]
This is similar to what we get in sequential ordering, but acquire-release is not as stringent as sequentially consistent ordering and lets compiler and processor perform any optimisations it’s allowed to.
It’s also important to keep in mind that any atomic operations after (B), atomic writes and loads on data that didn’t participate in happens-before relationship after (C) are not synchronised and are not guaranteed to be ordered.
```
void funcA()
{
	flag2.store(true, std::memory_order_relaxed);//(A)Thread-1
	flag1.store(true, std::memory_order_release);//(B)Thread-1
}
void funcB()
{
	while(!flag1.load(std::memory_order_acquire));//(C)Thread-2

	bool res = flag2.load(std::memory_order_relaxed);//(D)Thread-2
	assert(res);
}
```
Finally, memory_order_acq_rel have both acquire and release semantics. A store operation that occurs before atomic with memory_order_acq_rel can inter-thread synchronise with store. And, a subsequent load operation can inter-thread synchronise with an atomic that has memory_order_acq_rel.

Dependency Ordering

Dependency ordering allows us to establish a “dependency-ordered before” relationship to inter-thread synchronisation. This is achieved using memory_order_consume. This is a great way to ensure that any data dependent on the atomic operation is synchronised.
Following identities can be established here:
(A) happens-before (B) happens-before (C)
(D) happens-before (E) happens-before (F)
(C) depends-on (B)
(C) is dependency-ordered before and inter-thread synchronises with (D)
Therefore, (B) is dependency-ordered before and inter-thread synchronises with (D)

From these identities, it clear that value of ‘n’ will be synchronised across threads if the store operation is observed by consume. Therefore, (E) will never fire.
On the other hand, there’s no dependency relationship with the atomic operation (C) and (A). Therefore, it’s possible that (F) could trigger!
```
atomic<int> counter = 0;
int flag = false;
int n = 0;
void funcA()
{
    flag = true; //(A) Thread-1
    n = 10; //(B) Thread-1
	counter.store(n, std::memory_order_release);//(C)Thread-1
}
void funcB()
{
	while(!counter.load(std::memory_order_consume));//(D)Thread-2
    assert(n != 0);//(E)Thread-2
    assert(flag);//(F)Thread-2 /*This can trigger*/ 
}
```
Well, that’s it folks! Do leave a comment if there are any corrections, suggestions or improvements
WTF are Synchronization Primitives

March 21st, 2023
Introduction

When writing a concurrent code, there’s bound to be some data that will be shared across multiple threads. In an ideal world, every thread has a reliable and consistent view of data and the order in which operations are requested by application is maintained across threads. BUT, we live in a world that leans towards chaos and if proper care is not taken when writing a multi-threaded application, we might be on an express-way to undefined behavior, memory corruption and undefined code. This is where synchronization primitives comes in.

All the bad quirks of a concurrent code boils down to one single thing: “Writing to a memory location that’s accessible across multiple threads when we are not supposed to”.
If we think about it, if the data does not change, there can be any number of threads reading the shared data with no consequence. We don’t need any synchronization mechanisms in this case and a data race in this scenario would be impossible.
Try running the code below and see what abomination you get!!
```
#include <iostream>
#include <thread>
#include <string>

std::string printableStr;

void AddToString(std::string str)
{
    for(int i = 0; i < str.length(); i++)
    {
        printableStr.append(1, str.at(i));
    }
}

int main()
{
    std::thread thread1(&AddToString, "Hello ");
    std::thread thread2(&AddToString, "Concurrent World. ");
    std::thread thread3(&AddToString, "It's all the rage now!!!");

    thread1.join();
    thread2.join();
    thread3.join();
    std::cout << "Result: " << printableStr << "\n";
}
```
In the code above, there’s no guarantee that the order of the words, letters or even the validity of the data is maintained.
Therefore, care needs to be taken when we are modifying shared data so that it doesn’t conflict with the threads that are currently reading/writing data. In either case, we need some mechanisms to make one thread wait while the thread that’s modifying the shared data completes its work.
Let’s study 3 such low-level primitives that helps us achieve synchronization.

Mutex:

Named aptly as it provides mutually-exclusive access to a shared resource across multiple threads. The concept of a mutex is quite simple. The thread that initially reaches a shared resource locks the mutex, thereby suggesting that the current thread is using the shared resource and any other thread that tries to access this resource should wait until the current thread completes it’s processing and unlocks the mutex.

In the example below, using a mutex ensures that the order of letters in the supplied string is maintained and also ensures the validity of data, i.e., no data corruption takes place. BUT, there’s no guarantee to the order of words!! There’s no guarantee that “thread1” runs first, “thread2” next and “thread3” at the end. OS might decide “thread2” or “thread3” should run first!!! To ensure a proper sentence is formed, we need some way to make the main thread wait until the first thread runs, then wait for the second and third. We can use conditional-variables to achieve this.
For now, try running this code and see what happens!
```
#include <iostream>
#include <thread>
#include <string>
#include <mutex>

std::string printableStr;
std::mutex globalMtx;

void AddToStringMtx(std::string str)
{
    globalMtx.lock();
    for(size_t i = 0; i < str.length(); i++)
    {
        printableStr.append(1, str.at(i));
    }
    globalMtx.unlock();
}

int main()
{   
    std::thread thread1(&AddToStringMtx, "Hello ");
    std::thread thread2(&AddToStringMtx, "Concurrent World. ");
    std::thread thread3(&AddToStringMtx, "It's all the rage now!!!");

    thread1.join();
    thread2.join();
    thread3.join();
    
    std::cout << "Result: " << printableStr << "\n";
}
```
Conditional:

Conditional variables are composite types that work with the help of a mutex and a queue/stack to keep track of threads that are waiting. Conditionals are a signaling mechanism that enables us to resume the execution of a thread from a different thread, whereas mutex doesn’t support unlocking from a different thread.
A conditional variable requires a locked mutex to be passed, which it then unlocks and suspends the thread. When signaled, the mutex is locked again and the thread resumes it’s execution.

In the example below, multiple threads wait on “globalMtx” at the end of their lifetime. When all threads are resumed using “notifyAll”, all the waiting threads fight to execute the instructions that follow. If the conditional variable doesn’t lock the mutex on resumption of thread, it results in undefined behavior. Since the conditional variable locks “globalMtx” when thread resumes, the initial thread that gains control executes the instructions. If any other thread tries to lock mutex, it enters a waiting state as “globalMtx” is already locked. Execution proceeds when the current thread executing unlocks “globalMtx”.
Here’s a sample implementation of a conditional variable and its usage using a Mutex, Stack and windows native functions using same example as before and printing to output in the order expected.
```
#include <iostream>
#include <thread>
#include <string>
#include <mutex>
#include <Windows.h>
#include <stack>

class Conditional
{
public:
    Conditional(){}
    void wait(std::mutex& mx)
    {
        m_mutex.lock();
        HANDLE handle = OpenThread(THREAD_ALL_ACCESS, FALSE, GetCurrentThreadId());
        m_threadStack.push(handle);
        m_mutex.unlock();

        //Release the mutex, go into waiting state and then reaquire lock
        mx.unlock();
        SuspendThread(handle);
        mx.lock();
    }
    void signal()
    {   
        m_mutex.lock();
        HANDLE handle = m_threadStack.top();
        DWORD res = ResumeThread(handle);
        m_threadStack.pop();
        m_mutex.unlock();
    }
    void notifyAll()
    {
        while (!m_threadStack.empty())
        {
            signal();
        }
    }
private:
    std::mutex m_mutex; //Protects thread
    std::stack<HANDLE> m_threadStack;
};

std::string printableStr;
std::mutex globalMtx;
Conditional c;

void AddToString(std::string str)
{
    Sleep(10);
    for(size_t i = 0; i < str.length(); i++)
    {
        printableStr.append(1, str.at(i));
    }
    c.signal(); //Signals main thread

    globalMtx.lock();
    c.wait(globalMtx);   //This thread waits at the very end until signaled
    std::cout << "Thread " << GetCurrentThreadId() << " Finished\n";
    globalMtx.unlock();
}
int main()
{
    std::mutex mtx;

    mtx.lock();

    std::thread thread1(&AddToString, "Hello ");
    c.wait(mtx);
    std::thread thread2(&AddToString, "Concurrent World. ");
    c.wait(mtx);
    std::thread thread3(&AddToString, "It's all the rage now!!!");
    c.wait(mtx);
    
    mtx.unlock();

    std::cout << "Result: " << printableStr << "\n";

    mtx.lock();
    c.notifyAll();
    mtx.unlock();
    
    thread1.join();
    thread2.join();
    thread3.join();
}
```
Semaphore:

A semaphore is a specialized conditional that has an additional “count” parameter that keeps track of how many threads can access a resource simultaneously. Like Conditional-Variables, Semaphore is also a signaling mechanism, which implies that blocked/waiting threads must be resumed/signaled from different threads.
From C++ 20, standard library comes with “std::binary_semaphore” and “std::counting_semaphore” under “#include <semaphore>.

A binary semaphore only allows a single thread to access a resource, while a counting semaphore allows a user specified number of threads to run simultaneously.
For some of the important differences between semaphore and a conditional variable, you can refer: https://www.geeksforgeeks.org/difference-between-semaphore-and-condition-variable/
Expressions Taxonomy(X, L, R, GL, PR – Values): WTF are these

March 5th, 2023
Definition:

Lets first get a one line introduction and study each of the different categories of expressions taxonomy intimately in the subsequent sections.

L-Value

It’s traditionally called so because it usually appears on the left side of an assignment expression. It’s usually associated with a particular object.

R-Value

It’s traditionally called so because it usually appears on the right side of an assignment expression. It’s either a temporary(X-Value) or pure(R-Value) and it’s not associated with any object.

X-Value

It’s called an eXpiring value. It refers to an object nearing the end of its lifetime.X-Values are what makes move-semantics possible.

GL-Value

GL-Value is either L-Value or an X-Value. It’s called “generalised L-Value”.

PR-Value

PR-Value is called “pure” R-Value. It’s an R-Value that is not an X-Value. For example, if you call a function which is not a “reference”, it’s a pure R-Value.

Every value of an expression in C/C++ falls into one of these categories. This

Making sense of these
L-Value

Let’s go with the simplest one first, the L-Value! ANY “named” expression is an L-Value. In the following code snippet, all of the variables declared are L-Values.

struct Obj { int one = 100; float two = 20.f; }; Obj&& funcReturningRValueRef() { return std::move(Obj()); } //All of the implementations below cover to an L-Value. Obj lValue; Obj& lValueToo = lValue; Obj&& alsoLValue = std::move(lValue); Obj&& thisIsLvalueToo = funcReturningRValueRef();
X-Value

X-Values are what makes move-semantics possible. They enable us to access memory of an object that’s nearing the end of its lifetime(eg., local variable going out of scope) and perform move operations on the memory pointed. X-Values are created by following types of expressions:
– Function calls that return R-Value references to objects.
– When casting to R-Value references to Objects.
– When accessing members of a class through an object that’s an X-Value.
– When accessing members through a (.*) pointer-to-member expression in which first operand is an X-Value and second operand is a pointer to data member.

//First Case Obj&& funcReturningRValueRef(); // This returns an X-value //Second Case Obj testObj; static_cast<Obj&&>(testObj); // This is an X-Value. Obj&& NotRValue = static_cast<Obj&&>(testObj); // NotRValue is L-Value here //Third Case funcReturningRValueRef().one = 10; // Compile Error! <.one> is an X-Value //Fourth Case int Obj::*ptrToMember = &Obj::one; //Pointer to class member funcReturningRValueRef().*ptrToMember = 10; //Compile Error! Function returns R-Value
GL-Value, PR-Value

A GL-Value could be an L-Value or and X-Value. This generalization was necessary to differentiate between values that associate with a particular object and values that do not. When we say R-Value from C++0x, we usually mean R-Value references(which hold a reference to an object in memory, though temporary). Therefore, at any given point in time, a GL value will always associate with an object, while PR-Value is does not.
If GL-Value appears in context where PR-Value is expected, it’s implicitly converted into a PR-Value.

int x = 23; //23 here is a PR-Value struct Test{ int func() { //glvalue-to-prvalue conversion is applied here return m; } int m = 10; } ------------------------ Test test; test.func(); // This function returns a PR-Value ------------------------ Test first; Test second; // First and Second are both GL-Values // to first.m second = first; void operator=(const Test& other) { //All of the members of the assignee basically can basically used as R-Values this->m = other.m; } ------------------------

Category: C/Cpp

Introduction

What is ADL?

Back to the Original Topic

Conclusion

Introduction

Step-By-Step

Conclusion

Introduction

Organization of static variables and functions in code

Declaring and Defining A Static variable

Introduction

Parsing IT!

Wrapping it up

Introduction

Multiplication with a row view

Multiplication with a Column view

lambda with no Capture

lambda with Capture

Introduction

Definitions

Inter-Thread Synchronization

happens-before

Synchronizes-with

Dependency-Ordered before

Acquire

Release

Consume

Memory Ordering

Sequentially consistent ordering

Relaxed Ordering

Acquire-Release ordering

Dependency Ordering

Introduction

Mutex:

Conditional:

Semaphore:

Definition:

L-Value

R-Value

X-Value

GL-Value

PR-Value

Making sense of these

L-Value

X-Value

GL-Value, PR-Value