Saturday, March 18, 2017

Some C/C++ tips & tricks

Understanding Virtual Functions in C++

Virtual functions are a cornerstone of C++ polymorphism, enabling dynamic binding at runtime. This blog post delves into various aspects of virtual functions with practical code examples and detailed explanations.

Virtual Function Example

Let's start with a basic example that demonstrates the use of virtual functions.

[code]

#include<iostream>
using namespace std;

class Base{
public:
    int a;
        virtual void sum() {
        cout << "sum of class Base" << endl;
    }
};

class Derived : public Base {
public:
    int b;
    void sum() {
         cout << "sum of class Derived" << endl;
    }

};

int main() {
    Base *aptr;
    Derived d;
    aptr = &d;
    aptr->sum();
    return 0;
}


Output:


sum of class Derived

Without the virtual keyword, the output would be "Sum of class Base."


sum of class Base


Virtual Friend Function Idiom

This idiom allows friend functions to act as if they were dynamically bound:


[code]

#include<iostream>
using namespace std;

class Base {
    public:
       friend ostream& operator << (ostream& o, const Base& b);
    protected:
       virtual void print(ostream& o) const
       {  cout << "This is Base class print function" << endl;    }
};

/* make sure to put this function into the header file */
inline std::ostream& operator<< (std::ostream& o, const Base& b)
{
      b.print(o); // delegate the work to a polymorphic member function.
      return o;
}

class Derived : public Base {
  protected:
    virtual void print(ostream& o) const
    { cout << "This is Derived class print function" << endl; }
};

int main(void)
{
     Base b;
     cout << b;
     Derived d;
     cout << d;
     return 0;
}
Output:

This is Base class print function
This is Derived class print function

The end result is that operator<< acts as if it were dynamically bound, even though it's a friend function.
This is called the Virtual Friend Function Idiom. Note that derived classes override printOn(std::ostream&) const. In particular, they do not provide their own operator<<.

Confusing Base/Derived class pointer conversion

This example demonstrates dangerous conversions between base and derived class pointers:
#include<iostream>
using namespace std;

class BB{
public:
         virtual void Doit() { cout << "BB do it" << endl; }
         void Seeit() { cout << "BB see it" << endl; }
         virtual ~BB(){}
};

class DD: public BB{
public:
         virtual void Doit() { cout << "DD do it" << endl; }
         void Seeit() { cout << "DD see it" << endl; }
};

class XX: public BB{
public:
         void Seeit() { cout << "XX see it" << endl; }
         virtual void Doit() { cout << "XX do it" << endl; }
};

int main(void)
{
    DD *dp = new DD;

    BB *bp = static_cast<BB*>(dp);
    bp->Doit();
    bp->Seeit();

    XX *xp = static_cast<XX *>(bp);   //dangerous, please don't do it
    xp->Doit();
    xp->Seeit();

    return 0;
}


Output:
DD do it
BB see it
DD do it
XX see it


However, if we change the main function as follows (by using 'dynamic_cast' instead):

int main(void)
{
    DD *dp = new DD;

    BB *bp = dynamic_cast<BB*>(dp);
    bp->Doit();
    bp->Seeit();

    XX *xp = dynamic_cast<XX *>(bp);
    if (xp == NULL) {
        cout << "Wrong, this should not be allowed" << endl;
    } else {
        xp->Doit();
        xp->Seeit();
    }
    return 0;
}



Constructor and Destructor Calls in Inheritance

When a derived class instance is created, the base class constructor is called first, followed by the derived class constructor. On destruction, the process is reversed.

For example:

[code]   

#include<iostream>
using namespace std;
class Other{
    public:
       int ov;
       Other(int t):ov(t) { cout << "Other constructor" << endl; }
       ~Other(void) { cout << "Other destructor " << endl; }
};
class Base{
public:
    int bv;
    Base(int var):bv(var)
    {
        cout<<"Base constructor"<<endl;
    }
    virtual ~Base(void)
    {
        cout<<"Base destructor"<<endl;
    }
};
class Derived: public Base
{
public:
    int dv;
    Other mt;
    Derived(int d): mt(d++), Base (d++)     // Base class constructor gets call first, then followed by member initialization
    {
        cout<<"child constructor"<<endl;
    }
    ~Derived(void) {
        cout << "child destructor" << endl;
    }
};
int main()
{
    Derived obj1(8);
}

 

