• 10 Sep 2023: allow using /usr/bin/true instead of /bin/true on system that does not have /bin/true
  • 10 Sep 2023: tweak phrasing re: timing overhead to make it clear it’s about dealing with non-benchmark tasks that are accidentally timed
  • 12 Sep 2023: address negative times explicitly in hints, and indicate rare cases where real such results might happen
  • 15 Sep 2023: address -std=c11 hiding sigaction(), etc. without something like #define _XOPEN_SOURCE 700
  • 15 Sep 2023: mention that -fsanitize=address will dramatically increase overhead
  • 15 Sep 2023: add example of optimization flag when mentioning compiling with optimizations

1 Your task

  1. Write a program gettimings in C and/or assembly to take measurements needed to estimate the time required for:

    1. calling an empty function and having it return
    2. running the getppid function from <unistd.h>
    3. running a system("/bin/true") (which runs the command /bin/true in a shell) [or if you are on a system where /bin/true does not exist, but /usr/bin/true does, you may use system("/usr/bin/true") instead]
    4. sending a signal to the current process and having its signal handler start executing (but not including the signal handler returning)
    5. sending a signal to another process, then having that process’s signal handler send a signal back, then either:
      • having a signal handler for signal sent back start executing in the original process (but not including the signal handler returning); or
      • identifying that the signal was sent back in the original process using a function like sigwait

    Your program should take one command-line argument which is a number from 1 to 5 indicating which scenario above to produce timings for. (So we’d run it like ./gettimings 1, ./gettimings 2, etc.)

    For scenario 5 above, we need to run two copies of your program, similar to the signals lab:

    • The other process (the one not outputting timings), should be run as ./gettimings -1. It should print its PID and read a pid from stdin.
    • When we run ./gettimings 5 it should print its PID and read a pid from stdin.
    • We will test by entering the PID of the ./gettimings 5 process into the ./gettimings -1 process first, then entering the PID of the ./gettimings -1 process into the ./gettimings 5 process.
    • (It’s okay if we need to use control-C or similar to terminate ./gettimings -1 process.)
  2. Run your program and record the measurements it outputs.

    In a file called timings.txt:

    • either place the measurements output by your program or identify which data file(s) they are in
    • if necessary, convert the measurements from your programs to the time estimates listed above (be sure to include units)
    • describe what calculations (if any) were necessary to convert the measurements output from your program to time estimates

    If you place measurements output by your program in separate data files, make them .txt or .csv files.

    In either timings.txt or separate data files, your submission must include the parts of your program’s output you used to compute the final time estimates you report; if your program outputs additional data, that does not need to be submitted. Also, it is acceptable if your program only outputs summaries of the measurements it takes rather than every individual measurement.

    When producing the time estimates, you and/or your program must:

    • make an attempt to account for any measurement overhead (that is, the time unintentionally included in raw timings not used to do the task being timed but instead to obtain clock measurements, setup the task, etc.) One strategy might be to measure the time required for nothing and subtract this time from other measurements.
    • measure multiple instances of the above events to obtain your estimate (to limit the impact of variation in system performance on your estimates)
  3. Produce a Makefile whose default target (the one run by make) will compile and link your gettimings program.

  4. Submit all your timings.txt, any needed data files, and all your source files (Makefile, and all the C and assembly source files) to the submission site.

    (If your data files are quite large (many megabytes) and would be hard to upload, you may instead put it something like Box and give a link in timings.txt.)

2 Hints

2.1 Timing APIs

Since we are timing very short events, you want some function that can obtain high precision time measurements.

2.1.1 clock_gettime

One way to do this on Linux is using clock_gettime:

struct timespec t;
returnvalue = clock_gettime(CLOCK_MONOTONIC, &t);

will, when successful, set returnvalue to 0 and t.tv_sec to a number of seconds and t.tv_nsec to a number of nanoseconds. When unsuccessful, it will set returnvalue to -1 and errno (or utility functions like perror) can be used to obtain information about the error.

On OS X, clock_gettime exists, but (at least in the versions I have looked at) it is only accurate to the nearest microsecond (even though it reports its result in nanoseconds).

CLOCK_MONOTONIC specifies to use a timer that starts around system boot. There are also other clock options like CLOCK_REALTIME (measures seconds since 1 Jan 1970 midnight UTC).

In order to use clock_gettime, use something like #define _XOPEN_SOURCE 700 before #includeing any files then #include <time.h>. (The #define requests that header files make features from the X/Open Single Unix Specification available to you.)

An example utility function for using this is:

#define _XOPEN_SOURCE 700
#include <time.h>


