Saturday, February 8, 2020

More on std::move and std::forward

In the an earlier post regarding moves in C++, I explained what rvalue references are and did a speed comparison of a move with a copy. Here in this post, I would be highlighting the need of std::move and std::forward in a C++ program. Before that, let's just quickly see what an std::move and std::forward really do. I found this interesting description from one of the presentations by Scott Meyers.
What std::move does?
- it doesn't really move
- it does a rvalue cast on the object
Note, that decision to move or not is taken by the overload resolution process which looks at whether it can call a move assignment/constructor or should it fallback to the "copy" counterparts. For example:
class string
{
    string& operator = (const string&); // copy assignment
    string& operator = (string&&); // move assignment
 ...
}
void foo(const std::string s)
{
   std::string other_str;
   other_str = std::move(s); // still, calls copy assignment because 's' is const
}

What std::forward does?
- it does not really forward
- it does a conditional cast to the rvalue, unlike std::move where the cast is unconditional.

Note: Both std::move and std::forward accept a template type argument, but with std::forward template type deduction is forbidden, while with std::move it is allowed. So, you need to call std::forward always with an explicitly specified template type. This is needed because otherwise there is no way to know with-in std::forward(T&& arg)'s definition if the argument was bound to a lvalue or rvalue. This is because every argument has a name, which causes compiler to always deduce a lvalue-reference type for it. So:
- Calling std::forward<T&>(x) implies 'x' is bound to a lvalue (going by reference collapsing rules)
- Calling std::forward<T>(x) implies 'x' is bound to a rvalue.
A profuse explanation of this can be found in this stackoverflow post
Corollary: std::move is exactly equivalent to a 'std::forward<T>'.

So, let's see the usage of std::move and std::forward with-in the programs, beginning with std::move.

std::move scenarios
1. A class constructor accepting a rvalue reference that needs to be moved into one of its members:
class Test
{
    std::vector mVec;
    public:
        // std::move needed because 'in' is a lvalue (as it has a name, though it is of rvalue-ref type)
        Test(std::vector&& in) : mVec(std::move(in)) { }
        
        Test& add (const Test& t) { ... }

        Test& add (Test&& t) { ... }
...
}
2. A function returning by value, returns a name bound to a rvalue reference
Test foo(Test&& x) {
  x.add(std::vector({1, 22, 13, 56}));
  return std::move(x); // std::move required because x is a l-value, otherwise it will copy constructor
}
3. To invoke the move constructor/assignment when moving named objects:
    Test t (std::vector({1, 22, 13, 56}));
    Test t2 = std::move(t); // use std::move to invoke the move constructor or move assignment
4. To create a rvalue reference seating a named object:
    Test&& rt2 = std::move(t2); // use std::move to create a rvalue reference
5. To invoke a rvalue overload of a function:
   t1.add(std::move(rt2)); // use std::move to invoke rvalue ref overload of a function
Full example code can be found at std_move_examples.cpp

std::forward scenarios
For std::forward, there can be similar scenarios, but it's mainly used in the context of arguments passing to preserve move semantics during calls. Basically, its used in the context of "universal references" i.e. on name of templatized types like T&&, auto type like auto&& where type-deduction distinguishes between whether the reference is bound to a lvalue or rvalue.

1. To pass on the argument preserving its reference-ness type:
void bar(std::string& x) { ... }
void bar(std::string&& x) { ... }
template<typename T>
void foo(T&& x)
{
  bar(std::forward<T>(x));
}
int main()
{
  auto f = [](){ std::string s = "I am R value"; return s; }; // a rvalue reference creator
  std::string&& rrs = f(); // a rvalue reference
  foo(rrs); // will call the lvalue version of bar, as rrs is a name
  foo(f()); // will call the rvalue version
}
In the first call to foo, T is inferred as std::string&, while in the second call its inferred as std::string. The std::forward typecast to x ensures that its holds its intended reference-ness. A rough definition of std::forward would clarify this further:
template<typename T>
T&& forward(T&& param) {
   return static_cast<T&&>(param);
}
2. When moving/passing arguments inside a universal constructor
class Test
{
std::string ob;
public:
    // INCORRECT: moving a univeral reference is wrong as it may be bound to a l-value
    template <typename T>
    Test(T&& t) : ob(std::move(t)) { }
};
Use of std::move is wrong as it will unintentionally move the contents of a l-value, if it is passed to the constructor. Hence, std::move should be replaced by std::forward. Full code for these 2 cases can be found at std_forward_example.cpp

