CMSC216 Lab11: File Stats and Timing Strides

#include <time.h>               // for clock() and clock_t

{
  clock_t begin = clock();      // current cpu moment

  Perform computation that takes a while;

  clock_t end = clock();        // later cpu moment

  double cpu_time =             // convert into seconds
    ((double) (end-begin)) / CLOCKS_PER_SEC;

  printf("Elapsed CPU Time: %f second\n", cpu_time);
}

                           _________________

                            LAB11 QUESTIONS
                           _________________





Exercise Instructions
=====================

  Follow the instructions below to experiment with topics related to
  this exercise.
  - For sections marked QUIZ, fill in an (X) for the appropriate
    response in this file. Use the command `make test-quiz' to see if
    all of your answers are correct.
  - For sections marked CODE, complete the code indicated. Use the
    command `make test-code' to check if your code is complete.
  - DO NOT CHANGE any parts of this file except the QUIZ sections as it
    may interfere with the tests otherwise.
  - If your `QUESTIONS.txt' file seems corrupted, restore it by copying
    over the `QUESTIONS.txt.bk' backup file.
  - When you complete the exercises, check your answers with `make test'
    and if all is well, create a zip file with `make zip' and upload it
    to Gradescope. Ensure that the Autograder there reflects your local
    results.
  - IF YOU WORK IN A GROUP only one member needs to submit and then add
    the names of their group.


PROBLEM 1 QUIZ: Questions on stat_demo.c
========================================

  Analyze the `stat_demo.c' program. Compile and run it via
  ,----
  | >> make stat_demo
  | ...
  | >> ./stat_demo somefile.txt
  | ...
  | >> ./stat_demo a_dirname/
  `----

  Finally, you can contrast the behavior of `filestats.c' to the shell
  command `stat' which provides similar functionality.

  Answer the following questions about how the system call works.


File Access
~~~~~~~~~~~

  Which of the filling best describes how the `access()' system call is
  used?
  - ( ) It alters read/write access to a file by adjusting its mode bits
  - ( ) It is called to determine if a file exists using the `F_OK' flag
  - ( ) It ensures a file exists and can be accessed by creating if
    necessary
  - ( ) It must be called before `stat()' in order to initialize a
    `struct stat' data structure


File Size
~~~~~~~~~

  How does `stat()' report the Size of a file?
  - ( ) An integer is passed to the calls to be set to the size
  - ( ) The return value is the number of bytes in the file
  - ( ) The size is printed to standard output during the function call
  - ( ) The field `sb.st_size' contains the number of bytes in file


File Kind
~~~~~~~~~

  `stat()()' report the "kind" of file being queried. How is this
  information used in `stat_demo.c'?
  - ( ) The field `sb.st_filetype' is set to a string like "file" or
    "pipe" to indicate the type of a file and that field can be printed
    directly
  - ( ) An integer passed in as an address to the call is set to the
    type of the file
  - ( ) The kind is encoded in the `sb.st_mode' field of the struct and
    macros are used to distinguish the kind and print an appropriate
    message.
  - ( ) The kind is encoded in the `sb.st_mode' field of the struct and
    functions are used to distinguish the kind and print an appropriate
    message.

  Which one of the following is NOT a file "kind" reported by `stat() /
  lstat()'
  - ( ) Directory
  - ( ) Binary
  - ( ) Socket
  - ( ) Symbolic Link (symlink)


mtime / ctime
~~~~~~~~~~~~~

  Do some research and determine the difference between the `ctime' and
  `mtime' alteration times that are reported by `stat() /
  lstat()'. Which of the following best describes this difference:
  - ( ) `mtime' and `ctime' actually always report the same time and
    their redundancy is a historical oddity.
  - ( ) `mtime' indicates the last time that the file was moved from one
    directory to another while `ctime' indicates the last change to the
    data in the file
  - ( ) `mtime' is the last time of modification when data was altered
    in the file while `ctime' is the last access time when data was read
    from the file
  - ( ) `mtime' is when the actual data of a file changes while `ctime'
    is associated with permissions, links, or other meta data changes
    associated with the file.


Additional Items to Observe
~~~~~~~~~~~~~~~~~~~~~~~~~~~

  The function `ctime()' and `strmode()' both use an interesting
  technique to make it possible to easily produce a printable string for
  situations like those in `filestats.c'.  Time permitting, examine the
  source code for `strmode()' in `strmode.c' and discuss with a TA how a
  string is returned but there is no requirement to free that string.


PROBLEM 1 CODE: newer_file.c Program
====================================

  Fill in the template code provided in `newer_file.c'. The intent of
  the program is to ensure that two named files exist and then compare
  the modification time of them to print an older vs newer file.  This
  will require use of the `access()' and `stat()' system calls as well
  as a `diff_timespec()' function that is provided in the
  template. Below is a demonstration of how the complete program should
  work.

  ,----
  | >> make newer_file              # build
  | gcc -Wall -Werror -g -Og -o newer_file newer_file.c
  | 
  | >> ./newer_file
  | Usage: ./newer_file <file1> <file2>
  | 
  | >> echo A > A.txt               # create 3 files
  | >> echo B > B.txt               
  | >> echo C > C.txt               # newest
  | >> touch -d '-5min' A.txt       # oldest
  | >> touch -d '-3min' B.txt       # middle
  | 
  | >> ./newer_file A.txt B.txt
  | A.txt is OLDER than B.txt
  | 
  | >> ./newer_file C.txt B.txt
  | C.txt is NEWER than B.txt
  | 
  | >> ./newer_file C.txt C.txt
  | C.txt and C.txt are EQUAL in age
  | 
  | >> ./newer_file C.txt X.txt
  | X.txt cannot be accessed
  | 
  | >> ./newer_file Z.txt X.txt
  | Both Z.txt and X.txt cannot be accessed
  `----


