August 25th, 2005


Teaching Tips - Time

Just like any other science, Computer Science (which you really can't call a science on its own - but let's not argue on that point) too is experimental and quantitative. But most of our universities and engineering colleges don't think so - a CS degree from these places is equivalent to a M.A in English Literature. In the University where I studied CS, marks were awarded on the basis of the weight of the answer paper bundle. A paper on say for example, compiler design would contain exceedingly complex questions of the form:

What is a compiler? Explain its working - (15 marks)

Most of us soon realized that the ability to write in flowery language and fill the paper with `gas' was the sureshot way to achieving `pass with high distinction'. I became sort of an expert in this subtle art - I still remember writing an essay about the use of computers in space exploration to act as `filler' for a 15 marks question in an `Operating Systems' paper; that I got away with it is a tribute to the high standards of our technical education system.

Nowadays, as a teacher, I feel that the least I can do to my students is to show to them that what they are learning is *NOT* English Literature (there *is* a connection between literature and programming - more on it later) but something quantitative and experimental. Over the years, I have collected a bag of simple tricks which help to reinforce this idea. As and when time permits, I will be putting up a few of them on this blog.

A matter of `time'

Computer programs have to be correct, and they have to be efficient. Let me show a simple trick I demonstrate in the very beginning of my C programming classes; the audience is mostly students who have just started learning to write code.

Look at the code below:

	int i, j;
	for(i = 0; i < 40000000; i++)
		j = 1;
  • How much time does the program consume? Estimates of the form 1 milli second, 1 second, 10 seconds, 10 hours etc are what is required.
  • Difficult to answer unless you give some more info - say the machine has clock speed of 160MHz. (I demonstrate this on a 450MHz AMD K6 machine).
  • A few guys will answer by counting the number of `elementary operations' the program is doing and assuming that a clock speed of 160MHz means the machine can do 160*10^6 operations per second.
  • You can now discuss why this estimate is not accurate (problem with assuming 1 clock/instruction, problem with counting exact number of instructions involved in the code .. go as deep as you want keeping the student's maturity and exposure in mind)
  • You now ask for experimental results - use the `time' command to measure time taken - discuss why you have 3 values in the output of time.
  • Challenge the students to generate test cases where `real' time will be greater than `user+system'.
  • Is it possible to make the code execute the statement (j=1) 40000000 times and yet make it run faster?
  • Give some hints - the total execution time depends on the `loop overhead' - you reduce that and you get a speedup.
  • Somebody will come up with this solution:
    for(i = 0; i < 20000000; i++) {
    	j = 1;
    	j = 1;
    How profitable is this `unrolling' repeated many times?
  • Talk about compiler optimizations.
  • As an exercise, ask the students to discover more optimization strategies.

Once you lead a few such `exploration' sessions, your students will start thinking of the computer `lab' as being similar to the Physics or Chemistry lab - a place where you conduct experiments, take measurements and have lots of fun! (ask me if you want to know how to have fun in a Chemistry lab).