Teaching Tips - Time
Published on: 2005-8-25
Teaching Tips - Time
2005-08-25T19:20:00
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:
main()
{
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.