How to teach to write optimized code

Question

While reviewing someone's code I found many problems, such as writing lots of loops instead of a single loop.

For example let's take the case of basic square matrix multiplication.

Both matrices can be created in a single loop (with user input). Instead people write one loop for each matrix, so they are unaware of Loop Optimization.

Another problem is creating lots of variables.

They are very bad practices.

How to can I teach them the importance of code optimization?

Answer 1

In most cases, writing optimized code is actually easier to write (and to debug) than code which isn't optimized.

If you want to show them this, then you can show them a comparison between optimized code and their code. For the example you gave (this is pseudo-code):

# matrix creation, lets assume that they are 2x2 matrices.
firstMatrix := empty 2x2 array of doubles. 
secondMatrix := empty 2x2 array of doubles. 
for i from 0 to 4:
    # ask user to enter number for first matrix at (i/2,i%2)."  (0,0) for the top-left value in the matrix
    print "enter number for first matrix at (" +(i / 2)+","+i % 2+")."
    firstMatrix(i / 2, i % 2) = user_input()
    # ask user to enter number for second matrix at (i/2,i%2)."  (0,0) for the top-left value in the matrix
    print "enter number for second matrix at (" +(i / 2)+","+i % 2+")."
    secondMatrix(i / 2, i % 2) = user_input()

# matrices now initialized

Notice that the pseudo-code has only 1 loop that creates both matrices. So that's the optimized code, as you referred to it in your question.

Also, that code uses a minimal number of variables. So that's two for the price of one.

Then if you show them that writing code like that is shorter, and easier to understand, they'll start to write more optimized code.

Additionally, you can point them to sites that show optimized code vs. non optimized code from the perspective of complexity, as well as readability.

Answer 2

you not going to like this answer, but Don't teach it!!

At least, don't teach it unless your teaching a 300-400 level course in college.

Most code optimization is very tiny benefit, especially since modern compilers are able to do many of the optimizations for you and it's entirely possible for someone to optimize wrongly an slow something down instead.

More importantly code optimization takes time and often leads to less readable code, which is bad. It's very rare that any optimization other then algorithmic (Big O level) ones will ever be needed, and code readability is a huge and important factor of every program. You don't want to teach students to sacrifice readable, maintainable, and testable code for theoretical optimizations that often will not have a noticeable impact on rate that the code runs. Leave that to be learned in upper level coding courses only after they are able to write solid readable code.

The only type of optimization I would every worry about teaching is Big O level algorithmic optimizations, and even then I probably wouldn't worry too much about that until their in 200 level college courses.

For low level courses I would demonstrate the difference between quick sort and some naive sort, to show algorithms can matter, and not much else. Maybe give a quick example of a nested loop being much slower then two non nested loops, but I would not be emphasizing writing code efficiently, only showing that efficiency concepts exist, it's up to later classes for students to understand and make efficiency decisions.

At 200 level courses I would start stressing how things could be optimized algorithmically to some degree. You would likely be teaching more about different container types, linked lists vs arrays vs hash maps, so just explaining these algorithms in a way that touches on why one would use one over the other is good. You will be teaching them how skilled programmers use tricks to gain efficiency benefits by demonstrating the common algorithms they cam up with, which is great. However, the emphasis now is less about coming up with great algorithms themselves, and mostly knowing that algorithm decisions can matter and they should be picking the best collection/tool for the job based off of it's algorithmic efficiency.

At 200 level you can also start to point out particularly horrible Big O mistakes. The most obvious example would be including a nested for loop that does not need to be nested. Telling your students "try not to have multiple loops inside each other if you can avoid it, especially not if each of them can be large" is okay at this level. Give an example of why nested loops can be absurdly slow and how you can avoid it is okay, often this can be tied in with picking the right tool for the job by showing how iterating over an array once with a precompute phase to put stuff in a hash map before a second iteration is faster then the nested loop, and look here is a demonstration of another reason to use a hash map.

at 300 level courses your ready for a course that focuses entirely on algorithms, this one course should explain Big O vs Big Omega etc, give means of measuring algorithmic complexity, and really hammer in that algorithms matter. From this point on always bring up algorithmic complexity and ways to make better algorithms, their ready to adjust for this. However, still be quick to point out when an optimization was needlessly complex.

Sometime around 300/400 level optimization considerations other then algorithmic can be tackled as well. I would suggest tying this in with study of the physical limitations of a computer though. When you study how memory actually works you can give an example of how, for example, ensuring you access data 'nearby' each other to avoid cache hits is useful.

At this level of class I suggest explaining how the computer works and how this affects optimization decisions. Then give them an 'unoptimized' piece of code and tell them to optimize it. Write some automated testing scripts that will run the same code 1000 times on a large sample size, compare wall clock before/after it's run, and figure out the average speed of the code, then tell them you want them to provide N boost to it's runtime.

