The hardest interview I ever had: someone told me to go up to a whiteboard and solve a programming problem, in code, optimally, on the first try.
It’s a basic fact of our field that we iterate toward the final product. Not unlike a sculptor bringing the David out of a piece of marble, we go from a rough piece of code toward a refined piece of code in a series of stages.
We usually start with a piece of pseudocode that generally describes what we want a function to do. This can be written in basically any format (text, outline, pseudocode, diagram, etc.), but it has to detail the basic elements we expect to find in our function.
Specifically, our outline serves these two purposes:
- Expose functionality for better breakdown
- Reveal the interface elements that we might want or need
If we skip this step entirely, we tend to spend a lot of time reworking our basic code as we discover features we wanted to include.
Exposed Interface with Dynamic Allocation
Next, we write the first draft of our code. At this stage, we are basically limited to the information provided by the rough outline.
Because we don’t necessarily know what size our final data will be, we dynamically allocate space using malloc() or calloc(). This allows us to quickly modify the size and range of our data as we determine what elements we will include in the final product. This serves the secondary purpose of preserving our outline, as we have not yet optimized away extraneous variables required for simple reading.
Furthermore, because we don’t yet know how many of our parameters will be standardized (through precompiler definitions or static variables), we want to take as many of them as we can into account. At this stage, our interfaces can be incredibly daunting, because they allow us to tweak EVERY parameter through the function call. We also want to pass pointers into these functions, but we’re not sure whether to make them const, so there’s a risk of silly errors.
Note: At this stage, we might start defining structures to carry these parameters, just to reduce the size of the interfaces.
Refined Interface with Dynamic Allocation
As we move on, we begin to determine the size of our parameters and the scope of our data. While we’re not yet ready to jump to static allocation, we are becoming aware of what that statically allocated data might look like.
We are also ready to restrict the interface, as we have determined which parameters we intend to manipulate and which we will set to default.
There are two approaches to entering this stage:
- Rewrite your functions to restrict the interface to the core function
- Write wrapper functions to restrict the interface that the user deals with
Generally speaking, it’s safer and easier to go with the latter.
Refined Interface with Static Allocation
Now we’ve reached the point where we basically know what our data will look like. We’ve made the tough calls, determined the final flow of the code, and settled on the size and types of data we’ll employ at each level.
Now we begin replacing dynamic allocation with static allocation. If you’ve structured your interfaces properly, this is about as simple as replacing all -> with . and removing all allocation and free operations.
Note: Don’t forget to clear the values in your static variables, especially if you were relying on calloc() to do that.
Minimal Interface with Static Allocation
Now we perform the true optimization stage.
Because we’ve finally settled exactly how our code will work, we can begin to restrict the inputs to our functions with const and similar keywords. This restricts our interfaces to the smallest and most restricted they can be, resulting in code that is reliable and easy for the end user to work with.
We also start to clean up our headers, removing any of the “old” function interfaces which are wrapped by the cleaner interfaces. This helps restrict the interfaces and prevents the end user from doing dangerous things.
We also start working with our variables. Depending on the level of optimization required, we start to do things like move things to global scope or reorganize code to reuse static variables (which I generally do not recommend if it makes the code harder to read).
This stage should produce a final set of code that you’re happy to run and maintain, but there is another possible layer of optimization you can employ…
Optional Library Optimization
This is the sort of thing programmers had to do in the early days, to maximize utility of tiny systems.
Here we start reusing variables on the register level, optimizing out log code (and other valuable information), and generally render the code impossible to maintain.
Compiling with optimization does much of this naturally.
Generally speaking, this is only recommended for code you are virtually 100% certain you will never have to touch again.