The expect result is:

Base constructor
Other constructor
child constructor
child destructor
Other destructor 
Base destructor


Private Virtual Function Usage

Even private virtual functions can be used to enforce derived class behavior without being directly called by the derived class.


[code]

#include<iostream>
using namespace std;

class A{
    public:
       void foo() {
          cout << __PRETTY_FUNCTION__ << endl;
          bar();
       }
    private:
       virtual void bar() {
          cout << __PRETTY_FUNCTION__ << endl;
       }
};

class B: public A {
   private:
       virtual void bar() {
          cout << __PRETTY_FUNCTION__ << endl;
       }
};

int main(void)
{
    A *pa = new B;
    pa->foo();
    return 0;
}
 

Base class requires its Derived class to override its virtual function bar(),  but  it is better for its derived class not call it directly. so the expected result is:

void A::foo()
virtual void B::bar()


Polymorphism in Constructors and Destructors

Virtual functions cannot exhibit polymorphism in constructors and destructors.


#include<iostream>
using namespace std;

class A{
    public:
       A() {
          cout << __PRETTY_FUNCTION__ << endl;
          bar();
       }
       ~A() {
          cout << __PRETTY_FUNCTION__ << endl;
          bar();
       }
       virtual void bar() {
          cout << __PRETTY_FUNCTION__ << endl;
       }
};

class B: public A {
   public:
       virtual void bar() {
          cout << __PRETTY_FUNCTION__ << endl;
       }
};

int main(void)
{
    A *pa = new B;
    delete pa;
    return 0;
}

I would expect the result should be:
<=====Wrong result =====>
A::A()
virtual void B::bar()
A::~A()
virtual void B::bar()
<=====End Wrong result =====>

but the actual result is:

A::A()
virtual void A::bar()
A::~A()
virtual void A::bar()

Pure virtual function

Polymorphism won't be available if a member function is not virtual in the base class. Let's consider the following example:

[code]

#include<iostream>
using namespace std;

class Abase
{
public:
    virtual void FA()= 0;
    void FB()   // notice that there is no virtual here
    {
        cout << __PRETTY_FUNCTION__ << endl;
    }
    virtual void FC()
    {
       cout << __PRETTY_FUNCTION__ << endl;
    }
};

//sub class
class Subase: public Abase
{
public:
    void FA()
    {
       cout << __PRETTY_FUNCTION__ << endl;
    }
    void FB()
    {
       cout << __PRETTY_FUNCTION__ << endl;
    }
    void FC()
    {
      cout << __PRETTY_FUNCTION__ << endl;
    }
};

int main()
{
    Abase* inst = new Subase();
    inst->FA();
    inst->FB();
    inst->FC();
    return 0;

}



The result is:
virtual void Subase::FA()
void Abase::FB()
virtual void Subase::FC()

How many instances get created and which constructor is invoked

Please do some experiment in the following class: 

[code]
#include<iostream>
#include<string>

using namespace std;
#define TRACEPR cout << __PRETTY_FUNCTION__ << endl;

class B{
    private:
       int m = 0;
    public:
       B(int b=0):m(b){
           TRACEPR
       };
       B(const B &b):m(b.m) {
           TRACEPR
       };
       B &operator=(const B &b) {
          TRACEPR
          m = b.m;
          return *this;
       }
       virtual ~B(void) {
           TRACEPR
       }
       B(const B &&b):m(b.m) {
           TRACEPR
       }
       B &operator=(B &&b) {
          TRACEPR
          m = b.m;
          b.m = 0;
          return *this;
       }
};

B getB()
{
     B b;
     return b;
}

B &getrB()
{
     static B b;
     return b;
}

void setB(B b)
{
     B t = b;
}

void setrB( B &b)
{
     B t = b;
}


The compiler specific options as follows:

g++  -g -std=c++11 -fno-elide-constructors  runfile.cpp  -o runfile