I had one such project where I got something like a 25 x speed increase when doing math on a 3 dimensional cube where we had to consider the content of each 'touching' cube. The biggest increase was changing the logic to minimize cache hits, but things like loop unrolling and replacing methods with macros also came into play, these was using a C compiler with all optimizations disabled. It really helped to show how drastic optimization can be.

However, it's important to always stress readable code is most important and that premature optimization is bad, repeat constantly to only optimize proven slow points and to test your code to identify where the slowdowns occur before trying to optimize.

If your not teaching high level courses though, just don't do it. It's likely to lead to worse code most of the time and just adds an extra thing for students to learn and get confused about. Focus on their writing good maintainable code and only after they have mastered that should they worry about 'efficient' code.

Answer 3

First kind of optimisation is taking things out, a 2017 GCSE exam question had something like

FOR i=1 to len (string)

Len() will be called every time you go round the loop.

The trick here is to help the student spot things that don't change from one iteration of the loop to another. They need to be moved out and stored.

This leads to another kind of optimization, trading space for speed

length=Len(string)
for i=1 to length

This uses up a small amount of space, but saves repeated calls to Len(). The rule to teach is that if something 'expensive' to calculate is done repeatedly, then store it.

Another, teachable, but unlikely to be in exams is divide and conquer. For instance working out $x^y$. It's tempting to write a loop:

t=x
For i = 2 to y
    t = t * x

However we can see that $x * x$, i.e. squaring it, takes the same time as any other multiplication, but gets us twice as far, so we get something like

while y > 1
  if y is even then x*x , y = y /2
  if x is odd then x*t , y = y-1

The most mathematically challenging is dodging non-linear effects.

The time taken to sort a set of numbers goes up faster than the size, i.e. an array that is twice as big will take more than twice as long.

That means breaking it up into smaller arrays, sorting them and merging can turn a problem that grows as the square of the size of the array ($O(n^2)$), to one that's about $n \log_2{n}$ which is still non linear but a lot faster.

A few rules of thumb:

• It is easier to make correct code fast, than to fix buggy fast code.
• Premature optimization cause programmers to age prematurely.
• Better algorithms beat better processors.

Answer 4

Optimisation should not be taught as part of a general programming course. It should be taught as part of compiler design. This is because:

• Compilers are better at optimisation than humans.
• Premature optimisation gets in the way of the compiler, and can lead to less optimal code.
• Premature optimisation makes the code harder to read, and maintain, leading to more bugs, and long term degradation of the code (slower code).

That said, this is how to optimise, this is what should be taught.

• Optimise for readability.
• Big O: There is not much your compiler can do to help you here. Choosing a good algorithm makes the biggest difference. Therefore optimise for big O.
• First get it to work: passing all tests. Then get it to work fast.
• Only apply manual optimisations if there is a need for it.
• When doing an optimisation, measure, optimise, measure, compare.

The rest is detail.

If you are teaching optimisation techniques, then after teaching, why not to do it, you should start with techniques and patterns that always work. Look these up in a good book on optimisation, as most of the time intuition is wrong. And remember measure, optimise, measure, compare.

Answer 5

The best encouragement is demonstrating how some simple changes can result in orders of magnitude improvements for a specific task. The best example I've seen took a synthetic benchmark, and between un-optimised 'C' and 10 lines or so of hand-crafted NEON assembler (together with a cheap re-arrangement of the base dataset), resulted in something like a 1:30,000 speedup.

This video was one example I found quickly, it's aimed at showing how you can help the compiler when writing code.

Once you've established the value of optimised code, then you can go on to address where optimisations make sense. Code that only runs once might be best written for reliability and readability, code like memcpy may well be hand-optimised down to the level of machine micro-architecture. Code written for portability might be optimised differently.

When people try to optimise code by intuition, it is easy to make the wrong trade-offs. Most obviously when it comes to cache utilisation, but there are plenty of other micro-architectural traps which are less visible. Benchmarking is a critical part of optimisation (and this underpins the value message). There will be optimisation folklore which no longer holds with modern hardware and modern compilers - and sometimes hinders the compiler or readability.

What you really need to focus on teaching (after you have set the scene for how optimal code is good), is simple, cleanly structured code. At most levels, letting the compiler do its job is the important thing. In the example of repeating a static calculation, the detail could equally be 'written like this, you seem to expect the size to be changing - is that what you meant to convey', rather than 'you do realise the compiler only needs to evaluate that once'.

The opposite end of the scale is using a genuine resource constrained platform (as many of us learnt with), but these can be misleading with single level memory architectures and simple pipelines. In the MCU domain, interrupt latency is likely to be the limiting resource, rather than memory bandwidth (unless you're bit-banging a VGA output at the same time as running a 6502 emulator).