Wednesday, August 22, 2012

Performing Inner Join and Left Outer Join in LINQ Queries

Linq supports joining just like any other querying language. Syntax is bit different from standard SQL query though. Also We need to add some logic to achieve Left Outer Join as there is no standard keyword for this.

In our example, we have list of people with their name and their address. We also have list of houses in city with their house name and owner name. 

a. Lets understand performing inner join. Inner join joins two tables based on some condition. Results will include only those entries from joined tables which match the condition. To illustrate inner join we need to find out all the people who own a house with their address. We use "join" keyword with "on" clause to achieve this inner join.  Example I have provided is self explanatory.

b. If we have to output all the people along with their house names if they own otherwise print empty string, then we can go for left outer join. In this join lets make People as left item. We use  DefaultIfEmpty() method to ensure for every People entry will appear in output result. DefaultIfEmpty() provides empty\default for each non matching sequence i.e for any People object if matching sequence in Houses is empty then DefaultIfEmpty returns single default item. In next select we can check if result is default or contains some value. If result sequence contains some value other than default, then we can output that value otherwise we can output empty string or default value.

Below example shows how Left Outer Join and Inner Joins are performed in our example:



        public static void Main(string[] args)
        {
            People p1 = new People { Name = "Manu", Address = "Marathalli" };
            People p2 = new People { Name = "Dada", Address = "BTM" };
            People p3 = new People { Name = "Saavu", Address = "Kunadanahalli" };
            People p4 = new People { Name = "Vasanth", Address = "Munnekolala" };
            People p5 = new People { Name = "Andy", Address = "Jayanagar" };
            People p6 = new People { Name = "Putta", Address = "JP Nagar" };

            Houses h1 = new Houses { HouseName = "Jaipur Palace", HouseOwnerName = "Putta" };
            Houses h2 = new Houses { HouseName = "Mysore Palace", HouseOwnerName = "Manu" };
            Houses h3 = new Houses { HouseName = "Pune Vihar", HouseOwnerName = "Vasanth" };

            List<People> people= new List<People> { p1, p2, p3, p4, p5, p6 };
            List<Houses> houses = new List<Houses> { h1, h2, h3 };

            Console.WriteLine("Inner Join Results:");
           //Inner join to print all the Person with house with house name
            var houseOwners = from p in people
                              join h in houses on p.Name equals h.HouseOwnerName
                              select new { p.Name, PersonHouseName = h.HouseName, p.Address };

            foreach (var h in houseOwners)
            {
                Console.WriteLine(h.Name+" : "+h.PersonHouseName+" : "+h.Address);
            }

            Console.WriteLine("************************************************************************");

           //Left outer join to print all the people and also their house names if they have one otherwise empty string
            Console.WriteLine("Left Outer Join Results:");
            var allppl = from p in people
                   join h in houses on p.Name equals h.HouseOwnerName into tempOwners
                   from nonOwners in tempOwners.DefaultIfEmpty()
                   select new { p.Name, PersonHouseName = (nonOwners==null)? string.Empty:nonOwners.HouseName, p.Address };

            foreach (var h in allppl)
            {
                Console.WriteLine(h.Name + " : " + h.PersonHouseName + " : " + h.Address);
            }
        }

    public class People
    {
        public string Name {set;get;}
        public string Address { set; get; }
    }

    public class Houses
    {
        public string HouseName { set; get; }
        public string HouseOwnerName { set; get; }
    }


Console Output Window:


Thursday, August 16, 2012

Threads, Threads Overhead ,Kernel Internals, Kernel Architecture and Asynchronous Methods in C# - Part 2

Thread Context Switching:


A single CPU can only do one thing at a time. Windows keeps switching between processes to give user robust & responsive system and also better overall experience. Windows Scheduler give slices of CPU time to each thread. It is called Quantum(Time period varies from architecture to architecture). After each time-slice elapses windows scheduler switches to another thread. This is called thread context switching. This switching enables multiple threads to share same CPU & hardware resources to provide "multitasking" support. 

The next thread that gets CPU might be from different process itself. In such case windows has to change to that process virtual address space as seen by the CPU before executing any code of that process or processing any data  of that process. 

Each Context switch  has to go through below steps:
  1. Save the context of the thread that just finished executing.
  2. Place the thread that just finished executing at the end of the queue for its priority.
  3. Find the highest priority queue that contains ready threads.
  4. Remove the thread at the head of the queue, load its context, and execute it.
