DEV Community: Nicolas Mattia

Hunt bugs down before they are merged!

Nicolas Mattia — Thu, 07 Mar 2019 08:52:18 +0000

I discuss a few reasons why catching bugs in master is more expensive than
before they are merged, try to explain why some people think this isn't true,
and talk a bit about merge queues.

Hunt bugs down before they are merged!

Here's something I heard a few times from recalcitrant coworkers after I've
asked them to write more tests in one of my signature uptight PR reviews:

The cost of fixing a bug after it has been merged into the master branch
is the same as that of fixing it before it has been merged into the
master branch.

I beg to differ! Catching a bug once it has landed in the main codebase has a
huge associated cost. It boils down to the following reasons, which I'll
describe individually in the next few sections:

When someone hits a bug in the main code base, they were most likely not looking for one, but trying to get work done.
Whomever is tasked with fixing the bug may have lost context relevant to the faulty code, or maybe they never had any to start with.
Reporting a bug creates noise in the form of tickets and pull requests (PRs).

Let's jump right in!

story time

You are a frontend engineer for a company that stores online notes. You're
tasked with writing an autocomplete function allowing the user to find notes
more quickly:


+-----------------------+  +------+
| Gr|                   |  | open |
+-----------------------+  +------+
|                       |
| Great minds.txt       |
|                       |
| Grocery list          |
|                       |
| Grrr! said the lion   |
|                       |
| ...                   |
+-----------------------+

The following HTTP call returns the list of all of a user's notes:

GET /users/<user>/notes?query=<prefix>

It gets in the way

story time

And #2 in America!

You've been doing amazing work. You got the flow. Mind like water. You're done
with your frontend changes. You spin up a local instance of the server.

You try it out and realize that the server segfaults when there are no matches.

You despair. There goes your flow. The name of the backend engineers flash
before your eyes. You consider not inviting them to your wedding. You make a
mental list of who's most likely to have introduced the bug. You consider
quitting your job and becoming a barista in a different country -- maybe even
in New Orleans. You'll need a specialty, maybe peanut butter cookies. You'll
kill it with your peanut butter cookies. People will know about them from New
England to New Mexico. You'll become famous and, in a few years, run for
president of the United States. Then you consider the logistics: your fiancée
will need to quit her job, you'll need to hire a moving service, your dog may
not survive the flight.

You stash your local changes and set out to write a test case reproducing the
issue.

Unless you're a quality analyst, you probably don't go around trying to find
bugs for fun. Most of us discover bugs while trying to get something done:
maybe you're simply using the server, or you're writing a new feature that
depends on a different feature or function. Discovering wrong behavior in a
codebase is almost always more of an annoyance than a nice surprise.

Had the bug been caught before merge, the bug reporter would most likely have
been the person who introduced the faulty behavior, and would have most likely
been expecting to encounter "some" bug (correct software on the first attempt
is a myth, sorry).

It creates noise

story time

you> @channel I'm experiencing server crashes when there are no matches on
/users/foo/notes?query=bar, anybody knows anything about this?

tom> please use @here instead of @channel

pat> @tom please don't use "at" channel

jen> @you yes I think this is related to #2551

mol> @jen #2551 was fixed last week

