On zucchini, try running a large sized board for a large number of iterations. For example:
1024 1024 1000 3 9 8 9 9 9 10My program takes about 108 seconds to run with this configuration (running with the second command line argument of 0 that disables board printing and sleeping after each iteration).
If you program is much slower, then try to improve your program's performance to see if you can get closer to mine, or beat it.
First, copy your existing solution to a new file named faster.c, so that you don't lose your correct, working gol solution in gol.c:
cp gol.c faster.cThen try to improve the performance of the version that you have in faster.c (leave gol.c as your first working version). If yours is much slower than mine, think about your program's memory usage and see if you can improve the time by improving how it uses memory.
When you change your code you need to ensure that it still solves the correct problem. Verify that your changes still correctly implement gol by running the faster.c version on a small example with printing enabled.
If you discover some huge ineffiencies in your orginal gol.c solution in this process, you can copy your better version to gol.c (we will grade gol.c). DO NOT do this unless you are certain that faster.c is correct (correctness is more important that speed):
cp faster.c gol.cI'd say don't bother doing this copy if the changes to faster.c are relatively minor.
To ensure that you are running experiments without interference from other processes using up a lot of CPU and/or RAM, you can see what else is going on using these commands:
The who command will list who else is logged into a machine. The top command will show cpu and memory usage of processes running on a machine. Here is a lot more information about tools for examining system state.
Using zucchini: To keep zucchini free as much as possible for other groups trying to do final timing to beat me, please first run timed runs on another machine and see how close you are getting.
bash for loop: In bash, the Unix shell you are running, you can write a bash loop to tell bash to repeat an action some number of times. The syntax is almost like a C for loop except do and done are in place of { and }, and you need double parens. Here is an example for loop to run gol on the same input 5 times (hit the enter key after each line, the ">" is the bash prompt):
for ((i=0; i< 5; i++)) > do > ./gol oscillator_big.txt 0 > done total time for 1000 iterations of 1024x1024 is 109.384949 secs total time for 1000 iterations of 1024x1024 is 109.276287 secs total time for 1000 iterations of 1024x1024 is 108.414819 secs total time for 1000 iterations of 1024x1024 is 108.270923 secs total time for 1000 iterations of 1024x1024 is 107.267878 secstime command: You can also run gol in the time command to time the entire computation time (the above is from my gettimeofday timers in my code that do not include board initialization time):
$ time ./gol oscillator_big.txt 0 total time for 1000 iterations of 1024x1024 is 107.895470 secs real 1m47.910s user 1m47.827s sys 0m0.032s
# these are timed runs compiled with gcc flags -g -Wall # gcc -g -Wall -o gol gol.c # 1024 x 1024 board, 500 iterations: ~ 53 seconds 1024 x 1024 board, 1000 iterations: ~108 seconds (1m 48 s) 500 x 500 board, 500 iterations: ~ 13 seconds 1000 x 1000 board, 500 iterations: ~ 50 seconds 2000 x 2000 board, 500 iterations: ~200 seconds ( 3m 20 s) 4000 x 4000 board, 500 iterations: ~760 seconds (12m 40 s)You likely shouldn't run the last size as it runs for a very long time. I listed it just as an interesting data point and so that you can see how the runtime grows with the problem size: this shows linear increase in time with increase in problem size (each 4 times increase in the problem size results in about a 4 times increase in execution time). If you think about the complexity of GOL, this is what you would expect--it is an 0(n) algorithm for a fixed number of iterations.
Make sure you compare a version of your code that is compiled using the same compiler flags as used in the times shown (-g in the above times). You can often greatly improve your program's execution time by turning on compiler optimization during compilation. For example, if I compile my code without debugging information (no -g flag) and with the highest level of compiler optimization (-O3), I see a huge increase in its performance just from the compiler optimization (it is the exact same C code in both sets of results):
# these are timed runs of my program compiled with the gcc flag -O3 # gcc -O3 -o gol gol.c # 1000 x 1000 board, 500 iterations: ~ 8.2 seconds 2000 x 2000 board, 500 iterations: ~ 32.7 seconds 4000 x 4000 board, 500 iterations: ~131 seconds (2m 11 s)In general, you want to do development with the -g flag so that you can easily debug your program. The -g flag and the -O flags are not compatible, and -g wins. If you are running experiments on code you have already debugged and tested, then you may want to enable compiler optimization to improve its runtime.