Friday, April 20, 2018

Why matrix multiplication works in the way it does?

Matrices can be thought of as a collection of values organised in the form of rows and columns. Apart from the many operations that are allowed over matrices, matrix multiplication is a very commonly used operation. But, it may make one wonder on what may have motivated its algorithm where you multiply element-wise the row X of the first matrix with the column Y of the second matrix, and then sum the results to obtain the element at position (X, Y) in the result matrix. In this post, I am trying to address that aspect.
To understand the motivation behind this operation, let's first take a look at vectors, which are a simpler form of matrices i.e. a matrix having just a single row or a single column. An example of a vector can be a point in the 3D physical space, which will be basically a row or a column with 3 elements - each representing the distance of the point from the origin along the three dimensions. Another example can be a pixel in a RGB  image, which is again a vector of 3 elements each representing the intensity of the respective color. Now, let's look at a bit more complex example based on the physical space itself (like our first example on vectors) that will provide an insight into the utility of a matrix and also explain the idea behind the matrix multiplication algorithm. Consider a point (x, y) in the 2D space i.e. a 2D vector, which we would like to map to another point in a 3D space (i.e. a 3D vector) using the translation formula: (2x + 3y, 3x + 2y, 4x + y). So, to obtain the corresponding 3D vector, one can just fill the values of x and y from the input 2D vector in the translation formula. That's simple, but the important part is that, this translation can be accomplished by using a matrix where we multiply it the with input 2D vector to obtain the output 3D vector , as shown in the image below:

Looking at the first equation in the image, you may guess how we reached to the 3x2 matrix in there -  it's basically just derived from the coefficients in the translation formula that was mentioned above. By multiplying this matrix to any 2D vector, we can obtain corresponding 3D vector based on the translation formula! So, what matrix multiplication simply does is applying a translation operation on an input vector where the elements in the matrix just represent the amount of contribution of the input vector elements that is needed to compute the output vector. For example, in this case, to compute first element (i.e. 8) in the output vector, two times the contribution from the first element (i.e. 1) of the input vector and three times the contribution from the second element (i.e. 2) is used i.e. (2*1 + 3*2 = 8), which is the basic step in the matrix multiplication algorithm.
One may question, why not just directly use the translation formula? Why represent this in matrix form? The answer here (I think) is that using the matrix form and the matrix multiplication operation simplifies the translation especially if there is a huge input data-set. For example, if you want to apply the same transformation over 1000 such 2D vectors, then by just stacking them up column-wise in a matrix (which will than be of dimensions 2x1000) and multiplying it with the same 2x3 transformation matrix will give us all the 1000 3D vectors! This is somewhat shown in the second equation in the figure above. This representation immensely helps in doing such computations inside a computer that can process huge chunks of data in one go. In fact, the processors today (actually, since past 10 yrs) are capable of performing SIMD instructions and scientific libraries like in MATLAB OR numpy in python utilize these instructions to perform matrix operations really fast! I have written a small python script to show the amount of speed-up that you may gain when using matrix multiplication instead of multiple scalar multiplications. Here I just use the same example as in the image above and run/compare the two over 1 million 2D vectors. I make use of the numpy library of python to do matrix multiplication i.e. using numpy.dot(<mat1>, <mat2>) method in there. The amount of speed-up I see on my windows 10 laptop (with Intel Core i5) is approx. 100x!

Saturday, December 30, 2017

Interesting 'moves' of C++ 11

The ability to move an object instead of copying always, is one of the most important features of C++11! Haven't yet come across a concise, interesting and a complete description of this feature, except the one from Thomas Becker: C++ Rvalues explained which goes systematically into this topic, doesn't touch every nook and recess of it, but gives you pointers in most cases. At places, he refers to the book by Scott Meyers Effective Modern C++, which to admit, I started reading, but still lingering at the first few articles. In this entry, I am pouring down whatever I have understood till now about this topic so to not forget about it and that I can reload it later (sort of like doing a 'git stash' now, to 'pop' later :-) ).
C++11 has introduced a proper and complete way to refer to the rvalues (literals or temporaries like the return values of functions etc.) in the program. Rvalues existed before C++11, but you could not refer to them completely in the program. C++03 allowed you to refer to an rvalue using a const lvalue reference, for example:
template<typename T>
std::string to_string(const T& ob)
{
    std::string tmp = ...;
    return tmp;
}

