SE250:lab-3:twon069
Jump to navigation
Jump to search
Task 1
Codes:
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;
}
Results were:
n = 1000000 clock/CLOCKS_PER_SEC = 31 /1000
n = 10000000 clock/CLOCKS_PER_SEC = 421 /1000
n = 100000000 clock/CLOCKS_PER_SEC = 4687 /1000
n = 1000000000 assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 39
- 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:
n = 1000000 clock/CLOCKS_PER_SEC = 47 /1000
n = 10000000 clock/CLOCKS_PER_SEC = 500 /1000
n = 100000000 clock/CLOCKS_PER_SEC = 5265 /1000
n = 1000000000 assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 39
GF of 3
Results were:
n = 1000000 clock/CLOCKS_PER_SEC = 47 /1000
n = 10000000 clock/CLOCKS_PER_SEC = 484 /1000
n = 100000000 assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 39
GF of 5
Results were:
n = 1000000 clock/CLOCKS_PER_SEC = 47 /1000
n = 10000000 clock/CLOCKS_PER_SEC = 375 /1000
n = 100000000 clock/CLOCKS_PER_SEC = 3875 /1000
n = 1000000000 assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 39
GF of 15
Results were:
n = 1000000 clock/CLOCKS_PER_SEC = 47 /1000
n = 10000000 clock/CLOCKS_PER_SEC = 328 /1000
n = 100000000 clock/CLOCKS_PER_SEC = 3797 /1000
n = 1000000000 error: 17855 [main] main 3656 _cygtls::handle_exceptions: Error while dumping state probably corrupted stack) Segmentation fault (core dumped)
GF of 20
Results were:
n = 1000000 clock/CLOCKS_PER_SEC = 31 /1000
n = 10000000 clock/CLOCKS_PER_SEC = 344 /1000
n = 100000000 assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 39
- 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:
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
Results for MIN_ALLOC of 32:
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
Results for MIN_ALLOC of 1024:
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
Results for MIN_ALLOC of 1048576:
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
- 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:
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
- 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:
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
- A decrease in time can be shown significantly, the time to realloc is only done 3 times.
Task 4
With ensure_capacity:
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
Without ensure_capacity:
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
- 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:
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
GF of +1000:
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
- 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:
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
With arraylist_put:
..... 12 seconds after... nothing appeared... ..... 30 seconds... ..... 50 seconds... ..... 60..... ...................
- Obviously the time taken to shift all element by 1 space is just insane... @@