jen> okay nevermind, no idea @you :(

mkt> @channel lunch?

Whether you are reporting issues on Slack, GitHub, JIRA, you name it, reporting
a bug creates some noise. Some people will need to label the ticket, will try
to help you figure out the cause, others may simply get distracted because of
the extra Slack/GitHub/JIRA notifications.

All this can be avoided if bugs are caught before they are merged to master:
bugs are typically not reported before the code is part of the mainstream
codebase.

### The Hunt Mads “Hunter” Mikkelsen This one should be pretty straightforward. Finding a bug that's been introduced by a diff before merge into the master branch limits the search space to that diff only. Trying to find a bug on master means potentially having to consider the whole codebase, unless your codebase lends itself to things like bisecting.

Lack of context

story time

The VP of engineering comes to you, in his typical nonchalant tread:

VP: You'll need to fix that server crash bug.

You: But!

VP: I know it's not your area of expertise, but we need this fixed before
release.

You: But!

VP: See the bright side: you'll get to learn some Rust!

You: But... wait what?

VP: Yeah Andy rewrote the backend in rust last week. He's on holiday now
though.

You: ...

VP: Good luck! Don't forget about Engineering breakfast tomorrow.

As the VP leaves, you sing to yourself:

... there's a moooooon over bourbon street ...

Most of the time no one knows where the bug is and who introduced it. This
means that the odds of picking the right engineer to hunt down a bug are about
the same as trying to guess who in your team got their tonsils removed last --
if anybody actually got their tonsils removed.

The person tasked with fixing the bug then is not particularly likely to know
about the part of the codebase that is at fault. Even if the person who
introduced the bug is working on hunting it and fixing it, that person might
not have worked on that part of the codebase for a while. The context is either
absent or has been lost with time, which make debugging longer and more
frustrating.

This can be avoided by catching the bugs right after they've been written, and
before they've been merged.

Moar noise

story time

you> @channel I've got a fix for the server crash issue, anybody care to
review #2578?

tom> please use @here instead of @channel

pat> @tom please don't use "at" channel

jen> @you yes I'll have a look in a sec

mol> @you sure np

mkt> @channel coffee break?

Where does it end? Fixed the issue? A new round of PRs and reviews creates even more noise. At best this justifies hiring the intern whose job it is to move JIRA tickets around. Most likely it's a waste of time for everyone involved.

Why the fallacy?

So why do some people tend to think that it's more efficient to merge new
code and do damage control later (a.k.a shoot-from-the-hip coding)? Well, in
the short term, it may save time for the implementer (let's call a spade a
spade: the culprit) by:

Not writing tests or coming up with enough test cases.
Potentially merging without review.

These may save time to one person in the short term by allowing them to merge
faster and move on to other things; in the greater scheme of things however
time and energy is wasted.

Another reason why people tend to believe that fixing a bug in master isn't
necessarily worse than catching it before it is merged is that people often
don't realize that there's a cost associated with reporting bugs. And this cost
grows linearily with the number of people subscribed to the bug tracker,
involved in triage, and QA.

If you like your team, please make sure you catch your bugs before others find
them themselves!

Appendix: merge queues for greater good

Bugs are not the only way to break master, race conditions also apply to
software process. They may happen when a CI system only runs tests on a branch,
without rebasing on master first (note: some CI systems, like Travis and
CircleCI, will test both your branch as it is and after having rebased it
on or merged it into master). The following diagram lists three branches,
master, bob and alice:


bob master alice
 .    ✓      .   master is green :)
      |
 .    +------+   Alice uses `makeRainbow()`
      |      |
 .    |      ✓   branch alice is green :)
      |      |
 +----+      |   Bob removes `makeRainbow()`
 |    |      |
 ✓    |      |   branch `bob` is green :)
 |    |      |
 +---->      |   branch "bob" is merged
      |      |
      ✓      |   master is green :)
      |      |
      <------+   branch "alice" is merged
      |
      x          master is red :(
      |
      v

Alice forks a branch and used the function makeRainbow(). No bug introduced,
CI is green, everyone's happy. Around the same time Bob decides to do some
clean up, forks master, and removes the function makeRainbow(). From his
point of view, no one is using it, CI is green, everyone's happy.

Regardless of who merges first -- Alice or Bob -- the end result can't be good:
Alice's feature makes use of a function that doesn't exist in the codebase
anymore after Bob's changes. The solution to avoid those issues is to always
rebase a branch before running CI tests:


bob master alice
 .    ✓      .   master is green :)
      |
 .    +------+   Alice uses `makeRainbow()`
      |      |
 .    |      ✓   branch "alice" is green :)
      |      |
 +----+      |   Bob removes `makeRainbow()`
 |    |      |
 <----+      |   branch "bob" is rebased on master
 |    |      |
 ✓    |      |   branch "bob" is green and ready for merge :)
 |    |      |
 +---->      |   branch "bob" is merged
      |      |
      |      ?   merge is prevented on branch alice :|
      |      |
      +------>   branch "alice" is rebased on master
      |      |
      |      x   branch "alice" is red :(
      |      |
      |      |   Alice writes a new implementation of `makeRainbow()`
      |      |
      |      ✓   branch "alice" is green and ready for merge :)
      |      |
      <------+   branch "alice" is merged
      |
      ✓          master is green :)
      |
      v

The only thing you have to do is to ensure that no branch is merged without
being strictly on top of master. The simplest solution is to manually keep
track of the branches that should be merged:

Whenever someone wants to merge, their branch is enqueued.
Exactly one person pops branches from the queue, rebases them, and merges them if CI is happy.

This is a very tedious process and is better automatized by tools like bors-ng.

The Poor Man's Merge Queue

Merge queues need not be fancy. The first time we realized that we were wasting
a lot of time fixing rebase issues, my team and I came up with a very simple
solution: keep the PR numbers in a Slack channel's "topic" field. Got a PR you
want to merge? Add it to the right of the list. The left-most PR has either
been merged or failed CI? Remove it from the list, and rebase the new left-most
PR.

