Hacker News new | comments | ask | show | jobs | submit login
Special Cases Are a Code Smell (conjur.org)
198 points by fagnerbrack 22 days ago | hide | past | web | favorite | 216 comments



One of my more painful anecdotes goes like this: Years ago, we were coding a piece of government regulation that decides eligibility of some kind. The rules went something like this "if it's a man and over 60 or over 55 and part of these classes of occupation but not in .. or ... then .... If otoh, it's a woman and ... ". The law was written down in the exact same wording. We coded it in the same way 12 pages of conditionals split out into different functions to make it more readable. Then I came, armed with my knowledge of algebra, Cayley tables and optimization of boolean functions. I created a truth table for the boolean function at hand, optimized that function into a small equivalent expression and replaced the 12 pages of code by a one pager. A job well done.

Two months later the law changed adding a new special case somewhere deep inside. I could start over. Lesson learned: don't outsmart the logic of the business.


When coding from a well maintained specification, I always try to find an architecture where the structure of the code mimics the structure of the specfication. This way, maintenance of the code becomes a lot easier. Sometimes, there are some small points in specification that makes it difficult to have the same structure in code. It is a "spec smell". Often, after discussion with spec writer, it was an incorrect point that had to be fixed in spec.


The most extreme version of this was a colleague who wrote a parser for the "human readable" version of the H265 spec. This could then be turned into executable code - and also a set of test streams.

This resulted in him filing a large number of minor bugs between the spec and the reference implementation: https://hevc.hhi.fraunhofer.de/trac/hevc/query?status=accept...

And a product: http://www.argondesign.com/products/argon-streams-hevc/ (page includes explanatory video)


Very cool :)

On a much smaller scale, VPRI made part of their TCP stack by parsing ASCII diagrams of packet contents (e.g. see the STEPS reports at http://vpri.org/writings.php )

Edit: Ah, I see user nradov has already mentioned this in a sibling comment :)


Wow, that is some truly impressive piece of technology! Kudos to those who successfully completed the daunting task of actually implementing this pretty crazy idea.


It was largely the work of one very smart person; not so much a 10x programmer as a mathematician^10.

Edit: the tool critical to the project was "Ometa": https://en.wikipedia.org/wiki/OMeta


If I actually match a tech spec or a law, I usually put references to the related text in comments, next to the code handling it. E.G: I'll put the spec version + page, or law paragraph number.

This way you know when you come back to it, what must stay, what must go, and what must change.


Forget the cleverness of the code... If I see comments like that (providing direct references to the spec/law) I will know I am reading the work of a true artisan!

Hats off to you, you wonderful person!


VPRI wrote an experimental TCP/IP stack which parsed the structure of the relevant IETF RFCs to generate code.

http://www.vpri.org/pdf/tr2007008_steps.pdf (Appendix E).


Another similar route is to code it as an interpreter over a data structure that represents the rules - When stored in something like a database, it can then be hot-reloaded.


Perfect example of reality VS classroom.

There is a reason people tell you to do "KISS". Which is just coding what you need right now, and not trying to be too smart about it.

Life is full of special cases : try to code an international calendar application, and you'll see what I mean. So many cultural things, so many political things, so many legal things...

So yeah, if you can find an elegant way to generalize your problem, do so. But unless you work on a purely theorical topic, you will have special cases. And they will change.


This is something I learned: When coding for this kind of legal tests just make your code read as close as possible to how the actual law reads.

It's easier to check that the code matches the law (after all there are no test vectors on the law apart from case law so you have to go by the drafting) and it makes updates when an amendment is made much simpler.

That, and there is usually zero need to optimise.


Or instead of optimizing it by hand, you have a machine do it automatically.


Indeed. Besides, it makes audits and compliance demos so much easier.


>Lesson learned: don't outsmart the logic of the business.

Very often when people try to solve problems, like the one you faced, with software, they fail to recognize that you might have to rethink the business logic. It's my belief that the majority of software design for specific niche business and governments fail because there was a lack of willingness to change and simplify the rules.

Of cause a project create a new system for taxation will fail, if you have 6000 pages of rules, not including the tax law itself.

Often we think we have a software bug/issue, in reality what we have is a flawed business logic. Until such time the people in charge fixes the logic, we're not able to do anything clever of efficient in software.


>* they fail to recognize that you might have to rethink the business logic*

Oh, we often recognize this.

You try telling a paying client that you think their business process is sub-optimal. I'll fetch the popcorn...

There are systems out there essentially replicating the workflow of older systems which replicate the workflow of an even older one, which was designed simply to automate a paper-based process all those years ago. If you are talking to a large business then the chances are that the people you are talking to don't have authority to change the business processes even a little bit.


Or, as is more often the case in my experience, the logic is dealing with real world cases that are outside the software's control and the business logic must follow the real world cases to be worthwhile. Which I guess is what the parent's spec example is really an example of.


I worked on ERP software in a past life and this was the main challenge. The software had to deal with "normal" cases well enough to improve efficiency, but had to be flexible enough to allow employees to handle unavoidable exceptions, without becoming a giant kludge. There was nothing worse for a user than having to deal with a special case and finding that they can't because they are blocked by the software.


You're right. But when a government is involved, you cannot even start explaining to `the business` they have flawed logic. (Believe me, I've tried... and failed)


When a business with multiple layers of management is involved it also quickly becomes impossible.

“It was decided!”

“By whom? Why?”

“???, It was decided!”

“...”


It was decided over dozens of meetings with dozens of people, and there are not good notes. Those people are smart and considered more details than you did (but not always the same details). There is rightly fear that if we reconsider this again we will forget one of those other details and some up with a decision that is better for your case but worse overall because it breaks some other case.


Isn't it more likely they just keep on adding little exceptions in order to be able to show they pushed something through for their constituents? That's the impression I got when reading these laws in the first place (a bone for the liberals, a bone for the socialists, ....)


Depends. Sometimes things work that way, sometimes they do not. It depends on how much attention the extras would bring.


Isn't this is a feature, not a bug? When things are decided by a democratically elected body you don't necessarily want a contractor coming in and tweaking things "because this is a better way."


Alas the real world is often not amenable to the fiery rage of logical-minded programmers. I’m sure there are plenty of examples of poor logic in real-world policies that could be simplified but there are just as many or more exceptions that serve a purpose, whether the justification is encoded in your requirements docs or not.


That's also why large software projects for government usually fail.

Create a system that handles all the rules of a single municipality or so -- doable. But too expensive for a single municipality.

So we create one system that will work for all municipalities! That way they can afford it, right?

Yes, but none of them is going to change their process. All the different ways of doing more or less the same thing have to be supported, in one system.

End result: nothing working, way over budget. Every single time.


Interestingly, the APL community (or at least the kdb/K community) and the Forth community (from what I hear) often push in the exact opposite direction. They seem to love to take advantage of any accidental regularity in the problem as given to simplify the code as much as possible.

The logic is that often the specs don't change, and if you make the code concise enough, you can just rewrite it if you need to make it more general.


Oh, some things never change. Others change all the time... And there are a few that absolutely never changed, but as soon as you automate them, they will change.

If it was easy, developers wouldn't be well paid.


It's an uphill struggle, but I think the EU proposal to abolish DST changes may have been driven by this kind of desire for simplification.


Most projects like this fail because they don't practice TDD. They have pages of code and no single proof that it works as expected apart from feedback from people testing it which is prone to errors. 6000 pages of rules is not a problem. You can implement anything but if you don't care to prove you implemented it correctly then that will almost never work.


Proof and test are different things, you seem to be missing them. A proof is a math concept to verify that all cases are handled, a test is a implementation concept to check one particular case is handled the way you think it should be. Both are important because both uncover a different type of bug. (Proofs uncover cases where you didn't think of something, tests uncover cases where you thought of something but didn't get some detail right)


That’s a genuinely great anecdote, and very instructive. Please tell me you used a Karnaugh map.


yup.


Reminds me or working in the UK for a telecoms company on billing.

Every year on budget day I used to listen to the live speech from the house of commons in case they changed something that effected billing - one year they changed VAT (sales tax) in the middle of the month.


I realise these are very uncool, but I've always had great success with using rules engines for this kind of thing (insurance / government rules especially).

If you can get over their lack of coolness (some implementations use spreadsheets!?!?!) they are a nice way to separate the crazy complicated stuff that changes all the time from the rest of the more static logic.


