The Internal Architecture of JVM

Java Virtual Machine components are depicted in below diagram. Each time we run java_application/java_class, an instance of JVM gets created.

Class Loader Subsystem

Class loader subsystem loads classes and interfaces with fully qualified names into the JVM.

Execution Engine

Execution Engine executes all instructions contained by methods of a loaded class.

While executing a Java program, JVM requires memory for storing objects ,local variables, method arguments, return values, and intermediate computational results and JVM does that memory management on several runtime data areas. The specification of runtime data areas is quite abstract. This abstract nature of JVM specification helps different designers to provide implementation on wide variety of OS and as per choice of the designers. Some implementations may have a lot of memory in which to work, others may have very little. Some implementations may be able to take advantage of virtual memory, others may not.

Method Area and Heap
Each instance of the Java virtual machine has one method area and one heap. These areas are shared by all threads running inside the virtual machine. When the virtual machine loads a class file, it parses information about class type from the binary data contained in the class file. It stored the type information into the method area. As the program runs, the virtual machine places all objects the program instantiates onto the heap.

PC Registers and Stacks
When a new thread is created, it gets its own pc register (program counter) and Java stack. If the thread is executing a Java method (not a native method), the value of the pc register indicates the next instruction to execute. A thread’s Java stack stores the state of Java (not native) method which includes its local variables, the parameters with which it was invoked, its return value (if any), and intermediate calculations.

The Java stack is composed of stack frames (or frames). A stack frame contains the state of one Java method invocation. When a thread invokes a method, the java virtual machine pushes the newly created frame onto that thread’s Java stack. When the method completes, the virtual machine pops and discards the frame for that method.

In JVM ,the instruction set uses the Java stack for storage of intermediate data values. The stack-based architecture of the JVM’s instruction set optimizes code done by just-in-time and dynamic compilers.

Native Method Stacks

The state of native method invocations is stored in an implementation-dependent way in native method stacks, in registers or other implementation-dependent memory areas.

finding three elements in an array whose sum is equal to a given number

Finding three elements in an array whose sum is equal to a given number(say trisum)

Here, for every element(arr[i]) that we pick, trisum-arr[i] gives us the bisum (algorithm to find a pair of elements that matches to sum k), hence we make use of our bisum algorithm to find a pair that matches to sum k

Assumption: The input array is sorted.

Example
arr: {1,2,3,4,5} and trisum is 8 then tri pairs are 1,3,4 and 1,2,5
Here lets say arr[i] is 1 then bisum=trisum-arr[i] i.e, bisum=8-1=7 therefore we should run bisum algorithm for sum 7

Time complexity for this algo: O(n^2) because for every element we need to find set of pairs

Note: If the array is not sorted the the complexity would be nlogn + O(n^2)

/**
 * find 3 elements in an array, that sum up to particular number with best
 * complexity
 * 
 * @author ntallapa
 * 
 */
public class TriPairSumCloseToK {

	public void getTriPair(int[] arr, int expectedTriSum) {
		for (int i = 0; i < arr.length; i++) {
			int expectedBiSum = expectedTriSum - arr[i];
			String output = getPair2(arr, expectedBiSum, i);
			if(!output.equalsIgnoreCase("")) {
				System.out.println(arr[i]+","+output.toString());
			}
		}
	}
	
	/**
	 * Find the pair in an array whose sum with complexity O(n). This assumes
	 * the array passed is sorted array and there are no duplicates in the 
	 * array
	 * @param arr
	 *            input array of elements
	 * @param expectedBiSum
	 *            sum for which pair of array elements needs to be searched
	 */
	public String getPair2(int[] arr, int expectedBiSum, int ignoreIndex) {
		int start = 0;
		int end = arr.length - 1;
		int sum = 0;

		// output array to record matching pairs
		StringBuilder arrs = new StringBuilder();

		while (start < end) {
			//
			if(start == ignoreIndex)
				start++;
			//
			if(end == ignoreIndex)
				end--;
			
			sum = arr[start] + arr[end];
			if (sum == expectedBiSum) {
				// we have found one pair, add it to our output array
				arrs.append(arr[start] + "," + arr[end] + ";");
				start++;
				end--;
			} else if (sum < expectedBiSum) {
				// if the sum of the pair is less than the sum we are searching
				// then increment the start pointer which would give us the sum
				// more than our current sum as the array is sorted
				start++;
			} else {
				// if the sum of the pair is greater than the sum we are 
				// searching then decrement the end pointer which would give us 
				// the sum less than our current sum as the array is sorted
				end--;
			}
		}
		return arrs.toString();
	}

	/**
	 * Client to test
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		TriPairSumCloseToK p = new TriPairSumCloseToK();

		// sorted array algo
		int[] arr1 = { 1, 2, 3, 4, 5 };
		p.getTriPair(arr1, 1);

	}
}

algorithm to find first unrepeated character in a string

We can do it in two different ways

  • Algorithm with O(2n) time complexity and O(1) space complexity
  • Algorithm with O(2n) time complexity and O(n) space complexity

Algorithm with O(2n) time complexity and O(1) space complexity
Here we take a fixed size (256 in which all characters small and caps fall into) integer array and we scan the string two times

  • First scan we increment the counter in integer array for every character that appears in string
  • In second scan, we look for counter value 1 which gives the first unrepeated character in string

Note: Here space complexity is O(1) because the int array size is always constant irrespective of the string we pass

	public static char firtUnrepeatedCharInString(char[] s) {
		char result = '\0';
		int[] counts = new int[256];
		for (char c : s) {
			counts[c]++;
		}

		for (int i = 0; i < s.length; i++) {
			if (counts[s[i]] == 1) {
				result = s[i];
				break;
			}				
		}

		return result;
	}

Algorithm with O(2n) time complexity and O(n) space complexity
Here we take hashmap and we scan the string two times

  • First scan we insert every character that appears in string as key and its number of appearances as value in hashmap
  • In second, scan we look for key whose value is 1 which gives the first unrepeated character in string
	public static char firtUnrepeatedCharInString(char[] s) {
		char result = '\0';
		HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
		for (char c : s) {
			Object o = hm.get(c);
			if(o == null) {
				hm.put(c, 1);
			} else {
				int ctr = hm.get(c);
				hm.put(c, ++ctr);
			}
		}

		for (char c : s) {
			int ctr = hm.get(c);
			if(ctr == 1) {
				result = c;
				break;
			}
		}
		return result;
	}

Security aspects of standalone utilities in java

Security aspects of java application development

  • make sure the utility does not accept any file input that can be used in edit (write) mode, this way hacker can pass some system files to corrupt the system
  • Do not store any confidential data of the client/project in string literals because string literals are placed in perm heap space and hence these objects can be dumped to expose all the information
  • Handle all passwords in character arrays as string literals are a security threat (same explanation as above)
  • Do not construct SQL queries from any property files without prepared statement as they are prone to SQL injection attacks.
Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey