Hacker News new | past | comments | ask | show | jobs | submit login
The “Bug-O” Notation (overreacted.io)
203 points by danabramov 52 days ago | hide | past | web | favorite | 55 comments



> The problem with this code isn’t that it’s “ugly”. We’re not talking about aesthetics. The problem is that if there is a bug in this code, I don’t know where to start looking.

But this is precisely what people mean when they say it's ugly.

"Ugly" is what this gets translated as by your limbic system which registers in an instant: "fuck this big mess and the work it's going to be to reason about."

Aesthetics and usability are deeply entangled here, and the problem with that code is absolutely an aesthetic one. I want to say, more so. Because I experience it that way first, and only later do I enumerate the measurable reasons it's likely to be more buggy because of it.


Ugly, given that it is an emotional word, applies to any code that you don't like.

WHY do you not like some code? To avoid pointless discussions about taste and gut feelings, I'd bring it down to falsifiable statements.

"This is hard to maintain, for reasons X and Y" is such a statement. As is: "This is hard to test for reason: It needlessly engages in combinatorial explosion" is another.

Yes, you could shorten that to 'ugly'. Good for you.

Nevertheless, I've seen tons of discussions referring to 'ugly' code where the reasons were solid but completely different from maintainability (for example: "It is longer than needed", "It does is not idiomatic for this language"), or even not particularly solid ("It is ugly because it isn't functional", "It is ugly because the style guide says all APIs should always be interfaces", "It is ugly because I see tabs, not spaces").


In a sense those are all finer grained extensions of the same concept: How hard it is to reason about the code. On the highest level are easily quantifiable things like wrapping several error producing segments in a single try / catch block, obscuring the source of an error. Use of interfaces makes documentation and refactoring easy. Then the lowest level stuff is pure style -- much more subjective, but meaningful in a team environment. When people write code in the same style, you spend less time parsing style differences and more times parsing the actual semantics.


It’s true that gut reactions _are_ in part based on analysis like this. But just like with machine learning you’re gonna have some false positives for unfamiliar APIs. Things might look “weird” superficially but actually not be a problem. Or it could look “clean” but have a bad Bug-O. Thinking about it in rational terms first can help.


I agree. To be clear, I wasn't arguing against the need for dispassionate analysis. Or arguing that emotional responses can always be trusted. I was arguing only against the claim that these two things are mutually exclusive.

> Or it could look “clean” but have a bad Bug-O.

I think this is possible but in practice rare. I'd be curious to see an example of code you think falls into this bucket.


the problem is that "ugly" isn't precise and can get translated from other reactions that aren't based on experience but are instead just cargo cutting. it's great to use the faster parts of our brains to reason but still important to make sure we're not accepting the mistakes they might make.


It's also an emotive word that can make discussion more heated. If you're reviewing somebody's code and you call it "ugly", they're liable to get upset, and it's too imprecise for them to act on. It's far more helpful and less combative to explain, in concrete terms, what you think its problems are, and how a different approach could solve them.


It's aesthetics because your brain can see it turns into a multidimensional graph with all sorts of cycles that's, for all intents and purposes, infinite.


I'm not familiar with the language, and yet I remain unconvinced because I could still understand what the code in the first example is doing, and more importantly, see it all at a glance. I don't have to jump around between functions to follow the logic. More verbose code means more opportunity for errors and more code to look through and debug.

That said, I'd probably write something closer to this (once again, not sure if this is even valid, but you can just treat it as pseudocode):

    // don't create these every time, we're just changing their visibility
    let retryButton = createRetryButton(); // calls trySubmit() when clicked...
    let successMessage = createSuccessMessage();
    let spinner = createSpinner();
    let errorMessage = createErrorMessage();
    ...
    function trySubmit() {
     // assume these don't cause errors if the child isn't already there
     formStatus.removeChild(errorMessage);
     formStatus.removeChild(retryButton);
     formStatus.appendChild(spinner);
     succ = submitForm();
     formStatus.removeChild(spinner);
     if(succ)
      formStatus.appendChild(successMessage);
     else {
      errorMessage.setMessage(error);
      formStatus.appendChild(errorMessage);
      formStatus.appendChild(retryButton)
     }
    }


"yet I remain unconvinced because I could still understand what the code in the first example is doing, and more importantly, see it all at a glance."

