Algorithms as objects

We usually think of an algorithm as a single function with inputs and outputs. Our algorithms textbooks reinforce this notion. They present very concise descriptions that neatly fit in half of a page. This is fine until one actually attempts to implement it as a single function; all the little details add up until you’re left with a gigantic, monolithic function.

That monolithic function lacks readability; it’s so long that you have to scroll for a full minute to get to the end. It’s nested so deeply that you have to scroll horizontally to read it. It’s nigh-impossible to trace the state of a variable that was declared at the top as it mutates every other line.

Because of that, the function also lacks maintainability. Any single line-change has the potential to affect the many lines below it, altering the behavior in unpredictable ways.

Nobody wants to touch this code because it’s such a pain to get any context. There are just too many details. It’s like trying to learn the purpose of an airplane by reading an aerospace engineering textbook.

Complex code requires abstractions. Abstractions help communicate higher level concepts, improving readability and therefore reducing the time to fix bugs or add new features.

A compiler takes code as input and spits out an executable as output. Do you think compilers are implemented as a single monolithic function?

There’s a good chance that your monolithic function should be refactored into one or more classes. It’s okay to implement an algorithm as an object. I encourage it, even.

In this blog post I’ll walk through a handful of code smells that indicate you’ve got a class instead of a function, and then follow it up with code examples demonstrating code that exhibits these code smells. Finally, I’ll demonstrate how we might refactor the offending functions into classes.

Continue reading “Algorithms as objects”
Advertisements

Case Study: Reusing Double Dispatch for serialization

In my previous blog post, I gave a tutorial on the double dispatch pattern. I mentioned that you could reuse the pattern for a variety of things, one of those being I/O. In this blog post, we’ll walk through how we can add serialization support for our class hierarchy without touching the classes themselves.

Continue reading “Case Study: Reusing Double Dispatch for serialization”

Stop reimplementing the virtual table and start using double dispatch

Okay, you’ve ended up in a situation where you’re either

  1. using dynamic_cast* to find out the actual type of a pointer, then moving on to do what you really want, or
  2. checking some enum in a base class to see which derived class it really is so that you can perform type-specific operations on it

* or some other form of run-time type information

You know something is wrong with this, but you can’t think of a satisfactory solution. You’ve already considered adding another virtual function on the base class, but you’re worried about how many virtual functions are already there, or the impact that this might have on consumers of the base class.

Good on you for recognizing that. Admitting you have a problem is the first step to solving it 🙂

In this tutorial, I’ll talk about one solution to this problem I’ve had some success with: the double-dispatch Visitor pattern. With it, you can trim down those long if-else if blocks, separate responsibility into manageable pieces, and even stabilize your interface better.

Continue reading “Stop reimplementing the virtual table and start using double dispatch”

Oops!… I violated ODR again

ODR_Again

Often when you’re trying to debug a piece of code, the debugger steps into a block you didn’t expect it to. Most of the time this is because your code has a logic error, and it wasn’t doing what your mental model thought it would.

Other times it’s because you accidentally compiled with optimizations on, and the compiler did some magic to make the outcome the same even if the code was different.

This post talks about a scenario where it’s neither of those things. Instead it’s something much more dangerous and difficult to detect — a violation of the One Definition Rule (ODR).

In this post I’ll talk a little about C++’s One Definition Rule, and then discuss how one manifested itself in a project I was working on. I’ll talk about how to detect them, and how I resolved mine.
(I talk a lot about violating ODR in the context of a tool I use (SWIG), but the manner in which I violated ODR is applicable to any C++ library that links to another.)

Continue reading “Oops!… I violated ODR again”

The joys of forward declarations: results from the real world

random_graph
This is not what you want your dependency graph to look like (graph generated using https://skanderkort.com/erdos_renyi_graph_generator_analyzer)

As a C++ project grows and matures, the following line is inevitably spoken: “The build is too slow”. It doesn’t really matter how long the build actually takes; it is just taking longer than it was. Things like this are an inevitability as the project grows in size and scope.

In this post I’ll talk specifically about my recent use of forward declarations to vastly improve build times on one of those projects, and how you can too.

Continue reading “The joys of forward declarations: results from the real world”

A true heterogeneous container in C++

heterogeneous_container

Oftentimes I see questions StackOverflow asking something to the effect of

“Can I have a std::vector that holds more than one type?”

The canonical, final, never-going-to-change answer to this question is a thorough

“No”

C++ is a statically-typed language. A vector will hold an object of a single type, and only a single type.

“But…”

Of course there are ways to work around this. You can hide types within types! In this post I will discuss the existing popular workarounds to the problem, as well as describe my own radical new heterogeneous container that has a much simpler interface from a client’s perspective. Continue reading “A true heterogeneous container in C++”

Representing plane intersections as a system of linear equations

DoritoPlanet

When you are watching a digitally-rendered battle onscreen in the latest blockbuster movie, you don’t always think about the “camera” moving about that scene. In the real-world, cameras have a field of view that dictates how much of the world about them they can see. Virtual cameras have a similar concept (called the viewing frustum) whereby they can only show so much of the digital scene. Everything else gets chopped off, so to speak. Because rendering a digital scene is a laborious task, computer scientists are very interested in making it go faster. Understandably, they only want to spend time drawing pixels that you’ll see in the final picture and forget about everything else (outside the field of view, or occluded (hidden) behind something else).

Our friends in the digital graphics world make heavy use of planes everyday, and being able to test for plane-plane intersection is extremely important.

In this post, I’ll try to break down what a plane is in understandable terms, how we can create one given a triangle, and how we would go about testing for the intersection between two of them. Continue reading “Representing plane intersections as a system of linear equations”