Please inspect the following invoke combinations (some have compiler error) , pay attention about what constructor is called and how many instances are created, including xvalue, rvalue and lvalue type. 

1) B b = getB();
2) const B &b = getB(); // what if we don't use const?
3) B b = getrB(); 
4) B &b = getB();
5) setB(b);
6) setrB(b);




Object Slicing  

Object slicing occurs when a derived class object is assigned to a base class object, causing the derived part to be "sliced off."



#include<iostream>
using namespace std;


class B{
    public:
       virtual void F() { cout << "B F() "  << endl; }
       void C() { cout << "B C() " << endl; }
};


class D: public B{
    public:
       void F() { cout << "D F() "  << endl; }
       void C() { cout << "D C() " << endl; }
};


void objnotslicing(B &b)
{
     b.F();
     b.C();
}

void objslicing( B b )
{
     b.F();
     b.C();
}

int main(void)
{
     D d;
     objnotslicing(d);
     objslicing(d);
     return 0;
}



The result is:

// object not slicing happens
D F()
B C()     // please note that C() is a virtual function, hence the polymorphism.

// object slicing happens
B F()
B C()


Understanding and utilizing virtual functions correctly can significantly enhance the flexibility and functionality of your C++ programs. From dynamic binding to preventing object slicing, virtual functions are indispensable tools in advanced C++ programming. Experiment with these examples to deepen your understanding and see the power of virtual functions in action.








Saturday, February 25, 2017

SNAKE - System Design Principles to crack a system design in 5 steps


System design questions can be daunting, but with a structured approach, you can tackle them confidently. Here are five steps to help you systematically address any system design question:

1. Scenario: Understanding the Case and Interface

  • Typical Use Cases: Identify the primary use cases your system needs to support. Understand the end-user requirements and the core functionalities the system should provide.
  • Abstraction: Determine the level of abstraction your system should offer. This involves defining the system boundaries and the high-level components.
  • APIs: Design the APIs that will facilitate communication between different components of your system. Consider the inputs, outputs, and actions for each API endpoint.

2. Necessary: Constraints and Hypotheses

  • Total Users and Daily Active Users: Estimate the number of users your system will serve and the daily active user count. This helps in understanding the scale.
  • Transactions: Determine the number of transactions your system needs to handle. This includes read and write operations.
  • Concurrency: Assess the number of concurrent users or parallel executions your system must support.
  • Peak Load: Identify the peak load your system is expected to handle. This includes traffic spikes and maximum transaction rates.
  • Performance Requirements: Define the acceptable latency and response time. Understand how fast your system needs to be and the maximum delay it can tolerate.

3. Application: Services and Algorithms

  • Service Design: Break down your system into individual services or modules. Define the responsibilities and interactions of each service.
  • Algorithm Complexity: Perform a complexity analysis of the core algorithms. Understand the time and space complexity (Big O notation) to ensure efficiency.

4. Kilobit: Data Considerations

  • Data Generation: Estimate the amount of data generated by your system. This includes user-generated content, logs, and metadata.
  • Storage Requirements: Determine the storage space needed to persist the data. Plan for future growth.
  • Data Storage Solutions: Decide where to store the data. Choose between file systems, SQL databases, NoSQL databases, or a combination based on your requirements.

5. Evolve: Optimization and Scalability

  • Optimization: Identify areas for performance improvement. Optimize your system for speed, memory usage, and resource efficiency.
  • Extensibility: Ensure your system can be extended with new features and components without significant rework.
  • Scalability: Design your system to scale horizontally and vertically. Plan for adding more servers, instances, and resources as demand grows.
  • Availability: Ensure high availability of your system through redundancy, failover mechanisms, and disaster recovery plans.

4S Analysis Framework

Alternatively, you can use the 4S Analysis framework to structure your approach:

Scenario

  • Ask: Clarify the problem statement and requirements.
  • Features: Identify the core features your system needs to support.
  • QPS (Queries Per Second): Determine the expected query rate.
  • DAU (Daily Active Users): Estimate the daily active user count.
  • Interfaces: Define the interfaces for user interaction and system integration.

Service

  • Split: Break down the system into smaller, manageable services or modules.
  • Application: Design the core application logic and service responsibilities.
  • Module: Define the individual modules and their interactions.

