Mark: 2 revision(s)

2008-11-03T05:19:30Z

2 revision(s)

New page

1.
Original code:

<pre>
int main (void)
{
int x = 1;
int n = 1000000;
int i;
long t, t1, addTime;

ArrayList array;
arraylist_init (&array);

t = clock();

for (i = 0; i < n; i++){
arraylist_push ( &array, x );
}

t1 = clock();

addTime =(t1 - t);

printf("For no. of Insertions n = %d. taken for one element insertion is %ld / %d clocks", n, addTime, n);

return 0;

}

</pre>

Output was 0 for n = 10000. Higher Values tried.

For no. of Insertions n = 1000000. taken for one element insertion is 46 / 1000000 clocks
For no. of Insertions n = 10000000. taken for one element insertion is 437 / 10000000 clocks
For no. of Insertions n = 100000000. taken for one element insertion is 4040 / 100000000 clocks
For no. of Insertions n = 1000000000; error shows up

assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 39
/usr/bin/bash: line 1: 4536 Hangup ./arraylist.exe

2.

Using *10 growth factor.

For no. of Insertions n = 1000000. taken for one element insertion is 31 / 1000000 clocks
For no. of Insertions n = 10000000. taken for one element insertion is 343 / 10000000 clocks
For no. of Insertions n = 100000000. taken for one element insertion is 3447 / 100000000 clocks
For no. of Insertions n = 1000000000; error shows up

assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 39
/usr/bin/bash: line 1: 4536 Hangup ./arraylist.exe

Time taken reduces.

Using +100 growth factor.

For no. of Insertions n = 1000000. taken for one element insertion is 187 / 1000000 clocks
For no. of Insertions n = 10000000. taken for one element insertion is 19016 / 10000000 clocks
Anything else took way too long.

Multiplying by 2 allocates twice the existing memory allocation so more insertions can occur without having to allocate more memory.

3.

Keeping n = 1000000 constant and changing the value of ARRAYLIST_MIN_ALLOC (original is 16) by a factor of 10.

ARRAYLIST_MIN_ALLOC = 160
For no. of Insertions n = 1000000. taken for one element insertion is 31 / 1000000 clocks

ARRAYLIST_MIN_ALLOC = 1600
For no. of Insertions n = 1000000. taken for one element insertion is 47 / 1000000 clocks

ARRAYLIST_MIN_ALLOC = 16000
For no. of Insertions n = 1000000. taken for one element insertion is 31 / 1000000 clocks

ARRAYLIST_MIN_ALLOC = 16000
For no. of Insertions n = 1000000. taken for one element insertion is 46 / 1000000 clocks

ARRAYLIST_MIN_ALLOC = 160
For no. of Insertions n = 1000000. taken for one element insertion is 31 / 1000000 clocks

Therefore, no significant changes.

4.

Adding ‘ensure_capacity(&array, 100000000000 );’ before the t = clock(); line and repeating the first experiment gives the following results:

For no. of Insertions n = 1000000. taken for one element insertion is 46 / 1000000 clocks
For no. of Insertions n = 10000000. taken for one element insertion is 390 / 10000000 clocks
For no. of Insertions n = 100000000. taken for one element insertion is 3744 / 100000000 clocks
For no. of Insertions n = 1000000000. Error: /usr/bin/bash: line 1: 3944 Segmentation fault (core dumped) ./arraylist.exe

5.

ALREADY DONE THAT NYA NYA NYA!!

6.

Changing arraylist_push ( &array, x ); to arraylist_put ( &array, x , 0); and repeating experiment 1 gives the following results:

Takes way too long to wait for. Good explanation would be that to add something on to the start of a chunk of used memory (using arraylist_put), the entire used memory section must be shifted to make space for the new insertion whereas with arraylist_push, adding something to the end does not require any shifting of the used memory section.

SE250:lab-3:ssre005 - Revision history

Mark: 2 revision(s)