PROBLEM 2: clock_demo.c Program
===============================

  Demoers will walk through the `clock_demo.c' program to show how the
  `clock()' function is used in practice.  Students should look
  carefully at the techniques used to time the two different sections of
  code and print that timing info. These will be needed to fill in the
  subsequent programs.

  Running the `clock_demo' program on the command line will produce
  results that look like the following:
  ,----
  | >> make clock_demo
  | gcc -Wall -Werror -g -Og -Wall -Werror -g -Og    clock_demo.c   -o clock_demo
  | 
  | >> ./clock_demo 
  | usage: ./clock_demo <arrlen> <repeats>
  | 
  | >> ./clock_demo 1000 1000
  | Summing array length 1000 with 1000 repeats, ascending
  | Summing array length 1000 with 1000 repeats, descending
  | method:  sum ascending CPU time: 2.3750e-03 sec   sum: 499500
  | method: sum descending CPU time: 1.5760e-03 sec   sum: 499500
  | 
  | >> ./clock_demo 100000 1000
  | Summing array length 100000 with 1000 repeats, ascending
  | Summing array length 100000 with 1000 repeats, descending
  | method:  sum ascending CPU time: 6.6969e-02 sec   sum: 704982704
  | method: sum descending CPU time: 6.2286e-02 sec   sum: 704982704
  | 
  | >> ./clock_demo 100000 10000
  | Summing array length 100000 with 10000 repeats, ascending
  | Summing array length 100000 with 10000 repeats, descending
  | method:  sum ascending CPU time: 6.2730e-01 sec   sum: 704982704
  | method: sum descending CPU time: 6.1995e-01 sec   sum: 704982704
  `----


PROBLEM 2 CODE: `struct_stride.c' Program
=========================================

  The provided `struct_stride.c' program has a number of TODO items in
  it related to timing several computations and reporting their results.
  It is best to complete these items first and then attempt to answer
  the quiz questions as some questions require running the program and
  observing timing results.

  Use the lab's description of how the `clock()' function works to
  complete TODO items and print the results.

  When completed, the program can be run as show below:
  ,----
  | >> ./struct_stride 
  | usage: ./struct_stride <arr_length> <num_iters>
  | 
  | >> ./struct_stride 10000000 100
  | method: int_field_base CPU time: 1.2345e-01 sec   sum: 0
  | method: arr_field_base CPU time: 1.2345e-01 sec   sum: 0
  | method: int_field_optm CPU time: 1.2345e-01 sec   sum: 0
  | method: arr_field_optm CPU time: 1.2345e-01 sec   sum: 0
  `----

  NOTE: the timing information has intentionally been changed to read
  1.2345e-01 as calculating this timing information is part of the lab.


PROBLEM 2 QUIZ: Timing `struct_stride.c' Runs
=============================================

  NOTE: timing code varies from one machine to the next. The answers
  below were tested on GRACE and appear to be stable but system load may
  affect the outcome.


Relative Speed of Struct Layouts
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  After adding in calls to `clock()' and code the print times, run the
  `struct_strid' program.

  Run the program with a large array and a modest amount of array
  iterations such as using the following parameters:
  ,----
  | ./struct_stride 6000000 100
  `----

  Examine the times reported.

  Which option below reflects the relative speeds of the
  layout/algorithm combinations?
  ,----
  |   ------SLOWEST--------------------------------------------FASTEST-----
  | - ( ) arr_field_base > arr_field_optm > int_field_base > int_field_optm 
  | - ( ) int_field_base > int_field_optm > arr_field_base > arr_field_optm
  | - ( ) arr_field_base > int_field_base > arr_field_optm > int_field_optm 
  | - ( ) int_field_base > arr_field_base > int_field_optm > arr_field_optm
  `----


int_field_base VS arr_field_base
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  Examine the differences between the two types of structs that are used
  in `struct_stride.c' called `int_field_t' and `arr_field_t'.

  Now examine the first 2 code blocks that use these structs called,
  `int_field_base' and `arr_field_base'. Both involve arrays and structs
  which store an equal number of positive and negative
  integers. However, they differ in the overall layout of those
  integers.  Both use loops sum the "a" numbers first then sum the "b"
  numbers, then combine them for the total sum.

  Which of the following are possible explanations for the timing
  difference between `int_field_base' and `arr_field_base'?
  - ( ) `int_field_base' must perform more loop iterations than
    `arr_field_base' which will making it slower.
  - ( ) `arr_field_base' uses more memory to store then number than
    `int_field_base' and this additional memory increases speed.
  - ( ) `int_field_base' has a memory layout that is ABABABAB so when
    adding A elements, there is a "stride" through
    memory. `arr_field_base' has a layout like AAAAABBBBB so adding
    elements has no stride.
  - ( ) `int_field_base' uses struct field access. The assembly
    instructions to access array fields are slower than the assembly
    instructions that access array elements. This makes `arr_field_base'
    faster due to its use of plain integer arrays.


BASE vs OPTM versions
~~~~~~~~~~~~~~~~~~~~~

  The last two layout/algorithm sections are labeled "optm" as they
  perform a simple code transformation from their "base" version.

  Select ALL of the items below that are accomplished with this
  transformation.

  - ( ) Fewer loop checks/increments are needed as there is only one
    loop instead of 2.
  - ( ) The number of loop iterations is lowered for all loops in the
    optm version.
  - ( ) The memory stride is eliminated for the int_field_optm as both
    a/b elements are added each iteration.
  - ( ) The algorithmic complexity is reduced from O(N^2) in the "base"
    to O(N) in the "optm" version.