Saturday, July 30, 2011

Something about Interrupt, Mutex and Semaphore

The details of interrupt and mutex are not that simple. Be aware of the following bullets:

  1. Disable/Enable interrupt can be used to implement mutex. It is simple but flawed.
  2. For multi-processors, disable interrupt may not be useful, unless you disable interrupt on all processors, which will be prohibitively expensive.
  3. Atomic instruction, such as test-and-set, can be used to implement mutex. test-and-set is an atomic instruction which writes 1 to a memory location and fetch the old value of that location. For example, a spin-lock implementation is given as follow:
  4. while (test_and_set(lock)==1);
  5. Besides,  other atomic instructions such as exchange, compare&swap, load linked and conditional store can also be used.
  6. For the example given in 3), we will busy wait. To minimize the waiting time, we can do the following (add a guard variable):
  7. while (test_and_set(guard)==1);
    
    if(lock_value == 1)
    {
       put the thread in the waiting queue for the lock;
       go to sleep;
       guard = 0;
    }
    else
    { 
       lock_value = 1;
       guard = 0
    }
  8. Spin lock can sometimes delay releasing the lock. For example, thread A get switched out right after grabbing the lock. Thread B kicks in and try to grab the lock, but the lock has already been grabbed. Thread B has to be busy waiting, which will delay the switching back to thread A.
  9. Semaphore represents the number of resources that are still available to simultaneous users (e.g. there are still 4 available slots)..   
  10. Besides, we can also use implement some lock-free data structure in pursuit of better performance. These structures usually leverage some atomic instructions or atomic variables (the read/write to the variable is atomic, e.g. pointer type.). Some data structures are weak enough to be implemented without special atomic primitives, e.g., FIFO queue.

Friday, July 29, 2011

Things to Remember about memcpy()

If you want to implement memcpy(), you need to pay attention to the following things:
  1. if you can use wider data type, use it (e.g., copy a 32 bit instead of 8 bit).
  2. leverage the instruction set provided by the underlying architecture (processor). For example, some architecture has *p++, some only has *(++p).
  3. memory alignment. Sometimes if you want to do 32bit copy, the instruction may require memory address to be aligned. Therefore some extra work needs to be done.
  4. use pointer such as const char * for src.
  5. if the src and dest memory address overlap with each other, some extra work needs to be done.

Some Tricks about Optimizing Branches

You should be cautious when using branches in your code. Sometimes the performance could be hurt.
while (++i > count)
The above code may generate complex machine code. It is much better to let the compiler to generate code that utilizes the processors compare instructions in an efficient way. This means creating loops that terminates when a compare value is zero, which is as follow:
while (count--)
The following code is also not good:
while (count-=2)

Sunday, July 24, 2011

Find the Least Common Ancestor of Two Tree Nodes

Problem: Given two nodes in a tree, find the least common ancestor of them.

Solution: This is not a difficult problem. If there is parent pointer, things will be easier. However, simple solution still exist for tree nodes without parent pointer. See the code below:

node * common_ancestor(node *root, node *n1, node *n2)
{
   if(root==null || n1 == null || n2 == null)
     return null;

    if(n1 == root || n2 == root) return root;
   
   node * left = common_ancestor(root->left, n1, n2);
   node * right = common_ancestor(root->right, n1, n2);
   
   if(left && right) return root;
   
   return left ? left : right; 

}

More: if we need to do many common_ancestor() operations, there is a more efficient off-line algorithm called "Tarjan's off-line least common ancestors algorithm". It can get the least common ancestors for m pairs of nodes in just one tree traversal. The main idea is to leverage disjointed forest  with path compression and union by rank.

Friday, July 22, 2011

General Monty Hall Problem and Information Theory

Problem: There are three doors and only there is one door behind which there is a prize.You first select a door, then the host of the game will open one door behind which there is no prize (he can't open the door you had selected). Then you are given the choice to switch the door or not. This is the typical Monty Hall problem people talk about. The general form is that n doors with only one door behind which there is a prize. The host of the game will open m doors (m<n-1) behind which there are no prize. Then you are given the choice to switch to another door.

Solution: The most most important observation about this problem is that "probability" is actually not about "randomness", but about information. How much information we have will influence the probability".  Now let's first look at the basic form of the Monty Hall problem.

  • assume you chose door A, the probability that you had made the correct choice, P(A),  is 1/3. Assume the host opened the door C (the case for door B is the same), let us denote this action as O. The probability, P(A|O), which means the probability that you had made the correct choice given the host opened the door C, is what we are interested in. Actually P(A|O) = P(A) = 1/3, since unless you move the prize, there is no way you can change the odds of your original choice.
  • Besides, we can systematically calculate P(A|O). According to Bayes's theorem, P(A|O) = P(O|A)*P(A)/P(O). We know P(A) = 1/3. P(O|A) should equal 1/2, since if A is the right answer, B and C are both empty doors. The the probability for the host to open door C is simply 1/2. Then we need to calculate P(O). 
  • P(O) = P(O|A)*P(A) + P(O|B)*P(B) + P(O|C)*P(C). It is easy to know, P(O|C) = 0, also  P(O|A)*P(A) =1/6. We have P(O|B) = 1. The reason is that we had already chosen A, but B is the right answer, so the only choice for the host is C. Therefore, P(O) = 1/6+1*1/3 = 1/2. Then we have P(A|O) = 1/3.
  • Then the probability to win if we switch is P(B|O) = P(O|B)*P(B)/P(O) = 1*1/3 / (1/2) =2/3, so we need to switch!
Now let's try to tackle the general problem.

  • The probability to win if we stick to the original choice (assume it is A again), P(A) = 1/n, also we have P(A|O) = 1/n.
  •  The probability to win if we switch, P(S|O) = P(We switch to the correct door | Our original choice is wrong) = (1/(n-m-1))*(1-1/n) = ((n-1) / (n-m-1))*1/n). It is easy to know P(S|O)  > P(A|O), so we still need to switch.
  • Thinking in the way of information theory, after host reveal some empty doors, we are given more information. These information will change the probability distribution!