Saving the context requires thread context must be stored somehow so that when next switch happens to that thread we can restore this information. This step of storing and restoring from thread's context structure includes,
  • Saving the values of CPU registers that were assigned to the current thread into thread's context structure inside thread's kernel object data structure.  
  • Changing virtual address space if required as explained before.
  • Loading from next thread's context into CPU registers.
This is performance overhead at the cost of giving user a responsive system. This switching would allow,
  • Avoiding CPU starvation by preempting ready threads over threads that are waiting for input or resource.
  • Execution Ready threads to be taken up according to their Priority.
  • CPU time to all the processes allowing each one to run.
  • Keep system responsive even when few threads\processes go into deadlock or infinite loop.
Hence multiple thread approach will add to number of context switches which in turn affects performance.  

Now lets see how new thread creation adds to Windows performance overhead:

When windows context switches CPU from one thread to another, previously executing thread's data and code reside in CPU cache, so that CPU does not have access RAM. This is to avoid latency in accessing information from memory. When a new thread is created, it might have to access different data and execute different code altogether. Since this will not be on CPU cache, it has to populate this data from RAM into cache, to speed up the processing speed. This might happen every time a new thread is added, thus causing performance overhead.[CLR Via C#].

Now that we understand why thread creation, destruction and maintenance causes affects performance and memory efficiency , we will see how number of threads affect GC performance.

Number of threads also affect the performance of Garbage Collector. Before collection or GC cycle, GC must suspend all the threads. GC walks through stack of each thread to mark the root of each heap object, walk their stack again to update the stack to updating the roots of objects that have moved during compaction. GC resumes all the threads only after this collection cycle. This causes GC to perform slow.

Multiple threads keep the application responsive but they also have above explained overheads. When designing an application with multiple threads we need to understand real intent of each thread and its necessity before creating one.

I will end thread overhead concepts here. In my next articles, I will go briefly into Kernel and its architecture.










Monday, August 13, 2012

Threads, Threads Overhead ,Kernel Internals, Kernel Architecture and Asynchronous Methods in C# - Part 1

Before we get into Asynchronous methods and using them, let us find answers for:

What are threads, What is a kernel object and thread kernel object,  How threads are created and destroyed, How windows handles Threads, What a thread consumes, What is Context switching, Why do we use multiple threads, What is asynchronous in terms of CLR, Why we need asynchronous programming, How is it different from traditional threaded programming, What is ThreadPool, How can we achieve asynchronous behavior using ThreadPool, How ThreadPool and CLR are related etc.

I assure you I will not get into MultiThreading concepts or Thread synchronization concepts when trying to explain threads and asynchronous programming.

Threads:


As we understand basics of thread, Thread is a basic unit of execution. Threads can be thought of as logical CPUs. We can say thread's job is to virtualize CPU. Different processes run on different threads hence each of them have an isolated environment of execution. Thread is responsible for execution of application code. Also, Threading allows us to deviate from current or main thread and execute some computation or some method on different thread. We mostly use multithreading in scenarios where we need to keep the UI responsive irrespective of things going on underneath, when we need to compute\parse\work with large information which might not be of immediate concern, backup and restore activities which need not keep user idle, waiting for keystrokes or waiting for other processes or waiting on events etc.

Aim of any application is to avoid keeping user idle while he waits for something to happen. Threading allows to create separate execution context for these event based or computing based methods or I/O wait methods while letting the user work on the application. 

Everything sounds good and concept of threading seems to meet all our parallel execution or background execution needs. Don't get into parallel execution right away! We need to understand many other things before we get into parallel execution.

Quick Notes here:

a. All threads of a process share its virtual address space and system resources.

Threads Overhead: 


Thread is an OS concept than language or framework feature. Threads do have overhead like performance and space overhead associated with them. Two majors types of overhead with Threads are:

1. Memory & Resources that are associated with Thread.
2. Context Switching between Threads

OS allocates memory for each thread creation. Memory is allocated for different purposes. We will see each of them in brief. Every thread contains each of the following:

1. Thread Kernel Object:


Kernel object is a block of memory allocated by the kernel. This memory block is a data structure that contains and maintains information about the object. Typical Kernel objects are File objects, pipe object, mutex object, file mappings etc. In general any kernel(OS) function called by your application, that returns an handle back to the application may create a kernel object, but not always. An Application has to keep track of all kernel objects that are created by its process. In turn application can keep track of kernel objects by their handles. These handles can be later used by the process to clear off all the resources\objects that process created. Consider example of process. Process object is also a kernel object. Whenever a process is created, a table is created in which indexes of all the objects used by process are stored. Any kernel objects created by your process gets an entry in this table. 