Save some cost! DIY merge queue.

The 5 Raisons d'Être of Testing

Nicolas Mattia — Tue, 26 Feb 2019 09:18:12 +0000

The 5 Raisons d'Être of Testing

I describe five of the reasons why I think tests are important:

Ensure that the code you've written works.
Ensure that the code you've written works tomorrow.
Ensure that the code you've written works elsewhere.
Spot usability issues early on.
Show how your feature is supposed to work, and how it should be used.

important: None of the animals used in the examples were harmed in the
making of this post.

First, let's get in the mood (or skip ahead):

story time

You are a backend engineer at MyCuteThings.com, the famous website of cute
things. Your boss comes to you and Tommy (your frontend sidekick) one Wednesday
morning and declares:

There shall be a "breed" dropdown listing two cat breeds: Persian and
Siamese. When the user selects a breed in "breed" a picture of a cat of
that breed shall be displayed to the user. Feature codename: "ninja".

-- your boss

Tommy will deal with the HTML, CSS, and whatever else frontend people use. Your
job is to provide an API endpoint that will return the bytes of the correct
picture. You find a picture of a very cute Persian cat that you save as
cat.png. You take a picture of your very own Siamese cat that you save as
CAT.png. You settle on the following REST call:

GET /cats?breed=<nameOfTheBreed>

The usage is straightforward:

if nameOfTheBreed is persian then you read cat.png, return the resulting bytes and 200 OK.
if nameOfTheBreed is siamese then you read CAT.png, return the resulting bytes and 200 OK.
if nameOfTheBreed is anything else, you return zero bytes and 200 OK (company policy GTE-421-f, introduced in 2003, forbids you from using 404s).

Because we're dealing with software, anything that can go wrong will go wrong.
We'll go over the five reasons I listed above in more details and we'll see how
tests can help you damage control.

Ensure that the code you've written works

This may be the most straightforward reason to write tests. However, while it's
valuable to know that whatever you've just written works, it's probably the
least important reason.

Testing that code works is the raison d'être of tests!!! How dare you say
that it's not important???

-- Jimmy from Nebraska

Don't get it twisted Jimmy, I didn't say it was unimportant: the other reasons
are just more important. Most of the time you'll eventually try the feature
(open the website, click Siamese, watch in awe as your cat appears on the
screen) after having written the code -- which is as much information as you'll
get from a test. You will catch bugs like "trying to open cat.jpg instead of
cat.png" straight away anyway.

Running tests as you write the code is mostly a time saver when you develop a
feature, as you (usually) have a single command to run in order to check that
you've done things correctly. Also, by writing tests close to your spec, it
acts as a deadline (once your tests are green, you're done, you can move on to
something else). Moreover by first writing a (failing) test when tasked with
fixing a bug you ensure that the bug actually exists. This is typical
TDD.

Ensure that the code you've written works elsewhere

story time

You wrote your feature and Tommy wrote his part. Feature "ninja" got merged
into the master branch, after you diligently tested it out by hand. You go home
that evening, and as you're about to start watching the third season of The
Wire (for the second time, because you first assumed you didn't need English
subtitles) you get an angry phone call from Jason, the sales rep working late
nights because he's demoing the product to people in another timezone. Jason
explains that he can only get a picture of the Persian cat. Even when he picks
the Siamese option from the dropdown. The debugging process goes like this:

You: What OS are you using?

Jason: What's an awe-hess?

At which point you realize that Jason is running your code on his Windows
machine. Which, unfortunately enough, cannot tell the difference between
cat.png and CAT.png. You sigh, put the remote down and go back to the
drawing board.

Test suites are particularly important in projects that run in several
environments. You've written code that works on your machine? Great, but it's
likely that you forgot to update some config and that the component you just
wrote will break once it's deployed somewhere else, because you relied on
something specific to your (highly tuned, very particular) system.

If you have a unit test, you'll make sure it also works on the CI machine(s).
If you have an integration test for it, you'll make sure it works on the CI
machine(s) and on the various clusters that a deploy goes through.

Ensure that the code you've written works tomorrow

story time

A month has passed, and not only are you relieved that Season 3 was much better
that Season 2, but you've also forgotten all about feature "ninja". You're
sitting at your desk at 5pm, eyeing the clock on the wall more and more
frequently. Your boss comes out of his office, forehead sweating, cheeks
blushed from anger. He scans the engineering room and his eyes lock on you. He
starts walking in your direction. You think to yourself: "This can't be good.".