See Also: Monty hall and Bayesian probability theory,  The Monty Hall problem -- over easy

The Mystery about sizeof()

sizeof() is to get the size of a class or an class object. It might be simple conceptually, but there are some details you may not know.

  • what does sizeof() return?
class A
{
  static char x;
  int y;
};

int main()
{
  int s1 = sizeof(A);
}
        s1 = 4. Why s1 = 4? The size of static members will not be counted into the size of the class. The reason is that those static members are stored centrally and shared by all the instances of the class.
  • what does sizeof() return?
class A
{
  char x;
  int y;
};

int main()
{
  A a;
  int s1 = sizeof(A);
  int s2 = sizeof(a);
}
        s1 = 8 and s2 = 8. Why s1 = 8? The size it really needs is just 5 bytes. The reason is for alignment so padding is added. Why s2 = 8? sizeof(a) is equivalent to sizeof(A). Moreover, the padding scheme will sometimes make the order of data members matter. For example, if we have "char a; int x; char b;", the size will be 12. However, if we have "char a; char b; int x;", the size will be 8.
  • what does sizeof() return?
class A
{
  char x;
  int y;
  virtual void bar();
};

int main()
{
  int s1 = sizeof(A);
}
        s1 = 12. Why s1 = 12? Since virtual function is defined, 4 extra bytes need to be allocated for the pointer to virtual function table.

  • what does sizeof() return?
class A
{
  char x;
  int y;
  void bar();
};

int main()
{
  int s1 = sizeof(A);
}
        s1 = 8. Why s1 = 8? Since there is no virtual function defined, we don't need the 4 extra bytes for the pointer to virtual function table. For non-virtual function, there is a central place to find those functions, therefore we don't need such pointer.
  • what does sizeof() return?
class A
{
  char x;
  int y;
  void bar();
};

class B{
   int a;
   A aa;
   virtual void somefunction() ;
}

int main()
{
  int s1 = sizeof(B);
}
        s1 = 16. Why s1 = 16? The size of class A is 8. class B has one integer, one class A instance plus the pointer to the virtual function table. So the total size is 8+4+4 = 16 bytes.
  • what does sizeof() return?
int foo(int n)
{
  char b[n+3];
  return sizeof(b);
}

int main()
{
  int s1 = foo(8);
  
}
        s1 = 11. Why s1 = 11? In this case, at compile time, the compiler can't know the size of array b. The size is known at the run time. That is to say, sizeof() can be evaluated at run time for some case. But for the general case, it is evaluated at compile time.
  • what does sizeof() return?
class ABase{ 
        int iMem; 
}; 

class BBase : public virtual ABase { 
        int iMem; 
}; 

class CBase : public virtual ABase { 
        int iMem; 
}; 

class ABCDerived : public BBase, public CBase { 
        int iMem; 
}; 

int main()
{
   int s1 = sizeof(ABase);
   int s1 = sizeof(BBase);
   int s2 = sizeof(CBase);
   int s4 = sizeof(ABCDerived);
}
        s1 = 4, s2 = 12, s3 = 12 and s4 = 24. Why ? In this case, because BBase and CBase are derived from ABase virtually, they will also have an virtual base pointer (different from the pointer to virtual function table). So, 4 bytes will be added to the size of the class (BBase and CBase). That is sizeof ABase + size of int + sizeof Virtual Base pointer.Size of ABCDerived will be 24 (not 28 = sizeof (BBase + CBase + int member)) because it will maintain only one Virtual Base pointer.
  • what does sizeof() return? (edited on Aug 12)
void foo(int a[])
{
  cout << sizeof(a) << endl;
}

int main()
{  
   int a[10];
   foo(a);
   cout << sizeof(a) << endl;
}
    .    The sizeof() in foo() will return 4 while the one in main() will return 40. The reason is that the a in foo() is actually interpreted as a integer pointer.

Thursday, July 21, 2011

The Ugly Thing about char [], char *, const char *, char * const and char const *

These concepts seem simple, but mistake can be made if you haven't thoroughly understood them.

  • is following code correct?
foo()
{
char a[]= "I HATE U!";
a[0] = 'U';
}
        Yes,  array a[] will be allocated on stack and a[0] just modifies the first character.

  • is following code correct?
foo()
{
char *a = "I HATE U!";
a[0] = 'U';
}
        Compiler won't complain, but the program will crash. The reason is "I HATE U!" is a constant that will be allocated in the constant memory region.  If we try to modify its value thru pointer a, you will be hit by seg fault.
        However,  initializing the variable  takes a huge performance and space penalty for the array (using char a[] = "XXXX"). Only use the array method if you intend on changing the string, it takes up space in the stack and adds some serious overhead every time you enter the variable's scope. Use the pointer method otherwise.

  • is following code correct?
foo()
{
cont char *a = "I HATE U!";
a[0] = 'U';
}
        No, compiler will complain.  a is a pointer points to char constant, you can modify what a points to (a's value), but you can't modify the content of the address that a points to (*a's value).

  • is following code correct?
foo()
{
char * const a = "I HATE U!";
a++;
}
        No, compiler will complain.  a is a constant pointer, therefore you can'y modify what a points to (a's value). But you can modify the content of the address that a points to (*a's value) if that address is valid to access. In the above example, the address is not valid to access.

  • is following code correct?
foo()
{
char const *a = "I HATE U!";
a[0] = 'U';
}
        No, compiler will complain. char const *a is the same as const char * a.