SE250:lab-3:ssre005

1. Original code:

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;

}

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.