Storage

  • Schema: Design the database schema to support your data model.
  • Data: Plan for data storage, indexing, and retrieval.
  • SQL/NoSQL/File System: Choose the appropriate storage solutions based on your data needs.

Scale

  • Sharding: Implement sharding for distributed data storage and retrieval.
  • Optimize: Optimize your system for performance and efficiency.
  • Special Case: Address special cases and edge scenarios to ensure robustness.

By following these steps and frameworks, you can systematically and confidently approach any system design question, ensuring a comprehensive and efficient solution.


Monday, February 6, 2017

Mastering Thread Synchronization in C++ with Practical Examples

Thread synchronization is crucial in multithreaded programming to ensure that multiple threads can cooperate and share resources without conflicts. Here, we explore various synchronization techniques using practical examples in C++.

1. Signaling

Signaling allows one thread to notify another that an event has occurred. This ensures that a specific section of code in one thread runs before a section in another thread.

Example: Ensuring handlerA runs before handlerB.

[code]

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

pthread_t thread_a;
pthread_t thread_b;
sem_t sema;

sem_init(&sema, 0, 0);

void* handlerA(void*) {
    printf("functionA\n");
    sem_post(&sema);
    return NULL;
}

void* handlerB(void*) {
    sem_wait(&sema);
    printf("functionB\n");
    return NULL;
}

int main() {
    pthread_create(&thread_a, NULL, handlerA, NULL);
    pthread_create(&thread_b, NULL, handlerB, NULL);
    pthread_join(thread_a, NULL);
    pthread_join(thread_b, NULL);
    return 0;
}


2. Rendezvous:


Rendezvous extends signaling by ensuring two threads wait for each other at specific points.

Example: Ensuring steps in handlerA and handlerB occur in a specific order.

[code]
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

pthread_t thread_a;
pthread_t thread_b;
sem_t sema;
sem_t semb;

sem_init(&sema, 0, 0);
sem_init(&semb, 0, 0);

void* handlerA(void*) {
    printf("functionA step 1\n");
    sem_post(&sema);
    sem_wait(&semb);
    printf("functionA step 2\n");
    return NULL;
}

void* handlerB(void*) {
    printf("functionB step 1\n");
    sem_post(&semb);
    sem_wait(&sema);
    printf("functionB step 2\n");
    return NULL;
}

int main() {
    pthread_create(&thread_a, NULL, handlerA, NULL);
    pthread_create(&thread_b, NULL, handlerB, NULL);
    pthread_join(thread_a, NULL);
    pthread_join(thread_b, NULL);
    return 0;
}


3. Mutex:

A mutex ensures that only one thread accesses a critical section at a time.

Example: Safely incrementing a shared counter.



[code]
#include <pthread.h>
#include <stdio.h>

pthread_t thread_a;
pthread_t thread_b;
pthread_mutex_t mutex;

int count = 0;

void* handlerA(void*) {
    pthread_mutex_lock(&mutex);
    count++;
    pthread_mutex_unlock(&mutex);
    return NULL;
}

void* handlerB(void*) {
    pthread_mutex_lock(&mutex);
    count++;
    pthread_mutex_unlock(&mutex);
    return NULL;
}

int main() {
    pthread_mutex_init(&mutex, NULL);
    pthread_create(&thread_a, NULL, handlerA, NULL);
    pthread_create(&thread_b, NULL, handlerB, NULL);
    pthread_join(thread_a, NULL);
    pthread_join(thread_b, NULL);
    pthread_mutex_destroy(&mutex);
    return 0;
}



4. Multiplex 


Multiplexing allows multiple threads to enter the critical section, controlled by a semaphore initialized to a specific value.

Example: Allowing two threads to run in the critical section simultaneously.


[code]
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

pthread_t thread_a;
pthread_t thread_b;
pthread_t thread_c;
sem_t sema;

sem_init(&sema, 0, 2);

void* handlerA(void*) {
    for(int i = 0; i < 10; i++) {
        sem_wait(&sema);
        printf("functionA\n");
        sem_post(&sema);
    }
    return NULL;
}