My question with rules engines is, “how do you test and deploy changes to the rules?” If you go through the same process as the rest of your software, then why not just use code? If you have a different process, how do you make sure your rules don’t conflict or overlap in unexpected ways?


The rules are code and should be handled as such - but they're written in a domain specific way that makes them easier for humans to compare against the spec.


That is up to the business, though with a rules engine I imagine you can empirically test that all cases are covered by just running all possible inputs through it.


Whatever happened to the Mechanism vs Policy mantra? It was all the rage in the nineties but perhaps X11 soured people on the idea.

Anyway, business logic is a perfect example of stuff that should go in Policy: functional, side-effect-free code (but not necessarily tidy or easy to read) which computes a value from a set of inputs. Like the parent says, effort spent optimising here may end up being a poor investment if the requirements change every year.

Mechanism code, OTOH, generally ends up containing all the side effects. It's harder to test so it tends to be dumb and, therefore, less susceptible to changing requirements. Optimisations here can pay off because the code lives longer.

Really though it all comes down to tests, tests and more tests. Automation is an asset and test cases outlive everything so make sure they work against the interface, not the implementation.


Tests are great and all, but wouldn't have helped in this particular case. It also seems policy was separated cleanly - the problem was it was optimized instead of maintainable.


Or you could have written a code generation tool. But I guess for this kind of job it might have been overkill and introduce its own special bitrot.


GP was essentially being a protein-based transpiler. The reference source code was the appropriate legislation; the code GP wrote was transpilation output. Since biological transpilers are slow and error prone, it makes sense to keep the output as close as possible to the input, to allow for "incremental transpiling" ;).


It can still makes sense to translate the rules into a parseable format instead of hard-coding them, to allow for code generation (or dynamic evaluation) and programmatic analysis of the rules.


I've often thought tax laws should be expressed in some kind of domain specific language that you could directly interpret.


A very sensible idea, and not just for tax laws, but I can imagine a lot people having problems with that kind of approach because they survive by interpreting/creating the ambiguities that go into most legislation.


"Two months later the law changed adding a new special case somewhere deep inside."

Time for a DSL and a compiler from the DSL to a truth table! :)


I'm profoundly unconvinced by this. "Handle special cases, then do the thing" is such a widespread, nigh-universal pattern that I don't think it hides anything from the programmer. It's the pattern used by any function that checks its inputs!

Rejiggering an algorithm so as not to have special cases just puts cognitive load on whoever reads the code to suss out what the original algorithm was. "Why does this algorithm require its input array to be padded with zeroes? Oh I see, it doesn't - the developer just did that to remove some if statements."


This feels very much to me like architecture astronaut behavior. This overwhelming drive to pull "elegance" out of everything mundane or tediously complicated.

Yes, you can sometimes rewrite your algorithm to eliminate "special cases", but if you do it at the cost of comprehensibility, it's not a net gain. In the case of these examples, we're not really even talking about "special cases", but edge cases, where you literally need to deal with an edge in the data. In the case of the neighbor sums, edge cases were masked by padding. In the case of the staircase, the edge is just obfuscated by the doubled labels and then hidden in a modulo operation. These are totally fine except that they seem to provide no value except "elegance", and they come at a high cost in terms of understandability. (The first step is literally "transform to a different problem", so now you need to understand the original problem as well as the new problem, and how they relate.)

I'm all for elegance when it comes bundled with understandability or legibility or performance or even simplicity. But often it actually means "clever" and it's an extremely subjective measure that delivers little to no value and is prone to causing problems later.


That first example in the article was interesting because it made me realise that I have a strong aversion to pushing the complexity into the data rather than into the code. Modifying the list seems to me that it could be a cause of other bugs (what if the list is re-used and something depends on it?).


Never mind bugs, imagine that array has 5 million elements. Good luck re-allocating and copying that to add an element at the start and another at the end.


I don't like the approach of pointlessly reallocating the array this way, but 5 million elements is not a problem on any machine built in the last 20 years. That's just 20 megs for 4-byte integers. With modern GC, this is cheap. It's not something you'd want to do in a tight loop (the copy time will start to matter), but for something like the example, the cost (in machine terms) is negligible.


I also experienced an instinctual aversion to padding the array that I can't really motivate (honestly) except to say "I don't like it."

The version with special cases feels cleaner to me.


Padding the array is a bit of a code smell. You can't just pad an array without allocating a new block of memory. After allocation you need to copy the array into the new space. This is a significant amount of overhead to a fairly straightforward and efficient algorithm.


Well, that's easy to fix - copy your array into a linked list so you an insert elements at the head efficiently. ;-)


Yes, the real problem with this implementation is the data structure they use. But is `next == null` a special case? ogod what do we do?!


This is interesting. Is it possible to implement a linked list while eliminating the end of the list ‘edge case’, in the fashion of the parent article?


Create a "sentinel" node which represents null and also points to itself, perhaps?


> we're not really even talking about "special cases", but edge cases

Indeed. This article has a bit of a smell. Sacrifice performance to the almighty gods of your opinions about elegant code? It doesn't make code less buggy. It verges on a holier-than-thou attitude, that case-y code is Bad(TM), with a sequence of increasingly-contrived examples.

And in fact, lots of algorithms are unavoidably case-y. Teaching programmers to sneer at bounds-checking, as this article does, is downright irresponsible. Sure; the right language might do that for you -- but whether it's a default value or a runtime error, a programmer's failure to fully explore the edge cases will result in incorrect behavior, crashes or both.


I do feel that elegant implementations are superior to others (all other things being equal). However, we need to be careful how we define “elegant”. For instance, while I fundamentally understand the drive to eliminate special cases, I don’t think that zero-padding the input (or concatenating the reversed input) is necessarily more elegant. It certainly incurs a nontrivial runtime overhead (unless done via lazy data structures, in which case we’ve just hidden the special cases).


Those examples clearly show how used programmers have gotten to the ease of use that languages like Ruby (the one used in the examples) provide. "Just pad the array with zeroes" sounds like an easy enough idea until you realize this might imply reallocating several gigabytes of memory depending on the size of your data set, possibly even running out of memory.

Either way, the example implementation assumes the first and last elements are treated as having only one neighbor; which seems like an odd specification for the algorithm in the first place. To me it seems like the source of this code smell is a bit further up in the call stack.

As for the second example, it becomes even more obvious how inefficient the "better" solution is. Just copy the entire array except the last element, in reverse order no less (so it can't just be memcpy()'d). This is what happens when you teach kids Ruby (or php, or pythin or...) because the job market demands it, but not the fundamentals (i.e. C, C++, Pascal, etc.).

As for elegance, both "improved" examples seem extremely ugly to me. Not only do they turn a clearly readable if statement into something more magical, they also mutate their data before operating on it. Turning 5 lines of structured code into a one-line abomination isn't elegant, it's dumb. It decreases maintainability. It increases complexity. It makes room for errors to hide. It's, to put it simply, bad coding style.


And if you argue against this insanity at a code review, some clod is going to misquote Knuth at you. "Don't prematurely optimize" doesn't mean "just alloc half a gig of memory, and profile later if performance is unsatisfactory."


Ironically, complaining about the elegant solution of padding the array with "well this is going to suck on a multi-gigabyte in-memory dataset" is pretty much the definition of premature optimization. Chances are very high his dataset is not multi-gigabyte in-memory.


Not really. Making a one-time allocation for a linear pass through an array is almost always bad. It’s often just as bad for many small arrays as it is for one big array.

The idea to not prematurely optimize was never intended to be a free pass to use wasteful practices everywhere until there’s a horrible problem, it’s more about avoiding factoring your code into something you can’t maintain. Generally speaking, baking your corner cases into your precondition code is more dangerous than avoiding allocations.

The idea was also not to leave concerns about performance completely off the table until your application is correct; it is assumed that you are making somewhat reasonable choices for your unoptimized code and your architecture, not that you are actively trying to slow things down with unnecessary allocations.


I disagree with two points of what you said. The first is that you call something that copies an arbitrarily long memory section to avoid two ifs "elegant", the other is everything else.

Elegant code uses less instructions, clear structure and is in general one of the better implementations in terms of performance. The suggested implementation shifts the workload into standard ruby functionality, but multiplies it by many times in the process; turns the clear structure of two conditionals into weird data trasnformations that and ultimately performs much worse than just the two extra ifs.