Twenty minutes later, somewhat happy that your Saturday evening has freed up
(your boss and his wife were supposed to come over for dinner), you're going
through git logs with one goal in mind: trying to find who to blame for
removing the cat pictures from the repository, thereby breaking feature
"ninja".

commit 45d2fcd272a273c57033a493ca3df47a67f9bf01
Author: Jenny Marshalls <jen@mycutethings.com>
Date:   Tue Aug 21 01:15:33 2018 +0300

    Remove unused kitten pictures

You start walking to her desk, coming up with as many irrational patriarchal
arguments as possible to justify the lack of tests around your feature.

Say you write a feature that works (objectively) perfectly, although doesn't
have any associated tests. Then tomorrow I come around, and tweak your code to
add a new feature, inadvertently breaking yours. Then you blame me for
breaking my code. Don't blame me.

You can't expect anyone else to anticipate all the implications when they're
tweaking your code, because most likely even you can't. Hence it is your
responsibility to add a test spec-ing the correct behavior of your feature --
today and tomorrow.

SIDE NOTE: it goes without saying that commenting out tests is not the
right way to shoehorn my new feature into your existing code, but that kind of
stuff is hopefully caught during review.

Spot usability issues early on

When you decide to write a test for your new feature you might realize that
your interface is awkward to work with. This is really the simplest usability
check that you can perform, namely eating your own dog food.

Catching those issues before they've been merged, and before other code relies
on it, means that other people will appreciate working with your code more (and
thereby making people more inclined to try and understand and reuse your
feature -- rather than duplicating it) and it will ease the learning process for
newcomers.

Show how your feature is supposed to work and how it should be used

It's been three weeks since you blew your chance at a promotion. In order to
avoid similar situations in the future, you've added tests. Feature "ninja" has
been working seamlessly ever since.

Your sidekick Tommy tells you that Jenny needs help using a backend feature
that you wrote. Things have been weird with Jenny, you still feel guilty for
blaming her for the missing pictures and for the way you reacted to the
situation. You've tried your best to avoid a confrontation since then.

Tell her to look at the tests, you tell Tommy.

Reading tests is a great way to figure out how something is supposed to work.
It shows what the input should look like, and what the output will look like.
It shows what your feature can do as well.

If your feature has no associated examples or tests, the user has to rely on
the source code and on potentially out-of-date documentation to figure out how
it should (and should not) be used. A test is so much nicer.

Conclusion

The bottom line is that there's more than one dimension to having a working
codebase: it should be future proof, function in different environments, be
usable, and be self-describing. Tests are a great way to achieve this, and when
you pair them with a good process you'll become king of the world. Or at least a happy and efficient programmer, part of
a happy team.

Parallel Computing with DNA

Nicolas Mattia — Mon, 18 Feb 2019 10:24:25 +0000

DNA. Everybody knows that DNA is the blueprint by which our cells replicate.
Everybody knows that Horatio Caine uses it to catch bad guys. But... what if
we used DNA to build supercomputers? That is definitely science-fiction... or
is it? As I was working on DNA computing, I got my fair share of people staring
at me like I was crazy. Someone even asked me if I could find a way to take a
bird's DNA to grow an optimal plane out of it. I thought I would demystify it
a bit.

A bit of history

In 1994, Leonard Adleman (which you may know as the A in RSA) showed that it was possible to solve some pretty difficult problems, just by using DNA and other cell-reproduction related stuff. Wait, what? Did he just recreate a Primordial-Soup-like environment, and waited until an organic supercomputer evolved from it, somehow following the rules of natural selection? Well, not exactly. But we'll come to how things work in a minute.

DNA... but why?