This isn't because it's good code. It's because it's code that fits in a blog post, so of course you understand it quickly. If you didn't understand it quickly, the author's point couldn't be conveyed properly.

The question isn't really what happens when you have 10 lines of dodgy code. The question is, what happens when you have 10,000 lines of dodgy code?

(In a classroom, on a chalkboard, bubble sort isn't any slower than any other sort, and somewhat easier to draw, honestly. Quicksort is rather a lot of stuff to draw. But unless your code solely deals with lists small enough to fit comfortably on a blackboard with work room to spare, you are well advised not to use bubblesort.)


This comment just helped me to understand a great deal better why the author calls it Bug-O...because it's an issue that rapidly gets worse when n grows.

Imagine adding an additional state to the Bug(n!) version of the author's trySumbit() function, perhaps splitting the error state in to two different error messages based on what goes wrong. You would have to pay close attention to how you got to the state you are in in order to make sure you manipulated the DOM properly, and it would be hard to know you got it right. You would have to consider all the state changes into and out of your new state, figure out which ones are impossible, and account for all the ones that could happen.

If you want to add a state change to the Bug(n) example, all you have to do is add an an entry to the switch case without worrying about how you got there or how you leave.


Yep, exactly!


I’m not saying the first example is hard to _understand_. I’m saying that it’s hard to be confident it works or debug when it has a bad visual output because the unnecessary statefulness creates compounding mistakes over time.

My second example (that doesn’t have this problem) is pretty much what you wrote.


Thanks for sticking your neck out and providing code to back up your argument! I'm going to refute it quite heavily below, and just wanted to clarify that it's all down to the particular semantics of Javascript and browser form APIs. Since you say you're not familiar with the language, it's absolutely fine that you wouldn't have known this, so this isn't a personal attack against you; just a clarification for you and hopefully others about why this wouldn't work :)

    formStatus.appendChild(spinner);
    succ = submitForm();
    formStatus.removeChild(spinner);
You're solving an easier problem: synchronous form submission.

The code in the article (which is Javascript, the "J" in "AJAX"; although there's some stuff in the final example which I assume is "JSX") is solving asynchronous form submission (the "A" in "AJAX").

In general, Javascript programs work by attaching handlers to events. Events happen asynchronously, i.e. triggering an event like `submitForm` will push that event (or, equivalently, its handlers) to a queue, then carry on with the next instruction. Blocks of Javascript code, like event handlers, are also guaranteed to run from start to finish before anything else happens.

This means that your algorithm cannot work, even as pseudocode. Calling `submitForm()` will simply queue up that event. We won't be given the result of the form submission (which you call `succ`) since, according to the semantics, the form hasn't actually been submitted yet. This breaks all of the subsequent code.

What about faking it? We could try setting `succ = null`, and use an event handler on the form submission to overwrite this value. Then we can put a loop like `while (succ == null) { sleep(1); }` to wait until that handler gets run. Except Javascript doesn't have `sleep`, so we'd need to use a busy-loop instead like `while (succ == null) {}`. That will use 100% CPU while we're waiting, which is pretty horrible. Yet it also won't work! Remember that Javascript executes one block of code (like an event handler) before it starts on another (this is important to prevent horrible race conditions). In this case, the value of `succ` will never get overwritten, since the event handler can't be run until the current block has finished; yet the current block will never finish, since it's running an infinite loop!

Also, when I say that nothing else happens until a code block has finished, this includes interactions with the page. Hence even if it were possible to implement your algorithm in Javascript (which, as detailed above, I think is impossible), the entire page would freeze while we're waiting for the form submission to take place (possibly including the spinner, which defeats the whole point of having one). In browsers which don't use separate processes per tab, this might make the whole browser freeze.

Also note that your code still doesn't deal with the possibility of multiple executions, which is what the whole post was about. Even if it were possible to make your algorithm run in a browser, and even if that didn't cause the whole browser to hang, clicking the button multiple times would still cause multiple spinners to appear, which is exactly the problem that the original post was trying to avoid ;)


Thanks for the explanation; this really helps readers of the article who are not totally familiar with the environment. I've done UI programming before, but not in JS, which has a similar feel. Async certainly makes things more interesting, but I maintain that it's still possible to make the code simple and without needing an explicit state machine, by essentially adopting the "continuation passing style"[1] exhibited in the first example and adding guards to make the sections execute in order; one of the other comments here mentioned disabling buttons after they're clicked and not enabling them again until whatever async operation they started has finished, and that's the usual solution to problems like this. Besides acting like a "gate" on the code to prevent the state problems described in the article, the obvious disablement also informs the user to not click again.

[1] https://en.wikipedia.org/wiki/Continuation-passing_style


You could have been more generous and assumed they meant `succ = await submitForm();`


I've actually never used any async/await stuff, so I didn't know that's what it's for. All that stuff appeared in JS (and elsewhere) after I stopped doing Web dev. These days I mostly write Haskell, which AFAIK doesn't need all of that async/await/promise stuff because its already covered by laziness.


`await` is essentially syntactic sugar that means "wrap everything after this in a callback to be executed after this function does something asynchronously."


I see. That would presumably still have the problem of multiple spinners, as I mentioned at the end of my original comment?


Yes. You'd want to guard against this running more then once, probably by disabling the button until the submit finished.


This is a good attempt to kickstart the discussion of some quantitative metric about bugs and the time one needs to deal with it, but I wonder if there wasn't any software engineering theories or practices to address this.

If anyone know other related topics, please share them, thanks!


This is somewhat similar to the concept of “Cyclomatic Complexity”, which is the number of independent paths though a piece of code, and can be statically analyzed.

https://en.m.wikipedia.org/wiki/Cyclomatic_complexity


I like this concept better than cyclomatic complexity, precisely because this is what cyclomatic complexity is trying to poorly approximate. But it can't be automatically derived in the general case, or even terribly easily in non-general cases, either, unlike cyclomatic complexity.

I use a descendant of gometalinter on all my Go code, and one of the things it ships with is cyclomatic complexity, and I always turn it off. Precisely because I tend to think like this, it often gives my code terribly wrong ratings because it can't see that there's actually only a finite set of paths through the code that are possible, and also as the blog post demonstrates, sometimes adding more code actually simplifies the conceptual flow. But cyclomatic complexity will generally say the "more code" is even more cyclomatically complex.

There's also some Go-specific elements to my distaste for the measure, though; since in Go right now handling an error is automatically an if statement, that'll hit you right in the metrics. But in many cases,

    something, err := GetSomething()
    if err != nil {
        return errwrap.Wrapf("while trying to get something: {{err}}",
            err)
    }
Officially that's an if statement; unofficially, it ought to be a cyclomatic complexity of zero. Now, it isn't technically a free if clause, in the sense that a bug could live there, but if you're going to count the exception-based equivalent as zero (and it has the same callout; bugs can lie in your exception handling exactly the same way), then this ought to be practically zero too. Consequently, Go functions tend to get smacked with much higher complexity numbers than exception-equivalent code. Yeah, it's probably not a one-to-one, but it's certainly not as lopsided as the metric makes it seem.


Does gometalinter report absolute cyclomatic complexity numbers, or does it report density (cyclomatic complexity / sloc)?


Note one difference is that I'm talking about characteristics of an API, not particular code snippet. Although it's relevant.


This makes me wonder, are software metrics still a thing?


Yes.

At least for me.


There are various studies of defect density (bugs per 1000 lines of code) versus whatever factor someone thought would influence bugs. "Software defect density" seem to be the magic search terms for finding actual studies instead of blog posts.

I unfortunately can't find it, but I remember there being a study (by Microsoft?) of defect density for projects with different methodologies (scrum, TDD, whatever), which found lines of code is more correlated with defect rate than everything else they tried. They took that as a failure; I've always taken that to mean that reducing lines of code is the most important first step (or probably more accurately reducing tokens of executable code; one liners don't help and type annotations don't hurt).

While attempting to find that study, I found a study [1] that claims to have found an empirical sweet spot in defect density by module size - apparently 400 lines for assembly modules or 200 lines for ADA modules. Those are some weird languages to have numbers on, but maybe something else in that paper's family tree has something more relatable.

[1] http://www.cs.colostate.edu/~malaiya/p/denton_2000.pdf


even reducing tokens isn't a very good measure - lines of code is a proxy for complexity of implementation. I think a good measure (albeit a heuristic one) is how concise the implementation is relative to the complexity of the problem - or in other words, the ratio of accidental to essential complexity.


I've found TDD to be a good (but not perfect, as some people complain) way to keep complexity down - when you force yourself to test every state you very quickly start focussing on how to keep the number of possible states down.


I think that a more important reason is that TDD forces you to write code in small modules which can be tested independently. Because of this, you have small to medium size modules to reason about, rather than one huge class where you wouldn't know where to start.


It's a broad topic and called "code metrics" or "software metrics".


So what I think this points to is the importance of what I'm going to call "psychological reversibility" in programming: the ability for the developer (with the aid of their tools) to answer three kinds of question:

- how did this (wrong) control flow get here? Normally simple with stack traces, may be more complex with event systems. Part of the original rationale against GOTO.

- how did this (wrong) data item or variable get here?

- how did this piece of state get into this (wrong) state? This is often very hard to answer if the state is outside the program. DOMs are a large piece of global state that everyone working in the browser environment has to deal with.



There is a GCC plugin that can automatically calculate the cyclomatic complexity for programmers, and it has been built into the Linux kernel source tree. I don't know if there is any public statistics, but it would sound great for code reviewers.


After seeing callbacks cause a lot of "hard to debug" scenarios for me and for others, I'm starting to believe they are gotos in disguise.


Even worse: it's a "come from", a statement normally only seen in INTERCAL.


At least "come from" states clearly where the code is coming from.

Now... When your callbacks are names and not inline you can't really make that assumption.


They are.


This notation is already taken in the computer science world and is used in robotics planning algorithms. https://www.cs.cmu.edu/~motionplanning/lecture/Chap2-Bug-Alg...


Otherwise known as cyclomatic complexity?


Cyclomatic complexity refers to a specific code snippet.

I am talking about inherent characteristics of a particular API and how the patterns it encourages influences debugging.

For example:

>In fact, if any value looks wrong in the DOM of a React app, you can trace where it comes from by looking at the code of components above it in the React tree one by one. No matter the app size, tracing a rendered value is (tree height).


Really, all of this can be pared down to: reduce mutable state. That's what React does, and it's why code written in functional languages like Haskell tend to be much easier to reason about.

Basically, the fewer things you need to know about in a given context, the less likely you are too mess it up.


Cute, but it's still just asymptotic complexity... You can use asymptotic notation (big-O) to describe anything that grows. It doesn't have to be code runtime.


tl;dr avoid too much nesting, prevent DRY and make small but useful functions.

An advice that is valid since forever.


You can split the first example in small functions and it'll still be a mess. The post is not about duplication, function size, or nesting. We gained predictability by preventing _accumulation_ of errors — which we got by always restarting rendering from scratch.


Well- the React example doesn’t really restart rendering from scratch (as you yourself mentioned). And in larger applications you’d still prefer to not ‘redraw from scratch’ in React either and build on top of a previous setup.

Really what you’re doing is preferring more declarative programming practices over procedural. And as a consequence, more declarative APIs like React.


For the app developer, React code _does_ restart rendering from scratch. You have no access to the past rendered state from the render method (at least if you don’t intentionally escape the declarative model). This isn’t true only for bugs in React.

What happens internally in React is another question. But the point of React abstraction is to let _you_ think in terms of “render from scratch”.


Funny.

I tried to write software like that 10 years ago already, but I always failed at performance.

React was just what I was missing.


I'd go one step further and say it is about encapsulation and no side effects. And one of the biggest benefits is that you take the time when the problem space is modeled in your head to break it into its small solvable pieces. When you go back to refactor, don't just jam more code into function A. Refactor it to support the new use cases with new encapsulation.


The most important point was to minimise the number of states your code path can have.


Ah, but if it were so simple!

How many states can a selection of random, non-expert humans interacting with your code across a bevy of platforms encounter? The answer is always: Infinite.

Hand your application to a bunch of people that are completely ignorant of your intentions and it will reveal a seemingly endless bevy of code paths you didn't think we're possible! It will also reveal entire categories of code paths that have yet to exist but should!

In my TODO list I have a book idea... All I have is the title, "ERROR: This should never happen."


Funny how the post is about bug complexity, says that "Some API and language designs make a whole class of mistakes impossible. Some create endless problems." and then proceed to an example in Javascript... for which a whole language (Typescript) was invented precisely because it does not scales well.


My audience is JavaScript developers.


I was going to say something similar but then I thought about it a moment...

If I were going to write an article about maddening complexity in code that seems like it should be straightforward I too would choose JavaScript for my examples!




Applications are open for YC Summer 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: