6 ms·
The scientific-method-like "general approach to debugging" that the author describes in the last third of the paper works, but it's pretty inefficient. The num
by nostrademons 10y ago
The scientific-method-like "general approach to debugging" that the author describes in the last third of the paper works, but it's pretty inefficient. The number of possible hypotheses that may cause an observed bug is very large; if you test each individually, you may have to go through many permutations, and you're not systematically gathering data that may help you narrow the search space.
Rather, I've found "divide and conquer" debugging to be much more effective. You should know (based on your domain knowledge of the program) the rough sequence of operations between the input and output of your code; if you don't, try single-stepping through it or adding log statements. Pick a point approximately halfway across that computation, and inspect (via debugger, println, or unit tests) the state of the program at that point. Does it match your mental model? If so, the bug is between there and the output; repeat the process on the latter half of the code. If not, the bug is between the input and your intermediate point; repeat the process on this subset. As an added benefit, you can often find and fix other, unrelated bugs that may not be symptomatic yet but are silently waiting to trigger strange results.
This process is O(log N) in the size of the code path, while the "formulate hypothesis and test it" approach is potentially combinatoric if the code interacts with itself.
- lmitchell 10y agoThis is a surprisingly accurate description of the general sort of debugging technique I've gotten better at as I get better at programming. I find that logically it tends to make more sense to me to start with a high-level function, and step over its component function calls/loops one by one, inspecting the program state and diving into any that seem to be producing strange results. But overall, I definitely just find it's a lot more effective to start from a broad 'does everything look okay at this point?' than from a narrow 'I think the problem is this'.
- Swizec 10y ago> 'does everything look okay at this point?' than from a narrow 'I think the problem is this'. Even in a small real world codebase with just a few tens of thousands of lines and a couple hundred possible user interactions, you need the intuition for "I think the problem is this" or you're gonna be there for the rest of the year stepping through the code. Once you've scoped the problem to a potential few tens of functions, then you can spelunk through it to find the exact issue.
- lmitchell 10y agoSure - I didn't really mean to imply that starting at main() every time was the way to go about things. I guess my point is just that I find it's usually a lot more useful to methodically explore than it is to sit and hypothesize. I dunno, I suppose (like a sibling suggested) it's pretty much the same thing, but I feel like I usually prefer to bust out the debugger as soon as I have any inkling of where the problem could be, rather than spending lots of time beforehand thinking about it.
- Swizec 10y ago> You should know (based on your domain knowledge of the program) the rough sequence of operations between the input and output of your code This part is called experience, I think. Might the choice of pivots in your binary search be called a hypothesis? I suspect you and TFA are talking about similar approaches, but giving them different names.
- phorkyas31415 10y agoExactly. Have probably done that bisection thing a lot of times - but often you have to have that prior "domain knowledge" or more aptly: familiarization with legacy code base, to a point where it's theories and hypotheses all the way(). How'd you do a bisection or even a gradient decent on hypotheses? So for me the main point is just to realize quickly enough when the beginning theory is futile, so I should switch gear to another one or different methods. Still this wasting of hours often happens,.. and I'm doubtful if you can ever remove it from programming, let alone "scientifically" as the article suggests. () "the rough sequence of operations between the input and output of your code" - this phrasing also suggests to be far away from debugging hell a.k.a concurrency. At the latest then also your "bisection" becomes "theory" and guesswork, I presume.
- nostrademons 10y agoConcurrency bugs are a whole other can of worms, and can be maddeningly difficult to track down. You can drastically shrink the search space with a few simple techniques (immutable data, deterministic locking orders, message-passing, not sharing state between threads) though. When you find a concurrency bug, it's almost always because you have shared mutable state accessed by multiple threads. Don't do that - or access the state only through a well-defined abstraction that's proven correct like a producer-consumer queue, MVCC, or Paxos - and the number of places concurrency bugs can slip in is dramatically reduced.
- osullivj 10y agoGrasping the "no shared state" guideline was a big step forward for me in learning how to write safer concurrent code. My earliest attempts at writing multi-threaded code in the late 90s used thread pool approaches. One of Java's big selling points when it was new in late 90s was threading support. Somehow pools of worker threads executing the same code, often with each thread blocking synchronously when handling an HTTP request, seemed to become the dominant paradigm. Different threads executing the same logic inevitably leads to the dread shared mutable state, and deadlocks and races. Enter Sam Rushing's Medusa circa 2001/2, which made a virtue out of the necessity of Python's GIL. Coding single threaded async non blocking code in a callback style is paradigm shift in terms of decomposing a problem. Once that shift is made the big gain is avoiding shared mutable state. Now, when I code multi-threaded C++ server code I ensure that there is no logic or code shared between the threads. Threads communicate using locking producer consumer queues with well defined copy semantics. The result is no deadlocks and far fewer races.
- amelius 10y agoYes. But how could this be applied to a more complex and running system, say a human being for whom a doctor has to find a diagnosis?
- nostrademons 10y agoDoctors actually do use a very similar mechanism - differential diagnosis, as popularized on House (well, probably not exactly as popularized, but someone who's actually a doctor can go over the differences). The idea is to list all the possible diseases that could cause a patient's symptoms, and then run the appropriate tests or treatments to cut the search space by as much as possible. Cutting in half is often not possible in medicine, and they also account for how dangerous & urgent the condition may be when prioritizing.
- pryelluw 10y agoI dont know about humans (or other living beings), but its the same process I follow when fixing a car.
- DrJokepu 10y agoAlso, I observed that as you get more and more experienced, intuition ("hunch") works surprisingly well. It's not always reliable and sometimes it's just plain wrong though.
- brlewis 10y agoFrom the article: "Intuition can be an effective strategy for debugging but requires extensive experience and, when used as the only strategy, leaves the programmer unprepared to handle new, unfamiliar bugs." On the other hand, I don't see how you can keep experience and intuition from being a factor in any instance of the scientific method.
- philipov 10y agoIt sounds like a moot point. It's not possible to acquire the extensive experience necessary to have intuition without having another strategy in the first place. Intuition is the long-term consequence of employing a strategy: no longer having to step through the same sequence every time.
- dhodell 10y agoExactly this.
- jdefr89 10y agoIndeed intuition is needed. When John Nash, a Mathematician with schizophrenia, was asked why he believed such irrational things when he such a brilliant man, he responded along the lines of "Those irrational ideas came to me the same exact way my rational, ground breaking ideas came to me." So intuition will always be needed, we just need to remember to check it.
- enraged_camel 10y ago>> It's not always reliable and sometimes it's just plain wrong though. Yep, and in my experience this can result in wasting huge amounts of time. I've lost count of the number of times I've followed my intuition down some rabbit hole, and several hours later found that the issue was something totally unrelated. This usually happens when I've been coding for a while and am tired. :)
- tmaly 10y agoI always test the most basic assumptions and functionality in an isolated test. This usually highlights the problem much faster.
- dhodell 10y agoThanks for this comment. I did worry that this wouldn't come across very well, but my attempts to make it explicit all ended up poorly worded or read (to me) patronizingly. Still, to me it seems that you actually agree with what I've written. Forming a hypothesis it seems is the least understood / most confused part of approaching something scientifically. It does not mean that you need to test each thing individually every time you touch something. "Changing individual variables" as applied to this doesn't mean adding one log line in one place and moving it one step every time. Get the information you need! Be practical! I recognize state space explosion (the combinatoric complexity you refer to) in the article as a primary reason that debugging is difficult -- this complexity makes it difficult to form absolutely correct mental models about software. I'd also mention that if you're not systematically gathering data, you're not being very scientific. I didn't dig too deep into that because I wanted to avoid being patronizing. If folks aren't familiar with the scientific method, there are probably better references than me. I think what you're calling "divide and conquer," I am including (implicitly) as a strategy in the information gathering portion of the scientific method. I wish that I had more room to put more of these sorts of strategies in, but my article is already past the recommended length of Queue articles. The divide and conquer strategy is mostly generally effective, but it's not a universal tool. Debugging a race condition in some concurrent systems using this strategy is one example of where it fails if you're using it to get to a hypothesis. It might get you to "there is a race condition in my code," but this is not a hypothesis. It will not generally get you to, "there is a race condition between points A and B of my program when condition C is true and object O is not yet initialized." You can hopefully see how I can go from here to bring combinatoric complexity back into this strategy, turning O(log N) into superlinear O(log N!) (since factorial dominates exponents). And there's really nothing to be done about it: as I mention in the article, software describes the change of state in a system over time, and combinatorics is a fundamental part of state space complexity. For many modern systems, and increasingly, combinatoric complexity is a fundamental part of the equation. Finally, I felt that including strategies that were not globally generalizable and applicable to _all_ bugs would be in error. The paper is largely about cognitive / social psychology and pedagogy, less about process. I definitely agree that divide and conquer is a great strategy to use for gathering information in the debugging process. Use the approaches that have worked well for you in the past! Share those with people! Thank you for sharing this approach with people! --dho
- everybodyknows 10y agoThe "divide-and-conquer" paradigm extends to selection of input data as well: A few minutes testing known input sets, starting with the simplest, can save hours with the debugger. If none of the simpler input sets at hand repros the failure, it may be profitable to attempt to craft one. Now with a minimal failure case in hand, proceed with temporal "divide-and-conquer" along the lines you've so nicely laid out.
- unabst 10y agoJust pointing out that you are not contradicting the scientific method or in any conflict. In fact, the way you arrived at divide and conquer is though the scientific method. Tried and tested, it was better. The point is, the scientific method is just a tool. Where it is used is significant, as is preparing for it's use. Arriving at "divide and conquer" --> You want to apply the scientific method at the highest abstraction level possible first. You want to be as meta as possible, then work your way down. Dividing --> You're essentially preparing the code for easier consumption and by minimizing the problem surface first. Then when a problem is found, we are still guessing and testing. Except, most of the time the problem is so obvious it doesn't feel like guessing. Or it isn't. The mistake was already part of a known theory. Maybe it was of type "typo".