Mark: 9 revision(s)

2008-11-03T05:19:31Z

9 revision(s)

New page

==Task 1==
Codes:
<pre>
int main()
{
ArrayList alist;
arraylist_init(&alist);
long i;
int t, elt, maxCap;
maxCap = 1200000000;
elt = 50;

t = clock();

for (i = 0; i < 1000000; i++){
arraylist_push(&alist, elt);
}

t = (clock() - t);
printf("n = %d\n", i);
printf("clock/CLOCKS_PER_SEC = %d /%d\n", t, CLOCKS_PER_SEC);

return 0;
}
</pre>

Results were:
<pre>
n = 1000000
clock/CLOCKS_PER_SEC = 31 /1000
</pre>
<pre>
n = 10000000
clock/CLOCKS_PER_SEC = 421 /1000
</pre>
<pre>
n = 100000000
clock/CLOCKS_PER_SEC = 4687 /1000
</pre>
<pre>
n = 1000000000
assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 39
</pre>

*The results shows a linear increase when the number of times the array has to add something is increased in a linear fashion as well.
*The last result shows the memory being exhausted due to the array being too large

==Task 2==
===GF of 1.5===
Results were:
<pre>
n = 1000000
clock/CLOCKS_PER_SEC = 47 /1000
</pre>
<pre>
n = 10000000
clock/CLOCKS_PER_SEC = 500 /1000
</pre>
<pre>
n = 100000000
clock/CLOCKS_PER_SEC = 5265 /1000
</pre>
<pre>
n = 1000000000
assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 39
</pre>

===GF of 3===
Results were:
<pre>
n = 1000000
clock/CLOCKS_PER_SEC = 47 /1000
</pre>
<pre>
n = 10000000
clock/CLOCKS_PER_SEC = 484 /1000
</pre>
<pre>
n = 100000000
assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 39
</pre>

===GF of 5===
Results were:
<pre>
n = 1000000
clock/CLOCKS_PER_SEC = 47 /1000
</pre>
<pre>
n = 10000000
clock/CLOCKS_PER_SEC = 375 /1000
</pre>
<pre>
n = 100000000
clock/CLOCKS_PER_SEC = 3875 /1000
</pre>
<pre>
n = 1000000000
assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 39
</pre>

===GF of 15===
Results were:
<pre>
n = 1000000
clock/CLOCKS_PER_SEC = 47 /1000
</pre>
<pre>
n = 10000000
clock/CLOCKS_PER_SEC = 328 /1000
</pre>
<pre>
n = 100000000
clock/CLOCKS_PER_SEC = 3797 /1000
</pre>
<pre>
n = 1000000000
error:
17855 [main] main 3656 _cygtls::handle_exceptions: Error while dumping state
probably corrupted stack)
Segmentation fault (core dumped)
</pre>

===GF of 20===
Results were:
<pre>
n = 1000000
clock/CLOCKS_PER_SEC = 31 /1000
</pre>
<pre>
n = 10000000
clock/CLOCKS_PER_SEC = 344 /1000
</pre>
<pre>
n = 100000000
assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 39
</pre>

*The results shows no significant changes to the time it takes, however the larger the growth factor, the less element it seen to be able to hold.
*The above is due to growth factor being too large, and multiplying the original size sometime makes a large excess of unused array, which then takes up too much of the memory and exhausting it.
*Though is it not clear, but it should take less time to place elements into the array when the growth factor increases due to the time the memory needs to be realloced is lowered.

==Task 3==
Results for MIN_ALLOC of 8:
<pre>
n = 10000000
clock/CLOCKS_PER_SEC = 452 /1000
n = 20000000
clock/CLOCKS_PER_SEC = 922 /1000
n = 30000000
clock/CLOCKS_PER_SEC = 1296 /1000
n = 40000000
clock/CLOCKS_PER_SEC = 2079 /1000
n = 50000000
clock/CLOCKS_PER_SEC = 2391 /1000
</pre>

Results for MIN_ALLOC of 32:
<pre>
n = 10000000
clock/CLOCKS_PER_SEC = 485 /1000
n = 20000000
clock/CLOCKS_PER_SEC = 938 /1000
n = 30000000
clock/CLOCKS_PER_SEC = 1297 /1000
n = 40000000
clock/CLOCKS_PER_SEC = 2078 /1000
n = 50000000
clock/CLOCKS_PER_SEC = 2375 /1000
</pre>

Results for MIN_ALLOC of 1024:
<pre>
n = 10000000
clock/CLOCKS_PER_SEC = 469 /1000
n = 20000000
clock/CLOCKS_PER_SEC = 969 /1000
n = 30000000
clock/CLOCKS_PER_SEC = 1359 /1000
n = 40000000
clock/CLOCKS_PER_SEC = 2031 /1000
n = 50000000
clock/CLOCKS_PER_SEC = 2453 /1000
</pre>

Results for MIN_ALLOC of 1048576:
<pre>
n = 10000000
clock/CLOCKS_PER_SEC = 484 /1000
n = 20000000
clock/CLOCKS_PER_SEC = 968 /1000
n = 30000000
clock/CLOCKS_PER_SEC = 1360 /1000
n = 40000000
clock/CLOCKS_PER_SEC = 2031 /1000
n = 50000000
clock/CLOCKS_PER_SEC = 2468 /1000
</pre>

*Theres not really a change in time when the MIN_ALLOC is increased in a small scale compare to n, this could be due to small amount of memory does not take much time to be realloc'd, therefore the same amount of large alloc is only counted for in time.