The multi-gigabyte-dataset was obviously an extreme example (yet one that may very well happen in practice). The point is, bad code like that is inevitable going to slow down an application, the question is whether you care about speed at all. Arguably, if you're using ruby, you probably don't.

Premature optimization usually refers to taking straight-forward code and making it more complex based on certain performance assumptions, like unrolling loops or writing inline assembly. This is bad because, well written code is most of the time fast enough, and if it does need optimizations, that will become clear soon enough.

Choosing not change your code in a way that considerably impacts performance based on ones individual perception of cleverness and elegance, however, is not an optimization; it's avoiding a dumb mistake that will bite you in the ass later on.


Padding with zeroes doesn't have to involve reallocating anything--you could wrap the array in an iterator that first yields 0, then yields each array element, then yields 0 again.

E.g. in C# using Linq:

    foreach (var num in myArray.Prepend(0).Append(0)) { /* blah */ }


> Rejiggering an algorithm so as not to have special cases just puts cognitive load on whoever reads the code to suss out what the original algorithm was.

Sometimes that's how it goes, but other times the special cases were a result of just not knowing the original problem well enough to think of a clean solution that really captures its essence, and the special cases are evidence of a sort of resultant duct taping.

Agreed though, what you're describing definitely happens and I'm not a fan.


I'm glad I read this comment straight after I read the article because you've convinced me not to eliminate special cases in this particular manner.

I'm sure special case elimination is useful and sometimes necessary for clarity, but only if not done at the expensive of said clarity.

I would be open to seeing some examples that make clearer sense, though. A video I found much more convincing was Embracing Algorithms[1] from Apple's WWDC 2018. I just watched it last week, and I found the ways it broke down and deobfuscated rather simple problems into easier solutions that describe the problem and solution more concisely to be superior to what was in the article.

[1]: https://developer.apple.com/videos/play/wwdc2018/223/


I think it depends on the situation. For example, under a functional paradigm the first problem is solvable as a special form of fold. The functional paradigm has tons of concepts backing it that make solving it in a ‘foldlike’ manner clear (which would involve the sort of padding the author suggests). In fact, the elimination of the special case is just a utilization of a monoidal operation and identity. In a lot of contexts “monoid” is a bunch of Mumbo jumbo, but in some functional languages it’s an incredibly clear way to go about resolving the issue. It’d also be perceived as more elegant than pattern matching against the first and last element of a list using some kind of predicate (aka a guard).

I think a suggestion to think about your reader foremost resides at the core of your comment, and I think that’s what’s most important. In a context that’s predominantly iterative or object oriented you’re completely right—the special case pattern is far more pervasive and you’d be doing your readers no favors by abandoning it. However if you could expect your readers to come equipped with a host of functional idioms, the elimination suggestion isn’t so bad (at least from a semantic/comprehension standpoint, ignoring performance).


I'm struggling to understand your motivation at the abstract level. Would it be possible to provide a snippet of Haskell code with an example of a solution implemented this way?


My thoughts exactly... The French have a saying,

"With enough 'ifs' you could Paris in a bottle."

This is what we, as software developers, do! We create conditions to make (amazing) things happen!

Conditionals are the bread and butter of programming. They're what allow us to "fix" things in short order. They give us the flexibility to make our software work in a seemingly infinite number of situations.

They also make debugging easier! Waking through the logic of even a zillion conditionals is quite straightforward and gives you that, "aha!" moment pretty quickly. Whereas walking through an algorithm that only works on a weirdly transformed data set just has us scratching our heads wondering why the previous developer felt the need to, "fuck with the data" instead of just writing a few clear and concise conditionals.

Conditionals are also easy to split up! They give you lots of clear options if they start to "grow out of control" as it were. Whereas transforming the data in various code paths can rapidly create debugging nightmares!


The tradeoff is that conditionals increase the number of paths through the code. It's like Tony Hoare said:

> There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies.

I hit this problem the other day, writing some code to divide a set of items evenly into N subsets. I wrote a bunch of property tests for this, but kept having problems with the way it was handling remainders. I could have made the tests pass by adding a few more conditionals, but instead I tried to solve it using no more than one conditional plus a handful of arithmetic operations.

The reason I constrained myself was that those test failures were a precious resource to help me understand the problem. Adding complexity to the solution could have produced a correct implementation, but I felt it would more likely out-smart my test suite. I would rather work with something that's clearly broken in an obvious way, rather than possibly broken in an unknown way.

Eventually, I came to realise that the requirements I'd come up with were inconsistent!


Indeed, in the first example the special cases should really be moved out of the loop too, so you have the code looking like this:

    - code for left edge
    - code for body
    - code for right edge
Now, both you and the machine don't have to keep thinking about the edge cases every time through the loop body. It's a win-win situation.


It means you have two extra special cases: 1) list is empty; 2) left edge is the right edge (I.e. length is 1)


Nothing that can't be solved with more conditionals!

Conditionals are great because they're clear and concise...

    if not list: # Can't do anything with this
         return # or raise error
    if len(list) < 3: # Ditto
         return #ditto
Sure, there's more code but it's not bad code. It's just straightforward stuff that's easy to read and debug (if necessary).


"Programmers are not to be measured by their ingenuity and their logic but by the completeness of their case analysis."

- Alan Perlis


Does that really cover everything that goes into a good measure of their code? ;-)


It's a good baseline. I once wrote a paper featuring about 20 pages of case analysis. This makes me good programmer, yes? Well okay I wrote a dozen paragraphs of code and a theorem-checking algorithm, and abused that algorithm to populate a human-readable latex template, and published that without shame. Such a good programmer.


No, I would say that it's necessary but not sufficient.


Exactly: In the first example, they take an array, copy it and add extraneous data for the sole purpose of eliminating a couple if statements?

I'm not perfect either, but that deficiency for the sake of elegance is technical debt. A year later, when that piece of code is running thousands of times over thousands of numbers, nobody is going to know why it does what it does. Just that the system throws random out of memory errors or something.


>> Exactly: In the first example, they take an array, copy it and add extraneous data for the sole purpose of eliminating a couple if statements?

The IF statements are not even necessary. Compute the sum for the first elements neighbors first (sum[0]=element[1]) and the last element (sum[n-1]=element[n-2]) Then loop over the remaining elements with no conditionals.

I agree with the author that it's probably better to pad it than to have conditionals at every iteration, but for this problem there is no need to have a conditional at all.


Your algorithm breaks for lists of size 0 or 1.


Cognitive load isn't some anathema to all of programming. The trick isn't to avoid it, the trick is to isolate it.

Pretending like cognitive load is never worth the effort is wrong.


I see where you're going with this, but to be useful you need to split cognitive load (and the complexity it processes) into two groups.

There's complexity inherent to the problem and complexity that's incidental to the problem.

Cognitive load inherent to the problem should be isolated.

Cognitive load required to deal with incidental complexity (such as clumsy abstractions, etc) is a waste of time and should absolutely be minimised.


