SE250:lab-3:sshi080

Lab Report

This lab is to determine the time taken to execute an incrementing arraylist many times.

Code used for the tests:

#include <stdio.h>
#include <time.h>

int main() {

	int i;
	clock_t time_now;
	clock_t time_after;
	double time;

	time_now = clock();

	for(i = 0; i < 100,000,000; i++) {
		i = i+1;
	}

	time_after = clock();
	time = (time_after - time_now) / (double)CLOCKS_PER_SEC;

	printf("Processing %d additions: %f seconds\n", i, time);

}

Question 1

Question 1 is using default growth factor of *2

(Growth Factor *2)

Results

• Time taken for 100,000,000 iterations: 10.122 seconds
• Time taken for 100,000,000 iterations: 10.019 seconds
• Time taken for 100,000,000 iterations: 9.995 seconds

Question 2

Growth Factor *3

• Time taken for 100,000,000 iterations: 10.194 seconds
• Time taken for 100,000,000 iterations: 10.447 seconds
• Time taken for 100,000,000 iterations: 10.339 seconds

Growth Factor *5

• Time taken for 100,000,000 iterations: 10.089 seconds
• Time taken for 100,000,000 iterations: 10.038 seconds
• Time taken for 100,000,000 iterations: 10.189 seconds

Growth Factor *1.5

Time taken for 100,000,000 iterations: 10.698 seconds Time taken for 100,000,000 iterations: 10.41 seconds Time taken for 100,000,000 iterations: 10.475 seconds

Up until now there is subtle difference between the growth factors. It's safe to conclude that the memory is being allocated fast enough, but the putting of the values inside the array is what takes up the most time.

Growth Factor *1.1

• Time taken for 100,000,000 iterations: 14.580 seconds
• Time taken for 100,000,000 iterations: 14.472 seconds
• Time taken for 100,000,000 iterations: 14.507 seconds

Once you decrease the growth factor to 1.1, it now forms the bottleneck and the times increases significantly. The array isn't expanding fast enough to add the values in, hence causing a delay.

Question 3

I increased ARRAYLIST_MIN_ALLOC to various values but not much changed until I changed it to:

50000000

Results

Time taken for 100,000,000 iterations: 9.529 seconds
Time taken for 100,000,000 iterations: 9.436 seconds
Time taken for 100,000,000 iterations: 9.437 seconds

You can notice some difference at this stage, times are shorter, however, not much.

Question 4

*Time taken for 100,000,000 iterations: 9.145 seconds
*Time taken for 100,000,000 iterations: 9.052 seconds
*Time taken for 100,000,000 iterations: 9.033 seconds

Times are definitely shorter as the array size is preallocated.
The times taken in this case is the time taken to insert the values into the array.

Question 5

I had to decrease the iterations to 1,000,000, since it would take way too long for the 100 million. The growth factor is now + 1000 incremental.

* Time taken for 1000000 iterations: 2.707 seconds
* Time taken for 1000000 iterations: 2.742 seconds
* Time taken for 1000000 iterations: 2.751 seconds

The times are longer significantly, as everytime the array runs out of space, it only allocates 1000.
Hence I had to decrease the iterations to 1,000,000 to reach a suitable time for testing.

Question 6

For this exercise, arraylist_put is used instead of push, and elements are added to the start of the array. I also changed the iterations to 100,000 since it was taking very long.

Code changed:

for (i = 0; i < 100000; i++) {
	arraylist_put(&a1, value, 0);
}

Results

* Time taken for 100000 iterations: 3.806 seconds
* Time taken for 100000 iterations: 3.837 seconds
* Time taken for 100000 iterations: 3.743 seconds

The times are clearly much longer, in fact I had to keep decreasing the 0's until 100,000.
I assume the reason for this is everytime you insert a value, you have to shift all the other values forward 1 space, hence increasing th time taken significantly.