Results for MIN_ALLOC of 10000000:
<pre>
n = 10000000
clock/CLOCKS_PER_SEC = 376 /1000
n = 20000000
clock/CLOCKS_PER_SEC = 828 /1000
n = 30000000
clock/CLOCKS_PER_SEC = 1297 /1000
n = 40000000
clock/CLOCKS_PER_SEC = 1751 /1000
n = 50000000
clock/CLOCKS_PER_SEC = 2468 /1000
</pre>

*A decrease in time can be shown here for n = 10000000, 20000000, 40000000, this is due to no realloc is done to 10000000, and 4000000 values, and reallocing 10000000 to 20000000 took some times.
*However 50000000 remains the same due to having to realloc a larger chunk of memory, so the time is the same as the rest of the experiments.

Results for MIN_ALLOC of 50000000:
<pre>
n = 10000000
clock/CLOCKS_PER_SEC = 375 /1000
n = 20000000
clock/CLOCKS_PER_SEC = 782 /1000
n = 30000000
clock/CLOCKS_PER_SEC = 1140 /1000
n = 40000000
clock/CLOCKS_PER_SEC = 1547 /1000
n = 50000000
clock/CLOCKS_PER_SEC = 1921 /1000
</pre>

*A decrease in time can be shown significantly, the time to realloc is only done 3 times.

==Task 4==
With ensure_capacity:
<pre>
n = 10000000
clock/CLOCKS_PER_SEC = 391 /1000
n = 20000000
clock/CLOCKS_PER_SEC = 750 /1000
n = 30000000
clock/CLOCKS_PER_SEC = 1109 /1000
n = 40000000
clock/CLOCKS_PER_SEC = 1501 /1000
n = 50000000
clock/CLOCKS_PER_SEC = 1937 /1000
n = 60000000
clock/CLOCKS_PER_SEC = 2640 /1000
n = 70000000
clock/CLOCKS_PER_SEC = 2657 /1000
n = 80000000
clock/CLOCKS_PER_SEC = 3031 /1000
n = 90000000
clock/CLOCKS_PER_SEC = 3437 /1000
</pre>

Without ensure_capacity:
<pre>
n = 10000000
clock/CLOCKS_PER_SEC = 469 /1000
n = 20000000
clock/CLOCKS_PER_SEC = 906 /1000
n = 30000000
clock/CLOCKS_PER_SEC = 1281 /1000
n = 40000000
clock/CLOCKS_PER_SEC = 2062 /1000
n = 50000000
clock/CLOCKS_PER_SEC = 2359 /1000
n = 60000000
clock/CLOCKS_PER_SEC = 2733 /1000
n = 70000000
clock/CLOCKS_PER_SEC = 3657 /1000
n = 80000000
clock/CLOCKS_PER_SEC = 3953 /1000
n = 90000000
clock/CLOCKS_PER_SEC = 4296 /1000
</pre>

*A significant decrease in time, showing a great deal of time is going through reallocating larger chunks of memory.

==Task 5==
GF of *2.0:
<pre>
n = 1000000
clock/CLOCKS_PER_SEC = 47 /1000
n = 2000000
clock/CLOCKS_PER_SEC = 94 /1000
n = 3000000
clock/CLOCKS_PER_SEC = 125 /1000
n = 4000000
clock/CLOCKS_PER_SEC = 172 /1000
n = 5000000
clock/CLOCKS_PER_SEC = 234 /1000
n = 6000000
clock/CLOCKS_PER_SEC = 281 /1000
n = 7000000
clock/CLOCKS_PER_SEC = 344 /1000
n = 8000000
clock/CLOCKS_PER_SEC = 360 /1000
n = 9000000
clock/CLOCKS_PER_SEC = 437 /1000
</pre>

GF of +1000:
<pre>
n = 1000000
clock/CLOCKS_PER_SEC = 203 /1000
n = 2000000
clock/CLOCKS_PER_SEC = 734 /1000
n = 3000000
clock/CLOCKS_PER_SEC = 1891 /1000
n = 4000000
clock/CLOCKS_PER_SEC = 3422 /1000
n = 5000000
clock/CLOCKS_PER_SEC = 5296 /1000
n = 6000000
clock/CLOCKS_PER_SEC = 7516 /1000
n = 7000000
clock/CLOCKS_PER_SEC = 10126 /1000
n = 8000000
clock/CLOCKS_PER_SEC = 13266 /1000
n = 9000000
clock/CLOCKS_PER_SEC = 17655 /1000
</pre>

*The difference here is massive, taking up to 17seconds to fill in 90million elements, whereas multiplying by 2 simply takes up less than a second!

==Task 6==
With arraylist_push:
<pre>
n = 1000000
clock/CLOCKS_PER_SEC = 47 /1000
n = 2000000
clock/CLOCKS_PER_SEC = 94 /1000
n = 3000000
clock/CLOCKS_PER_SEC = 125 /1000
n = 4000000
clock/CLOCKS_PER_SEC = 172 /1000
n = 5000000
clock/CLOCKS_PER_SEC = 234 /1000
n = 6000000
clock/CLOCKS_PER_SEC = 266 /1000
n = 7000000
clock/CLOCKS_PER_SEC = 344 /1000
n = 8000000
clock/CLOCKS_PER_SEC = 328 /1000
n = 9000000
clock/CLOCKS_PER_SEC = 453 /1000
</pre>

With arraylist_put:
<pre>
..... 12 seconds after... nothing appeared...
..... 30 seconds...
..... 50 seconds...
..... 60.....
...................
</pre>

*Obviously the time taken to shift all element by 1 space is just insane... @@

SE250:lab-3:twon069 - Revision history

Mark: 9 revision(s)