It is important to understand the reasons why people came to study DNA Computing. The problem Adleman was trying to solve was really difficult. It is called the Hamiltonian Path Problem (but let's call it The Roadtrip Problem), and it goes something like this:

Take a map
Cut out a part of the map, and you'll be left with a few cities, linked by roads
Grab a pen. Can you trace a path that goes through every city exactly once, following the roads?

Roadtrip problem. Alright. The idea is this: the more cities you have, the longer it will take you to find out. And unfortunately, if you double the number of cities, you will probably need more than twice the amount of time to solve the new problem. And that means that if you just try every solution one after another, it is going to take an awful amount of time. Wouldn't it be nice if you could try several of those possibilities at once?

This is basically the reason why computers nowadays have more that one core working at a time. It usually goes from two to eight, the latter more often than the former. Still, if a problem takes one year to be solved on a single core, using 8-cores instead would still take a month and a half. Not that cool if you need the results to do something else, huh? Well, that's why super computers exist, hosting 250k+ cores. Your one-year-problem now takes about two minutes.

Sometimes even that is not sufficient (which is kind of a good thing in regards to cryptography, for instance). One of the fastest algorithms for solving our roadtrip problem runs in O(n^2 2^n). Basically that means that if a computer takes two thousandths of a second to solve the problem with eight cities, the same computer will need two minutes with sixteen cities, and a bit less than a week to compute a result for thirty-two cities. Most of that huge growth in time in regards of the number of cities comes from the exponential term 2^n, and the multiplication by n^2 does not help at all.

When scenarios like that show up, it drives some scientists mad, and sometimes gives them weird ideas. Among those is trying to solve NP-Complete problems with DNA.

DNA algorithms

DNA strands are like little strings (or sentences) containing information, in the form of four characters: A, T, C and G. It happens that the characters A and T attract each other, and the same goes for C and G (if like me you can never remember which goes with which, it's very simple: Achilles and the Tortoise form a pair, and so do the Crab and his Genes). Characters of such pairs are called complementary to one another. If two DNA strands happen to contain sequences of complementary characters, they will attract each other, and clamp together, giving long
DNA strands their sexy shape.

Now, let's be serious, it's 2015. And in 2015 you can design your DNA strands and have them produced. Let's do exactly that (at least the design part). Bear with me for a minute, and imagine that we have our own DNA-strand-printer. Let's design a simple DNA strand, containing a G character followed by 9 A characters:

GAAAAAAAAA

(a DNA strand, not somehow's death throe)

Alright. Let's call that strand N. Also, let's print it two thousand times. Now let's create an other strand. It is composed of 3 T characters, surrounded by a C and a G :

CTTTG

We'll print that one... let's say ten thousand times (by the way, DNA is very tiny). Those strands we call d. Now we'll go to the kitchen, grab a bucket, fill it up with water, and throw our twelve thousand DNA strands in it. Congratulations, you just built and programmed your first DNA computer!

Let's get that straight, right now: you won't be running Minecraft on it anytime soon. But what exactly happens in the bucket? First of all, both strands contain complementary characters. The sequence TTT in d (our second strand) will tend to be attracted to any three As in our first DNA strand N. Yet, it can do even better: the first four characters of d, namely CTTT, are a perfect complement to the first four characters of N: GAAA. They will clamp together, and leave out two tails: a simple G on one side, and 6 As on the other side. Wait, this looks almost familiar...

Indeed, since DNA strands are flexible, the two tails will act as a new DNA strand GAAAAAA, which has the same structure as N, but with 6 As instead of nine. You see where this is heading: the process will repeat itself! Another d strand will float by, and its leading C character will get hooked. Every time this happens, the number of A characters on our main string will be reduced by three! Eventually, there won't be any A left on our strand, all covered with Ts.

What we just implemented is a division of 9 by 3, effectively giving zero. The strand N encoded the number 9 with nine A characters, and the strand d encoded the subtraction by 3, with three T characters. This is easily extended to any numbers, can be used e.g. for checking if a number is prime or not. The truly amazing part is that all the computations are (almost) completely parallel: you have thousands of pairs forming, independently of others!

Of course, this is very theorethic, even though some succesful experimentation was done already. It is still the very beginning of DNA computing, and the time it takes to run an algorithm exceeds by far that of a computer (if you can run the given algorithm in a first place). Yet, it is promising, and in the end theoricists don't care that much if it will work one day.

My contributions

In February 2015 I completed a research project as part of my Master's studies. I was able to provide solutions to several problems using DNA algorithms, like:

Checking if a number is prime
Computing the square root of a number
Implementing binary inputs for DNA problems

and also did some analysis on how fast/how reliable such algorithms were. The improvements compared to other DNA based computing are that

it is more scalable (at least theoretically)
it only uses DNA strands (Adleman, for instance, also used enzymes).

If you are hungry for DNA algorithm knowledge, have any questions, or want to
complain about anything: just drop me a word in the comments below!

There are many problems (and solutions!) related to computing with DNA, and
some of the following might be interesting to the reader:

Adleman, L.M.: Molecular computation of solutions to combinatorial problems. In: Science Magazine. (November 2009)
Zhang, D.Y., Winfree, E.: Control of dna strand displacement kinetics using toehold exchange. In: J A C S Articles. (June 2009)
Qian, L., Winfree, E.: Scaling up digital circuit computation with dna strand displacement cascades. In: Science Magazine. (June 2011)

Also, Microsoft developed a tool for visualizing DNA computing. Have fun!