CodeSOD: Just a Bit Bad

Eyal N works on some code which relies on "bit matrices": 2D arrays of bits. Since they are working in C, in practice this means that they have one giant array of bytes and methods to handle getting and setting specific entries in the matrix.

One day, Eyal sat down to do a remote pair-programming session with a co-worker. It started out alright, but the hours ticked by, the problem they were dealing with kept showing thornier and thornier edge cases, and instead of calling it a day, they worked late into the night.

The next morning was full of regrets, both in terms of too little sleep and in terms of code artifacts. The code that they'd written over night was tangled, incoherent nonsense. It compiled, and it looked like the outputs were correct, but the actual process was as opaque as lead painted with Vantablack.

Deep inside that pile of sewage-smeared spaghetti code, Eyal found that they had found a special approach to zeroing out a block of memory.

Now, if you've ever worked in C, you know that creating and setting blocks of memory is easy- arguably too easy. If, for example, you want an array of bytes that's initialized to zero, you can do it with one step using the method calloc. If, for some reason, you want to do it in two steps, you can combine malloc with a memset call.

Or, if you want to do it in many, many more steps, you can do this:

static void matrix_set(matrix_t mat, size_t row, size_t col, bool val, size_t dim) { set_bit(mat, row * dim + col, val);}// ...for (size_t i = 0; i < dim; i++) { for (size_t j = 0; j < dim; j++) { matrix_set(mat, i, j, 0, dim); }}

Starting with the for loop, you can see that they call matrix_set once for every bit in the matrix. matrix_set itself just calls out to set_bit after doing a little arithmetic to find the correct 1D index for a given 2D coordinate.

It's a simple enough bit of code. It certainly doesn't exhibit any deep horrors, but it's impressive that they managed to turn a single, high-performance operation into a gruelingly slow operation which needs to set values eight times for every byte in the matrix.

"I was practically sleeping in my chair, struggling just to keep my eyelids open, and wasn't exactly paying attention to what was going on," Eyal adds in defense.

They didn't supply the implementation of set_bit, but the method poses a bit of another problem. No matter how you slice it, you need to & or | a value with the current value of the byte containing the bit. Which means you have to read the current value of the bit. Or, as Eyal explains:

I later realized that this code technically exhibits undefined behavior, since clearing the first bit in every byte involves reading freshly-allocated, uninitialized memory.

The moral of the story: get some sleep.

[Advertisement] ProGet supports your applications, Docker containers, and third-party packages, allowing you to enforce quality standards across all components. Download and see how!