void print_string(std::string& s);  // (1)
void print_string(const std::string& s); // (2)

print_string(to_string(4));
If only print_string (1) is available, then the compiler would give an error saying that it could not find a suitable candidate for the call to print_string. With print_string(2) being present, everything would go fine. The reason is print_string is being called with an rvalue and it cannot be referred using an lvalue_reference as in (1), but can be referred using a const lvalue reference as in (2). So, you could refer to rvalues in C++03 too, but it was not complete in the sense that you could not modify the rvalue using that reference (as it was a const reference).
C++11 introduced rvalue references using which you can also modify the rvalues they are pointing to! An obvious question would be that why would you want to modify an rvalue which is usually a constant or a temporary object that's internally created by the compiler? The answer is that we may want to make use of the resources of the temporary object that's already created and save our CPU time to recreate it. The temporary object would anyway go waste otherwise. And that's the rationale behind the introduction of "moves" in C++11. So, now C++ has a new reference type (donated with '&&') using which you can declare names that can refer to rvalues. Also, the new type is handy is passing references to rvalues along a chain of function calls without any copying of actual values (also know "perfect forwarding").
In this post, I plan to experimentally show on how much performance improvement you can extract by using moves instead of copies. The example code can be seen at: compare.cpp. In the example, as you can notice, I define two classes MoveableSeq and NotMoveableSeq and as the name implies the former has a move constructor, while the latter doesn't have one. Both these classes define an array of 1000 values which is dynamically allocated at the construction time. To compare the two, I create a std::vector of objects of both these classes. For NotMoveableSeq, the objects are copied into the vector, while for MoveableSeq, the objects are moved into the vector. There is also a third scenario where the objects are "emplaced" into the vector i.e. they are directly created inside the vector, thus involving neither a copy, nor a move. For comparison, I collect the time taken for objects number starting from 1000 to 250K and plot the graph for all the three cases, as shown below. The result is as you would expect - nothing to explain further! The code to plot this graph was done using python and it is uploaded at the same github location as compare.cpp.

Saturday, September 12, 2015

A peek into security and https

Somebody asked me about https (vs. http) a few days back and it triggered a DFS in my head's neural flora to dig out the answer. The answer was found and was good enough for the questioner but not good enough for me - because of the holes in there! So I did some research over the web/books to fill in those holes and then thought to put it down here for future reference. So, in this post I will talk about same basics of cyber-security and zoom a bit into https (or SSL). Let's first look at what all aspects fall under the umbrella of security:  
  • Confidentiality/Authenticity i.e. we do not want our information to be visible to others or want it to be only visible to a handful of people (aka the "authentic" ones) 
  • Integrity i.e. we do not want that the information we are conveying to get distorted/modified in between before it reaches intended destination 
  • Availability i.e. we do not want that the services we are providing to others get disrupted or become inaccessible to them
If any of the aspects is compromised, then we call it a "security-breach". For example, consider the infamous "Man-in-the-middle attacks" where an eavesdropper snoops into a conversation and either steals the information compromising Confidentiality, or distorts the information compromising Integrity. Then, there are "Denial-of-Service attacks" that compromise the Availability aspect of security. Now, let's look at in brief the most common techniques that are adopted to ensure Confidentiality and Integrity (I will not cover Availability in this post).

Data Encryption

