Posted on

Fearless refactoring

C++ is a much more complicated language than I ever imagined. I’d had a little bit of exposure to it earlier in college, and I hated it because of the amount of setup that was required to get it running. We were introduced to CodeBlocks and Eclipse, but both of them just seemed so clunky. Figuring out compiler options, makefiles, and trying to get programs that compiled on my home development Ubuntu workstation and on the schools Windows RDS environment and the professor’s autograder was just just too much. So when I really started diving into Python, it was like coming out from being underwater too long and getting that breath of air.

Working on the Pennykoin Cryptonote codebase got me a bit more comfortable with it. I stil didn’t understand half of what I saw. Half of it was the semantics of the code itself, half of it was just trying to understand the large codebase itself. Eventually I was able to figure out what I was looking for and make the changes that I needed to make. I never really felt comfortable making those changes, and even less so publishing and releasing them. That’s because the Pennykoin codebase had no tests.

I’ve spent the last few days working on some matrix elimination code for my numerical methods class. During class, the professor would hastily write some large, procedural mess to demonstrate Gaussian elimination or Jacobi iteration, and not only did I struggle to understand what (and why) he was doing, but he often ran into problems of his own and we had to debug things during lecture, which I thought was wasteful of class time.

As I’d been on an Uncle Bob kick during that time, I decided I would take a TDD approach to my code, and began what’s turned out to be a somewhat arduous process to abstract and decouple the professors examples into something that had test coverage, and allowed me to follow DRY principles. Did I mention that our base matrix class had to use C-style arrays using pointer pointers? Yes it was a slog. Rather than be able to use iterators through standard library arrays, every matrix operation involves nested for loops. I’ve gone mad trying to figure out what needs dereferencing, and spent far too long tracing strange stack exceptions. (Watch what happens when have an endl; at the end of a print function and call another endl; immediately after calling that function…

I started out working on the Gaussian elimination function, then realized that I needed to pull my left hand side matrix member out as it’s own class. Before I did that I tried to create my own vector function for the right hand side. So I pulled that out, writing tests first. Then I started with my new matrix class. I ran into problems including a pointer array of my vector class. For reasons that I’ll not get into, I kept the C-style arrays. I slowly went through my existing test cases for the Gaussian class, making sure that I recreated the relevant ones in the matrix class. Input and output stream operators, standard array loaders (for the tests themselves), equality, inequality and copy functions were copied or rewritten. After one last commit to assure myself that I had what I needed, I swapped out the **double[] lhs member for matrix lhs, and commented out the code within the relevant Gaussian functions with calls to lhs.swapRows(). Then I ran the tests.

And it worked

Uncle Bob talks about having that button of truth that you can hit to know that the code works, and how it changes the way you develop. I’m not sure if he uses the word fearless, but that’s how it feels. Once the test said OK, I erased the commented code. Commit. Don’t like the name of this function? Shift+F6, rename, test, commit. These two functions have different names, but do the same thing, with different parameter types? Give them the same name and trust the compiler to tell the difference. Test OK? Commit.

It’s quite amazing.

I spent several hours over the past few days working on adding an elementary matrix to the matrix elimination function, and I made various small changes to the code, adding what I needed (tests first!) and making small refactors to make the code clearer. I’ve had to step into the debugger a few times, but it’s going well. There’s still one large function block that I’ve been unable to break down because of some convoluted logic, but I’m hoping to tackle it today before moving on. And I’m confident that no matter what changes I make, I’ll know immediately whether they work or not.

Posted on

Gaussian Elimination with TDD C++, Part 1

I’m pretty pleased with myself. I managed to pull an epic coding session Friday night and met the deadline on a school assignment. I almost used the word finished there, but I merely got it working. As Uncle Bob said, getting it working is the first step to completion, refactoring and cleaning it up is the next.

The purpose of the assignment was to implement a Guassian Elimination function in C++. The professor, an old Fortran/C++ veteran who had done a lot of scientific matrix work back in the day, wanted us to use pointer pointers for the matrix rows, to make swapping rows faster. They gave us the following specification of how the Matrix would be represented in a data file:

3 // int N representing the size of the matrix A
1 1 1 // values of A[row i]
0 1 1 // A[i+1]
0 0 1 // A[i-N]
1 1 1 // right hand side

The professor then went through the algorithm for solving such a matrix on the board. Later they showed us how to generate datafiles with solvable problems for testing, but we’ll skip over that for now.

The example that the professor did in class was a bit of a mess, so I went looking for better examples. Rosetta Code has examples of Gaussian Elimination in many different programming languages. The C version is pretty close, but even looking at the gauss_eliminate function here, we can see that it’s doing a lot and can further be broken down into smaller functions. 

void gauss_eliminate(double *a, double *b, double *x, int n)
{
#define A(y, x) (*mat_elem(a, y, x, n))
    int i, j, col, row, max_row,dia;
    double max, tmp;
 
    for (dia = 0; dia < n; dia++) {
        max_row = dia, max = A(dia, dia);
 
        for (row = dia + 1; row < n; row++)
            if ((tmp = fabs(A(row, dia))) > max)
                max_row = row, max = tmp;
 
        swap_row(a, b, dia, max_row, n);
   
        for (row = dia + 1; row < n; row++) {
            tmp = A(row, dia) / A(dia, dia);
            for (col = dia+1; col < n; col++)
                A(row, col) -= tmp * A(dia, col);
            A(row, dia) = 0;
            b[row] -= tmp * b[dia];
        }
    }
    for (row = n - 1; row >= 0; row--) {
        tmp = b[row];
        for (j = n - 1; j > row; j--)
            tmp -= x[j] * A(row, j);
        x[row] = tmp / A(row, row);
    }
#undef A
}

My experience with C++ has been limited, mostly schoolwork with CodeBlocks and Eclipse; I prefer using JetBrains these days. And I’ve never done tests in it, so after I set up a new repo the first thing I did was spent some time figuring out Google Test before I wrote my first line of code. I started with making sure I could load files, then started writing output helpers, overloading the ostream operator and creating a print() function.

Let me say: Test Driven Development is HARD. It requires a lot of thought up front about what it is that you are trying to do. I started off with a todo list: 

- call GaussianElimination function
- read file from file system
- get size from file
- create matrix(size)
- load vector data from file
- create 2d vector array size N
- initialize matrix with values

and started working through each of them, going through the red light/ green light cycle: writing a test that would fail, then implementing the code that would make that test pass — and NOTHING MORE. Like any discipline, it’s hard. But the effect is amazing. Having a magic button that lets you change code and get [ PASSED ] back after is exhilarating.

I’ll admit that I cheated a bit as the deadline approached. I hadn’t implemented proper comparison operators for the Matrix class, so I was doing everything by eyeball before I got to the point where the code worked and I could submit for credit. The result was still a far cry from the way I usually operate, with a bunch of manually entered code.

I’ll share more in a further post.