LAB 12 QUESTIONS SOLUTION

- Name: Tanner Hobbs
- NetID: Hobbs131

Answer the questions below according to the lab specification. Write
your answers directly in this text file and submit it to complete the
lab.


PROBLEM 1: Timing Benchmarks
============================

  The code in `reversal.c' implements two functions which reverse the
  elements of an array. They take markedly different approaches.
  ,----
  | void reverse_arr1(int *arr, long size){
  |   int *tmp = malloc(sizeof(int)*size);
  |   for(long i=0; i<size; i++){
  |     tmp[i] = arr[size-i-1];
  |   }
  |   for(long i=0; i<size; i++){
  |     arr[i] = tmp[i];
  |   }
  |   free(tmp);
  | }
  |
  | void reverse_arr2(int *arr, long size){
  |   for(long i=0; i<size/2; i++){
  |     int tmp = arr[i];
  |     arr[i] = arr[size-i-1];
  |     arr[size-i-1] = tmp;
  |   }
  | }
  `----


(A) Predictions
~~~~~~~~~~~~~~~

  Predict which of these two functions will run faster based on their
  code characteristics.

Function reverse_arr2 will run faster because less instructions are required. Two for loops are ran through at n iterations in the first method whereas in the second only one for loop is ran for n/2 iterations
(B) Timing
~~~~~~~~~~

  Modify the provided `reversal.c' file to perform timing calculations
  on the two functions as they are called on different sizes of arrays.
  Print runtimes in a tabular format.

  Paste the C code you wrote below to show you how you timed the
  function runs.

  clock_t begin, end;
  double cpu_time1;
  double cpu_time2;
  begin = clock();
  reverse_arr1(arr1,size);
  end = clock();
  cpu_time1 = ((double) (end - begin)) / CLOCKS_PER_SEC;
  printf("cpu time reverse_arr1: %.4e   ", cpu_time1);


  begin = clock();
  reverse_arr2(arr2,size);
  end = clock();
  cpu_time2 = ((double) (end - begin)) / CLOCKS_PER_SEC;
  printf("cpu time reverse_arr2: %.4e   \n", cpu_time2);


(C) Analysis
~~~~~~~~~~~~

  Paste the table of numbers your code produced for timing the two
  reversal functions. Describe if the one you predicted would be faster
  actually was measured to be faster.

  cpu time reverse_arr1: 2.0000e-06   cpu time reverse_arr2: 1.0000e-06
cpu time reverse_arr1: 1.0000e-06   cpu time reverse_arr2: 1.0000e-06
cpu time reverse_arr1: 1.0000e-06   cpu time reverse_arr2: 1.0000e-06
cpu time reverse_arr1: 2.0000e-06   cpu time reverse_arr2: 1.0000e-06
cpu time reverse_arr1: 1.0000e-06   cpu time reverse_arr2: 1.0000e-06
cpu time reverse_arr1: 1.0000e-06   cpu time reverse_arr2: 1.0000e-06
cpu time reverse_arr1: 2.0000e-06   cpu time reverse_arr2: 1.0000e-06
cpu time reverse_arr1: 1.0000e-05   cpu time reverse_arr2: 2.0000e-06
cpu time reverse_arr1: 7.0000e-06   cpu time reverse_arr2: 2.0000e-06
cpu time reverse_arr1: 9.0000e-06   cpu time reverse_arr2: 4.0000e-06

The one I predicted to be faster seems to be faster


PROBLEM 2: ax then xpy VS axpy
==============================

  Examine the timing code in `axpy.c'. Consider the 3 functions `ax()',
  `xpy()', and `axpy()'.  Note that these are timed in `main()' as
  follows.
  ,----
  | // start timing 1
  |     ax(a,x1,size);
  |     xpy(x1,y,size);
  | // stop timing
  |
  | // start timing 2
  |     axpy(a,x2,y,size);
  | // stop timing
  `----
  This is because the first two functions together do what `axpy()'
  does.

  Note also that `axpy()' has two "fairness" loops which do affect the
  results but compensate for the fact that the previous two functions
  combined have two loops.

  Time these functions using the provided code. Explain the results you
  observe and if one appears to be faster than the other, describe what
  features of the processor and memory architecture might be affecting
  the timings.

  axpy seems to be slightly faster than ax and xpy together. This may be because the scaling of the array and the addition of arrays operations are done simultaneously in the for loops thus reducing the amount of instructions handled.


PROBLEM 3 (OPTIONAL): Profiler
==============================

  This problem demonstrates the utility of a performance *profiler* to
  help locate "hot spots" in code which take most of the run time
  associated with it.

  Change into the directory `warsim' that is part of the lab code
  distribution.  The code contained within it implements a simple
  simulation of the card game War.  The details of the game are not
  important except that the program simulates playing of the game then
  reports statistics on it.

  First compile the program by using the provided Makefile.
  ,----
  | > make
  | gcc -Og -g -pg -no-pie -c libwar.c
  | gcc -Og -g -pg -no-pie -c libcardlist.c
  | gcc -Og -g -pg -no-pie -o warsim warsim.c libwar.o libcardlist.o
  `----
  Notice that the option `-pg' is passed in which will enable
  /profiling/ of the code. The `-no-pie' option is present in case a
  buggy version of `gcc' is present and has no significant effect.

  Run the resulting `warsim' program as follows.

  ,----
  | # show usage
  | > ./warsim
  | usage: ./warsim cardfile ngames [logfile]
  |
  | # simulate 10 games
  | > ./warsim full.deck 10
  | ----------------------
  | Final stats
  |   0.60 P1 Win Ratio
  | 408.50 Avg battles per game
  |  30.30 Avg wars per game
  |
  | # simulate 100 games
  | > ./warsim full.deck 100
  | ----------------------
  | Final stats
  |   0.54 P1 Win Ratio
  | 301.56 Avg battles per game
  |  22.94 Avg wars per game
  |
  | # simulate 2000 games
  | > ./warsim full.deck 2000
  | ----------------------
  | Final stats
  |   0.54 P1 Win Ratio
  | 298.48 Avg battles per game
  |  22.79 Avg wars per game
  `----

  This last run might take a few seconds as 2000 games are simulated.

  After the runs are finished, the file `gmon.out' appears. This is an
  output file that is generated on running programs with profiling
  enabled.
  ,----
  | > ls gmon.out
  | gmon.out
  | > file gmon.out
  | gmon.out: GNU prof performance data - version 1
  `----

  The contents of the file are binary and must be interpreted by the
  program `gprof'.  Use the `-b' option to show "brief" output and pass
  in the name of the program that was run.
  ,----
  | > gprof -b warsim
  | Flat profile:
  |
  | Each sample counts as 0.01 seconds.
  |   %   cumulative   self              self     total
  |  time   seconds   seconds    calls  ms/call  ms/call  name
  |  50.11      0.06     0.06  2387860     0.00     0.00  print_list
  |  25.06      0.09     0.03 32507650     0.00     0.00  card2str
  |   8.35      0.10     0.01   596965     0.00     0.00  end_battle
  |   8.35      0.11     0.01     4000     0.00     0.00  new_stack
  |   8.35      0.12     0.01       52     0.19     0.19  str2card
  |   0.00      0.12     0.00  8073378     0.00     0.00  stack_empty
  |   0.00      0.12     0.00  6656812     0.00     0.00  queue_empty
  |   0.00      0.12     0.00  3944508     0.00     0.00  stack_top
  |   0.00      0.12     0.00  1675522     0.00     0.00  queue_add
  |   0.00      0.12     0.00  1675522     0.00     0.00  queue_remove
  |   0.00      0.12     0.00  1571470     0.00     0.00  queue_front
  |   0.00      0.12     0.00  1465470     0.00     0.00  stack_pop
  |   0.00      0.12     0.00  1465470     0.00     0.00  stack_push
  |   0.00      0.12     0.00   596965     0.00     0.00  start_battle
  |   0.00      0.12     0.00     6001     0.00     0.00  new_queue
  |   0.00      0.12     0.00     6001     0.00     0.00  queue_free
  |   0.00      0.12     0.00     4000     0.00     0.00  stack_free
  |   0.00      0.12     0.00     2000     0.00     0.00  deal2
  |   0.00      0.12     0.00     2000     0.00     0.06  playwar
  |   0.00      0.12     0.00     2000     0.00     0.00  queue_copy
  |   0.00      0.12     0.00     2000     0.00     0.00  queue_rotate
  |   0.00      0.12     0.00        1     0.00    10.02  read_deck
  | ...
  `----

  The first part of the output shows a breakdown of how much time was
  spent in each function associated the most recent run of the program.

  Analyze this breakdown and make suggestions as to where optimization
  effort might best be spent to increase the speed of warsim.