If the two parties involved in a conversation follow an encryption scheme that an eavesdropper cannot guess, then the conversation becomes secure. Key-based encryption schemes are the most common in the field of security. In such schemes, you encrypt your message using a key (or simply a number or a sequence) and decrypt it using the same or other coupled-number. How you do the encryption with the key depends on the encryption algorithm you are using. A simple algorithm could be just doing an XOR of the message with the key. Consider encrypting an M with a key K to yield ciphertext E(M):
Encryption: E(M) = M xor K
Decryption: M    = E(M) xor K
So, both the parties involved in the communication needs to know K. Such a scheme is called Symmetric Key Encryption. But of course, this algorithm of using XOR is simple to crack, when a single constant repeating key is used. Algorithms that are used normally with Symmetric Encryption are much more complex and difficult to crack like AES, blowfish etc. The difficulty with Symmetric Key Encryption is that the same key needs to be shared between the 2 parties and so the question is how to securely share the key? Thankfully, there are already techniques to do the sharing of the key like Diffie-Hellman Key Exchange etc. But, the other way is to use Asymmetric Key Encryption, where you don't need to share the key! The following picture depicts what happens in Asymmetric Key Encryption (aka Public Key Encryption)
Source: http://en.wikipedia.org
Basically, there are 2 entangled keys for one user as against one shared key in Symmetric Encryption. One of the key is known to all (called public), while the other key is only known to the user (called private). As shown in the picture, if somebody wants to send a message to the user then he will encrypt the message using the user's public key and then the user can decrypt it using his private key. The message encoded using a public key can only be decoded using the corresponding private key and private key is only known to the user. It looks like magic, but its Number Theory. For the mathematics involved here, please look at the RSA implementation Usually, both symmetric and asymmetric encryption schemes are used in tandem, where asymmetic encryption is used in sharing the key that will be used later for symmetric encryption. 

Digital Signatures

With data encryption we are able to ensure that Confidentiality aspect of security is preserved. For maintaining Integrity, using Digital Signatures is the most common technique. Digitally signing of a document (or any data) is a two step process: 1. Generating a hash of the input document using some hashing algoithms like SHA or MD5, 2. Then using your private key to encrypt the generated hash. The encrypted hash is basically the digital signature. The sender will send the document along with the signature to the receiver. The receiver will first use the public key of the sender to decrypt the signature to recover the hash; and also will regenerate the hash from the document and compare the two hash-es. If they do not match, that means somebody tampered with the document or with the signature. Note that, nobody other than the sender can regenerate the signature after modifying the document as he will not have the private key of the sender.
Now we will see how the data encryption techniques and digital signature come into play in https or SSL.

How https ensures secure communication?

There is one more player in https protocol in addition to the sender and the receiver who is known as "Certificate Authority" (CA). These CA's are authorized organizations analogous to government organizations whom you trust. Some of the CA's are Verisign, Symantec, Google Internet Authority etc. The websites who want their customers to connect securely obtain a certificate (SSL or X.509) from one of these CA's. This certificate contains the public key of the website, details of the organization that owns the website, details of the CA and the digital signature done by CA using its private key. Now, lets look at what happens when we try to connect to such a website using a web browser:
After browser sends a connection request to a secure website, the corresponding web-server responds back with its SSL certificate. Now, the browser needs to verify if the certificate is genuine. Looking at the certificate, browser knows about which CA has signed it and then using the public key of that CA it verifies the integrity of the certificate, as discussed above in the digital signatures section. With this it ensures if no eavesdropper has tampered with the certificate. Next, the browser generates a random session key and sends it to the web server not before encrypting it with the public key of the server (public key was present in the certificate). In this manner, a session key is securely exchanged between the browser and the web-server. After this, both the web-server and the browser can securely exchange data using Symmetric Encryption with the session key. This ensures that anybody who snoops (and who might be replaying the SSL certificate) will be not able to decode any communication as he doesn't have the private key of web-server and thus also the session-key. This makes the https perfectly secure!

 

Thursday, November 6, 2014

Write your logger in C++

While writing any decently big software, you will in most cases dump messages at various points in the software to capture important events or issue warnings and errors. You typically do this by adding printfs, cout's, cerr's etc. and all of this works pretty fine. But, what if tomorrow you want to dump all messages in a log file instead of pushing them on stdout or you want to do some processing over all the messages like adding a message code in the header or replacing all the end-of-line characters with just a space etc. Well, you can say that I will go over all the places where the messages are being dumped and easily adapt them - works, but can be immensely cumbersome and error-prone. Why not do something that's elegant, maintainable and less error-prone? Why not use the power unleashed by C++? Why not create a logger class that unveils a convenient and flexible interface to dump messages. Following is an example of such a class:

#include <iostream>
#include <fstream>
#include <string>
class MyLogger
{
public:
    // 2nd bit tells that you need to push to a file too
    enum LoggingMode { NORMAL=0, FILE_ONLY=2, TEE_MODE=3 };

    MyLogger(bool is_err=false) {
        m_Mode = NORMAL;
        m_fLogErrorStream = is_err;   
    }

    ~MyLogger() {
        if ((int)m_Mode & 2) m_OutFile.close();
    }