Handle is nothing but the index to this kernel object's entry in this process table. Kernel takes care clearing a kernel object whenever the usage count of that object becomes zero.

Quick points here:

a. Usage count is the common property across all these kernel object data structures. 
b. Closehandle will decrease the usage count of kernel object by 1. It will cleared off only when the usage count reaches 0. Hence a kernel object may remain in memory even after the process dies. 
Does not this point touch something about "Disposing" unmanaged resources in our managed code? Yes, you got it! 

Now back to threads, OS creates and allocates a kernel object data structure for each thread created. This data structure contains information about thread. This data structure also contains information about "Thread context". This is a memory block that contains set of CPU registers. When Windows is running on a machine with an x86 CPU, the thread’s context uses about 700 bytes of memory. For x64 and IA64 CPUs, the context is about 1,240 and 2,500 bytes of memory, respectively.[CLR Via C#]. Each thread maintains exception handlers, a scheduling priority, thread local storage, a unique thread identifier, and a set of structures that system requires. These all information will be part of kernel object data structure.

Thread Context includes thread's set of CPU's registers, kernel stack, thread environment block and user stack in the address space of user's process. We will see each of this concept one by one.

2. Thread Environment Block(TEB or TIB): 


TEB is also called as Thread information Block (TIB). TEB is user-mode portion of Windows thread control structures. Structure of TEB can be seen here. TEB structure should not be directly accessed .  This contains head of thread's exceptional handling chain. 
This also contains storage for data that is local to the thread and also some data structures that can be used by user interface modules like OpenGL and GDI. This structure consumes 1 page of memory.

More information about TEB and viewing TEB information can be found here.

3. User Stack:


a. This stack is used to store all local variables and parameters passed to methods.
b. It also contains address indicating what thread should execute next after returning from current method.

1MB is allocated by default by windows for a thread's user stack.

4. Kernel Stack: 


In simple terms, this is the stack used by kernel. Any parameters that are passed from user-mode code to kernel are copied from thread's user stack to thread's kernel stack. OS does this copying. Kernel also stores local variables that are used by thread's kernel method on this stack. This stack is used by kernel to store all the arguments that are passed to other kernel methods, to store all local data of those functions and to store return addresses.

All arguments passed to kernel method is validated before OS starts operating on them. Once OS starts operating on these arguments , application will not be able to modify these arguments' values. The kernel-mode stack is 12 KB when running on a 32-bit Windows system and 24 KB when running on a
64-bit Windows system.

5. DLL Thread ATTACH and Thread DETACH notifications:


Whenever a thread is created in a process, windows calls DLLMain methods of all the dlls that are loaded in the process by passing DLL_THREAD_ATTACH flag. Also when a thread dies, windows calls DLLMain method with DLL_THREAD_DETACH flag on all the dlls that are loaded in the process. This may be required to initialize the thread with expected state as the executing library wants it.

Imagine the case where  there are numerous dlls loaded in our process and windows has to call DLLMain method on all dlls for each thread creation and destruction. That sure is a overhead, is not it?

All the above factors that a thread contains makes us understand, memory (space) and performance (time) overhead that is involved in thread creation, destroying and keeping it alive.

But this is not all, Context Switching between threads also adds to performance overhead. Let us see this in detail in my next article.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
I will continue with more information about context switching adding to thread overhead, more into kernel and OS architecture and need for asynchronous methods in next my article.

Note: This article is the information that I pooled from CLR Via C# book, MSDN articles, University websites, StackOverflow answers, Albahari's C# 4.0 Nutshell etc. If you have any problem with content please let me know.

Friday, August 10, 2012

Find Whether Each Element of One Array Occurs Same Number of Times In Second Array - O(n)


Problem:
Given two arrays find out if each element in array1 occurs same number of time in array2 :-
input = {2,3,4,2,3}
{3,2,3,2,4}
output = true

Solution 1:

Below solutions assumes that numbers are positive. If two arrays contains same numbers in any order then XOR of all elements of one array must be same as XOR of all elements of another array.


This does not work in case where XOR result of two arrays are same. As Anshu Pointed out in his comments e.g.  [36, 74] is same as [98, 12] See my other solutions in such case.

        static bool AreTheySameArrays(int[] arr1, int[] arr2)
        {
            if (arr1.Length != arr2.Length) return false;
            int xor1 = arr1[0]; int xor2 = arr2[0];
            for (int i = 1; i < arr1.Length; i++) { xor1 = xor1 ^ arr1[i]; xor2 = xor2 ^ arr2[i]; }
            return (xor1 == xor2);            
       

Solution 2:

This solution covers all the cases.  This approach uses brute force approach of keeping the count of each element in first array and reducing the same when we find the same element in second array. Finally, we iterate over this count list to find whether all the elements have count as zero. If not return false.



        static bool AreTheySameArraysUsingDictionary(int[] arr1, int[] arr2)
        {
            if (arr1.Length != arr2.Length) return false;
            Dictionary<int, int> countTable = new Dictionary<int,int>();
            for (int i = 0; i < arr1.Length; i++)
            {
                if (countTable.ContainsKey(arr1[i])) { countTable[arr1[i]]++; }
                else countTable.Add(arr1[i], 1);
            }

            for (int i = 0; i < arr2.Length; i++)
            {
                if (countTable.ContainsKey(arr2[i])) { countTable[arr2[i]]--; }
                else return false;
            }
            foreach(KeyValuePair<int,int> entry in countTable)
            {
                if (entry.Value != 0) return false;
            }
            return true;
        }


Note:
Solution is not tested regressive. If you find it not working let me know. 

Monday, August 6, 2012

Longest Common Substring Problem - Dynamic Programming (C#)

Given two strings, we need to find out the longest sub string of first string which is also present in second string. 

Let us understand what sub strings are, sub strings of a string "manu" are 'm', 'a','n','u','ma','man','an', 'anu', 'nu'. We are only concerned about sub strings but not all permutations of the given string . 

Let us take example of strings, "hello" and "yellow". The common sub strings for these two are many but we need to find out the longest one which is "ello" in this case. Yes, now we get the idea. This can easily be solved in a recursive way. This problem is where we need to use previously computed result and build solution over it. Common sub string will start with a character that is common in both string 1 and string 2. With compromise to time and space we can solve above problem in O(m*n) time and O(m*n) space using straight away approach. Since we use previously computed values, we can store them and avoid extra computations and thus make this solution belong to category of "Dynamic Programming". 

For each character str1[i] we loop with all the characters in str2. If str1[i] matches with any character in str2, we can say common sub string  exists here which is of length (length of longest common sub string of str1[1..i-1], str2[1..j-1] +1) or starts here which is of length 1. We will use a two dimensional array of dimensions [str1.len, str2.len] to store, longest common sub string at that point [i,j].

if str1[m] == str2[n] 

     LCS(Str1[1..m], str2[1..n]) = LCS(str1[1..m-1],str2[1..n-1]) +1
else
      LCS(Str1[1..m], str2[1..n]) = 0

For "hello" and "yellow" above mentioned LCS method can be explained with below table:










This wiki link explains this solution better using tables to store intermediate values and solving complete problem by solving smaller problems. We will code above explained solution using C#. We need to iterate over each character of string 2 inside each character looping of string 1 and make sure we update lcs_so_far whenever we come across lcs of common sub string of greater height. We can use the length and last index of common sub string to actually print the longest common sub string.

Below implementation does not handle boundary or any special checks. It is only to explain the longest common sub string algorithm. [Tested with multiple inputs]

Code:

        public static void PrintLongestCommonSubstring(char[] str1, char[] str2)
        {
            int[,] l = new int[str1.Length, str2.Length];
            int lcs = -1;
            string substr = string.Empty;
            int end = -1;
            
            for (int i = 0; i < str1.Length; i++)
            {
                for (int j = 0; j < str2.Length; j++)
                {
                    if (str1[i] == str2[j])
                    {
                        if (i == 0 || j == 0)
                        {
                            l[i, j] = 1;
                        }
                        else
                            l[i, j] = l[i - 1, j - 1] + 1;
                        if (l[i, j] > lcs)
                        {
                            lcs = l[i, j];
                            end = i;
                        }

                    }
                    else
                        l[i, j] = 0;
                }
            }

            for (int i = end - lcs + 1; i <= end; i++)
            {
                substr += str1[i];
            }
            
            Console.WriteLine("Longest Common SubString Length = {0}, Longest Common Substring = {1}", lcs, substr);
        } 


Longest Common sub string problem can be solved efficiently using suffix trees. We can achieve almost linear time with suffix trees or even "Trie". I will cover "Trie" and\or suffix trees in some other article. "Trie" allows you easy text search like suffix trees. They both allow a text to be searched in quicker time but may need space and time to create the tree.

Note: Using trees will be ideal here.