/// returns the number of nanoseconds that have elapsed since an arbitrary time
long long nsecs() {
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec*1000000000 + t.tv_nsec;

2.1.2 the cycle counter

x86-64 has a per-core Time Stamp Counter which can be accessed with the assembly instructions rdtsc (read time stamp counter) or rdtscp (read time stamp counter and processor ID).

rdtscp sets %edx to the upper 32 bits of the 64-bit time stamp counter, %eax to the lower 32 bits of time stamp counter, and %ecx to a ID number that should be unique to the core. The timestamp counter starts counting roughly when each core starts, but it may count at slightly different rates on each core, so you should not attempt to subtract numbers from two different cores.

Without writing assembly, GCC and Clang expose these using some built-in wrapper functions declared in <immintrin.h>:

__int64 rdtsc();
__int64 rdtscp(int *pointer_to_core_id);

where __int64 is most likely the same as a long on 64-bit Linux. The cycle counter is in units of clock cycles (not seconds or similar). On systems with variable clock rates used for running instructions, often the time stamp counter will be based on clock cycles of a special constant rate clock rather than the clock used by each core to run instructions.

2.2 Obtaining and consolidating multiple measurements

There are several reasons why measurements will not be consistent:

To mitigate this, usually one would:

(For how many timings, a possible rule of thumb is to take at least enough timings to take half a second of real time.)

2.3 Avoiding measurement overhead

Whenever you time something, in addition to timing that something you will also end up timing some of your timing code. To compensate for this, I would recommend timing nothing (just running your timing code timing an empty block of code) and subtracting this from your other timings.

In addition, the amount of overhead is generally lower when you compile with optimizations (for example, -Og or -O1) and (when timing) without enabling slow debugging features like -fsanitize=address, so I would recommend trying to do so. Keep in mind, however, to enable optimizations, you’ll need to keep the compiler from doing optimizations that eliminate the things you are trying to time. The ideas in section 2.4 can be helpful for this.

2.3.1 Negative times from overhead

Sometimes students get consistently negative times after attempting to subtract overhead. Usually I think this is the result of issues like:

If you you make an significnat effort to eliminate/diagnose measurement errors that would cause a negative time and still have a negative time and you report it accurately when you report your results, that is fine. In some rare cases, these results could be real due to how modern processors work:

Because processors try to run multiple instructions at a time, in some unusual cases, it might be possible that something that takes a very short amount of time runs entirely simulatenously with your timing code around it and so takes no time. In other unusual cases, it’s possible that relocating or making apparently inconsequential changes the timing code speeds that code up slightly (due to arranging code or data on the stack in a slightly better way in memory, etc.).

There are ways to avoid instructions overlapping (by including instructions that the proecssor manufacturer designates to prevent this; see, for example, this Intel document) to make sure you are only timing the task of interest and not how it interacts with instructions around it, but that is not required for this assignment.

2.4 Compiler optimization and function calls

I recommend turning on compiler optimizations to avoid measuring slow code for setting up system calls and the like. But, when timing a function call, you may have problems with the compiler’s optimizer replacing a function call with the body of that function. Some possibilities to avoid this:

2.5 If sigaction or sigset_t is not defined

If you compile with -std=c11 or similar, , this requests only C standard functions by default, and <signal.h> is part of standard C, but includes only a limited set of funtions/types (not including most of what we discussed for signal handling).

You can request the full set of Linux/Unix functions (despite using -std=c11) by using a feature test macro like #define _XOPEN_SOURCE 700 before including anything (or, equivalently, by compiling with an option like -D_XOPEN_SOURCE=700). This #define requests features from X/Open System Interfaces associated with the POSIX.1-2017 standard.

There are similar feature test macros that request slightly different sets of functionality; Linux documents all of these in the feature_test_macros manpage.

2.6 Timing the signal handler

When sending a signal to the current thread, kill() is guaranteed to return only after the signal is delivered. (This is not gaurenteed if you send to another process.) If you want to avoid specifying the process ID, you can also use the function raise() [which can only send a signal to the current process] instead of kill() [which can send to any process].

2.7 Timing receiving a signal back

2.7.1 Need to wait for signal

If you send a signal to another process kill() can and often will return before the signal is handled, so you can’t just call kill() the appropriate number of times. Also, if you send the same signal twice to a process before it is handled, then the signal may only be handled once.

2.7.2 Missing signals coming back

The last timing task requires waiting for a signal to be received by your current process. The naive approach of:

/* MIDDLE */

has the problem that the signal can be received at MIDDLE and lost. To avoid this problem, some approaches for doing this:

Blocking a signal ensures that the operating system will not deliver it (that is, will not run its signal handler), but blocked signals will still be recorded as pending (that is, needing to be handled at some point).

3 Collaboration

As with most homework assignments, this assignment is to be completed individually.

  1. If you use usleep, you can’t also use #define _XOPEN_SOURCE 700. Workarounds include changing the 700 to 600 or using more modern function like nanosleep.↩︎

  2. To be most reliable/portable, the flag should be declared as a volatile sig_atomic_t to tell the compiler to expect the value to be modified by signal handlers, but as long as the loop calls something like usleep, probably other types will work.↩︎