SE250:lab-3:rwan064
Introduction
The aim of this lab was to test the performance of an implementation of an Array-based list.
Results
The same basic code was used for all tasks. There are some differences but they are explained on the section for each task.
// File: main.c
// Author: Rajitha Wannigama
// Purpose: SE250 Lab 3
// Date created: 8:43 p.m. 18/03/2008
// Last updated: 11:23 a.m. 18/03/2008
#include <stdio.h>
#include <time.h>
#include "arraylist.h"
int main( int argc, char *argv[] )
{
clock_t t0, t1;
double time;
FILE *fp;
char filename[] = "task1_results.txt";
fp = fopen( filename, "w" );
if ( fp == NULL ) {
printf( "Cannot open file \"%s\" for writing\n", filename );
return 0;
}
// Range of n: 1,000 to 1,000,000 (thousand to a million)
int i, j;
int start = 1000; // Thousand
int incr = 1000; // Thousand
int end = 1000000; // Million
ArrayList xs;
arraylist_init( &xs );
for ( i = start; i < end+1; i += incr ) {
t0 = clock();
for ( j = 0; j < i; j++ ) {
// Insert "i" number of elements
arraylist_push( &xs, 0 );
}
t1 = clock();
time = (double) (t1 - t0) / (double) CLOCKS_PER_SEC;
fprintf( fp, "%d %f\n", i, time );
arraylist_clear( &xs );
}
fclose( fp );
return 0;
}
I outputted the results of each experiment into a file and then imported them to excel to draw graphs. This way it's easy to compare the results of each experiment.
Task 1
From the graph it is clear that as we have more elements to put in, it takes a longer amount of time. This is as expected. But there are also "bumps" on the graph which is probably because the ArrayList needs to be resized, and this would take more time since a new area of memory needs to be created and then the contents of the previous one must also be moved to that new location.
Task 2
I did the test for growth factors 1.5, 2.0 (from task 1), 2.5, 3.0, 3.5, 4.0 and 10.0.
After 3.0 it didn't seem to make much of a difference on the time taken to add n elements. I think that a growth factor of 2 gave the best times and using higher values just uses up more memory without giving any performance enhancements.
Task 3
As the value of ARRAYLIST_MIN_ALLOC is increased, the performance of the ArrayList was also increased probably due to the fact that no new memory needs to be created.
Task 4
Extra line of code was used to allocate maximum capacity to arraylist.
ensure_capacity( &xs, end ); // end = 1 million = 1000000
As you can see from the graph, allocating the maximum capacity gave a smooth curve with the best times. The big jumps in the beginning and in the middle are probably due to the way the memory is arranged or some other internal working of C that I don't know about.