SE250:Lab-2006-05-30:mgar059

Amortised Analysis

Important Conclusions

In this graph you can see the general levels. as the array runs out of space, the graph makes a "step" when a copy operaion is run. This is because the array is being copied into a new larger array.

There seems to be a lot of unexpected noise. This is due to varous memory management issues. As arrays are derefrenced, or even randomly, the garbage collector runs. This creates unexpected calculations of time costly operations.

This can be reduced by using the "System.gc()" command before operations to purge the heep. By using a large heep which does not need the garbage collection to be run e.g. "-Xmx1000m"

Another issue causing a regular pattern of fluctuation in results, is the JVM switching between 40mb blocks of memory. This can be seen by using different MINIMUM memory allocations at the start. This can be done using "-Xms1000m" along with "-Xmx1000m". This has a big effect on the results and makes it look more like what is theoretically expected.

NOTE: These results were gathered without expanding the heep size or using the "System.gc()" command where possible. This is because in a practical situation, these are factors which will effect the preformance of the add operation.

When the the algorithm for increasing the size of the array is a factor, the time for the operations follows a staggered linear pattern. When this is changed to a constant increment, the time for inserting elements degrades to a costly quadratic function.

Question 1

• Objective: Run an experiment to determine the time taken to insert N elements into the set, for suitably chosen values of N1.

class SimpleIntList {
    int [] elements = new int[ 16 ];
    int size = 0;
    void add( int x ) {
        if ( size >= elements.length ) {
            int [] newes = new int[ (int)(elements.length * 2.0) ];
            System.arraycopy(elements, 0, newes, 0, size);
            elements = newes;
        }
    elements[ size++ ] = x;
    }
}

Results for question 1

In order to obtain results for the size of arrays being measured, the memory had to be extended using "-Xmx500m" to increase the heep size to 500mbs.

	public static void test(int number){
		SimpleIntList list = new SimpleIntList();
			long start = System.currentTimeMillis();
			for(int i = 0; i < number; i++){
				list.add(1);
			}
			long end = System.currentTimeMillis();
			System.out.println(end-start + " milliseconds taken for " + number + " random numbers");
	}

Some results were:

• 467 milliseconds taken for 10000000 numbers
• 934 milliseconds taken for 20000000 numbers
• 1448 milliseconds taken for 30000000 numbers
• 1837 milliseconds taken for 40000000 numbers
• 19821 milliseconds taken for 50000000 numbers
• 17330 milliseconds taken for 60000000 numbers

File:250Mgarlabresult1.JPG

Growth factor of 2, initial array size of 16

In this graph you can see the general levels. as the array runs out of space, the graph makes a "step" when a copy operaion is run. This is because the array is being copied into a new larger array.

There seems to be a lot of unexpected noise. This is due to varous memory management issues. As arrays are derefrenced, or even randomly, the garbage collector runs. This creates unexpected calculations of time costly operations.

This can be reduced by using the "System.gc()" command before operations to purge the heep. By using a large heep which does not need the garbage collection to be run e.g. "-Xmx1000m"

Another issue causing a regular pattern of fluctuation in results, is the JVM switching between 40mb blocks of memory. This can be seen by using different MINIMUM memory allocations at the start. This can be done using "-Xms1000m" along with "-Xmx1000m". This has a big effect on the results and makes it look more like what is theoretically expected.

Question 2

Repeat of question 1 with a groth factor of 1.5 instead of 2.

Results for question 2

These results appear to be slightly better than the results for Question 1

• 499 milliseconds taken for 10000000 random numbers
• 934 milliseconds taken for 20000000 random numbers
• 1434 milliseconds taken for 30000000 random numbers
• 1807 milliseconds taken for 40000000 random numbers
• 1823 milliseconds taken for 50000000 random numbers
• 2633 milliseconds taken for 60000000 random numbers

File:250Mgarlabresult2.JPG

Growth factor of 1.5, initial array size of 16

For this experiment the results were similar to those of question one. Is is easier to see the steps where the array size is increasing. It is also easier to see the difference in step sizes increasing, as more elements have to be copied.

Question 3

Repeat of question 1 with a groth factor of 1.1 and 5.0.

Results for question 3

For a growth factor of 1.1

• 1512 milliseconds taken for 10000000 random numbers
• 2727 milliseconds taken for 20000000 random numbers
• 3912 milliseconds taken for 30000000 random numbers
• 5206 milliseconds taken for 40000000 random numbers
• 6437 milliseconds taken for 50000000 random numbers
• 7559 milliseconds taken for 60000000 random numbers

File:250Mgarlabresult3.JPG

When the growth factor is 1.1, the time taken to insert is clearly linear. There are many copy operations making the cost of inserting elements more costly at each point. As the array increases in size by very small amounts, the setps are not very visible.

For a growth factor of 5.0

• 436 milliseconds taken for 10000000 random numbers
• 483 milliseconds taken for 20000000 random numbers
• 795 milliseconds taken for 30000000 random numbers
• 4099 milliseconds taken for 40000000 random numbers
• 3927 milliseconds taken for 50000000 random numbers
• 8432 milliseconds taken for 60000000 random numbers

File:250Mgarlabresult4.JPG

Where the growth factor is large, the length before each step is greater. Also the size of the steps start out greater. In the second step a lot of noise is visible. This is due to the JVM switching between the 40 mb blocks of memory. This is reduced and when the minimum size of the heep is increased.

As the growth factor reaches 1, the performace starts to suffer.

Question 4

Using an initial allocation size. SimpleIntList now has the constructor:

    SimpleIntList(int n){
    	elements = new int[n];
    }

Results for question 4

When a large initial size of elements, the time taken for inserts appears to improve. This is because the number of times the array grows is less. The bigO for the majority of operations is O(1).

Results for question 5

when we replace the way the array increases in size as it runs out of free elements, from a factor to a constant factor of 1000 elements, the runtime changes from a roughtly linear runtime, to a quadratic runtime