void* handlerB(void*) {
    for(int i = 0; i < 10; i++) {
        sem_wait(&sema);
        printf("functionB\n");
        sem_post(&sema);
    }
    return NULL;
}

void* handlerC(void*) {
    for(int i = 0; i < 10; i++) {
        sem_wait(&sema);
        printf("functionC\n");
        sem_post(&sema);
    }
    return NULL;
}

int main() {
    pthread_create(&thread_a, NULL, handlerA, NULL);
    pthread_create(&thread_b, NULL, handlerB, NULL);
    pthread_create(&thread_c, NULL, handlerC, NULL);
    pthread_join(thread_a, NULL);
    pthread_join(thread_b, NULL);
    pthread_join(thread_c, NULL);
    return 0;
}

5. Barrier:

A barrier ensures that no thread proceeds past a certain point until all threads reach that point.

Example: Synchronizing threads before proceeding to the next step.


[code]
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

pthread_t thread_a;
pthread_t thread_b;
pthread_t thread_c;
pthread_mutex_t mutex;
sem_t barrier;
int count = 0;

void* handlerA(void*) {
    pthread_mutex_lock(&mutex);
    count++;
    printf("Func A access done.\n");
    if (count == 3) sem_post(&barrier);
    pthread_mutex_unlock(&mutex);
    sem_wait(&barrier);
    sem_post(&barrier);
    printf("Function A\n");
    return NULL;
}

void* handlerB(void*) {
    pthread_mutex_lock(&mutex);
    count++;
    printf("Func B access done.\n");
    if (count == 3) sem_post(&barrier);
    pthread_mutex_unlock(&mutex);
    sem_wait(&barrier);
    sem_post(&barrier);
    printf("Function B\n");
    return NULL;
}

void* handlerC(void*) {
    pthread_mutex_lock(&mutex);
    count++;
    printf("Func C access done.\n");
    if (count == 3) sem_post(&barrier);
    pthread_mutex_unlock(&mutex);
    sem_wait(&barrier);
    sem_post(&barrier);
    printf("Function C\n");
    return NULL;
}

int main() {
    sem_init(&barrier, 0, 0);
    pthread_create(&thread_a, NULL, handlerA, NULL);
    pthread_create(&thread_b, NULL, handlerB, NULL);
    pthread_create(&thread_c, NULL, handlerC, NULL);
    pthread_join(thread_a, NULL);
    pthread_join(thread_b, NULL);
    pthread_join(thread_c, NULL);
    return 0;
}

6. Deadlock:

Deadlock occurs when two or more threads are waiting on each other to release resources, causing all of them to get stuck.

Example: A simple deadlock scenario.


[code]

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

pthread_t thread_a;
pthread_t thread_b;
sem_t sema;
sem_t semb;

sem_init(&sema, 0, 0);
sem_init(&semb, 0, 0);

void* handlerA(void*) {
    printf("functionA step 1\n");
    sem_wait(&semb);
    sem_post(&sema);
    printf("functionA step 2\n");
    return NULL;
}

void* handlerB(void*) {
    printf("functionB step 1\n");
    sem_wait(&sema);
    sem_post(&semb);
    printf("functionB step 2\n");
    return NULL;
}

int main() {
    pthread_create(&thread_a, NULL, handlerA, NULL);
    pthread_create(&thread_b, NULL, handlerB, NULL);
    pthread_join(thread_a, NULL);
    pthread_join(thread_b, NULL);
    return 0;
}

7. Producer-consumer:

The producer-consumer problem involves multiple threads producing items and adding them to a buffer, while other threads consume and remove them from the buffer.

Example: Unlimited buffer producer-consumer.


[code]

#include <pthread.h>
#include <semaphore.h>
#include <deque>
#include <stdio.h>

pthread_t thread_producer;
pthread_t thread_consumer;
pthread_mutex_t mutex;
sem_t sema;
std::deque<int> buffer;

pthread_mutex_init(&mutex, NULL);
sem_init(&sema, 0, 0);

void* producer(void*) {
    while(true) {
        int num = rand() % 100;
        printf("producer set %d\t", num);
        pthread_mutex_lock(&mutex);
        buffer.push_front(num);
        sem_post(&sema);
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

void* consumer(void*) {
    while(true) {
        sem_wait(&sema);
        pthread_mutex_lock(&mutex);
        int back = buffer.back();
        buffer.pop_back();
        pthread_mutex_unlock(&mutex);
        printf("consumer get %d\n", back);
    }
    return NULL;
}

int main() {
    pthread_create(&thread_producer, NULL, producer, NULL);
    pthread_create(&thread_consumer, NULL, consumer, NULL);
    pthread_join(thread_producer, NULL);
    pthread_join(thread_consumer, NULL);
    return 0;
}

8. Finite Buffer Producer-consumer:

When the buffer is finite, producers need to wait if the buffer is full, and consumers need to wait if the buffer is empty.

Example: Producer-consumer with finite buffer.

[code]
#include <pthread.h> #include <semaphore.h> #include <deque> #include <stdio.h> #define N 10 pthread_t thread_producer; pthread_t thread_consumer; pthread_mutex_t mutex; sem_t sema; sem_t spaces; std::deque<int> buffer; pthread_mutex_init(&mutex, NULL); sem_init(&sema, 0, 0); sem_init(&spaces, 0, N); void* producer(void*) { while(true) { int num = rand() % 100; printf("producer set %d\t", num); sem_wait(&spaces); // wait signal pthread_mutex_lock(&mutex); buffer.push_front(num); sem_post(&sema); pthread_mutex_unlock(&mutex); } return NULL; } void* consumer(void*) { while(true) { sem_wait(&sema); pthread_mutex_lock(&mutex); int back = buffer.back(); buffer.pop_back(); pthread_mutex_unlock(&mutex); sem_post(&spaces); // signaling producer printf("consumer get %d\n", back); } return NULL; } int main() { pthread_create(&thread_producer, NULL, producer, NULL); pthread_create(&thread_consumer, NULL, consumer, NULL); pthread_join(thread_producer, NULL); pthread_join(thread_consumer, NULL); return 0; }

9. Readers and Writers Problem:

This problem involves readers and writers who need different synchronization. Multiple readers can access the resource simultaneously, but a writer requires exclusive access.

Example: Readers-writers problem.

[code]
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

#define N 4
pthread_t thread_writer[N];
pthread_t thread_reader[N];
int readers = 0;

pthread_mutex_t writeOk;
pthread_mutex_t readerOn;

char BufferA[20];
char BufferB[20];

void* writer(void*) {
    int counter = 1;
    while(1){
        pthread_mutex_lock(&writeOk);
        sprintf(BufferA, "WriteA: %d", counter);
        usleep(100);
        sprintf(BufferB, "WriteB: %d", counter);
        counter++;
        pthread_mutex_unlock(&writeOk);
    }
    return NULL;
}

void* reader(void* arg) {
    while(1) {
        pthread_mutex_lock(&readerOn);
        readers++;
        if (readers == 1) {
            pthread_mutex_lock(&writeOk);
        }
        pthread_mutex_unlock(&readerOn);

        printf("%s from thread %ld\n", BufferA, (long)arg);
        printf("%s from thread %ld\n", BufferB, (long)arg);
        usleep(500);

        pthread_mutex_lock(&readerOn);
        readers--;
        if(readers == 0) {
            pthread_mutex_unlock(&writeOk);
        }
        pthread_mutex_unlock(&readerOn);
    }
    return NULL;
}

int main() {
    pthread_mutex_init(&writeOk, NULL);
    pthread_mutex_init(&readerOn, NULL);

    for(int i = 0; i < N; i++) {
        pthread_create(&thread_writer[i], NULL, writer, NULL);
        pthread_create(&thread_reader[i], NULL, reader, (void*)(long)i);
    }

    for(int i = 0; i < N; i++) {
        pthread_join(thread_writer[i], NULL);
        pthread_join(thread_reader[i], NULL);
    }

    pthread_mutex_destroy(&writeOk);
    pthread_mutex_destroy(&readerOn);

    return 0;
}
By understanding and implementing these synchronization techniques, you can effectively manage multithreaded programs, ensuring safe and efficient execution of concurrent tasks.