Exercises 1

Deadline 2025-10-24 23:59

All filenames refer to the g0.complang.tuwien.ac.at. You should perform your measurements on this machine.

Submission

A plain text file containing just the questions is available at /usr/ftp/pub/anton/lvas/efficient/25/Exercises1.txt. Please create a subdirectory 1 in your git project, copy that file there, and answer the questions with a text editor, inserting parts of the transcript where needed. For answers where the supporting evidence is longer, put the supporting evidence in a file (or several) in the same directory. Don’t forget to commit and push the directory and the relevant files before the deadline.

Please do not just answer the questions, but document how you arrived at the answers (this is also useful for preparing yourself for the interview part of the exam later in the semester). A good way to do that for some questions is to provide transcripts of your shell sessions. You can either cut-and-paste the text from the terminal session, or use script -f <filename> to write the transcript to the named file (and then copy parts of this transcript into your Exercises1.txt.

Setup for questions Q1-Q6

There are programs

/usr/ftp/pub/anton/lvas/efficient/25/q1a
/usr/ftp/pub/anton/lvas/efficient/25/q1b
/usr/ftp/pub/anton/lvas/efficient/25/q1c
/usr/ftp/pub/anton/lvas/efficient/25/q1d
/usr/ftp/pub/anton/lvas/efficient/25/q1e

They run on the command line and take no parameters.

You need only one transcript for all the programs to answer the following questions, but point out in your answer where

Q1: Which of these programs are fast enough? Why?

Q2: Which of these programs are CPU-bound?

Q3: Which of the CPU-bound programs spend most of their time in user mode?

Q4: Which of the CPU-bound programs spend most of their time in system mode?

Q5: Which program consumes the most memory?

Q6: Which program consumes the most CPU time?

Setup for questions Q7-Q11

The source file /usr/ftp/pub/anton/lvas/effizienz-aufgabe23/magichex.c can be compiled with

gcc -O /usr/ftp/pub/anton/lvas/effizienz-aufgabe23/magichex.c -o magichex

and the resulting binary can then be run with, e.g.:

./magichex 3 0  

(Append >/dev/null to avoid cluttering your transcript with the output).

This is the invocation you should use for answering the questions below.

Show the relevant parts of the output of gprof along with the answers for the following questions.

For answering the questions that deal with coverage, make sure to delete magichex.gcda (if present) before making the run for producing your data; otherwise the results of multiple runs will accumulate in magichex.gcda; your answer should only be about one run with the invocation above.

Q7: Which function consumes the most time according to the profile?

Q8: Which function is called most often?

Q9: Which function calls sethi most often

Q10: Which function is called by lessthan most often?

Q11: According to the gcov output, which line in solve is executed most often?