Key Analytics of Algorithm

Points to consider when analysing an Algorithm:

1. A sequence of statements which is executed only once is O(1). It does not depends on how many statements are in the sequence.
2. If a problem of size n can be solved with a simple loop
         for(i=0;i < n;i++)
            {statements;}
   where statements is an O(1) sequence of statements then the time complexity is n*O(1) or O(n)
3. If we have 2 nested loops,
       for(j=0;j < n;j++)
           for(i=0;i < n;i++)
                {statements;}
   then we have n repetitions of an O(n) sequence .so the complexity is n*O(n) which is O(n²)
4. suppose if the inner loop depends on the outer loop index,
       for(j=0;j < n;j++)
           for(i=0;i < j;i++)
                {statements;}
   The inner loop gets executed j times. so the total is n*(n+1)/2 times.so the complexity is O(n²). The result is same as the result for 2 nested loops.so the variable number of iterations of the inner loop doesnt affect.
5. In a loop if a index jumps by an increasing amount in each iteration, such as
       n=1;
       while(n < =x)
       {
           statements;
           n=2*n;
       }
   in which n takes values 1,2,4,8..until it exceeds n.ie n=2⁰,2¹,2²,2³.......This sequence has 1+Log₂n values.so the complexity is O(log₂n)
6. If the number of iterations of the loops decreases by a constant factor with every iteration
       h=n;
       while(h > 0)
       {
           for(i=0;i < n;i++)
               statements;
           h=h/2;
       }
   then there are log₂n iterations of the outer loop and n iterations of the inner loop. so the overall complexity is O(nlogn)

Java Threads

Threads in Java

Performance factors

Important  factors to the performance of a Java program is separated into two main parts:

• Memory Consumption of the Java program
• Total runtime of a program

Memory

Java handles its memory in two areas. The heap and the stack

Native Memory

Native memory is the memory which is available to a process, e.g. the Java process. Native memory is controlled by the operating system (OS) and based on physical memory and other physical devices, e.g. disks,etc.

The processor (CPU) of the computer computes the instructions to execute and stores its computation results into registers. These registers are fast memory elements which stores the result of the CPU. The processor can access the normal memory over the memory bus. A amount of memory a CPU can access is based on the size of the physical address which the CPU uses to identify physical memory. A 16-bit address can access 2^16 (=65.536) memory locations. A 32-bit address can access 2^32 (=4.294.967.296) memory locations. If each memory area consists of 8 bytes then a 16-bit system can access 64KB of memory and the 32-bit system can access 4GB of memory.

An OS normally uses virtual memory to map the physical memory to memory which each process can see. The OS assigns then memory to each process in a virtual memory space for this process and maps access to this virtual memory to the real physical memory.

Current 32-bit systems uses an extension (Physical Address Extension (PAE)) which extends the physical space to 36-bits of the operation system. This allows the OS to access 64GB. The OS uses then virtual memory to allow the individual process 4 GB of memory. Even with PAE enabled a process can not access more then 4 GB of memory.

Memory in Java

Java manages the memory for use. New objects created and placed in the heap. Once your application have no reference anymore to an objects the Java garbage collector is allowed to delete this object and remove the memory so that your application can use this memory again.

Java Heap

In the heap the Java Virtual Machine (JVM) stores all objects created by the Java application by using the "new" operator. The Java garbage collector (gc) can logically separate the heap into different areas, so that the gc can faster identify objects which can get removed

The memory for new objects is allocated on the heap at run time. Instance variables live inside the object in which they are declared.

"Java Stack"

Stack is where the method invocations and the the local variables are stored. If a method is called then its stack frame is put onto the top of the call stack. The stack frame holds the state of the method including which line of code is executing and the values of all local variables. The method at the top of the stack is always the current running method for that stack. Threads have their own call stack.

Escape Analysis

Java objects are created in the heap. The programming language does not offer the possibility to let the programmer decide if an objects should be generated in the stack. But in certain cases it would be desirable to allocate an object on the stack, as the memory allocation on the stack is cheaper then the memory allocation in the heap, deallocation on the stack is free and the stack is efficiently managed by the runtime.

The JVM uses therefore internally escape analysis to check if an object is used only with a thread or method. If the JVM identify this it may decide to create the object on the stack, increasing performance of the Java program.

Garbage Collector

The JVM automatically re-collects the memory which is not used any more. The memory for objects which are not referred any more will be automatically released by the garbage collector.

To see then the garbage collector starts working add the command line argument "-verbose:gc" to your virtual machine.