<p>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.</p>

<p>As an example, here's an exercise which illustrates the problem:</p>

<p>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".</p>

<p>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.</p>

<p>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.</p>

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

CC BY-SA 4.0
2020-01-29T05:18:38.923Z
*"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.
kaya3
CC BY-SA 4.0
2020-01-29T05:20:18.983Z
It's a possibility. Use quadratic rehashing if you're concerned. And you're right, that's not it.
Pseudonym
CC BY-SA 4.0
2020-01-29T01:15:30.903Z
2020-01-29T01:15:30.903Z
Pseudonym
<p>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:</p>

<ol>
<li>Immerse students in their current layer.</li>
<li>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.</li>
<li>Warn students about the dangers of premature optimizing</li>
<li>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.</li>
</ol>

CC BY-SA 4.0
2020-01-21T13:48:41.480Z
Note: http://www.anvari.org/fortune/Miscellaneous_Collections/362740_the-first-rule-of-program-optimization-dont-do-it.html
Buffy
CC BY-SA 4.0
2020-01-21T13:56:18.863Z
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.
Buffy
CC BY-SA 4.0
2020-01-21T17:38:56.273Z
And ask the student to show how much their optimizations have improved the performances.
Michel Billaud
CC BY-SA 4.0
2020-01-21T13:39:30.507Z
2020-01-21T18:37:26.967Z
2020-01-21T18:37:26.967Z
Ben I.
<p>It might be helpful to use a tool such as <a href="https://godbolt.org/" rel="nofollow noreferrer">Compiler Explorer</a>. 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 <code>-O3</code>. </p>

CC BY-SA 4.0
2020-01-22T01:35:17.083Z
2020-01-22T01:35:17.083Z
igordsm
<p>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).</p>

<p>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 <code>struct baz{char a; int z; char b;};</code>.</p>

CC BY-SA 4.0
2020-01-19T23:49:20.723Z
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.
Buffy
CC BY-SA 4.0
2020-01-21T06:18:20.693Z
Do you mean, they're trying to "help the compiler to make optimizations" instead of focusing on correctness,  readability and simplicity?
Michel Billaud
<coding-style>
How to prevent organization/OS students from becoming premature optimizers?
# How to prevent organization/OS students from becoming premature optimizers?

(Asked by: username_0 on 2020-01-19)

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;};`.

**Tags:** coding-style

> **Comments:**
> **username_1**: 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.  
> **username_2**: Do you mean, they're trying to "help the compiler to make optimizations" instead of focusing on correctness,  readability and simplicity?  

---

## 3 answers

### Answer by username_3 on 2020-01-29. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_4**: *"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.  
> **username_3**: It's a possibility. Use quadratic rehashing if you're concerned. And you're right, that's not it.  

---

### Answer by username_5 on 2020-01-21. Score: 2

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.

> **Comments:**
> **username_1**: Note: http://www.anvari.org/fortune/Miscellaneous_Collections/362740_the-first-rule-of-program-optimization-dont-do-it.html  
> **username_1**: 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.  
> **username_2**: And ask the student to show how much their optimizations have improved the performances.  

---

### Answer by username_6 on 2020-01-22. Score: 2

It might be helpful to use a tool such as [Compiler Explorer](https://godbolt.org/). 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`.


---