I think where you can easily handle the edge cases, as done in the first and third` examples here, it's a good idea, because it's far easier to check correctness of the algorithm.

In the particular case you mentioned it's perfectly reasonable to explain why the array is getting padded in a code comment.


The first example is not at all good. It does not, in fact, eliminate the special cases, and becomes almost certainly less efficient—demonstrating why I would say that for this particular case a Good Programmer would write the code in the first form and not the second.

The special cases: they are not removed, merely transformed from `if` statements to boundary conditions on the iterator. The `i == 0` and `i == input.size - 1` checks effectively move into the iterator, with how the nice and clear `input.map.with_index do |_, i|` becomes the magic `(1...padded.size-1).map do |i|`. The 0 added to the start and end are also easily arguably special cases.

The second form is almost certainly less efficient because you’re creating at least one new array, unnecessarily.

> The special cases are gone, and the simple algorithm shines through.

The algorithm does shine through more, but the special cases are not gone, merely transformed (and into an arguably less clear form), and the code is less efficient.

Simplifying things is a worthy goal, and a lot of special cases are code smells, but be careful in seeking to remove them, and remember to at least consider performance, even if you end up deciding to prefer succinctness instead.


Yeah, a little OCD but I couldn't stand the first example (and some of the others). Here's a more reasonable implementation that doesn't special case (or more precisely wraps the special-casing in a standard library method):

  class Array
    def neighbor_sums
      map.with_index do |_, i|
        fetch(i - 1 & 0xFF_FF_FF_FF, 0) + fetch(i + 1, 0)
      end
    end
  end

  [1, 1, 1, 1].neighbor_sums # [1, 2, 2, 1]


Absolutely! Enumerating the neighbors of an element of a list by definition requires bounds checking. It's not more elegant to instead do some extra additions with numbers known to be 0 at compile time.

Represent the question faithfully first, then optimize later maybe sometimes.


> The first example is not at all good

No, it's not, but in my opinion not because of any of the reasons you just stated. Unless you're writing Go, that code should have been a fold over addition, or a `sum` function if available in the standard library.


The repeated if checks inside a loop could easily be less performant than the O(1) operation of adding 2 items to a array.

I think you’re too quick to assume that your preferred solution is faster.

Personally, I’d use the more clear code and only if the code proved to be a bottleneck even consider refactoring for performance. Whether the author’s preferred solutions are clearer, I’m not convinced however.

Finally, the author doesn’t claim that the special cases are gone, but more so that the input is transformed in a way to allow processing that is blind to them.


The checks are indeed an added cost, and that’s why I said “almost certainly less efficient” the first time rather than “less efficient”. (But subsequent times I did drop it.)

But what you call “the O(1) operation of adding two items to an array” is simply not true:

① While appending to arrays is normally O(1) in the cases that there is still spare capacity in the array and the entire thing doesn’t need to be reallocated, prepending is O(n) as it has to move all of the subsequent values along.

② What’s happening is not just adding two items to an array, but rather allocating an entire new array and copying all the values into it; this will be roughly O(n), but with a high constant overhead: allocating memory is expensive.

I can’t speak of any Ruby interpreter’s performance on the matter, and I’m fairly confident that the conditionals will be much more expensive there than they would be in Rust (where I have no doubt at all that the conditional version would smoke the allocating version in all cases), but allocating memory is a pretty expensive business.

> Finally, the author doesn’t claim that the special cases are gone

I quote: “The special cases are gone”. Further, I do not grant your response that the processing is blind to them—the inside of the loop is, but the special cases were moved to the boundary conditions of the loop. They’re still there.


The repeated checks in the loop will be reduced significantly in cost due to branch prediction.

Adding an item to each end of the array induces two problems:

- Adding to the beginning of the array will require all elements of the array to be shifted, and possibly a reallocation and cache miss (depending on implementation language).

- Adding to the end of the array will require traversing the array, potentially causing an extra cache miss.

Cache misses and reallocations are generally the highest performance costs to pay in computing today. O(x) alone is not sufficient to determine an algorithm's real-world performance.


than the O(1) operation of adding 2 items to a array.

Not very familiar with the language, but the code appears to create a new array by concatenating three arrays, which means copying all the elements; how is that O(1)?


Well, read in good faith and assume, if your reading results in an obvious contradiction, you probably assumed something that wasn’t what the author intended: in this case, that arrays are immutable


Well, if you're dealing with immutable arrays, then concatenating is even more expensive on average, because you either end up copying everything (which is O(n)), or the array isn't really an array (and you start paying for various forms of indirection).


We, get this: what if you’re using mutable arrays?

#whoa

I understand that reading is hard and avoiding needless posturing in order to display a personally-appraised superior intellect is harder, but reading in good faith requires that you put in some effort and not knee-jerk


Uh, no, he's assuming that the (+) operator concatenates arrays by allocating a new one. Which is correct. "Read in good faith" indeed.


You buffoon, you hydroencephalitic harrumpher, if your pasting on my statement leads to an obvious contradiction, you try again in good faith to find a better syntax tree. If you can, you ask a polite follow up question, not blow hard

Coirdially yours,

falsedan


Let's say the array is 1m elements...

the "ifs" inside the loop will be correctly predicted for cases 2..999,999

the processing is not "blind" to the new special case: "the array is padded", the loop is 1..size-1, which I think it's an error. Shouldn't be 1..size-2?


There are three dots in the range, not two.

1...size-1 == 1..size-2


Appending to an array is O(1). Prepending is going to be O(n).


The amortized cost of prepend (unshift in ruby) is O(1) (since Ruby 2). Of course that means at some point you'll get O(n) prepend.

[1] https://stackoverflow.com/questions/8353026/what-is-the-run-...


Getting amortised O(1) prepend is interesting because it's just like append, except you "center" or "right-justify" (if you don't care about O(1) append) the array in the allocated space, and exponentially reallocate when full as with append.


Prepending would be O(1) because it's creating a new array instead of prepending in place. Still bugs me (seems inelegant, even if not necessarily inefficient) so I wrote my own version: https://news.ycombinator.com/item?id=18988075#18998572


> Prepending would be O(1) because it's creating a new array instead of prepending in place.

No, you still need to copy the old array to the new array.

FWIW, Ruby may already be allocating some space before and after the array to accommodate a few pre-/appendages.


>No, you still need to copy the old array to the new array.

That's just a lock (nontrivial but O(1)) and a memcpy (technically O(n) but trivial, and O(1) for the common case if it's implemented with vector instructions), plus in any event the sums-of-neighbors method has to be at least O(n) on an idealized Von Neumann machine because it must read every element of the source array and also write every element of the destination.


In other words, O(n), not O(1).

> technically O(n) but trivial

"Technically" O(n) is the only O(n). There isn't some widespread colloquial use of Big O notation where O(n) means something else. Whether it's trivial is beside the point, but for a large n, O(n) in both time and space can be prohibitive, and it may become important that I don't use such an algorithm. For example, if I have 8 GB of data and 12 GB of working memory I can't satisfy those space requirements.

> and O(1) for the common case if it's implemented with vector instructions)

What is the common case in your view? memcpy in the general case is O(n). That you can perform multiple copies in parallel might affect the real time, but it doesn't affect the time complexity because O(kn) = O(n) for a constant k even if that k = 1/16 or however many copies you can perform at once.

> plus in any event the sums-of-neighbors method has to be at least O(n) on an idealized Von Neumann machine because it must read every element of the source array and also write every element of the destination.

O(3n) = O(2n) = O(n)


> "Technically" O(n) is the only O(n).

In idealized algorithmic analysis, but not necessarily real life. "Amortized O(1)," which I assume you concede is a commonly-used, meaningful and legitimate term, means "technically" an idealized O(>1) but O(1) in practice.

Calling memcpy inside a Ruby method call is amortized O(1) because for any "n" that fits within available memory, it will always be much faster than the other things in a Ruby method call, which involve dozens of locks, hash table lookups with string keys, dynamic type checks, additional Ruby method calls and so forth.

Likewise, computational complexity on an idealized Von Neumann machine isn't always the same on a real computer, in both directions. Dynamic allocations are theoretically O(n) but may be O(1) if the program never exceeds the preallocated space. Or suppose there were a loop over an array of pointers which dereferenced each pointer; the dereferences are theoretically O(1) but may be O(n) if they evict the parent array from the cache.

> What is the common case in your view?

Such as an array small enough that it can be copied with 10 or fewer vector load/stores.

> O(3n) = O(2n) = O(n)

Yes, that's my point. It's impossible to implement the example in less than idealized O(n) time, so O(n) and O(1) operations are equivalent complexity-wise WRT the entire method.


> In idealized algorithmic analysis, but not necessarily real life.

Big O notation is used for idealized algorithmic analysis. If you want to talk about real life, you can count cycles, seconds, watts etc.

> "Amortized O(1)," which I assume you concede is a commonly-used, meaningful and legitimate term, means "technically" an idealized O(>1) but O(1) in practice.

Yes, but I wouldn't take O(1) on its own to imply amortized complexity. Not that pretending that an array copy is O(1) in practice is particularly useful here since if you measure a copy operation in practice, you'll find that the time it takes scales roughly linearly with the size of the array. Not to mention that the space complexity is O(n) no matter how you put it.

> Such as an array small enough that it can be copied with 10 or fewer vector load/stores.

Are other cases conversely "uncommon"? My point here is that this is entirely your opinion and doesn't pertain to whether an array copy is O(1) or O(n) complex.

> Yes, that's my point. It's impossible to implement the example in less than idealized O(n) time, so O(n) and O(1) operations are equivalent complexity-wise WRT the entire method.

Not in terms of space.


Array copies are O(n), not O(1).



The one where you yourself even say it's O(n)? Big-O is concerned with asymptotic complexity. It's O(n) until you show us it's not (e.g. implementation code, not musings.)


Here's my second reply to him, where I myself point out that idealized Von Neumann machines don't exist in real life, and certain idealized O(n) operations (such as memcpy) may in real life for any possible "n" be cheaper than some baseline constant C (such as the cost of a Ruby method call): https://news.ycombinator.com/item?id=18988075#19001585


These suggested fixes look worse to me. In the first one, the "wrong" function was quite clear (special case 0, special case 1, general case) while the second one allocated memory. I'd call that a code smell!


Agreed. A better solution here is to have a generic accessor on the Array that can return a default value for out-of-bounds accesses. There almost is one already, the two-argument version of fetch(), except that interprets negative indices as counting from the end. But if we create a variant that doesn't treat negative indices specially then the code becomes very simple

  result = input.map.with_index do |_, i|
    input.better_fetch(i-1, 0) + input.better_fetch(i+1, 0)
  end.to_a


Yeah, in Rust it’d fall very neatly out of the type system, as `input.get(i - 1).unwrap_or(0) + input.get(i + 1).unwrap_or(0)`.


Funnily enough, that Rust code is actually buggy, because i is a usize and if i == 0 then i-1 will panic due to underflow. You'd have to write

  input.get(i.wrapping_sub(1)).unwrap_or(0) + input.get(i+1).unwrap_or(0)
This also technically won't work right if the slice has usize::MAX elements, but that's rather unlikely.

This is one area where Swift's choice of using signed Int for most things actually works quite well. The equivalent Swift code would be something like

  (input[safe: i-1] ?? 0) + (input[safe: i+1] ?? 0)
though unfortunately Swift doesn't ship with Array.subscript(safe:) so you have to write that yourself.


A slice of a non-ZST element cannot have `usize::MAX` elements, by definition of `usize`.


Slices of ZST elements is indeed what I was thinking of, but is there anything actually stopping me from constructing a `std::slice::from_raw_parts(0 as *const u8, usize::MAX)`? What if I'm working on an architecture where the heap and stack are separate address spaces, and every single address in the heap is reachable? In fact, doesn't WebAssembly work this way? If I can declare that my linear memory is usize::MAX bytes, then constructing a slice that covers the entire memory address seems like a potentially-valid thing to do.


> i is a usize and if i == 0 then i-1 will panic due to underflow.

Not in release mode.


While it's true that it doesn't panic in release mode, that's supposed to be an optimization and the correct semantics are what's implemented in debug mode. Besides, you don't want to write a program that only functions in release mode.


In ruby, this is most easily achieved with:

    result = input.each_cons(3).map do |left, _, right|
        left + right
    end
This maps over consecutive three-tuples in `input` and returns empty array for `len(input) < 3`.

Edit: nevermind, boundary conditions are still special cases.


On the other hand, the first one has a bug when the length is 1, which the second one fixes... but of course you could fix it without allocating memory either.

Relatedly, in image and video processing the (literal) "edge cases" are sometimes handled by allocating the buffer slightly larger in the first place, so that filtering operations (which are very similar to that example) don't run off the edge. Maybe the real lesson here is "think ahead"?


I'm reminded of Linus Torvald's interview at Ted [1] where he talks about programming "taste", and compares the following two code snippets:

  remove_list_entry(entry)
  {
      prev = NULL;
      walk = head;

      while (walk != entry) {
          prev = walk;
          walk = walk->next;
      }

      if (!prev)
          head = entry->next;
      else
          prev->next = entry->next;
  }

  remove_list_entry(entry)
  {
      indirect = &head;

      while ((*indirect) != entry)
          indirect = &(*indirect)->next;

      *indirect = entry->next;
  }
[1]: https://www.youtube.com/watch?v=o8NPllzkFhE


That first case is hideous (hope Linus agreed with me!) but does remind me of my favorite computer scientist joke:

===

The physicist is showing his friend the programmer a thermos.

"You see, you can put a hot drink inside, and then take it with you. It doesn't matter how cold it gets outside; when you pour the drink out it's still hot!"

The programmer is quite impressed.

The physicist continues, "Or you can put a cold drink inside, and then take it with you. It doesn't matter how hot it gets outside; when you pour the drink out it's still cold!"

Now the programmer is really dumbfounded.

He asks, "But how does it know?"

===

Unfortunately though I like the joke, I still see waaay too much code written by the programmer in the joke.


Is the joke that the programmer interprets it as the drink waiting to pour out? Or?


A non-programmer will just figure the programmer is a bozo (you could tell this joke with a physicist and a geologist, or any combination of <local-in-group-0> and <local-out-group-0>): that's simply how thermoses work.

But a thermos with a switch on the top to say "insert hot" or "insert cold" would be absurd. A thermos is simply a container _with no concept of temperature_, just isolation: it just maintains the state blindly; whether that state is hot or cold is managed by the "caller" who inserts and extracts the contents, inspecting them itself if it wants to know what had been put into it.

Yet I still see plenty of code that does have a variable to indicate what's inside, perhaps an enum {hot, cold} or worse a bool. Yuck -- you should simply store the thing and if you need to know its state you look at it. That variable is something to get out of sync; something you need to be careful to set and maintain, something at threat to a race condition or ill-timed interrupt. Bleagh. If your first language was FORTRAN, OK. Otherwise there is no excuse.

Sadly I see shit like that in pedagogical examples too, which is malpractice.


"I still see plenty of code that does have a variable to indicate what's inside, perhaps an enum {hot, cold} or worse a bool. Yuck -- you should simply store the thing and if you need to know its state you look at it."

Now I'm confused... How are those two things different? The variable indicating what's inside is going to be coming from the actual state itself, no?

It sounds like perhaps you're talking about some case where a developer has somehow copied a state and referred to the copy somewhere else. Or are you talking about a computed variable of some part of the state being a code smell?


He's talking about explicit state, which can be a code smell when you can have equality efficient (or more) stateless solution.


Many modern languages require programmers to know exactly what is stored in any location. This is done in the name of "safety", but is just dumb. Code that needs to know the types of absolutely everything is simply slow and requires enormous repetition (or a system of boilerplate generation such as the STL).


I interpret the story as though the programmer thinks about the world (in this case, the thermos) as actors, acting explicitly on their inputs. This type of thinking aligns with code full of conditional statements, such as checking the input liquid temperature rather than what the thermos does (just keeping the liquid at the same temperature).


To be more explicit, I see "how does it know?" as analogous to code like this:

    if (condition == True)
        return True
    else
        return False


It's a joke about type systems (as I read it). HotDrink and ColdDrink are both subclasses of Drink, and Thermos has a method "void fill(Drink * drink)" and a method "Drink * pour()". The programmer is asking how the calling code knows whether the Thermos is returning a HotDrink * or a ColdDrink * when pour() is called.

Of course, the answer is "the code should know beforehand what's in there". If someone hands you a thermos with no clue what's inside, then you either have to assume it could be hot OR cold (ie. just use the base Drink * pointer) or you have to check the temperature (ie. explicitly check the type of the return pointer using runtime type information or some kind of Variant-style wrapper.


The joke is how does the thermos know whether to keep the drink hot or cold and that a programmer thinks that must be how the system works.


This is an especially interesting comparison because while it does clearly exhibit the sort of elegance only achievable through the elimination of special cases, it's also a good demonstration of the tradeoffs one sometimes has to make for this purpose.

The second is significantly 'cleaner,' but with pretty bad readability [0]. The first version has excellent readability.

In practice, the way I'd evaluate the two is by looking at how much other code depends on (or at some point may depend on) the piece under consideration. If nothing else or only very little depends on the code, I'll opt for readability; if it's likely to be somewhat foundational and other stuff is going to grow on it, I'll opt for the more abstract, cleaner version, and document thoroughly.

[0] I'm guessing the readability isn't nearly as bad if the first example is using a common C idiom; I don't use C enough to know. My main criterion for judging readability is: how much does the structure of the code match the conception of the algorithm you're starting with. The conception here has to do with navigating links; the pointer stuff is incidental complexity.


To me the main readability problem of the first example is that it does the head check as the last step rather then first step. Meaning we have to consider "wait, when is this null again".

The main problem with the last one is that it's not immediately obvious what the "indirect" represents. When it clicks that it is "the pointer to potentially update", it's pretty easy to understand.


The 2nd one would be significantly more readable with explicit typing (to make it clear that you're dealing with a pointer to pointer).

Though I think putting the head check at the beginning like you said will make the first example very reasonable (and relatively compact too).

  remove_list_entry(entry)
  {
      if (head == entry) {
          head = entry->next;
      } else {
          prev = head;
          while (prev->next != entry) {
              prev = prev->next;
          }
          prev->next = entry->next;
      }
  }


There's a third alternative, which I've heard of as "virtual head", that removes the extra indirections in the loop and removal:

    while(p->next != entry)
     p = p->next;
    p->next = entry->next;
I've deliberately not shown the initialisation of p, because it's a bit tricky in C (but trivial in Asm); p is not initialised to the head, nor the address of the head, but to a "virtual" node centered around the head, such that p->next will initially access the head. If the next field is at the beginning of the structure, p does point to the head; else p points to a location before the head. It would be something like (char*)&head - offsetof(Node, next);


For those curious how to create the "virtual head" in C:

    struct entry { int value; entry * next; };

    entry * head = NULL;
    void remove_entry(entry *target) {
        long offset = (long)&((entry*)0)->next;
        entry * curr = (entry*)((long)&head - offset);

        while (curr->next != target)
            curr = curr->next;

        curr->next = target->next;
    }
But I'm not sure how portable that is. It is portable if the next pointer is the first member of the struct though. From 6.7.2.1.13 in the C99 standard:

>A pointer to a structure object, suitably converted, points to its initial member

    struct entry { entry * next; int value; };
    ...
        // virtual entry where &(curr->next) = &head
        entry * curr = (entry*)&head;
Note that it's exactly the same logic as the grandparent since

    *curr = curr->next

    indirect = curr
    *indirect = *curr
    *indirect = curr->next
    indirect = &(curr->next)
But, I think that the virtual head entry is an easier mental model.

C99 standard: http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf


You can get the same effect by using a “dummy” node. The dummy node has a next pointer, but no data, and the dummy node always exists at the front of the list. The list structure contains the dummy, instead of using a pointer to the front of the list.

    struct Node
    {
        struct Node* next;
    };

    struct DataNode
    {
        struct Node* next;
        struct Value value;
    };

    struct List
    {
        struct Node dummy;
        // You can also add length, etc.
    };

    // entry must be in list
    void remove_list_entry(struct List* list, struct Node* entry)
    {
        Node *prev = &list->dummy;

        while (prev->next != entry) {
            prev = prev->next;
            assert(prev != NULL);
        }
    
        prev->next = entry->next;
        free(entry);
    }


This is the coding equivalent of a designer putting appearance over usability.

In this case, it is putting code elegance over readability/maintainability. Sure, you've reduced the number of if statements, but those if statements explicitly represent the logic behind the calculations. Come back 6 months later, and you'll be scratching your head about what's going on. Unless you add a comment, but comments are also a code smell.


Comments are a code smell? WTF? No. Just... No.

Not having comments is a code smell. Everything has context and it is wrong to assume that the next developer to come along will know/understand it well (or at all). Even you as the original coder might not remember why you did something a certain way.

I personally comment like I'm going to start suffering from a massive cognitive decline any day now and will need most things re-explained to me.

Example: I was looking at some old code this morning...

     temp.write('\n')
     temp.close()
Why's that newline being written there? From the perspective of the code it serves no propose. Good thing I had a comment right above it...

    # Add a trailing newline so 'cat' doesn't leave an ugly mess
"Ah, yes. That's a good reason to add a newline."


You misunderstood.

The need for comments means the code is not clear. That need is a code smell.


I think that's too broad.

Needing comments to explain what the code does is a smell.

Needing comments to explain why the code needs to do what it does is not a smell.


I don’t think zero comments should be the goal, just that minimizing the need for them is often a good idea. Why can generally be included in the code. Total = SubTotal + SalesTax; Needs no real explanation.

Code smell is just another way to compare two possible approaches. If one version can include significantly fewer comments without issue then that’s good sign.


> If one version can include significantly fewer comments without issue then that’s good sign.

Which is why I don't buy what the article tries to sell, at least not fully.

In the first example, having a few initial handle-and-exit if statements to deal with edge cases, and a main body that's clean means you don't need to comment.

The approach suggested by some here that you could just have two for loops over the input, while clever, might not be immediately obvious to everyone and as such would probably need a comment explaining it.

The latter does not need special case handling, but is less obvious.


>Why can generally be included in the code. Total = SubTotal + SalesTax; Needs no real explanation.

Sure, and if all the code you ever write is implementing some trivial school assignment then your probably fine. No one with half a brain thinks your example requires a comment, but it's a bad example.


No offense, but functionally like that shows up in school assignments and billion dollar companies back ends. However, it’s easy for even that simple idea to end up being something like: Item.FinalPrice = Item.BasePrice * CalculateModifier(Item.ItemCode, Item.OrderContext); Which sacrificed understanding for elegance.

Sure, the functionality to find that SalesTax number might take tens of thousands of hours to create and cover a multitude of egde cases. Still with proper context, structure, naming conventions, etc the why’s should be clear. If your thinking “The exceptions function adjusts for tax holidays. So of course it needs to get exceptions based on location and the order date, and then it needs each items metadata etc” then that’s a great sign.

Elegant code is elegant when it encapsulates the why’s not just the how’s.


>However, it’s easy for even that simple idea to end up being something like: Item.FinalPrice = Item.BasePrice * CalculateModifier(Item.ItemCode, Item.OrderContext); Which sacrificed understanding for elegance.

Sure, and I'd call that bad code unless it exists because there are far more considerations than sales tax. Either way I don't see how that is an example of when to or not to leave a comment.

>Sure, the functionality to find that SalesTax number might take tens of thousands of hours to create and cover a multitude of egde cases. Still with proper context, structure, naming conventions, etc the why’s should be clear.

Again, that's just not true. I have a hard time imaging that you're a professional engineer with real world experience if you've never found yourself in a situation where variable names alone could not express the _why_ behind a piece of code.

>Elegant code is elegant when it encapsulates the why’s not just the how’s

Great, not always possible. For example:

  // We have a longer than normal backoff period on
  // timeouts here because device XYZ is a piece of junk
  // and randonly stops responding for minutes at a time
or

  // version 2 of the spec switched to an XML format and
  // allows the header to be anywhere above the root
  // element of the document (as a processing
  // instruction). We cannot define a reasonable min
  // header position/length. Just read the whole file.
  const size_t MinHeaderLength = std::numeric_limits<size_t>::max();
or

  // Workaround issue caused by .NET 4.6.1 upgrade which
  // has more restrictive certificate checks for secure
  // connections. This is currently affecting SignalR
  // Scaleout connections to Azure Service Bus.
  AppContext.SetSwitch("Switch.System.IdentityModel.DisableMultipleDNSEntriesInSANCertificate", true);
Of course you could suss out the reasoning on your own eventually, but why force people to do that? What variable naming scheme would you use to convey those reasons?


You’re missing my point of course we sometimes need comments. It’s a question of design tradeoffs. CalculateModifier could be part of a great design or a terrible one, but the need for comments based on the near meaningless name is an obvious issue that would need to be balanced by something else. Consider these projects:

Several years ago I was updating this ancient Object Pascal program. OS X had just showed up and they finally decided to do a full rewrite, but they wanted to do this is stages. Anyway, this thing was still using Apple Talk networking not TCP/IP and I was rewriting the network stack so we could replace each system individually. Surprisingly, the code was very easy to read, but was also filled with a long legacy of past issues. Comments on 68000 processor issues could safely be ignored for example. So yes lots of comments, but most of them had become useless.

More recently, I was redeveloping a .NET website that had been built by someone in love with XML. Unfortunately, the mismatch between the way the code operated and the way the system operated meant that you needed to carefully read each comment. It had slightly fewer, but far more nessisary comments which was one sign among many that it was a horrible design.

Which is why I am talking about nessisary comments. Many comments can safely sit in source control or automated tests. Their context quickly becoming outdated. However, when a systems design nessitates a great many important comments that’s a bad sign.


Many coders will argue that these comments are the type of information that should be captured by the version control system, not in the code itself.

The biggest problem with comments is they are not part of the tested integrity of the system. In other words, they are never tested for correctness.

How many times have you come across a comment that appears to have no bearing on what the code is doing? In heavily commented code, this happens all the time because a developer (not necessarily the original developer) makes a change and does not update the comment. It could be that the developer was in a hurry and sloppy, or that the change was upstream and made the comment irrelevant, or maybe the code was copied and pasted into a context that doesn't match the comment, or whatever. The point is that comments can become stale, and a stale comment is worse than no comment at all.


This has been a debate I’ve had with a friend for awhile now. I think that clear code consists of good naming, formatting, structuring, etc., and you should only need to comment high-level functionality, weird cases, or where it’s not really possible to clarify things further. They, however, commment nearly every single line/block. Their code isn’t even bad, they just do it “just in case”. To me it feels like a lot of work for not much benefit.


I generally only see this from extremely junior devs. This behavior is a waste of time for negative benefit, as comments have maintenance cost.

I consider this behavior to be a sign of an immature dev. If I ever see a senior engineer do this, I'll know he/she's probably over-leveled.


> I generally only see this from extremely junior devs.

He’s definitely junior in this case. He’s only in his first programming job out of college. I tried to get him to see the error of his ways but not everyone will listen to reason. :)


If he’s actually writing good code (so has sufficient skill) and is working somewhere with decent mentorship, he’ll probably get the message soon enough. Code reviews from senior engineers should tell him to cut it out every time.


That's simply not at all true. Code can be clear as day in it's purpose, but not in it's intent because it is implementing a requirement that the next reader may not be aware of. In other worda, the comment explains _why_.


What percentage of requirements should you keep in your source code?

CSS for example might assign a button to be green. Should you trace back to the specific requirement to say why it’s green or can you trust if somone changes it to blue it’s becase the requirement changed. I would generally say the second.

Ideally, the vast majority of requirements can be treated as such. Cases where I have wanted to include the comments generally relates to brittle code where some change likely has knock on effects. Ideally such code should be avoided where possible. IMO, such things are also better cought in unit tests and documented in source control providing more context.

That said, including things like design goal can be helpful to get people familiar with the system. But again IMO, specific requirements should rarely sit in comments rather than unit tests, design documents etc.


Well, I didn't mean every requirement of course. I meant the code that gets things working the right way when a cursory view of the code doesn't tell the whole story. I wouldn't question a button color without good reason to do so, but what if that single button was green when every other was blue? What if the button we're shaped like a camel, or called an API in a non-standard way?


> I wouldn't question a button color without good reason to do so

Exactly, and I don’t think a comment about an old requirement would generally do so. Someone just gave you the new requirement which presumably replaces the old one.

But, if the comment mentions 508 usability as an issue or as you say it’s shaped like a camel, then that’s going to be an issue for any version of the website you create. Basicly, comments that make it on the minimum list are suck there and don’t become relevant when comparing different possible designs.

Code smell is about comparing designs and implementations not high level requirements. If 1/2 your customers uses JAWS then you got to do what you got to do.


I disagree with the article. The reasoning is much clearer when you specifically spell out how you’re handling special cases than trying to finagle your input and padding with zeros and whatnot.

It’s literally hiding your intentions and reasoning for doing things, which I think is anathema to good code maintenance.


For neighbor-sum, instead of saying "each output value is the sum of its input neighbors", we can say "each input value contributes to the output values of its neighbors."

Then it is natural to iterate over the input and not the output:

    for (int i=1; i < length; i++)
       output[i-1] += input[i];
    for (int i=0; i + 1 < length; i++)
       output[i+1] += input[i];
"Invert the problem" is a really powerful general strategy.


That's actually the kind of solution I thought the author of the article was going to suggest, before I read their solution.

On an unrelated note, why do you use i+1<length rather than i<length-1 ?


Certainly subjective. One could in many instances easily find it clearer making the special cases explicit instead of messing with the data beforehand in order to force it to fit into a more general algorithm, these instances included.


Hey! Here's a fun trick I learned from Knuth's TAOCP, the one with the tape drive algorithms.

You want to search an array for an element:

    int i;
    for (i=0; i < array.length; i++) {
        if (array[i] == value) break;
    }
    return i;
This is bad because we have two comparisons every loop iteration. But simply append our search term:

    array.push(value);
    int i;
    for (i=0; ; i++) {
        if (array[i] == value) break;
    }
    array.pop();
    return i;
and we've cut our comparisons in half!


I'd prefer the first version in almost all situations except for a major performance bottle neck. The second version is less clear to the reader and thus likely done wrong.


Yeah tape-based algorithms are an anachronism, but the idea of eliminating bounds checking via a terminal value is very powerful.

An example of this in action is LLVM's MemoryBuffer [1], which is input to a parser. How to write a parser? Perhaps it performs bounds checking at each production. However LLVM guarantees that the MemoryBuffer is NUL (0) terminated. A parser can then arrange for NUL to be a terminating character, and handle it uniformly.

The resulting parsers are faster, and also significantly clearer and easier to write, because there's no need for bounds checking at all.

http://llvm.org/doxygen/classllvm_1_1MemoryBuffer.html


However it requires that the terminal value does not occur in the input.

For a parser that's probably not a problem (it can transform NULs in the input to a different token), in other situations it's not so easy.


Wouldn’t you want something like “if (i == array.length) { return FALSE}” before the return statement? Returning array.length+1 as “not found” feels like it’s just begging for an out of bounds exploit.

Clever example of this approach, though!


For this to be guaranteed to work, underlying storage has to be resizable (clearly not using linked list like semantics since it's named 'array').

So that means some small amount of the time, a linear search (a supposed read-only op) results in a possibly massive allocation or I need to allocate one extra space each time? Search is now not multi-reader thread-safe either. I mean, I can see the value, but surely a modern filter findAny is superior to this.

EDIT: can't post in response but I thought you meant that this trick carried over.


It was literally using magnets to write a new value to the end of the tape.


This is the one that leads to the joke with the punchline "... insert a known lion in Capetown to ensure the search terminates", isn't it?



and introduced a dynamic memory allocation ! yay, unuseable in real-time systems !


Don't most modern compilers in the last 20 years do this for you automatically?


No way! Compilers won't secretly append to an array.


If you were to translate these examples into a systems programming language like C, I think you’d find these “simpler” cases are anything but. They’d look much more complicated. They’re filled with new allocations and memory copying. They’re essentially new algorithms at that point.


Arrays are not special cases. They have a beginning and an end.

Trying to expand the Array by prepending and appending to it shows lack of knowledge of memory, performance, and maintainability. If loop is refactored away from 'padded', all hell breaks loose 3 months down the line.


Got an easy problem to solve? Let's make it difficult to reason about and hard to maintain. But no if statements!


I don't think this article captures the main advantage – when you have layers of logic, eliminating special cases lets you have O(n) pieces of code instead of O(n^2). And even if each portion is less readable, 100 functions beats 10,000 functions any day.

A good example of this is making values non-nullable by default, with Optional types, and eliminating a huge swath of special case handling.

But the benefit doesn't show up without significant scale, and isn't worth it for functions that are just used once or twice.


This is something I've definitely changed my mind on several times in my life.

I studied Maths at uni so I definitely have a bias to the author's position of transforming the problem into a form where an elegant solution "falls out" naturally. However, I think this is because I am comfortable (from training) with transformation steps and can easily see whether they matter or not in terms of affecting the answer.

The example the author uses seems nice because their entire audience is experienced/intelligence enough to see why padding zeroes works.

There's a puzzle where you are given an array of ints and told every term appears twice except one. You have to find this "lonely element". This can be solved naively by looping through the list and recording how many times you see each number.

It can also be solved "elegantly" by XORing the whole list - but it is not immediately obvious why this works. In this case I would definitely say the elegance is not worth the obfuscation cost.

The personal compromise I've come to is to try and refactor the code so that specifical cases are extracted and quarantined as much as possible, leaving the main algorithm hopefully clear and elegant.

For example, in the article's first example, I would not pad the array but would split out a separate function neighbours(i) which returns [1], [n-1] or [n-1, n+1].

This approach makes more sense in more complicated examples, (say a 3D grid) or in particular if padding is impossible, like you have to calculate (sum of neighbours) + (product of neighbours).


Special cases are a sign you have a business problem that is worth solving.


What if the business is a special case among general solution businesses?


It's way too strong to say special cases are a code smell. A code smell is something that means most likely something is off. Special cases are just one way of achieving a result and often the most readable and maintainable one. The alternatives can be just as "smelly" in their own right.

I'd say this is a special case (ha!) of the principle that each person and organization has their own personal tendencies. If you say "X is a code smell" and the internet disagrees, it probably means you or your organization have a tendency to choose X when it's not the right solution.


I used to have a math teacher in high school who would say: "When a mathematician doesn't have what he wants, he re-arranges things so as to get it."

Basically he meant, if the problem isn't presented in a way that makes it convenient to solve, rearrange the problem fist, then solve it.

A classic example of this from high school math would be: https://en.wikipedia.org/wiki/Completing_the_square


"If I need to add a new function and the design does not suit the change, I find it’s quicker to refactor first and then add the function."

https://martinfowler.com/books/refactoring.html


One-offs and edge case requirements are everywhere. The article entertains the idea of eliminating edge cases. Edge case requirements aren't the problem. The problem is how you solve for them. This is a form of complexity management and fortunately there are a few good approaches that solve for most forms of complexity.

The way I commonly approach edge cases is that they are dealt with by an additional rule (and possibly accompanying data structure) in otherwise existing similar common functionality. If current functionality is not sufficient then write new functionality to solve for and replace other existing insufficient functionality. This allows for consideration of edge cases as formal requirements while minimizing expansion of complexity. It is refactoring and not innovation.

If there is a need for innovation and new functionality then the requirement is a dedicated feature instead of an edge case. The difference between a feature and an edge case is the different level of intentional overhead required for documentation, integration, testing, and maintenance.


Funny. Linus Torvalds somewhat feels this way judging by this https://m.slashdot.org/story/176163

Repeated below:

At the opposite end of the spectrum, I actually wish more people understood the really core low-level kind of coding. Not big, complex stuff like the lockless name lookup, but simply good use of pointers-to-pointers etc. For example, I've seen too many people who delete a singly-linked list entry by keeping track of the "prev" entry, and then to delete the entry, doing something like

if (prev) prev->next = entry->next; else list_head = entry->next;

and whenever I see code like that, I just go "This person doesn't understand pointers". And it's sadly quite common.

People who understand pointers just use a "pointer to the entry pointer", and initialize that with the address of the list_head. And then as they traverse the list, they can remove the entry without using any conditionals, by just doing a "*pp = entry->next".


Yes, it would be nice if your inputs could take any form at any time to accommodate your "ideal algorithms". Sadly, inputs have definite form and changing them may require unnecessary work, such as allocating memory!


12am/12pm are ambiguous and should be avoided when possible. Try asking people what time 12pm means and you'll see that some will struggle and some will get it wrong, especially if they're from a place that uses a 24 hour clock. But even a 24 hour clock is ambiguous at 00:00. What date should it be? This can be solved by using 11:59 and 23:59 instead.

12pm is usually used for noon. Ironically, of the two choices, it makes the least sense. It makes the PM hours become:

12, 1, 2, 3...

When one would expect:

...9, 10, 11, 12

Unfortunately, people weren't quite as into zero-indexing in ancient history.


Right, 12 is 0 on AM/PM clocks. Once you get to understand that, it's easy to reason with (though 24-hour clocks are the far superior siege weapon).

00:00 is not ambiguous, though. There is no such date on 12-hour clocks (there's no zero! Just 12…), and on 24-hour clocks it's unambiguously the beginning of the day (24-hour clocks are zero-indexed).

In fact, 00:* dates are consistently unambiguous, because they don't require you to define whether you're using a 12 or 24 hour clock. I think you're thinking about 12:00 on 12 hour clocks.


I can certainly imagine cases for which this is true, but I more often than not would expect this to be true mostly at the end of a long tail of requirements smell and model smell.


I'd say if you're working for a real business making money and don't have special cases in the code, you should watch out because some competitor is going to be moving faster than you, and you probably don't bring much value.

In any significantly complex system of business logic, special cases abound. A system of only special cases is of course bad, but a system with a few here and there are expected.


I note that some languages effectively do the array-padding by default. In PHP, accessing an out-of-bounds element results in a Notice (not even a Warning, let alone an Error) and a NULL return value. Of course, in an integer context, NULL gets coerced to 0, so the following will work just fine:

    $input = array(1, 3, 4, 5, 0, 1, 8);
    $i = 0;
    echo $input[$i - 1] + $input[$i + 1];

    // outputs 3


I agree with the principle. Often when you run into a lot of special cases it can be a sign you have modeled something incorrectly. But I don't really agree with these examples. In these cases the "naive" approaches all feel perfectly adequate.

Write it out as straightforwardly as possible. Add some unit tests for the special cases. And then move on to something more worthy of your time than trying eliminate a few if statements.


I suppose a side benefit of eliminating special cases is that you also eliminate branches, which may make things faster. If your preprocessing step is quick and branches are very expensive it might make a real difference.

It reminds me of programming assignments where you're tasked to solve a maze. Exploring the maze is really annoying if you have to special case the edges; much easier if you just build an edge-of-the-world wall first.


This article is unconvincing--the author doesn't even attempt to justify the claims made throughout. I.e.:

> Notice how we treat the endpoints as special cases, complicating the simple rule “sum both neighbors of every element.” A better approach is to first transform the input so the special cases vanish, leaving only the general case.

Why is that a better approach? The author never deigns to share their reasoning.


Be smart, write DRY code, but leave room for hooks to implement special cases. Make code readable, maintainable, and extensible.

Write for maintainability and extensibility. I know you can solve the given problem better, with more succinct syntax and clever shortcuts. Please don't though. The code you write today is here to stay. Plan for the war, and don't overoptimize the individual battles.


Ugly structures that don't map to clear concepts are worse than any special case.

Padding array makes you go "wtf is that?"

I would rather see something like this: (i > 0 ? input[i-1] : 0) + (i < input.size - 1 ? input[i+1] : 0) which clearly maps to "if there is a left neighbor, add it; if there is a right neighbor, add it; return the sum."


Where there's muck, there's brass.

Business is smelly, messy, and just filled with exceptions, special cases, and weird deals with an diabolical structures.

Most startups start with a beautiful, elegant system with zero real users, then they hit traction, and with added business the business logic parts of the code base turn into eldritch monstrosities.


Forcing others to alter their inputs because you want to simplify your method (because code smell??) is nuts.

If you say:

Oh by the way, if you want to call "final_step" be sure to remember to mirror your input array otherwise my method will break.

I would say:

Oh by the way, You are fired.


Sometimes it feels like all I do is move problems around like boiled broccoli on a plate.


Life is made of special cases and it isn't an ideal mathematical model that you can describe with a beautiful one liner. Write solid tests, write meaningful comments, don't over engineer things and you should be good.


Isn't the "better" code wrong in the first example?

instead of "result = (1...padded.size-1).map do |i|" shouldn't be "result = (1...padded.size-2).map do |i|"?


There are 2 forms of range in ruby: inclusive 2 dots - 1..5 => 1, 2, 3, 4, 5 and exclusive 3 dots 1...5 => 1, 2, 3, 4

It's always felt deeply counter-intuitive to me because .. feels like it represents less than ... but that's a separate discussion.


The structure of common sense knowledge is "A unless B unless C unless D..."

Thus the ultimate way to organize a program is to have a clear separation between the specific and the general.


You just change the way they are handled; the knowledge about the special case is now hidden in the setup code, which might be better in some cases and worse in other cases.


I always wondered how on modern day computers software can still run as slow as it often does. This article has really opened my eyes.


>Before going on, consider how you’d solve this yourself.

    var sum = 0;
    for(v : vals) {sum += 2*v;}
    sum -= (vals.first + vals.last);
simpler and much faster than any of the mentioned methods in the article.

(Proof: when you sum the neighbours of all the elements then you add each element twice except the first and the last one.)

Even simpler and even faster:

    var s = sum(vals) * 2 - vals.first - vals.last;


Even though the wording is a bit ambiguous, the problem is to output an array of neighbour-sums, not a single sum-of-neighbour-sums.


oh, ok, thanks.


Special cases exists because reality is not perfect.


Can we get the months to be evenly 30 days? ;)


    result = [0] * len(xs)
    for i in range(0, len(xs) - 1):
        result[i] += xs[i + 1]
        result[i + 1] += xs[i]
    return result


No, special cases are what happens when nice neat abstractions meet dirty, messy reality.

Get used to it, kid.


The only hardcoded numbers in code should be 0 or 1. Anything else, like 5, is a smell.


It depends, hard coding 12 as in months in a year is fine. Best to do it through a named constant though.


Depends on the domain.




Applications are open for YC Summer 2019

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

Search: