View source for SE250:lab-3:bvic005

For this lab we are testing the speed of an array list data structure.

=Task1=

First we had to test the time taken to insert a large number of values into an array list, using the arraylist_push function. It took me a short while to remember/work out how to use the array list structure, but once i had, the code was quite simple. All i needed was a for loop pushing the same value into the array(i used a int with the value 128) and a couple of clock calls to measure the time(and a print statement to display the times). After i had that code running, i added a for loop that would change the number of number to push.

Code:
<pre>
#include "arraylist.h"
#include <stdio.h>
#include <time.h>

int task1() {
	int counter, n;
	double clockStart, clockFinish;
	int num1 = 128;
	ArrayList newList1;

	for (n = 1000000; n < 1000000000; n *= 2 ) {

		arraylist_init( &newList1 );

		clockStart = clock();

		for (counter = 0; counter < n; counter++) {

			arraylist_push( &newList1, num1 );

		}

		clockFinish = clock();

		printf("Time for %d Pushes: %g s\n", n, (clockFinish - clockStart)/CLOCKS_PER_SEC );

		arraylist_clear(&newList1);
	}

	return 0;
}

int main() {
	printf("Task1: \n");
	task1();

	return 0;
}
</pre>

Results:
I initially used three machines to test this. The lab machine running cygwin, login.cs via ssh, and shell.ece via ssh.

Lab:
<pre>
Time for 1000000 Pushes: 0.062 s
Time for 2000000 Pushes: 0.094 s
Time for 4000000 Pushes: 0.219 s
Time for 8000000 Pushes: 0.453 s
Time for 16000000 Pushes: 0.89 s
Time for 32000000 Pushes: 1.766 s
Time for 64000000 Pushes: 3.641 s
Time for 128000000 Pushes: 7.157 s
assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 39
     13 [sig] arraytest 5180 h:\year2\250\lab3\arraytest.exe: *** fatal error -
called with threadlist_ix -1
Hangup
</pre>

As you can see, when attempting to push 256million ints, the program ran out of memory.

login.cs:
<pre>
Time for 1000000 Pushes: 0.08 s
Time for 2000000 Pushes: 0.18 s
Time for 4000000 Pushes: 0.37 s
Time for 8000000 Pushes: 0.74 s
Time for 16000000 Pushes: 1.47 s
Time for 32000000 Pushes: 2.93 s
Time for 64000000 Pushes: 5.88 s
Time for 128000000 Pushes: 11.76 s
Time for 256000000 Pushes: 23.46 s
arraytest: arraylist.c:39: ensure_capacity: Assertion `alist->arr != (element_t*)0' failed.
Aborted (core dumped)
</pre>

This was slightly slower than the lab machine, but it managed 256million pushes, before running out of memory attempting 512million.

Shell.ece:
<pre>
Time for 1000000 Pushes: 0.04 s
Time for 2000000 Pushes: 0.07 s
Time for 4000000 Pushes: 0.14 s
Time for 8000000 Pushes: 0.29 s
Time for 16000000 Pushes: 0.55 s
Time for 32000000 Pushes: 1.09 s
Time for 64000000 Pushes: 2.22 s
Time for 128000000 Pushes: 4.55 s
Time for 256000000 Pushes: 8 s
Time for 512000000 Pushes: 15.59 s
</pre>

This was significantly faster than both other machines, and even managed 512million1(i have not tried 1024mill)!. However, despite the reported 8 seconds for doing 256mill, it actually took more like 1 minute, and for 512mill, around 5 minutes not the reported 16 seconds. Because of this, i suspect the operating system is spending a lot of time reshuffling memory before actually running the loop, hence the shorter run times, and longer overall times.

With all these values, the times are scaling approximately equally with the push number.

=Machine Change=

The rest of the tasks where run on the shell.ece server, and an intel pentium M laptop running ubuntu(linux). Due to time constraints, pushes are limited to 128mill.

=Task2=
In this task we had to repeat the previous experiment with different "growth factors" in the function that resizes the array when necessary.

shell.ece:
<pre>
Factor 1.5:
Time for 1000000 Pushes: 0.03 s
Time for 2000000 Pushes: 0.07 s
Time for 4000000 Pushes: 0.14 s
Time for 8000000 Pushes: 0.29 s
Time for 16000000 Pushes: 0.54 s
Time for 32000000 Pushes: 1.09 s
Time for 64000000 Pushes: 2.16 s
Time for 128000000 Pushes: 4.69 s

Factor 1.7:
Time for 1000000 Pushes: 0.03 s
Time for 2000000 Pushes: 0.08 s
Time for 4000000 Pushes: 0.16 s
Time for 8000000 Pushes: 0.3 s
Time for 16000000 Pushes: 0.55 s
Time for 32000000 Pushes: 1.1 s
Time for 64000000 Pushes: 2.19 s
Time for 128000000 Pushes: 4.49 s

Factor 2:
Time for 1000000 Pushes: 0.03 s
Time for 2000000 Pushes: 0.07 s
Time for 4000000 Pushes: 0.15 s
Time for 8000000 Pushes: 0.3 s
Time for 16000000 Pushes: 0.56 s
Time for 32000000 Pushes: 1.1 s
Time for 64000000 Pushes: 2.18 s
Time for 128000000 Pushes: 4.58 s

Factor 2.5:
Time for 1000000 Pushes: 0.04 s
Time for 2000000 Pushes: 0.07 s
Time for 4000000 Pushes: 0.14 s
Time for 8000000 Pushes: 0.3 s
Time for 16000000 Pushes: 0.55 s
Time for 32000000 Pushes: 1.08 s
Time for 64000000 Pushes: 2.15 s
Time for 128000000 Pushes: 4.44 s

Factor 3:
Time for 1000000 Pushes: 0.03 s
Time for 2000000 Pushes: 0.07 s
Time for 4000000 Pushes: 0.14 s
Time for 8000000 Pushes: 0.28 s
Time for 16000000 Pushes: 0.55 s
Time for 32000000 Pushes: 1.08 s
Time for 64000000 Pushes: 2.16 s
Time for 128000000 Pushes: 4.51 s

Factor 4:
Time for 1000000 Pushes: 0.02 s
Time for 2000000 Pushes: 0.08 s
Time for 4000000 Pushes: 0.13 s
Time for 8000000 Pushes: 0.3 s
Time for 16000000 Pushes: 0.55 s
Time for 32000000 Pushes: 1.08 s
Time for 64000000 Pushes: 2.16 s
Time for 128000000 Pushes: 4.57 s
</pre>

Laptop:
<pre>
Factor 1.5:
Time for 1000000 Pushes: 0.15 s
Time for 2000000 Pushes: 0.3 s
Time for 4000000 Pushes: 0.59 s
Time for 8000000 Pushes: 1.17 s
Time for 16000000 Pushes: 2.33 s
Time for 32000000 Pushes: 4.7 s
Time for 64000000 Pushes: 9.66 s
Time for 128000000 Pushes: 20.5 s

Factor 1.7:

Time for 1000000 Pushes: 0.19 s
Time for 2000000 Pushes: 0.28 s
Time for 4000000 Pushes: 0.59 s
Time for 8000000 Pushes: 1.14 s
Time for 16000000 Pushes: 2.3 s
Time for 32000000 Pushes: 4.59 s
Time for 64000000 Pushes: 9.39 s
Time for 128000000 Pushes: 21.43 s

Factor 2:
Time for 1000000 Pushes: 0.15 s
Time for 2000000 Pushes: 0.28 s
Time for 4000000 Pushes: 0.56 s
Time for 8000000 Pushes: 1.16 s
Time for 16000000 Pushes: 2.3 s
Time for 32000000 Pushes: 4.56 s
Time for 64000000 Pushes: 9.14 s
Time for 128000000 Pushes: 21.33 s

Factor 2.5:
Time for 1000000 Pushes: 0.16 s
Time for 2000000 Pushes: 0.3 s
Time for 4000000 Pushes: 0.56 s
Time for 8000000 Pushes: 1.15 s
Time for 16000000 Pushes: 2.28 s
Time for 32000000 Pushes: 4.54 s
Time for 64000000 Pushes: 9.13 s
<128mill failed>

Factor 3:
Time for 1000000 Pushes: 0.16 s
Time for 2000000 Pushes: 0.29 s
Time for 4000000 Pushes: 0.59 s
Time for 8000000 Pushes: 1.16 s
Time for 16000000 Pushes: 2.35 s
Time for 32000000 Pushes: 4.67 s
Time for 64000000 Pushes: 9.32 s
<128mill failed>

Factor 4:
Time for 1000000 Pushes: 0.15 s
Time for 2000000 Pushes: 0.31 s
Time for 4000000 Pushes: 0.6 s
Time for 8000000 Pushes: 1.21 s
Time for 16000000 Pushes: 2.4 s
Time for 32000000 Pushes: 4.75 s
Time for 64000000 Pushes: 9.15 s
<128mill failed>
</pre>

=Task3=
In this task we had to vary the initial size of the array. When i did this, i found no significant variation in the push time.

=Task4=
In this task we preallocated enough memory for the array sizes we where testing, so that the memory would never have to be reallocated during the push runs.

Shell.ece:
<pre>
Time for 1000000 Pushes: 0.04 s
Time for 2000000 Pushes: 0.07 s
Time for 4000000 Pushes: 0.13 s
Time for 8000000 Pushes: 0.27 s
Time for 16000000 Pushes: 0.53 s
Time for 32000000 Pushes: 1.07 s
Time for 64000000 Pushes: 2.13 s
Time for 128000000 Pushes: 4.47 s
</pre>

Laptop:
<pre>
Time for 1000000 Pushes: 0.17 s
Time for 2000000 Pushes: 0.29 s
Time for 4000000 Pushes: 0.58 s
Time for 8000000 Pushes: 1.13 s
Time for 16000000 Pushes: 2.28 s
Time for 32000000 Pushes: 4.55 s
Time for 64000000 Pushes: 9.16 s
Time for 128000000 Pushes: 19.69 s
</pre>

These results show that for lighter push values, the time are consistently, if slightly, shorter. However, for lower values, the times are more equal, or longer.

=Task5=
In this task we increased the array memory size by a fixed amount each time it was necessary, rather than exponentially increasing it. Due to the increase in time taken for this method, the push number range is now from 100thou to 102.4mill.

shell.ece:
<pre>
Time for 100000 Pushes: 0 s
Time for 200000 Pushes: 0.01 s
Time for 400000 Pushes: 0.01 s
Time for 800000 Pushes: 0.03 s
Time for 1600000 Pushes: 0.06 s
Time for 3200000 Pushes: 0.12 s
Time for 6400000 Pushes: 0.24 s
Time for 12800000 Pushes: 0.44 s
Time for 25600000 Pushes: 0.88 s
Time for 51200000 Pushes: 1.72 s
Time for 102400000 Pushes: 3.45 s
</pre>

Laptop:
<pre>
Time for 100000 Pushes: 0.03 s
Time for 200000 Pushes: 0.03 s
Time for 400000 Pushes: 0.07 s
Time for 800000 Pushes: 0.12 s
Time for 1600000 Pushes: 0.23 s
Time for 3200000 Pushes: 0.46 s
Time for 6400000 Pushes: 0.92 s
Time for 12800000 Pushes: 1.83 s
Time for 25600000 Pushes: 3.66 s
Time for 51200000 Pushes: 7.31 s
Time for 102400000 Pushes: 15.53 s
</pre>

As you can see, while the times are around 10x larger than with the previous method, they seem to scale with the push number increases similarly.

=Task6=
In this task we had to repeat task1, but putting the new entries in the array at the start, rather than end. This had a dramatic effect on speed, so the put range was decreased to 1000 to 128thou.

shell.ece:
<pre>
Time for 1000 Pushes: 0 s
Time for 2000 Pushes: 0 s
Time for 4000 Pushes: 0.01 s
Time for 8000 Pushes: 0.02 s
Time for 16000 Pushes: 0.1 s
Time for 32000 Pushes: 0.39 s
Time for 64000 Pushes: 1.57 s
Time for 128000 Pushes: 6.26 s
</pre>

Laptop:
<pre>
Time for 1000 Pushes: 0 s
Time for 2000 Pushes: 0.01 s
Time for 4000 Pushes: 0.05 s
Time for 8000 Pushes: 0.07 s
Time for 16000 Pushes: 0.29 s
Time for 32000 Pushes: 1.14 s
Time for 64000 Pushes: 4.49 s
Time for 128000 Pushes: 18.07 s
</pre>

The speed hit from putting each new entry at the start is extremely dramatic. Also, the time scaling is no longer in sync with the put number increase. This is presumably because every stored value in the array must be moved every time a new one in inserted on the start.

[[User:Bvic005|Bvic005]] 23:42, 18 March 2008 (NZST)