1
$\begingroup$

While I'm sure that the comp-sci 101 mistake of having a triple nested loop with two recursive calls is sure to be cured by a decent comp-org class, it can have the unintended side-effect of turning students, enlightened by this hidden knowledge of registers and memory management, become obsessive about unrolling loops in trivial ways and trying to out-O3 the compiler like it's ($CURRENT_YEAR - 40).

What is the prevention to this error of learning in the course of teaching the subject? I doubt that most students will ever be in a situation where there will be a difference caused by writing something like struct baz{char a; int z; char b;};.

Improve this question
$\endgroup$
2
  • $\begingroup$ I'm not getting the point of your question. Parts of it seem inconsistent with other parts. Perhaps you are being "clever" at the expense of understanding. $\endgroup$
    – Buffy
    Jan 19, 2020 at 23:49
  • 1
    $\begingroup$ Do you mean, they're trying to "help the compiler to make optimizations" instead of focusing on correctness, readability and simplicity? $\endgroup$
    – Michel Billaud
    Jan 21, 2020 at 6:18

3 Answers 3

Reset to default
2
$\begingroup$

The way that everyone generally learns this lesson is to spend a significant amount of time tracking down an efficiency issue that is nowhere near where you expected it to be. I'm not sure there's another way to really learn the lesson.

As an example, here's an exercise which illustrates the problem:

Write an implementation of an open-addressing hash table set. The keys are 64-bit integers. There are two operations: initialise, and "add an element if it doesn't exist, return a boolean which says if it was already there".

Use a prime-sized table, and make sure it grows if it gets too full (e.g. require that it start modest-size and grows if the length of a collision chain is greater than some constant). The hash function should be specified to eliminate that as a variable, but of course students are free to implement it however they like.

The exercise is to write it and test it for correctness as well as you can, doing all the optimisations that you can think of, do all the timings you want, but don't actually profile it yet.

Give your best guess as to where the biggest remaining bottleneck is. Now use instruction-level profiling to find out where it actually is.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "grows if the length of a collision chain is greater than some constant" Isn't there a possibility here that several of the hashes could actually be consecutive integers, so that resizing the array doesn't "split up" the chain, hence the array needs to be resized again immediately? I'm assuming that's not the bottleneck you meant, because you only offered this as one example of how to decide when to resize the array. $\endgroup$
    – kaya3
    Jan 29, 2020 at 5:18
  • $\begingroup$ It's a possibility. Use quadratic rehashing if you're concerned. And you're right, that's not it. $\endgroup$
    – Pseudonym
    Jan 29, 2020 at 5:20
2
$\begingroup$

I'm honestly not that I would address this problem at all within my own courses, but if it is to be faced, I suspect that the solution would be something like this:

  1. Immerse students in their current layer.
  2. Really teach the metaphor and thought-process of the layer that they are currently in, and only accept code that utilizes that model of thinking.
  3. Warn students about the dangers of premature optimizing
  4. Show students how to use a profiler in order to figure out what is actually slowing their code down. Tell students to address their efforts here.
Improve this answer
$\endgroup$
3
  • $\begingroup$ Note: anvari.org/fortune/Miscellaneous_Collections/… $\endgroup$
    – Buffy
    Jan 21, 2020 at 13:48
  • $\begingroup$ I'll note that most source level attempts at optimization actually get in the way of a compiler doing a good job. If the program describes 'in detail' how to do something, rather that just what is to be accomplished, the compiler may be stymied to improve it. $\endgroup$
    – Buffy
    Jan 21, 2020 at 13:56
  • $\begingroup$ And ask the student to show how much their optimizations have improved the performances. $\endgroup$
    – Michel Billaud
    Jan 21, 2020 at 17:38
2
$\begingroup$

It might be helpful to use a tool such as Compiler Explorer. It allows one to put side by side C code and its compiled version. It can be used to show that the compiler often generates the same assembly code for the "naive" code and the hand "optimized" one. It also supports compiler flags, so you could use it to show the difference between unoptimized code and -O3.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.