    void initFile(const std::string& outfile)  {  
        m_Mode = FILE_ONLY; // set the m_Mode to file mode  
        m_OutFile.open(outfile.c_str(), std::ofstream::out | std::ofstream::app);
    }

    void setMode(const LoggingMode& mode)
    {
        m_Mode = mode;
    }

    template <typename T>
    MyLogger& operator << (const T& val) {
        out() << val;
        if ((int)m_Mode & 2) fout() << val;
        return *this;
    }
    
private:
    LoggingMode m_Mode;
    bool m_fLogErrorStream;
    std::ofstream m_OutFile;
  
    std::ostream& fout() {
        return m_OutFile;   
    }
    std::ostream& out() {
        if (m_fLogErrorStream) return std::cerr;      
        return std::cout;
    }

};
To keep the interface of the logger C++like, operator << is overloaded. The operator is implemented as a function template whose specialized versions would be generated by the C++ compiler based on the types of the argument it is applied to. Based on the LoggingMode, the MyLogger class decides whether to log to usual streams (i.e. stdout or stderr) or to a file only or to both. The enum LoggingMode can be extended to support other modes. Following is a simple test for this class and it works:
MyLogger mlog;
int x = 100; float y = 6.67;
mlog.initFile("test.log");
mlog.setMode(MyLogger::TEE_MODE);
mlog << "Hello World!!\n";
mlog << "Value of x and y is: " << x << ", " << y << "\n";
In this test, the arguments to operator << were the usual types viz. const char*, int and float. Let's try other things that are typically given to the cout/cerr objects like 'std::endl', 'std::flush', 'std::hex' etc. popularly known as manipulators. All these manipulators are basically functions (or function pointers) and can also match to the operator << function template - hence, no further extensions should be needed. But, that's not entirely true - for example, consider the std::endl function that has the following prototypes:
ostream& endl (ostream& os);

template <class charT, class traits>
basic_ostream<charT,traits>& endl (basic_ostream<charT,traits>& os);
Now when you have a statement like 'mlog << std::endl', the compiler will be left confused when trying to resolve the type 'T' for std::endl as it will have 2 ambiguous choices.Hence, it will bail out giving the errors as shown below (using MSVC 2010 compiler):
error C2914: 'MyLogger::operator <<' : cannot deduce template arg as function arg is ambiguous
error C2676: binary '<<' : 'MyLogger' does not define this operator or a conversion to a type
acceptable to the predefined operator
So, how do we fix this? We know that we need to choose the first prototype as that corresponds to 'ostream', so let's add a specialization for operator <<, that will help the compiler zero-in on the first prototype:
MyLogger& operator << (std::ostream& (*manip)(std::ostream&)) {
#if DEBUG
    if (manip == std::endl) {
        std::cout << "endl found!\n";
    }
#endif
    manip(out());
    if ((int)m_Mode & 2) manip(fout());
    return *this;
}
With this specialized implementation of operator << added, the compiler is now able to resolve the ambiguity and we get the desired result!

Sunday, June 26, 2011

got hitched!

All the way from the moon, down she landed on my floor,
Draped with innocence & charm -
Dusky damsel she, knocked my door!
Oblivious and lost, I moved towards the door & it switched,
Awestruck with her gaze -
Revived later, only to find myself hitched!!


Past 7 months were, as if I was caught in a 'time warp' - lot of things changed, including my status (as title says) ;-) and my car, my hairdo to name a few..Time's now slowly de-warping and I am back to my usual chores..
BTW today, I completed 50 days of my nuptials and also 5 years in software industry - nice day to get back to posting!
..signing off now as dinner's calling

Sunday, December 26, 2010

All world's a stage! - Shakespeare

Incidentally, while browsing the web, I came across the following monologue from Shakespeare:

All the world's a stage,
And all the men and women merely players;
They have their exits and their entrances;
And one man in his time plays many parts,
His acts being seven ages. At first the infant,
Mewling and puking in the nurse's arms;

.. [Read full text at http://www.artofeurope.com/shakespeare/sha9.htm]

Here, he visualizes the whole world as a stage and a life as a play. Though, I had heard about this comparison of Shakespeare earlier, but never read this original speech/poem of his. What impresses me most is that he serves the truth "as is" on your platter - without any garnishing!

These lines definitely reminds me of the other lines "hum sab to rang-manch ki katputliaan hain.." from the eternal movie 'Anand' which still reverberates in the heart of Indian cinema.