I'm reminded of a quote from Moore in "Thinking Forth":
"A lot of conditionals arise from fuzzy thinking about the problem. In servo-control theory, a lot of people think that the algorithm for the servo ought to be different when the distance is great than when it is close. Far away, you’re in slew mode; closer to the target you’re in decelerate mode; very close you’re in hunt mode. You have to test how far you are to know which algorithm to apply."
"I’ve worked out a non-linear servo-control algorithm that will handle full range. This approach eliminates the glitches at the transitioning points between one mode and the other. It eliminates the logic necessary to decide which algorithm to use. It eliminates your having to empirically determine the transition points. And of course, you have a much simpler program with one algorithm instead of three."
"Instead of trying to get rid of conditionals, you’re best to question the underlying theory that led to the conditionals."
That's part of a chapter of the book called Minimizing Control Structures. Forth guys are crazy about taste, and if I've learned anything from reading their stuff, it's that chasing tasteful programming to its end gets very hard.
OP is right on the money. The hard thing is that it is a creative process, and takes a real understanding of the problem you're solving to do it. Worst of all, aside from the feeling of solving a puzzle well, the benefits only begin appearing much later. I'm glad the kernel team takes it seriously.
Be it kernel programming or Forth, the cultural shock can hit hard.
Most programming languages try their best to make things easier than easy, in order to maximize programmers' productivity. The focus on this parameter alone over-promotes the "worse is better" or "good enough" mindset.
That doesn't fare well with kernel programming. It's even worse with Forth. As soon as your "word" (function in Forth lingo) has to deal with more than two or three variables, you're in trouble. As soon as you have more than two levels of control-flow structures, nightmares begin.
If you're looking for programming practice then I recommend Forth. It may or may not be a "practical" language for you, but it makes you really think about complexity.
> That's part of a chapter of the book called Minimizing Control Structures.
Since the book is creative commons and freely available, I decided to download the book and have a look. Figure 8.1, the "automatic teller" example is just downright hilarious. The author presents the code and throws a challenge at the reader: "Easy to read? Tell me under what condition the user’s card gets eaten." Here's the code:
IF card is valid DO
IF card owner is valid DO
IF request withdrawal DO
IF authorization code is valid DO
query for amount
IF request <= current balance DO
IF withdrawal <= available cash DO
vend currency
debit account
ELSE
message
terminate session
ELSE
message
terminate session
ELSE
message
terminate session
ELSE
IF authorization code is valid DO
query for amount
accept envelope through hatch
credit account
ELSE
message
terminate session
ELSE
eat card
ELSE
message
END
(hopefully no transcription errors from copying out of the PDF…)
Yes, it's easy. It gets eaten if the owner is not valid. Took one glance.
The thing that makes me laugh is that the example is contrived. This is the sort of thing code editors solve. Even though I could quickly glance at it and decipher the conditionals by eye, if I were working with this I'd still throw it into an editor that shows me code scope. That makes it trivial and removes any chance of error. This is a problem that has been solved.
I'm sure I will get a lot of responses saying I've missed the point, and yes I'm aware that I've dodged it, but the author acts like the problem of navigating nested conditionals is somehow impossible, which I think is ridiculous. Not only do lots people do it every day, not only are there tools that help us do so, but there's pretty much no way to exist in this world without depending on software that is written this way (ever looked at the source for GCC, to pick one example?) Not saying it's right, but it's clearly not a deadly problem.
Just as taste is a subjective thing as is often hard to articulate... I think my biggest complaint about that code is that I had to read all of it to make sure there weren't other cases where the card gets eaten. And try to follow what was going on.
Taste-wise, an easy fix for this is to do early exits. Instead of nesting, you could easily do (I'm on mobile so no fancy formatting):
If card is not valid: return message
If user is not valid: eat card; return
Etc
Now that's my personal taste. It makes it way simpler to quickly skim and understand what's going on.
> Yes, it's easy. It gets eaten if the owner is not valid. Took one glance.
Nit-pick, but it seems that the card only gets eaten if the card is valid AND the owner is not valid. If the card isn't valid, the owner is never checked and the card isn't eaten.
Just the raw formatting of that could be improved, by cuddling up ELSE IF from separate lines.
Aren't there some END tokens missing? Let me put them in:
IF card is valid DO
IF card owner is valid DO
IF request withdrawal DO
IF authorization code is valid DO
query for amount
IF request <= current balance DO
IF withdrawal <= available cash DO
vend currency
debit account
ELSE
message
terminate session
END
ELSE
message
terminate session
END
ELSE
message
terminate session
END
ELSE
IF authorization code is valid DO
query for amount
accept envelope through hatch
credit account
ELSE
message
terminate session
END
ELSE
eat card
END
ELSE
message
END
Okay, now:
IF card is valid DO
IF card owner is valid DO
IF request withdrawal DO
IF authorization code is valid DO
query for amount
IF request <= current balance DO
IF withdrawal <= available cash DO
vend currency
debit account
ELSE
message
terminate session
END
ELSE
message
terminate session
END
ELSE
message
terminate session
END
ELSE IF authorization code is valid DO
query for amount
accept envelope through hatch
credit account
ELSE
message
terminate session
END
ELSE
eat card
END
ELSE
message
END
Okay, just one ELSE IF; not much opportunity for that.
I dunno, the first example seems unsatisfying. The original has that ugly condition, the "good" version seems overly clever. And for all the talk of taste and aesthetics, both versions ignore an elephant in the room: defensively dealing with `entry` being absent from the list.
Not that I've never abused addresses like this. But having written this multiple times, I currently prefer something like this:
remove_list_entry(entry)
{
if (head == entry) {
head = head->next;
return;
}
for (prev = head; prev->next; prev = prev->next) {
if (prev->next == entry) {
prev->next = prev->next->next;
return;
}
}
}
There's still an `if`, but it isn't so bad since it's an early exit. What is "tasteful" about hiding the fact that one of the cases is far simpler than the other? There's conditionals and then there's conditionals. There's cases and then there's cases.
The other benefit of this approach: you eliminate segfaults by construction, because the `while` has been replaced with a much more normal `for` loop iterating through the list. Keeping it normal is 80% of the secret to avoiding security holes.
Rather than appealing to something nebulous like "taste", I prefer to focus on concrete functional benefits. What is a situation where someone using or modifying this function might be subtly led astray? That seems a better guide.
I don't think anyone's mentioned that there are two functional benefits to Linus's version: testability and performance.
The author touched on testability. Dropping the "if" case eliminates one code path that may contain bugs.
But also, the revised code may perform a lot better if you're searching a lot of short lists. In that case, the target item has a large, though not likely, chance of being first in the list. This kills predictability of that "if" branch. Eliminating it can save ten cycles or so, possibly shaving 25% or so off the runtime of this function for short lists. (For large lists, the branch becomes predictable, and you start having cache issues due to the list's linked nature.)
My current side-project is an NES emulator. Nearly all my (non-algorithmic) performance enhancements have been of this nature: find some unpredictable branch nested inside a tight loop → eliminate the branch with "clever" logic → 25% performance gain on that loop.
(That there are no checks for "error" cases is a distraction. There aren't any in the original example either, because it's an example and the error cases aren't relevant to Linus's point.)
I agree partially w.r.t. testability of branchless code, but there's a flipside too: often the root cause of an edge case is in data-structure shape, so full coverage isn't necessarily sufficient. In other words, if an edge case is "folded into" the normal path via something like Linus' trick, you still need to actually test the case where (in this example) `head` is being removed, or else you aren't certain that the folding of cases is valid. And if you're testing that case, then you'll have full coverage of the original (branchy) code too.
Totally agree w.r.t. performance, though. Even if the branch is never taken, control flow can reduce the scope of other compiler optimizations.
Yes, this is a good point. I had thought of this too and somehow convinced myself that the "head" case disappeared (since the non-"head" case would fail if "indirect" weren't initialized properly), but I'll admit that's a shaky argument.
This comment thread was refreshing to read because it was technically enlightening, devoid of malice, and each party conceding arguments while expanding and clarifying places where it broke down or wasn't clear.
Something we can all strive for professionally and while commenting on HN.
I'd say branch mispredictions and cache misses are the two biggest factors to performance. Almost everything else is noise in comparison. I keep saying if your architecture doesn't account for these, you've wasted 90% of the CPU guaranteed.
I do the exact same techniques in my game engine (sadly proprietary) - even in JavaScript its dead easy to run circles around both Three.js and Babylon.js in terms of performance to the point I'm simply amazed at how fast JavaScript VMs can be if you really push them.
Eliminating branches, cache misses and allocations in the main loop yielded by far the biggest performance boost. (For the curious, we abused ArrayBuffers to guarantee contiguous memory allocations in JavaScript)
I'm not a low level programmer, so this is a honest question.
In the better version, why doesn't the while condition (that must be tested at least once) present predictability problems whereas the if check in parent does?
However, if I'm not mistaken, branches are costly only when they're mispredicted. Hence, the question (as I see it) is wether one can better predict the behavior of Linus' better version (which only has one conditional) or that presented above (where there's an early return condition followed by the while condition).
It seems to me that the version above (which has two conditionals but is not like Linus' worse version because it has an early return) should be similarly costly to predict. Consider the situations where either most of the calls are to remove the first element (A) or most of the calls aren't (B). Let's see what happens in these cases:
- On Linus' code, the while is evaluated the first time. In case A, the while is correctly predicted to exit the while, the swap is made and the function ends. In case B, where the while yields true many times before hitting our element, you should have to pay the cost of a misprediction when you finally find it.
- In the early return code above, the situation is... the same. In case A the early return if is predicted correctly to yield true, and the function ends. In case B, the early return if is correctly predicted to yield false and then the while predicts mostly trues until you finally hit your element, time at which you pay the same misprediction penalty than above.
So... aren't both functions similarly expensive in terms of branch misprediction costs? Am I fundamentally wrong on my understanding on this issue?
Where is that early return you mention? I don't see the return keyword used in either examples. They both do the exact same while loop, but Linus' version adds a level of indirection to save a conditional later on. You're still touching the same memory in both cases so they should be identical in terms of cache misses.
From my understanding, the first version has two possible branch misprediction points while Linus' version only has one. This will probably only have a visible impact if the function is called in a loop however.
But to me the biggest advantage of the 2nd variant is its simplicity. This is the only way to stay sane with a growing codebase and keep shipping robust code.
Its no use getting a fast function if you can't integrate it optimally with the rest of the codebase. Raw performance isn't at the micro level but the macro one. This is where simplicity becomes critically important.
When every branch removed on a mainline path in the kernel saves years of compute time globally and every byte removed in the kernel saves terabytes of memory globally, being clever is absolutely the right thing to do. Removing that one branch takes away an expensive pipeline stall[0]. The version akkartik has above adds a extra branch (and expensive pipeline stall) to _each iteration_ of the loop; Linus would probably not be pleased, to put it mildly, if anyone submitted a patch like that.
And the method Linus shows isn't even particularly clever; it's been a common example for handling linked list insertion in C for decades. All these "Linus is being too clever" postings show is that most programmers aren't cut out to be kernel or embedded programmers.
Taste is malleable and relative. One can even entertain different notions of taste. I personally have at least two – "understandable" and "performant" – and they aren't always (but sometimes are) exclusive of each other.
I suspect Linus's "taste", given Linux's problem domain, tuned to some combination of performant + testable + reviewable + portable. In the example given, Linus's rewrite meets these requirements; hence his assertion that it is in better taste.
I feel at this point, the notion of 'good taste' has become even more ill-defined, something very personal. Then the notion is not very useful as a coding guideline.
There isn't a domain where taste isn't personal. It's always a blend of art and science. Just because you can't define it exactly though, doesn't mean you can't get closer to it by working at it.
Are you seriously arguing that Linus would think cleanly performant code is not in good taste? You're welcome to ask him that directly and see what he says.
EDIT: Okay, I'm being excessively snarky there; my apologies.
I will say instead that is that "good taste" depends on the context. What's "good taste" for kernel development isn't necessarily the same as "good taste" for enterprise development or the same as "good taste" for app development.
As a rookie programmer (but 10 years in IT, loving maths), this was my thought exactly. Basically a matter of field/domain definition, insofar as humans still have to interact with the code.
In short: most enterprise code should be elegant and simple, even if verbose (many conditionals, as little nesting as possible, etc) so that a 12 years old can understand it, because in real life you'll get much turnover and lack of means/skill/motivation. Hence, costly maintenance, etc.
Writing an open-source kernel consistently for 20+ years is an entirely different problem, and the fact that you use code in both these examples is a distant commonality of the problem sets; it is my experience thus contention that the human factor and real world conditions are paramount to ascribing qualitative assertions such as 'good' or 'tasty'. That is, until machines program themselves or others without human oversight. ;)
Yes, of course, I'm certainly not cut out to be a kernel programmer. Were the audience in that TED chat kernel programmers? I thought we were discussing "taste", not what it takes to get a patch into the kernel. Linus does work on other projects, you know.
I prefer the shorter version for being shorter, and for generalizing the update point at the end (and giving it a name), which stresses that there will be an update (delete).
Alas, most of my coworkers would prefer the "explicit" version with all of the extra lines.
Aside: I sure miss identifiers with underscores in them, rather than MashedTogetherEnterpriseSelfCrockumentingMego :-(
I agree with the condition about "If you're at BigCo". It really depends on who's going to read/edit the code, how often, and how many times it's going to be executed.
For a line of code that's going to be executed on a global scale billions of times every second, and only changed (very rarely) by extremely good developers, then I'd happily trade a bit of clarity for a bit more performance.
But if it were an oft-edited method in an in-house application that's going to be supported by junior devs? I would prefer clarity.
As always, there are no universal rules, only tradeoffs.
If you understand C pointers, this is obvious: it keeps track of where the pointer to the current node came from, and replaces it with a pointer to the next node once it reaches the entry to be removed.
I agree, in fact taste might rightfully be defined as that which is obvious to an experienced developer in the environment. Code which simply relies on conventions and avoids complexity is often immediately elegant.
This is a great point but I'm trying not to think disparagingly about the skill level future maintainers, too: deadlines and distraction are a powerful negative equalizer.
The next person to touch that code could be you, in two years after you've mostly moved on to another project / major upgrade and are back in a hurry to make a “quick” change, investigate a security report, deal with a scaling issue, etc
For heaven's sake, everyone, please stop getting hung up on the fact that there's no error checking. Example code usually doesn't show error checking because it obscures the main point of the example.
(which, for kernal code, would be turned off later, anyway)
In languages other than C, with exceptions and stack traces, most precondition checks just become clutter, anyway. Although it would be nice to have "Eiffel" style pre/post-condition (invariant assertion) blocks out-of-line that can be enabled or disabled...
SPARK does that with efficient, system code. Then proves the code free of common errors in C. Then other tools can generate unit tests from the specs just in case. Frama-C does something similar for C. I'm not sure what the usability or thoroughness is like vs SPARK, though.
Totally agree, never play code golf with your production code. Your cleverness will bite you in the arse when you can't be promoted or allowed to move to a new project, because your code is so clever that you're the only one who can properly maintain it.
But I think that's part of the argument. Reasoning about edge cases in code full of nested loops and conditionals is hard. Eliminating branches and opportunities to hide fencepost errors (for instance) goes some way towards reducing cognitive noise so you can focus on the meat.
Of course that's not the full argument. And I'll throw in one more: it isn't anywhere near the top of the list in terms of importance, but aesthetically pleasing, elegant code has a certain amount of value, if only to other programmers. (Naturally, it has to be correct, too.)
More likely, because there are fewer code paths to follow. Given Linus's explanation, I think that's part of the basis of his "taste", not conciseness (which in this example I suspect is a byproduct).
Define obvious. At least the pointer pointer version is obvious to me in this task.
Pointer pointer can't be applied everywhere. If you try to reverse a linked list in O(n) time with O(1) space using a pointer pointer, the code would be less obvious than using a prev pointer.
> You can always go back and make it look pretty safely with good tests.
Yeah, but you won't. I think that's part of the reason why people care about "taste". I want to maximize the chances that essentially the first draft is good enough to be maintained for as long as possible, because years of hard-won experience has taught us that it will.
> Yeah, but you won't. I think that's part of the reason why people care about "taste".
Ahh but you eventually will (at least in my experience). If you don't need to the code either doesn't matter (dead code) or works just fine.
I think I have looked at my own companies entire code base a couple of times. Do I see nasty crap... all the time. And I often fix it for good taste when it is really bad but I have to say the value prop isn't very good compared to adding tests or other automated validation (including automated profiling and dead code analysis).
Kernel code and in particular C are sort of special cases because they are hard to test and performance is generally a high concern. But for many other higher level languages and problem domains this is not the case.
I have been meaning to look how at how much code bases change overtime. In the case of Linux I wonder how much of the Kernel code has stayed the same (lets say over a 5 year period). Probably not a ton but I bet for other domains particularly business software the code either just dies or changes dramatically over time.
Then there are I suppose other domains where the code really can't physically change often (ie space probes and embedded devices).... for those systems I really really hope they have lots of tests.
Counterpoint: test code is also code and when unit test tyrants rule a team it can easily break down into a mess of maintenance (which suddenly more than doubles).
Speaking of good "taste" you could apply your "taste" to what are worthy tests and what are not (ie adding just maintenance). The fact of the matter is you need some sort of testing to happen or some sort of proof that your code works on a continuous basis and if you don't have that to happen IMO I'm not going to say it is good code particularly when it is based solely on one persons opinion of what is good looking code. Aesthetics compared to performance, readability and automated testing are pretty low on my list. You may say aesthetics brings those characteristics and it might but lets have some tests to prove it.
As for maintenance and test code being invalid it doesn't have to be as buggy and in fact can be even in done in a data driven style or declaratively. Besides if it is a true unit test you should have written the test. If its your code and you have such good "taste" shouldn't it not "break down into a mess"?
There are plenty of projects like SQL Lite, and jQuery that have excellent "taste" not just because of the quality of code but because of the test coverage. Oh and I won't go downvote people who disagree (which my parent seems to be) because I hold that to be poor in "taste" IMO.
Another issue both versions have is that they will not tolerate head being NULL.
Don't be afraid of double pointers, although they may seem overly clever at first glance, they can be really helpful for situations like this. Linus's code is considerably shorter, and not particularly difficult to debug or to understand, assuming you understand double pointers.
Another case where double pointers can be really useful is in the interface for linked lists. I.e.
Defining the interface that way allows properly removing the last entry from the list. Workarounds like making a list struct and passing a pointer to that are just double pointers in disguise. Returning the new head is error prone, since you can easily forget to reassign it.
An early exit is not the worst thing in the world, but an edge case is still an edge case. And if you have full "end of list" checks you make it even worse because now you're doing that in two places too. And if you do something with the entry, now that's in two places.
Sure, the case where it's the head of the list is simpler by itself. But treating it specially means more code, and more duplication, and it's not even faster.
To criticize the cleverness of Linus' code is fine. But the algorithm is the argument here, not the specific way he wrote it.
Edit: Also, I don't really buy into your argument about for loops. You trade one problem for another. Your version won't segfault (except the case where it does), but it will silently fail to remove anything.
1. "The algorithm" is the same in all cases here: a linear scan with a look-behind of 1. We're just talking about how the algorithm gets translated into code.
3. Yes, I don't do any error handling and neither does Linus. I wasn't trying to bring up the importance of error handling. I was trying to bring up the importance of avoiding undefined behavior. "Segfault" was shorthand for that. Dereferencing NULL is undefined behavior. I mostly don't care about "taste", but showing undefined behavior while talking about taste seems egregious.
4. Finally, I don't get nearly as hung up about "duplication" as most programmers: http://www.sandimetz.com/blog/2016/1/20/the-wrong-abstractio.... I realize this is still a minority opinion, but we own the future. (This comment has a bunch of duplicated 'e's, but we both agree that that's unimportant to "DRY" out. Your concerns strike me as similar. When you try to minimize the number of occurrences of "x != NULL" you're doing Hamming compression, not programming.)
This version is more clear for a human, but it does contain duplicate logic.
This line:
head = head->next;
is another form of this line:
prev->next = prev->next->next;
Both delete by setting "->next". Code duplication is a common source of bugs, and that's the rationale behind Linus's version, which eliminates duped code.
Not only is it duplicate, it also contains nasty "behavior". If prev->next equals NULL then dereferencing this would result in segfault, so in this case another if statement is required.
Like Linus example, this is just an example too and does not cover or comment on all the issues, so there are still elephants lurking in the shadows, just to name a few:
- Can entry be NULL? (segfault)
- Can head be NULL (list is empty)? (segfault)
Since the Linus example has the apparent precondition that the entry to be removed must be present in the list, there are no segfaults with proper API use. Since your code tries to eliminate that precondition, I'd argue "Remove NULL from the list" and "Remove something from an empty list" is something to expect, but you didn't account for that.
Point being: Don't be overly critical of examples; they are just examples.
I guess my fundamental criticism is this: how is a list traversal that doesn't check for the end of list being held up as an example of "good taste"?
You're right that they're all just examples. I'm just a random guy on the internet, and it's easy to push back against me. But we all have the tendency to nod along when someone we respect says something sagely on TED. It seemed useful to point out that the sage has no clothes on in this case. So go ahead, point at my skimpy cladding as well. I won't mind.
> If entry is null and head is valid segfault on line 10.
To get to line 10, we need prev->next == entry. Since we are talking about the case where entry == NULL, that requires prev->next == NULL
The for loop condition is prev->next, which will fail if prev->next == NULL, hence line 10 would never be reached in that case.
The difficulty of analysing all of this shows why mutable structures and variables make code hard to follow - perhaps the real good taste solution is to use something like finger trees instead of linked lists, together with a language which eliminates null.
I agree with you that moving the conditional to the beginning as an early exit keeps things simple, and while I don't see anything unusual about a 'while' loop and feel they have their place, this 'for' definitely works well.
I would make one small tweak, replacing this line
prev->next = prev->next->next;
with
prev->next = entry->next;
Just makes it a bit more straightforward to understand (as well as infinitesimally more efficient).
Totally, it's not about the one right way to do something. I do think there's some value in putting thought into how to write.. maybe "clean" code would be a less charged word than tasteful.
> both versions ignore an elephant in the room: defensively dealing with `entry` being absent from the list.
Indeed, both versions really have a poor taste.
Both are code snippets which can only work under very restrictive assumptions.
The main argument `head` is implied and the `entry` to be removed must be present.
Such piece of code has to be duplicated and tuned for every list and use case.
I even wonder why Linus bothered to show this example, while he leads one of the most famous software masterpiece.
This isn't an API though. 'head' is fine being implied, and if 'entry' doesn't exist, why is it being passed in ? That's a further code 'smell' to follow up.
Sure, you need to be massively defensive if you're writing an API or boundary, but within an owned codebase, if you're eliminating edge-cases, you should follow them all the way up.
tl;dr if you're calling remove_list_entry, only do so if you have an entry.
Or course, I'm not Linus, so I have no idea of his thought process.
Oh, absolutely. I have a long history of preferring code to be safe rather than fast[1]. In this case, for any project I had a say in you'd have to convince me with concrete measurements that this particular loop was on the critical path, and then you'd have to write a dozen tests to convince me that it was being used right without the terminal check, and that any future users would get unambiguous errors in debug mode. And after all that, you wouldn't be allowed to claim that taking away one of the conditions is "tasteful".
I actually tend to be pretty lax about coding style, believe it or not. But dereferencing NULL is undefined behavior.
The "bad taste" program of Linus performs two comparisons if it want to remove the first entry of the list. The "good taste" program of Linus, like your program perform only the needed number of comparisons.
For me, your program is similar to the one of Linus where you have unrolled the first iteration of the loop in order to avoid pointer syntax difficulties. Your program makes it also trivial to fix what you called the elephant. I think Linus has omit it for simplicity of example.
I like your program slightly better than the one of Linus because the syntax is less tricky, but I think the point of Linus was only the superfluous comparison in the "bad" one.
I didn't know that whiles were less normal than fors.
And though I don't object to for loops in this situation, I really had to puzzle yours out, because of the way your loop pointer is one behind the place of interest.
I believe you when you say it is segfault-free, but again I would have to puzzle at the code to be sure.
I think I'd be ok with a `while` that looked like this:
while (prev->next) {
if (prev->next == entry) break;
prev = prev->next;
}
or even this:
while (prev && prev->next != entry)
prev = prev->next;
Both are reasonable enough that they wouldn't trigger my (pretty laissez faire) sense of "taste". My core point: checking for the end of the list should be non-negotiable.
The `for` is just extra icing: it creates a scope for `prev`; you can tell at a glance that it's traversing a list. The update is closer to the termination check. But yes, this bit is negotiable.
There's a compromise enterprise developers should recognize from CS classes that's almost elegant enough for the kernel crowd: use a sentinel node for the element before the head. The edge case is eliminated, and no more &(*)->; ASCII Cthulhu.
Really, if you think the good version is overly clever, you probably have a very fundamental problem with your abstract reasoning. A very human one, as history is full of people having that problem--and ultimately, the good version taking over anyway.
People for a long time had strong objections to a number "0", because it doesn't make sense to have a number for nothing! Why not just have no number at all! 0 is not a number, it's a special case! Wrapping it up in arithmetic like that is just overly clever! After all, 0 is not a number!
The whole problem with that is the preconceived and completely unjustified notion that 0 is not a number. Just accept that 0 is a number, and suddenly, things become much easier to reason about, much more elegant to work with.
Similarly, the whole problem here is that you have the preconceived and completely unjustified idea that removing the first element is a special case. You can define it to be, just as you can define 0 to be a special case. But you could just as well simply let go of that preconceived idea and accept that it's not, and suddenly all the problems that you imagine are there disappear, and you have simpler code, just as having integer types with a zero makes for simpler code.
".. if you think the good version is overly clever, you probably have a very fundamental problem with your abstract reasoning.."
Just to show that you're talking out your ass, here's a code snippet where I did the address of address thing in precisely the same "remove from linked list" situation. In a VM and programming language and operating system that I wrote from scratch[1].
Moreover, I lived with it for months before I decided it wasn't worth the cleverness[3]. In this case. So I have some plausible claim to having found the "simplicity on the other side of complexity" in this case[4].
As a general rule I'd recommend not reaching conclusions about people from things they write in a comment on the internet. You're looking at them through a tiny peephole into their belief system. When in doubt, ask questions. "Excuse me sir, do you have much experience with C?", "Are you saying pointers to pointers are always bad?", and so on.
(Clever analogy there about 0. Totally agree with it. Utterly non-applicable in this instance.)
> Just to show that you're talking out your ass, here's a code snippet where I did the address of address thing in precisely the same "remove from linked list" situation. In a VM and programming language and operating system that I wrote from scratch[1].
I'm no sure what exactly that code/that change is supposed to tell me, so I can't tell whether it's a good argument. Mind condensing it down/pointing out what specifically you mean?
> As a general rule I'd recommend not reaching conclusions about people from things they write in a comment on the internet. You're looking at them through a tiny peephole into their belief system. When in doubt, ask questions. "Excuse me sir, do you have much experience with C?", "Are you saying pointers to pointers are always bad?", and so on.
Well, that depends on whether you want to make a point for other people in the discussion or discuss some issue with a specific person. As such, that was not really a judgement of your person, but rather a general statement about a group of people (which obviously might be wrong in some cases).
> (Clever analogy there about 0. Totally agree with it. Utterly non-applicable in this instance.)
You mean not applicable in the case of your code, or in the code in the article, or what else?
(edit: and yeah, I realize how the wording might give the impression that I was talking specifically to/about you, but I really wasn't, I was just using what you wrote as the opportunity, so I ended up addressing you :-)
Yeah my link is in a strange syntax, but mostly I just wanted to point at the specific line containing address:address, which is the same as a pointer to a pointer. That line is in a function called delete-before-cursor which uses a (doubly) linked list to maintain the state of a text editor.
I love your project! The of testing pervading the whole system is a very good one. I also like parameters being immutable unless they're a product, that's a great way of making passing references hurt less.
I still prefer the version Linus recommended. It's not for speed - I think it's more understandable. It's more simple (in the way Richard Hickey says, one strand rather than many) and there is less of it. Proving it correct would be easier, not that I actually would.
When people say "clever" to me, I think of code that is being tricky about something. (My canonical example of clever code is Duff's Device.) Linus' example doesn't read as tricky to me, it reads as very straightforward.
Thanks! I'm very happy that you noticed that little feature about immutability so quickly. I'd love to hear from you off-thread if you have any more questions or comments about Mu (email address in my profile).
I tried in my original comment not to bring Linus into it. I didn't want to be just another person on the internet poking holes at a famous person. If the examples had both included a guard for the end of the list I'd have been like, "eh, no accounting for taste, but ok," and moved on in silence. But we shouldn't be teaching/encouraging people to focus on minor considerations like the number of `if`s when there's a larger problem with undefined behavior. Since you already took a look at Mu, here's a place where I try to elaborate on this belief system: https://github.com/akkartik/mu/blob/07b54625f7/001help.cc#L7...
For my money, Linus's example of "good taste" gives up rather a lot of clarity to achieve succinctness. The original is simple and clear. His preferred version is shorter, but also harder to understand because of its use of a complicated indirection. And that's not good taste. It's just showing off.
“Programs must be written for people to read, and only incidentally for machines to execute.”
― Harold Abelson, Structure and Interpretation of Computer Programs
If I put my "Java goggles" on, the first, "untasty" snippet looks so very obviously to be the right way to do it. But...
If I put my "C goggles" on, the "clever" version from Linus looks much more direct, obvious, and better in general...much like the final example from the article author.
While I agree, I also think that it depends on your background. I guess pointer arithmetic should be second nature for a kernel developer? So there might not be much clarity cost then.
It's a long time since I wrote much C but Linus' version seems like idiomatic C to me. The use of pointers in C is an ordinary thing and those who write a lot of C should be fluent in their use.
It's interesting to apply the same technique to other languages. I have to use VB.net most of the time so here are implementations of the tasteless and tasteful versions in VB (untested so there might be bugs). Even in VB the tasteful version is shorter and, I think, clearer.
Module Module1
Public Class ListEntry
Public value As String
Public [next] As ListEntry
End Class
Public Head As ListEntry
''' <summary>
''' Straight translation of Torvalds' tasteless version.
''' </summary>
''' <param name="entry"></param>
Sub RemoveListEntry(entry As ListEntry)
Dim prev As ListEntry = Nothing
Dim walk = Head
' Walk the list
While walk IsNot entry
prev = walk
walk = walk.next
End While
' Remove the entry by updating the head or the previous entry.
If prev Is Nothing Then
Head = entry.next
Else
prev.next = entry.next
End If
End Sub
''' <summary>
''' Straight translation of Torvalds' tasteful version.
''' </summary>
''' <param name="entry"></param>
Sub RemoveListEntry1(entry As ListEntry)
Dim indirect = New ListEntry
indirect.next = Head
' Walk the list looking for the thing that points at the thing that we
' want to remove.
While indirect.next IsNot entry
indirect = indirect.next
End While
' ... and just remove it.
indirect.next = entry.next
End Sub
Actually, I find the double pointer version easier to understand, and incidentally it is also the way always wrote this in C. And I pitied the pascal programmers who had to use the original version.
'Simplify so a fool can understand your code, and you will have fools editing it.'
In the original pascal pointers/refs came only out of new (AFAIR), you couldn't point into structures or to local variables. That makes this trick impossible.
I'll grant that you can't do it quite as efficiently as in C but you can do the same trick as I showed for VB.Net (in another post in this thread) and create a new entry that points at the head then use that as your indirect pointer. The problem is caused not by being unable to point at locals or members but by Pascal's pointers being strongly typed so that you can't simply dereference some random word length memory cell to get a new reference.
So not identical but still simpler than the tasteless version.
Taste is dependent on the audience. An audience of kernel maintainers would probably share Linus' taste here, while an audience of enterprise developers would find the original code more palatable.
I think the specific example can create a distraction because of the use of indirection, but that there is a more general point to discuss: at what point is a chunk of code "too clever?"
One argument is that code should be written so that junior or average (or even below average) developers can be put to work on it. Another view is that part of a junior developer's learning experience ought to include not shielding him from alleged complexity or "clever" constructs, because sometimes they really are better or even unavoidable.
Cleverness for its own sake is one thing to avoid, but I think that's almost too subjective a standard to use.
'cleverness for its own sake' often makes it into standard practice later.
And I seriously fail to see the 'for its own sake' here. This cleverness reduces the number of moving parts, does the 'dont repeat yourself' and thus reduces ways modifications of the code could break it due to overseeing a case.
I just shuddered to think how this would be done in java - with a LinkUpdater interface, and a RootLinkUpdater and ElementLinkUpdater, and one instantiation per iteration, and suddenly we have a lot of code around to keep the active code's function simple - to a point where it is completely pointless because of adding a lot of machinery. (And java does collections differently anyway.)
I agree with you, about this specific example and in general.
When I look back on my career, often when I've said something is "clever for its own sake" was only clever because of a lack of understanding on my part, and rarely for its own sake, outside of toys and obscurity competition where such cleverness is the point.
In userspace this is generally true, and it sucks because "good taste" should really be an engineering determination not compromise to human laziness and mediocre slackers.
I was given a piece of advice very early on in my career that I've always been grateful for, which is fundamentally the same as this. IF and FOR are both code smells.
One case of this is just simplifying loops with some functional goodness
var listOfGoodFoos = new List<Foo>();
for(var i = 0; i< listOfAllFoos.Count; i++)
{
if(listOfAllFoos[i].IsGood)
listOfGoodFoos.Add(listOfAllFoos[i]);
}
return listOfGoodFoos;
VS
return listOfAllFoos.Where(x => x.IsGood);
But perhaps a more interesting point is it can also be a a sign of DRY gone wrong - two things that aren't actual repeats of each other, but just similar code, are smushed together with lots of IFs hang around to make it actually work.
A connected piece of advice was "it is easier to push things together than pull them apart" so err on the side of assuming two bits of code are not the same, knowing you can refactor them together later (probably only a few hours later) if it turns out they are in fact pretty similar.
Does it come down to having a deeper understanding of what is available? In your example, I guess a new engineer may not know that Where() is available, but a seasoned engineer should know.
I also think that this why the social aspect of code review is so important. It is a knowledge sharing mechanism.
> I guess a new engineer may not know that Where() is avaiable, but a seasoned engineer should know
I'd guess the opposite. Its only in the last few years that many mainstream languages have adopted this sort of functional syntax. The new engineer probably learned it right away from the docs, while the seasoned guy churns out smelly-old for loops without a second thought.
GP makes a great point about different loop logic being 'smushed together', that seems to be the most common kind of ugly code (and I've been guilty of it). Perhaps that is psychological. for/while makes loops appear expensive, while the functional code hides that detail and the programmer doesn't think of it.
Might depend on how trendy the new feature is. Because I still see newish Java programmers who apparently don't know that java.date.util exists, and who also don't know that rolling your own date math is only done by date manipulation library authors and connoisseurs of slow moving train wrecks.
A second, related but harder to pin down, issue exists here. I see relatively inexperienced developers who, for instance, get a little confidence with Javascript chaining and callbacks, and work themselves into corners where a given filter method (like the 'Where()' example) doesn't quite do what they need, and suddenly they have no idea what to do. So they hack in something awful in the middle, forget that it is a weird homegrown something instead of a library function, and see profoundly strange problems later.
Both of those are things programmers grow out of, hopefully. But they seem to be instances of having APIs with large surface areas causing what amounts to research failures.
For loops, even in C# are used in performance sensitive contexts. I believe things have changed in versions of .NET and if you're using things like Mono that also have its own versions.
Foreach generally (or used to) generate more garbage/allocations. Foreach against some types in some versions of C# (ex: structs) produces no allocations. There are also some ugly mutation related things you could do using for instead of foreach, but I'd call that bad code.
The same things are true on many platforms - foreach is generally preferable for non-peformance sensitive code. In some languages and libraries, foreach constructs will do things similar to auto pointers or reference counted pointers, which makes them safe enough, but also slower. The point is that foreach can take up more memory, cause garbage, or cause allocations/free on some platforms and languages which is not always desirable. For is therefore a better choice if you don't want this behavior. Mostly though, using for instead of foreach is micro-optimizing in these cases. Where I'd usually do it is somewhere critical in my code, like something called a lot per frame game loop for example. If I caught someone using a foreach that generated lots of allocations and is called a lot of times in these contexts, I'd probably kill them (and have).
So in short, I guess I'd agree that "many" people would do it, but it's context dependent which include performance goals, target platform, language limitations, and more. Mostly, it's better to just write the code that is safe and works, and go back and fix any bad decisions like this. If it's obvious though, I don't have a problem with the optimization from beginning.
Having made my fair share (if not more) of terrible (and terribly embarrassing) errors in C using the for-loop, I love foreach and its brethren in other programming languages. I only write classical C-style for loops very, very rarely these days.
Absolutely - it's why the advice was so good as it led me to trying to discover alternative patterns that remove the ifs.
On our team I try and code reviews to both be about code quality and learning. Reasonably often we'll go down mini rabbit holes about different ways things could be written and the various merits of them. We also try and have more than two people reviewing to spread the learning even more. That can make it worthwhile rewriting good sections of code to be worse just to discuss why the original way was better.
As a junior I learnt a great deal from reviewing the senior devs' code.
Here's one thing to keep in mind. They both end up doing the same thing, but it's more obvious that the Where implementation is not doing anything subtly different from what you think at first glance.
Without reading the for implementation carefully it's much harder to verify:
* You're looping from start to finish
* Over each element
* You're only adding the items to the new list that match the conditions.
That all said, I think this swap is only a good idea if the thing you're swapping with is commonly used. Which admittedly is a chicken-and-egg problem, but does largely exclude non-library function transformations or one-off transformations.
Depends which expresses the actual intent more clearly. To my mind, that it's the list of foos that are good is what's important, and the loop and conditional are implementation details.
In a way, yes. On the other hand, it boils down the code that some poor soul of a maintenance programmer needs to deal with to a single line which is more readable, too. Win-Win.
I don't disagree. But then again I've had peers review code similar to this and flag an issue saying it's too clever because that poor soul might not know what "where" is doing or that the use of lambdas is "too complex."
That is certainly something I've also come across. This kind of functional style is very readable once you understand it, but it does have a learning curve just like learning what "for(var i = 0; i< length; i++)" means.
I actually did a little presentation to the team about how to refactor a for loop to an self implemented where/filter function to explain the connection. For me, realising that all the where was doing (or at least potentially, there might be some behind the scenes optimisations going on) was passing in the condition for an IF in a FOR loop suddenly clarified everything for me.
In case anyone's interested, this is these are the code steps (javascript)
var people = [{name: 'bob', gender: 'male'}, {name: 'dave', gender: 'male'}, {name: 'sarah', gender: 'female'}];
var getAllMen = function(population) {
var returnList = [];
for(var i = 0; i< population.length; i++){
if(population[i].gender === 'male'){
returnList.push(population[i]);
}
}
return returnList;
}
var males = getAllMen(population);
___
var getAllMen = function(population) {
var returnList = [];
for(var i = 0; i< population.length; i++){
if(isMan(population[i]){
returnList.push(population[i]);
}
}
return returnList;
}
var isMan = function(person){
return person.gender === 'male';
}
var males = getAllMen(population);
___
var filter = function(anyOldList, filterCondition){
var returnList = [];
for(var i = 0; i< anyOldList.length; i++){
if(filterCondition(anyOldList[i]){
returnList.push(anyOldList[i]);
}
}
return returnList;
}
var isMan = function(person){
return person.gender === 'male';
}
var males = filter(population, isMan);
var females = filter(population, function(person){
person.gender === 'female';
});
var females = filter(population, person => person.gender === 'female');
var females = filter(population, x => x.gender === 'female');
I definitely agree with this, but note that the semantics in your code are different from those in Linus's example - your code filters out ALL matches.
This is actually an important point. Quite a few times I've written something that started as a list comprehension, changed it to a lambda later in the sprint and finally to a loop when the requirements became more detailed. - The real world is unfortunately full of business requirements that think that they are special flowers.
Does your coding style not involved lining function arguments (and other things) that are broken into two lines up vertically? Converting between 8 spaces and 4 would screw this up.
My preferred whitespace code-style is to use tabs for indentation and spaces for alignment. Under no circumstances should two consecutive lines be aligning something (with spaces) and have different levels of indentation (with tabs), I can't imagine why you would ever need to do this, so this has never been an issue for me.
My preferred whitespace code-style is to use tabs for indentation
What does "I convert it back to 4 space tabs before I commit anything" mean, then? If you're putting \t tabs in your file, 4 space tabs vs 8 space tabs refers to the way your editor renders \t. What are you changing before committing, your editor settings?
Edit: oops, just realized you're not the person I was responding to. The convert it back before I commit anything comment suggests he/she is using spaces. Or is very confused.
Sorry, I should have mentioned that I was not the GP. Even if you use spaces rather than tabs, the idea is the same. Do you mean something like the below? Note: \t represents tabbing (not necessarily the number of tabs, just spacing using tabs), and _ represents spaces.
int f(int x,
\t\t__int y) // one 4-width tab, pad with spaces
{
\t\t// do stuff;
}
int f(int x,
\t\t\t\tint y) // one 8-width tab, whoops
{
\t\t\t\t// do stuff;
}
In this case, you should not be using tabs, since logically you haven't entered a new block yet and as such should not be increasing the indentation. It should be
Even if you use spaces rather than tabs, the idea is the same
It's not, because there does not exist an editor that is smart enough to recognize that these 4 spaces are indentation tabs while these 4 spaces are spacing spaces. It's not impossible, but show me an editor that does it today (especially with C++) and I'll eat my hat :D
I agree with you that if you're using actual tabs for indentation it works fine.
>It's not, because there does not exist an editor that is smart enough to recognize that these 4 spaces are indentation tabs while these 4 spaces are spacing spaces.
Oh yes I see your point. All the more reason to use tabs for indentation and spaces for alignment. :)
You don't know what that Where() costs you, though. The abstraction in your second snippet does _at least_ as much work as the code in the first snippet _and_ has an unknown level of extra overhead.
Abstractions are not free. Because we can almost always afford the luxury of abstractions, some people forget that there's an engineering tradeoff there. There's always something underneath that nice, pretty-seeming abstraction that has to do the dirty work. Because that abstraction has to be pretty and handle generic situations, it (not always but often) can't be optimized to be more efficient in specific situations.
Zero-cost abstractions are a thing though. Compiler magic can even fuse together multiple calls like this on the same collection into the equivalent regular loop. So it can in fact be faster rather than slower, in the right context.
Like most things, it's all contextual. Were I your manager and we were working on a business app, this might pass code review just fine or I might even suggest what you did here if you had showed me the original.
Another piece of context in a business app might be - "Do we need these values now or later?" That is, should this be lazy, stream results, something like that? I am assuming this is supposed to be C#, but still speaking somewhat generally. You might need to instead yield rather than looping and returning an intermediate list. Better yet, I'd also look for you to return something like a read-only list (ex: IEnuemrable in C#) since this is a query result and that can be done with the first version.
Unfortunately if we had been writing a game though lets say, I would have failed you miserably for the latter version and added 1 mental strike to the "send you packing" count. Why? For loops are most certainly not code smells on most platforms. As a few people said, the mechanics of "Where" in some languages may just be cloaking a for loop. More importantly, for loops tend to be much more performant, can be inlined easier, and generally produce less garbage than lambdas and other similar language constructs. It may different than I last looked, but back when I used to touch C#, for was most certainly preferable for anything performance sensitive provided you didn't need laziness, and if you did, there's still at least "yield" (though at that point, we're approaching what Where can does anyway). I could go on about cache lines, trashing, GC pauses, and so on, but hopefully you get the idea.
Overall, I am afraid I must disagree and point out that your advice you treasure is too generic. FOR and IF are very valuable in certain contexts. I think the real advice someone might have been trying to give you is to aim for more functional constructs, that is functions that are pure/idempotent/referentially transparent, compose, and operate on sets of data where possible rather than individual points of data. Like any advice, this isn't universal and quickly unravels in many situations such as performance-sensitive contexts like game programming, real-time programming, and so on, or may in fact just be the best practice of the target language.
I absolutely agree with you about performance stuff, if you are in a position where milliseconds matter this may well not be the right way of doing things.
Also, to open up another interesting area, Linq operating on IQueryable objects can do some pretty interesting stuff in the background, merging sql queries and the like. I've never looked into if it does anything similar for IEnumerable - although I will should the situation come up.
FOR and IF are indeed valuable, but that doesn't make them not smells. For me a code smell is not an anti-pattern - it is just an indication that something has the potential to be wrong. If you are writing lots of IFs and FORs in your code that might well be fine, but it has a good chance of causing problems. Smells, for me, just mean "justify this decision" - not "never do this".
Things like FOREACH are good sane defaults, so the justification only happens based on what you are doing like in the performance example.
IQueryable actually is a superset of IEnumerable (implements it - https://msdn.microsoft.com/en-us/library/system.linq.iquerya...). It is generally useful if you want the laziness and ORM/ORM-like features. If you are using LINQ with SQL, then it would be better to return something like that for many use-cases. IEnumerable is good for general use of course and when you want to make the assumption that you "don't need" all that stuff which is pretty good one for more general cases where you just want read-only results or lazy read-only results (via things like yield).
I agree about potential. Nested FOR and IFs though raises that potential hugely. There is rarely a reason to be nesting more than a few levels deep. In many decades of programming, of course I have deeply nested, yet I have refactored it each time. I have managed to avoid doing excessive nesting the entire time as have most of my colleagues. I am sure someone can find a piece of code somewhere written for something that simply cannot be refactored well or justifies itself otherwise, but I'm not afraid to say statistically that is easy to avoid and hard to justify. I think the nesting issue just raises a bunch of flags including: performance, composability, reusability, clarity, maintenance, and cloaking. So in that sense I do feel it is what you describe as an anti-pattern more than a code smell.
That is more imperative programming (your first example) vs. functional programming (your second example). The problem with functional programming is that you need to know how the functions are implemented to be able to estimate performance.
Don't write the block to the if without curly braces on the next line. It's a common source of bugs when the code has to be extended (possibly by someone else), to forget to add the braces.
It's not simplifying it though, it's just hiding the complexity in syntactic sugar. I prefer the first way of doing things vastly over the second. Yeah, it's more code, but it's also more or less "what is actually happening", instead of an euphemism which has to be unpacked.
I disagree, I believe it is properly using abstractions to write simpler, more straight-forward code. I think of syntactic sugar as 1-to-1 replacements. For example, the -> in C and C++ is syntactic sugar for a dereference followed by a field access (ptr->field; (*ptr).field). If it's not a 1-to-1 replacement, then it's more likely to be an actual abstraction.
The first example is code duplication, and almost every line is suspecious.
var listOfGoodFoos = new List<Foo>(); // is listOfGoodFoos a good name?
for(var i = 0; i< listOfAllFoos.Count; i++) // is the loop condition correct?
{
if(listOfAllFoos[i].IsGood) -- the only interesting line is burried in here
listOfGoodFoos.Add(listOfAllFoos[i]); -- is i the right index variable? (vs. j, k, n, especially in nested loops)
}
return listOfGoodFoos;
The second example is obviously correct, and highlights the condition.
A quote from Tony Hoare comes to mind:
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.
Actually, it's written exactly as often as the original construct.
The idea that writing more than 5 letters, or a for loop here and there, is this giant cesspool source of errors is totally alien to me. Of all the ways in which my programming sucks, this was never among them. So thanks for you permission, I'll use it wisely :P
Yep. As long as the abstraction is tested and functions as advertised it can be very useful.
I'd much rather see a few lambdas in a chain of function calls than blocks of conditionals and loops. Every keyword or bit of code that has to be typed is a potential source of errors, and abstractions of this sort help minimize that.
All programming languages are "euphemisms" in that sense - even C has a lot of layers between it and how modern hardware behaves. It is simplifying if it expresses the important aspects of the result rather than the implementation details of how the machine calculates it.
Sure, but when programinng, what the machine does and how long it takes, sometimes does matter. I have to think of all those jQuery examples floating about out there that just do $('#foo') in several places -- sure, it looks simpler than putting it once into a variable, but from the viewpoint of what the computer ends up doing it's utterly ass-backwards.
There's no reason a `.where` should be slower than an explicit loop though. Indeed it should offer more opportunity for future performance improvements, because it doesn't constrain the implementation with irrelevant details - the compiler is free to e.g. make the loop run backwards, or split the collection into chunks and parallelize, if it figures that that would be faster.
At some point that breaks down though doesn't it. I mean from one perspective a conditional in high level code doesn't describe "what is actually happening, either." That's especially true if an optimizing compiler or interpreter mangled it up.
From another perspective your argument can be applied to any function call in library code.
In either case I don't think your position is that strong.
> I mean from one perspective a conditional in high level code doesn't describe "what is actually happening, either."
Sure, and from another perspective even the most efficient code does nothing to stop the heat death of the universe and is therefore functionally equivalent to doing anything else or nothing at all. However, that's just splitting hairs. It's not really an argument anyway, but rather a preference.
The question is more whether it's a reasonable preference to think syntax X is helpful but syntax Y is hiding things. Thinking deeper might show that the issue is actually familiarity, and the two should be rated the same in terms of abstraction.
These are great examples, and they hint to, but do not mention, the big counterpoint: development time. In his own examples, the author admitted that though the code was ugly, it worked. He then spent extra time reworking the existing code to make it, well, prettier.
"If I had more time, I would have written a shorter letter." -- Voltaire
The problem is that, in many (most?) professional settings, the developer is under huge pressure to get shit done. Not get it done perfectly, not done beautifully, but just done in the first place. We rarely have the leeway to spend extra time refining existing code, existing features or bugfixes, to make them prettier. It's gotta be done, and it's gotta be done yesterday because maybe some other part of the project is blocked because of it or some customer paid for it and it was supposed to be done last month or it broke and why the hell isn't it fixed yet!?
Some projects, I daresay mostly open-source projects, can afford to be detached from the pressure of deadlines that corporations require, and reject code that isn't to their quality standards. Sadly, that's not the case for most of us.
I think you are overlooking a number of things, first of all the code examples are not just prettier they are faster as they bypass test conditions. Save possible compiler optimization or CPU branching strategies which I am not too familiar with, this would at least still save execution cycles in certain cases/languages. Might seem small here, but when it's for library code, code that gets duplicated in memory and needs to also copy variables and closures (i.e. rows on a webpage), or simply a practice all across the codebase, it will have effect.
Not only that, but as the author outlined it's easier to read and parse for another developer, and there are less chances for errors.
I, for one, strongly believe that pushing software excellence reduce the number of high pressure situation to "get shit done", as it's better to take control of the code than other way around.
Apart from trivial or throwaway projects, code is read many more times than it is written. Spending time reworking some code to make it easier to read will pay off over the long term.
(There's the question of whether making code more compact but more "clever" truly makes it easier to read, but that's a separate point.)
This demonstrates the general move in the marketplace from companies developing software, to instead hacking out quick product for fast money.
The startup mentality has made this worse, and continues to do so.
Good software requires thought and time to get right. Unfortunately, those people buying software are often willing to pay for low-quality hacks these days, in the name of a quick fix.
It's just another commodity now, and as such, like many other products, more about cost than quality.
> This demonstrates the general move in the marketplace from companies developing software, to instead hacking out quick product for fast money.
I can attest that there never were "good ole days" of software development. There never was "take all the time you want, do it right". There were always schedules, commitments, and budgets.
It is certainly true, if there is absolutely no time to clean up, there is nothing to do be done about it.
However I think there are too points to consider here.
First, cleaning up code is a skill and as such it improves with practice. That is the more you get used to fixing code quality the faster you are at it and the easier it is to include it under time pressure. If you are never given the opportunity to do it, there is no chance to become more efficient at it and there will never be enough time to do it inefficiently.
(The above is IMHO even more true about testing.)
Second, it is the favorite excuse of the lazy programmer. "Pragmatism", etc. From the outside it's hard to distinguish between lacking time and lacking willingness.
While the improvement might or might not be worth the cost of figuring it out for this case in isolation, note that a more experienced programmer would write the final better version first, without even considering looping over the whole 2d array. How do you learn to do that? By revising your code!
If you never get to learn better, you're letting your management force you to retard your own development. Unless you're a temp it's probably even costing your employer more than it gains. Of course, there's a balance between learning and firefighting. Just don't put the fulcrum all the way over on the left edge.
It may be quicker for the original developer to throw together some awkward but working code -- the real expense comes from the time spent by subsequent devs having to read and understand it.
Linus' "good" version has a McCabe cyclomatic complexity of 2, whereas the "bad" version has a value of 3. So, objectively, one could argue there is improvement there (albeit small). Validation of the "good" version will be easier (e.g. code coverage testing) with fewer paths through the code. Additionally, a lower cyclomatic complexity typically implies less stress on the developer's working memory while reading code (since you don't have to consume an internal brain "register" holding the result of a conditional while following the flow of control).
> it only performed 256 loop iterations, one for each point along the edge
alarm bells
There are only 252 points along the edge. This code will act on each corner twice. If you were performing an operation like `+= 1` on each edge element, this code would be wrong. When you copy and paste it later and change all the `= 0` to something else, you might end up with an unfortunate surprise.
Once I saw this mistake in the 2nd code example, I guessed it would also appear in the 3rd one. Sure enough, it does. This is just as unsavory to me as the original code.
I'm not sure if the author is here or not, but if you are, can you see the fix?
The way I'd do it if I didn't want to use ifs is to loop n times, and for each row fill the first cell and the last one. So now I have the left and right side at O(n). Then i'd loop n-1 times starting at the second column and for each column fill the first and last cell again. O(n) all in all without repeating yourself, and no tests.
Another way to look at this problem altogether would be to change the data structure, so instead of using a classical 2d array the problem becomes trivial if you use a spiral array. Filling the edge in this case is just a matter of filling the first 4*(n-1) cells. Obviously this solution's acceptability depends entirely on what you're gonna do with your data afterwards.
for (i = 0; i < GRID_SIZE - 1; ++i) { // Note the "-1"...
// Top Edge
grid[0][i] = 0;
// Bottom Edge
grid[GRID_SIZE - 1][GRID_SIZE - i - 1] = 0; // Reverse the order: from left to right
// Left Edge
grid[GRID_SIZE - i - 1][0] = 0; // Reverse the order: from bottom to top
// Right Edge
grid[i][GRID_SIZE - 1] = 0;
}
This way, for every row/column, the loop acts on all but the last cell, which is actually the first cell of some other column/row.
I feel like for the each side you could actually handle two items per iteration, one forwards _and_ one backwards. That way your iteration count could be halved.
That doesn't reduce the number of cells touched, and would make the algorithm more complicated. It would also probably hurt cache locality. Going backwards is also pointless complication, you could just as easily cut into two sections and go forward in both.
And furthermore why split in two? Why not split the range into three sections, or four, or N and completely unroll the loop?
Honestly the whole second half seemed damned weird. Give the requirement to zero the edges of a two dimensional array, it's so astonishingly obvious to just hard code the 0 and width-1/height-1 that do do anything else suggests a special effort to make a sub-optimal solution simply for arguments sake.
Yes. Another issue is that his grid is a square. It's hard to know whether this was sensible - author hasn't described the domain.
You could address both issues by having two for loops, one following the other. The first loop changes the top and bottom rows. The second loop changes the sides but not for the top and bottom cells. A comment could highlight that you're not updating the corners.
Here is which seems to be idiomatic in digital photo processing (e.g. darktable):
for (int r = 0; r < GRID_SIZE; r++) {
for (int c = 0; c < GRID_SIZE; c++) {
if (i == 1 && j >= 1 && j < GRID_SIZE - 1)
i = GRID_SIZE - 1;
grid[i][j] = 0;
}
}
Of course, this one has a conditional, and many would frown on mucking with the loop counter outside of the for statement.
A source for this style may be dcraw, e.g. see from border_interpolate():
for (row=0; row < height; row++)
for (col=0; col < width; col++) {
if (col==border && row >= border && row < height-border)
col = width-border;
// etc.
The dcraw code is so tightly written that I assume Dave Coffin has good reason for this choice, but I've never tested variants for performance.
Not being used to C syntax, I took this as a typo at first:
indirect = &(*indirect)->next;
The position of the parentheses make it look like you're dereferencing only (* indirect). But on second look, you need the parens there so that it's (* indirect)->next as opposed to indirect->next. Then the & operates on the whole thing. I'd be tempted to wrap it in a second set of parens for clarity, but perhaps it's entirely obvious to a programmer who's actually used to using pointers. IE:
I think the whole example comes down to Linus being really good at C. He wants code from people who are similarly fluent in the idioms and syntax of the language.
It's quite clear to me[0]: The member access and subscript operators (. -> []) have the highest precedence, and the pointer dereference and address-of operators (* &) bind from right to left. And in any event if you left out the parentheses the compiler or IDE would likely catch your error.
[0] As someone who likes coding in C/C++ for fun but has never for my day job.
It's busier to look at due to the syntax of the language, but if you're comfortable with pointers one could argue that it's conceptually simpler than the first example. And since linked lists are all about pointers, operating on the pointer directly seems logical.
That said, for someone unused to the syntax (as I am!), I agree that it is definitely harder to mentally parse. So which is objectively better probably depends on your audience.
You have 20 years of experience on this kind of stuff and don't recognize the textbook example code for handling the head pointer case of a linked list? Well, okay...
(It's at least 23 years old because I learned from textbooks that have this example code way back then. It probably dates all the way back to K&R.)
Well, I'm at work so I can't dig around my library but it was easy enough using date range restrictions to find an academic example in Google that dates back to '99: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf . (It was actually the first hit.) Searching further backwards in time is left as an exercise to the reader.
Multi-level pointer dereferencing is a fundamental C / assembly language skill and Linus' example was just about the most basic example there is.
Maybe. But if it is a common idiom in the linux kernel (is it ?), it doesn't mean anything that the first time you encounter it you will take some small amount of time understanding it, because then you'll know about it, and it won't cause any problem in the future.
I don't know how to reconcile Linus's track record is of indisputable brilliance and success (I use Linux and Git on a daily basis and am eternally grateful for both), with the fact that I would absolutely DESPISE working with a peer with the kinds of attitudes and opinions on coding that Linus has.
I think the problem I have is that a lot of people use Linus's examples and stories as justification for their own suboptimal interpersonal skills, overly-clever code that only they understand, but without the same level of brilliance or track record to justify it.
Ultimately I think Linus's contributions to Software are pantheon, but he should not be looked to for imitation or lessons. His lessons for success are detrimental to the vast majority of software engineers.
You make claim after claim, and I think they do need substantiating evidence. After all, I find it highly unlikely that if he were even 10% as bad as you make it sound he would be the head of one of the most successful projects - especially since everybody working with him does so voluntarily. There would have been breaks long ago. The fact that the Linux kernel held together under the original author loudly speaks against assumptions of "bad interpersonal skills" on the side of Linus.
See what I already wrote. This is like marketing research - what do you believe, what people tell you or the data about what they actually do? Because the data say what I already wrote. So you might as well interpret this as "Linus is a very humble guy" and have better support from the data.
Or, alternatively, you can believe that a really mean person who doesn't care about others and behaves badly still managed to hold the kernel developers together. Sure, a single or even a few discontent developers can't easily fork the kernel - but if there would really have been a problem even a tenth as large as claimed by some (and I've never seen any of them actually having had any personal contact with Linus) they would long ago have forked. See node.js/io.js, OpenOffice, and other prominent examples for what happens when developers are not satisfied with the project's leadership.
I don't understand what this has to do with refuting the original claim:
> Ultimately I think Linus's contributions to Software are pantheon, but he should not be looked to for imitation or lessons. His lessons for success are detrimental to the vast majority of software engineers.
You're not supplying any examples others can learn from or benefit from imitating, you're just asserting they must exist.
Uhm... this is again backwards. I'm not making any claims - I'm responding to others who do. And I did (still) provide evidence: The Linux kernel project itself. Instead of individual anecdotes or some carefully selected email or sentences taken out of context I point to the whole project as the final outcome measurement. See what I wrote?
I won't argue with your main point, but a fair share of kernel devs are probably not working there voluntarily, since they write kernel code for their employer.
I'd expect that most devs capable of writing reasonable Linux kernel code would not have difficulty finding employment somewhere else doing something else.
But this is backwards! You don't become a kernel developer by being assigned to the job by your employer. Instead, employers hire people who are kernel developers. Source: I myself contributed a teensy tiny bit to the network stack loooong ago (2.4 kernel), and I worked with real kernel developers when I worked at one of the major Linux companies and for them with large (mostly US) software companies.
I get what you are saying and I agree somewhat, but there are also some lessons to be learned from Linus and things to consider. I especially agree that many lesser talented people use his behavior as a justification for their own. I disagree that at least some of his lessons or behavior is detrimental.
A good realization in life that many of us have is, "Most people are wrong about most things most of the time." This feels sometimes like it applies by an order of magnitude to programming. I think Linus has a style that deals with this reality head-on and it certainly is not for everyone.
One needs to perhaps not be exactly like Linus, but draw some insight from what he does. First, he is bluntly honest with people and there is virtue there. You can argue there is a polite way to be honest, yet sometimes I wonder if I have found it. For huge parts of my career I made my life harder or even self-sabotaged myself by being overly polite to people. I was always assuming (and often still do) that I am wrong and they are right. Further, I give people the benefit of the doubt, try to help them save face in front of others even when wrong, and hear them out before making judgements. It sounds solid and is many ways a healthy attitude for life in general as well as programming.
The problem that arises is that people are people. It is true that people will take advantage of you. It is true sometimes if you give them an inch, they will take ten. It is true stupid people often get ahead. More often the answer is simply people don't get the message.
You can sit and do a code review with someone, ask them politely to do something, send an email, have a lunch chat, whatever, and the message still does not get across with most programmers. You can say that is bad communication or "my fault," but actually I am speaking more about what I observe rather as a whole than my own personal experience. I have had the privilege of working with best friends for small parts of my career, and even then this was an issue. I can't imagine people with better textbook communication than we did, but maybe what we needed was more Linus-style communication. Sometimes the advice or knowledge is beyond colleagues, and they'll even say, "Yeah, oops, I know you said to do X, but I did Y, my bad." That doesn't help you in project and getting things done, especially if it means minimum someone spends time to fix mistakes they know they should have never made.
If you are direct or even a bit abrasive, there is no ambiguity. I grew up in two different cultures side-by-side and traveled the world at various points, living abroad for periods too. Without providing too much PII, I will say that my experience with American culture is that it is very polite, understanding, apologetic (Canadians get this rep.), relatively open, and welcoming. People in American workplaces are on the one hand uptight, more wound up, extremely dishonest, very opportunistic, melodramatic, and a host of other negative traits. On the other hand, Americans are very precise, thoughtful, at least feign listening to you, clever, and methodical. Compare that to another culture that I'd describe as masters of improv, extremely practical, open, honest, and yet sloppy, self-centered, arrogant, overconfident, and disorganized. Neither culture is better than the other, and like Linus, his style just represents one view point of dealing with programmers that is not really better or worse than most others that work.
I will say that in the second culture I mention, things get done faster for certain types of work. The openness aspect also really matches a part of what Linus does. People tell you exactly what they think of you. Sometimes it's really hurtful such as telling you that you look "fatter" one day vs. another. They don't think of it as malicious though because from their perspective, they think something is wrong and they are trying to help. By pointing out you look like you are gaining weight, you might be surprised to know what is really going on is they think you might be sick and want to take care of you. They think you might be eating bad and want to feed you better food. Sometimes, sure, they are just being dicks.
One can think of what Linus says as just a philosophy that won't work for everyone. Someone telling you exactly what you did wrong and not trying to be diplomatic, cute, or passive aggressive about it ensures the message is clear. It helps you in that you may never make that mistake again. There is no ambiguity hopefully and you either do what he says or decide all of it is not worth your time. Playing games, working people with you do not like, pretending to be nice, and blindly following cultural idiosyncrasies are not things I personally enjoy. Some people need those layers of protection or to live a life with those things, and that's fine I guess and equally OK if I decide not to for myself.
I personally cannot work in an environment like most of corporate America anymore or even startups. I need people to be "real" with me, and to learn non-obvious things. I need to be constantly improving, not patted on the back and stabbed in the back by that same person. I want to be stabbed in the front. Of course I realize for many people that might be soul crushing and too much.
The problem I think is that people are misinterpreting what is going on here. Using curse words at everyone for the sake of cursing or yelling for the sake of yelling is not the message. Nor is one true style of coding. To me, his message in part is "Be honest, be direct, be specific, and be clear." He has one clear direction for most of his projects and expects people to follow it or go home. IMO, this is what many software projects need - good, unwavering, solid leadership. It usually doesn't work with a pure democracy because no decisions, at least not the heard ones are made. I look at committees like the W3C and others and see how long it takes to produce output, how much fighting, etc. I look at github issues and see the long threads of people trying to fake politeness. No thanks.
An ignorant tyrant isn't what is needed either. This is where it gets hard. If there was one style for all projects, we'd use it for all projects. Sometimes democracies maybe do work for small projects. Sometimes the real leader is not the person identified in charge. It takes some luck to have what Linus's projects have and the same leader who is good for one type of project is not good for another. I am 100% certain Linus would fail leading many projects.
As for Linus WRT to the software pantheon, you'd be surprised by what I just wrote to note that I don't really care about him. I do not have heroes or believe in hero worship. Moreover, although I use and value Linux, I do not actually like it and I am somewhat unhappy it exists (but happy vs. Windows lets say). I simply use it because it is better for many of my use-cases than what is out there. That won't stop me from pointing out all the legacy warts and wondering if all this time, money, and effort would not have been better spent on a new OS with a new philosophy that did not carry over the ton of anachronisms and design mistakes from Unix and the surrounding community. I do not even consider most of what is in Linux that interesting or innovative, but I am still glad it exists and most of all can easily appreciate the pragmatism of bringing Unix to the home and affordable business world.
Anyway, look at things for what they are and separate that from your personal beliefs, and it will help you learn even more.
I can see where you are coming from, but the problem with speaking plainly and directly in all cases is that it can run into some pretty hard cultural boundaries. What you say and what people will interpret you as saying can be quite different. I struggled for a long time to understand that, so let me explain.
The way this seems to work around here (I'm a Canadian, and I've worked in the US, too) is that it is just fine to be directly critical of others if you are talking downward socially. Boss to subordinate, parent to child, teacher to student, it's just fine. But it's not really OK peer-to-peer or upward. And if you insist on being bluntly critical peer-to-peer or upward, what you are saying carries the additional meaning that the person is a real bozo or messed up really badly, so you are justified in talking down to them, as a sensible knowledgeable person dealing with a fuck-up.
That said, it is possible to convey criticism sideways or up, but it requires some social tap-dancing to emphasize that you are only telling the person they are mistaken, not that they are laughably hilariously wrong. The simplest of them is understatement. Compare "That doesn't look right to me. Could you check that it's doing what you expect?" to "No. That's wrong."
Next time you are tempted to be bluntly critical, keep this in mind. Your message may be taken as much more severe criticism than you intend.
Finally, let me add that this rule is not universal. In some cultures and subcultures, it's much more OK to be directly critical. In others, presumably, it's even less tolerable.
Yes, in part what I was saying that in some cultures, people are more openly critical. It just is accepted, and no one gets too offended unless they are from another culture. What you are saying about the inability in US/Canadian culture to be upwardly critical or even critical sideways is entirely true. It is also such a silly thing and really makes the workplace unpleasant for many people, more than someone calling my code shit might do.
As someone who grew up in multiple cultures and lived in other cultures (Toronto, Canada among a few others), I see all too clearly what it means to cross or run-up against cultural boundaries. I've had to explain to girlfriends (outside my culture) for instance not to get offended by my family (non-American) and the things they will say. Quickly, they come to realize that despite the sometimes harsh sounding words, culturally my very blunt family is much warmer than anything they encountered before.
I am also well aware of what criticism means in different cultures and workplaces and I do not struggle with what you described. Your advice about keeping all that in mind is solid from a practical perspective. What I am saying has nothing to do with advising or advocating people to be like Linus or like me. Rather I am saying a few important things - understand the value of bluntness, the reasons behind it, don't be harsh for the sake of being harsh, pretending is silly, and that I am a firm believer in honesty.
I do value knowing what the culture norms are, but I try not to let myself be entirely bound in life by them. I have worked long enough and put myself in situations not to work with people who make me play stupid games or diplomatic twister. People should not discount the value of being direct just because it is against their cultural norms. Further, they should see that people from other cultures or other mindsets might have another point of view worth considering. As a result of just being honest, I find in most situations my communication is perceived clearly. I know this because people tell me exactly that and the results seem to match.
There was an interesting article recently in the NYT or Washington Post or something else big about the UN Ambassador for Israel and what gets said to him from enemy countries behind close doors (nice things, blunt things) vs. the crazy rhetoric some of the same ambassadors use when addressing what he calls the "public UN." In part, one of the points he was making is that the real work was getting done behind closed doors and the rest was mindless gesturing and show for the people back home in various countries.
Regarding Linus specifically, what he says can be taken (and is) sometimes as harshness for the sake of it. That does not mean there is not passion, value, truth, and other things to be found. Notice though that the truly valuable things Linus says in harsh ways are nearly always backed up by facts. If Linus says someone's code is stupid, often he points out exactly why and where instead of wasting time trying to be diplomatic about a bad commit. Taking this to the extreme where you don't provide any reason, feedback, and facts is a big problem. People who do this are not being honest or blunt, they are just being jerks and there lies part of the difference.
Perception is important and that's something people forget. I get that people are sensitive, caught up in their culture, yet at some point I would advise people to think with their brains and grow up. People like to do the same thing I described in the UN - gesture using their status, position, titles. That is a dumb thing that stands in the way of getting things done and what many people would perceive as being a good person. If a CIO wanted to fire me because something I said hurt his/her feelings, that's fine with me and not a place I want to work. I would never purposely say hurtful things to someone, at least things that were not true and certainly not without a concrete reason. My view though is a bad prescription for many people, so it's important to also understand that.
It's also worth noting that there is a time and a place for criticism, which is not all the time. More often than not, instead of whining and blowing up at someone, the situation will correct itself if no one pretends or lies to provide encouragement otherwise. At some point you may need to still intervene, but it is contextual. I'll never tell someone who is doing a bad job a bunch of positive things to encourage them for the sake of it. Likewise, when they start doing an actual good job, I will thank them for it. Linus perhaps could use a little more positive reinforcement. I guess he's OK with how he is, so be it.
I am not afraid to sound insulting here by saying that I think it's a sign of low intelligence if you cannot step outside of yourself at times. Obviously it's hard to do this all the time. People really get so caught up in doing what is expected rather than thinking for themselves. This conjures notions of "sheeple" and living a false narrative. I find these things far more revolting than what anyone could say to me with simple words, other people believe otherwise. I learned long ago there is no way you can make everyone like you, but you can respect everyone at least on basic levels of behavior which does not necessarily mean bowing to their cultural norms and emotions, rather simple, basic humanity.
You mention some examples of social tap dancing. While doing consulting, I had to become the master of this and it's rather a necessary skill in this world that I hate. What people are doing by saying things like, "That doesn't look right to me" is usually lying by omission, acting passive aggressive, or simply communicating poorly by garbling the message. To be honest, this sometimes really annoyed me in Canada when people would pass-off passive aggressive behavior as "polite" behavior. Of course my own culture skews this perception and most of the time. My solution was to take my own advice - understand their point of view, don't be offended, and move forward to what's real.
Generally, I try to always provide facts, reasons, clarity, and to keep calm. I expect the same back, as it should be. I would rather live a good, honest life and not live in a fantasy world. One semi-effective test is that if you have to ask yourself if you are being an a-hole, you are the a-hole. Surprisingly, I have only actually yelled at anyone seriously once in my career and it was related to something just about anyone would react the same (racism). Being honest and blunt doesn't mean you have to treat people poorly, yell, or go out of your way to be negative. On the contrary, I tend to compliment people more because I am not afraid to be open.
I find being open breaks down a lot of important barriers at times. In my personal life, this often leads to a lot of "Thank yous" and being the go-to friend for advice, confessions, problems, and more. In the workplace, people feel comfortable bringing tough and embarrassing problems to me because they know they will get an honest and constructive answer. I often felt crippled at points in my career when I got polite, useless feedback. I can't express how many problems in life or programming I have solved by simply telling it like it is. Quite often, it has nothing to do with dropping f-bombs. Sometimes I just tell someone that I feel stupid and need help, and I am happy when others reciprocate. As you can see, this is probably one area where Linus and I differ, but I can't help but laugh at the reactions he gets from ridiculous people that don't want to admit their own faults. I have many faults and I freely admit them because I want help.
If I had to actually give a piece of advice here, it would be to just be yourself and figure out what you value. Everything you do should be working towards that. If someone stands in your way, don't run them over, just put yourself in a better position - find a new job, move, cut them off, be the better person, prove your points with facts, do whatever you need to get past it while staying a good person. Lying to yourself is a hard thing. Being critical is not being cynical, it is being honest if you approach it with a clear mind. This is all often at odds with tech culture and it has admittedly hurt me in a few cases. But I feel alright with myself and that is success for me.
I don't know why I'm even replying, this will get so much hate here, oh well...
1. Just because things aren't done "the way you would do them" doesn't mean they're "bad" or "wrong".
2. If you're not on a solo project, I've found writing correct but less "clever" code to help shorten ramp-up time for new devs and be more beneficial to future maintainability of the code-base and system.
TL;DR; Swapping values by XOR'ing may look elite and clever but hurts you in the long run.
Comparing the two versions, I found the 'clever' version to have less cognitive overhead, since the reader has less state to keep track of (1 vs 2 variables).
I don't find the pointer syntax that difficult to reason with.
People will and are arguing that "it is kernel code, it should be complicated" but I really think this is backwards. Because it is low level and debugging is really cognitively intense and difficult at this level the code should be even clearer and easier to understand.
People aren't arguing kernel code must be complicated. People are arguing that dealing with pointers should be second nature to kernel developers, so the lines of code causing you and me congnitive overhead should be second nature to a kernel Dev.
I still think one should not make code more complicated than it has to be just to weed out the newbies.
An OS kernel is going to be a very complex piece of code (ignoring microkernels) because what it does is complex. But that is all the more reason to keep the code as straightforward as possible. (There are still going to be times where code is not straightforward due to inherent complexity of the problem, or performance considerations, or portability, ...)
>In quite a few cases non-trivial code doubles as filter for less skilled devs
Right, until the less skilled dev it's you, months later after you moved on to other stuff, and have to get back and fix some clever shit you wrote but don't understand anymore.
Unless you're doing numeric or performance critical work, code should be optimized for readability and maintainability.
If this example is too "clever" for someone, even sight unseen, they aren't (yet?) cut out to be a kernel hacker. I don't disagree with your general principle, but the linked example is idiomatic and understandable C for someone with a decent knowledge of the language, which is (I'd imagine/hope) the standard expected of contributors to Linux.
Actually I believe this particular example is basic and pretty understandable C.
I was talking about the more broad idea of knowingly writing clever code to raise the entry barrier for new devs. Or just writing clever code for whatever the reason. It's almost guaranteed to backfire, to new devs who will have to maintain it or to yourself, when you will have to read it in a less smart moment.
Projects should be accessible to new developers regardless of their complexity level. Even operating systems. Otherwise they will simply stagnate and die.
Also, "less skilled devs" are just people that are still learning. We've all been there.
I am pretty sure it hurts you in the short run too. After all, the microcode probably does a register rename or the like with a normal swap, but has to actually burn cycles on using aritmetic for the xor swap.
On modern CPU architectures, the XOR technique can be slower than using a temporary variable to do swapping. One reason is that modern CPUs strive to execute instructions in parallel via instruction pipelines. In the XOR technique, the inputs to each operation depend on the results of the previous operation, so they must be executed in strictly sequential order, negating any benefits of instruction-level parallelism.[3]
I've been told many times that it's better to eliminate edge cases. I still don't really believe it as a universal law.
When explaining the algorithm "remove an element from a linked list" to someone else, I would say "starting at the head, go along the list until you find the element; then delete the element". When explaining the algorithm "delete an element from a linked list", I would say "if you're at the head, update the head to be the next element; otherwise update the `next` property of the previous element to be the `next` property of the current element". It's so naturally a two-case problem that I'd be really surprised if anyone came up with the one-case answer first. Therefore, the two-case answer is the more readable to someone who has not seen the code before, because it corresponds to their intuition about how the algorithm should work.
As a bonus, it's clear to me that the naive algorithm is correct, but I have to do mental work to convince myself that the one-liner algorithm is correct. (I'm saying nothing about the code; only the algorithms.)
I agree much more with the reduced complexity of the later example (initialising the edges of a square), and I actually think it's worth double-counting the corners in this instance because the code is so much cleaner. (EDIT: Although I suppose the easy fix doesn't detract from the ease-of-reading, so actually it's avoidable.) In that instance, there's doubt about which is the natural algorithm to pick: one could conceivably come up with "initialise the top and bottom, then initialise the left and right", or "initialise the zeroth element of each side, then the first of each side, then…" as one's first attempt at solving the problem. Therefore I like this particular simplification.
> I still don't really believe it as a universal law.
If you were doing kernel development, you would. If you were writing enterprise CRUD applications, you wouldn't even think about it, and if you were developing hight throughput middleware, you'd switch that law on and off depending on where you are on the code.
I think "competitive" (i.e. solving algorithmic challenges for fun) coding really gives you some insight into how to write code that's short and to the point. The user with the most reputation on LeetCode, for example, consistently posts solutions that are surprisingly short, efficient, and readable.
Stefan Pochmann is also the inventor of two different methods for blindfolded Rubik's Cube solving. Classic Pochmann is a quite elegant solution as it effectively deals with one piece at a time, where previous methods generally separated orientation and permutation into separate steps, and deal with more pieces at once. M2 is 'tasty' in a different way - there are many more edge cases to handle but it replaces the 14-move swap sequence in Classic Pochmann with a single move. Perhaps I'm stretching a bit but it seems like an example of the same kind of thinking.
Side note - blindfold Rubik's Cube is way easier than you think. If you're a programmer and can already solve one sighted, I'd imagine you could learn Classic Pochmann in a week.
Well, I went over there, looked at the list of recently-active topics, and contributed exactly one boring solution to one of them. Now to never post there again.
Both versions suck. If "entry" is not found in the list, the code will run off the end of the list, either de-referencing zero and faulting or going off into junk, depending on how the list ends.
Writing low-level list manipulation more than once sucks. It leads to bugs. Such manipulation should be encapsulated. That's why we have containers in modern languages. The Linux kernel is still C, not C++, which leads to too much of this sort of thing.
I think practicing C programmers are using the list implementations that were given to us two decades ago. Or any of the newer alternatives. And if they aren't, it's not because of the language.
The big problem: both Linus's and above versions don't handle the case if entry wasn't found, for example, if entry was null. This is the fundamental issue with trying make code overly compact: sometime you lose the sight of important edge cases. Segfaults are not tasty. I generally prefer to write code that reflects my thought process and avoid unnecessarily try making it compact. As Knuth had said "Programs are meant to be read by humans and only incidentally for computers to execute”. Uglier versions allows to explicitly documents edge cases. This enables future maintainer to make sure these cases are covered when s/he makes code changes. Obviously taking this to another extreme would ruin this. The better taste lies somewhere between the compact Linus's version and some zeolite's too verbose version.
Small problem: Another thing to think about is extra pointer redirection required in Linus's code. This is fine for most cases but if I was dealing with very large list over and over then that's unnecessary perf hit.
The 'entry wasn't found' case is an entirely different issue than what Linus is showcasing. It may or may not be relevant for the particular function, depending on its contract and documentation.
I would argue for the last example it is better to write split the loop into four. I believe the intention is even clearer (because you are doing four different things), and that it is also faster even when optimizations are off due to better cache behavior. It may also make a smart but not "sufficiently smart" compiler to transform two of the loops into simple memset.
The author doesn't mention that the grid being initalized is square, and simply describes it as grid[rows][cols]. However, all his solutions are only correct for a square grid.
One solution for arbitrary dimensions could be
for (i = 0; i < rows; ++i) {
grid[i][0] = 0;
grid[i][cols - 1] = 0;
}
for (i = 0; i < cols; ++i) {
grid[0][i] = 0;
grid[rows - 1][i] = 0;
}
You're updating the corners twice. Not really a problem with a simple assignment, but as no_protocol pointed out elsewhere [0], it could be if you ever wanted to change that to, say, an increment.
You're right, my version is unoptimized because I was trying to keep the code neat as in the article. I think that optimizing the code for hypothetical future reuse is a bit premature. You could make a performance argument, but this optimization is going to prevent just 2 memory accesses, which aren't going to matter much compared to all the rest. If I was chasing performance I would start by memset'ing the top and bottom edges since they're contiguous in memory.
The code in the examples is not valid in any historical version of C. The use of the -> operator with an implicit int as the left argument ("entry" in the examples) was only valid from 1975 in Unix C (but not in GCOS C) until K&R C in 1978. The use of C++ style comments ("//") is only valid in standard C since 1999.
There's no point in arguing over pseudocode as if it's C.
The root of the problem is that "the thing that points to an entity" is not a consistent concept in this kind list. Sometimes it's "head", sometimes it's an entity's ->next. I wonder what Linus would think of implementing the linked list with a dummy head node, having no value and pointing to the first entity. Personally, I think that would be tasteful. It allows for simple loops like the "good taste" one, but you don't have to think so hard about how to implement a simple operation like remove. You don't need the added indirection.
Depends on where you store it. If you're just passing around node pointers, then you could create the dummy node on the stack only when you need it and it's the same indirection cost as the "indirect" pointer. If you've got a "list" struct that you're passing around (pretty unlikely in C), you could embed the dummy node directly.
The example there about edges on an array is something I've had to directly deal with myself when I implemented a multidimensional image-processing function for GNU Octave. The problem is to find connected components in a binary image, where voxels are either 0 or 1. You want to find all the islands of ones, and you want to be flexible if diagonals count as being connected or not.
The problem, of course, is that along the edges you don't want to check for neighbours outside of the image boundary. I found no good way to do this for an n-dimensional image, after a few attempts of writing very complicated code. In the end, I ended up padding the whole image with a boundary of zeros, iterating over the padded image with an "if(current_voxel)" conditional that skipped checking for lit neighbours around the boundary, and when checking for lit neighbours at the original image's boundaries would give no neighbours at the padded zero boundaries.
The code was cleaner, but I incurred a big realloc, because N-dimensional images in Octave are stored as contiguous Fortran-order (column-major) arrays. I'm still looking for a better solution to this problem.
I think there are three generally accepted ways to do this:
1) Pad with zeros until you fill your extent
2) Pad with an arbitrary constant of some kind
3) Pretend that spilling over one edge loops back to the opposite edge, as if the image was just a view over a repeating signal in that dimension.
The first two are naive and work well enough for simple tasks. The third actually has some basis to it, although it does seem odd. The third option is actually how the image is treated when you transform the image using a 2D Fourier transform. Instead of cutting off the "signal" and padding with zeros, it assumes that the signal is continuous and repeating (i.e. it is a 2D or N-dimensional Fourier series).
I know MATLAB uses this as the default for some (irritatingly not _all_) of it's operations, especially those concerned with Fourier transforms. I can't speak to Octave, but I believe they try to aim for bug compatibility with MATLAB where possible. One nice property of this kind of behaviour is that it avoids introducing some artefacts in the image when performing some sort of kernel filter or convolution.
Note that the interesting bit here is that Python + Numpy actually makes this whole debacle a bit easier to deal with. You can implement solution 3) easier than 1) or 2) with Python, since you can use negative indices in any iterable. So for an image `I`, you can call `I[xdim, ydim, -1, wdim]` for any N-dimensional image and the wrapping works well. Of course you then have to ensure you don't go past the "extent" of your N-dimensional space, but that's simple enough to enforce with 0 and `I.shape`. A lot of people complain that negative indices make no sense and are an annoying language flaw, but this is one scenario where I'm really glad they're available. Numpy views would also probably alleviate your realloc problem, since you can use views to simulate extents within larger matrices, without requiring copying / separate allocation.
Also, it's really slow and wasteful to be doing bounds-checking for each voxel of an image that is almost completely not a boundary, whereas you can't avoid checking if each voxel is lit. :-)
One anti-pattern I've seen a few times, across multiple codebase and companies, is the
for i in 1...cases:
switch(i)
To me, his first example fits this perfectly, except he is using ifs instead of a switch. Basically, if you are generating a big, trivial sequence and then filtering it down afterwards, think harder and probably there is a way to generate the sequence you are actually after directly.
> One anti-pattern I've seen a few times, across multiple codebase and companies, is the for i in 1...cases: switch(i)
Also known as the "for-case" loop. Version 2 is a prime example of this, and what not to do. It processes case 1, then case 2, then case 3, then case 4. The author rewrites it as one loop of 64, but four loops of 64 each would also be acceptable.
> To me, his first example fits this perfectly, except he is using ifs instead of a switch. Basically, if you are generating a big, trivial sequence and then filtering it down afterwards, think harder and probably there is a way to generate the sequence you are actually after directly.
Now you're talking about a different problem. The conditionals in the first version do not iterate through like code doing "switch(i)". I agree that it's better to directly generate than to filter, but that's a totally separate anti-pattern.
Maybe I'm wrong about this but I noticed that the code didn't call free() to the element that has breen removed. That would cause a memory leak. Am I missing something here?
The caller still holds a pointer to the element and can free it. I would argue that delegating the responsibility of freeing the element to the caller is more performant, since that allows the code to reuse that list element and insert it into a different (compatible) list.
That's the kind of performance/ease-of-use trade-off that sounds reasonable in an open source project with strict code reviews (but in very few other places)
All due respect to Linus, but the second example is much less readable. Proof of that: the code was reduced in half, but the amount of comments was doubled.
I think concepts like "elegance" and "good taste" of code should exist, but they are obviously subjective. My choice of good taste always considers readability first.
I'm pretty sure that the comments are for people who Linus doesn't want contributing to the kernel. This code would likely have no comments at all if checked into the Linux kernel because it would be obvious to everyone allowed to do commits.
I know Sufficiently Smart Compilers are a running joke, and I know a lot of people think the idea is a bad one, but come on...this should be the job of a compiler. The first example is way more understandable. Yes, it branches, and yes it is more code and less efficient. But a compiler should be able to derive the more efficient version from the more understandable code. And it's a shame that it doesn't.
For the curious like me who wanted to see the assembly for the Linus examples and compare https://godbolt.org/g/sqdBrf. Most importantly they have the exact same number of branches and their loops are exactly the same size 4 instructions on all opt levels greater than 02. The setup code for the first one is much longer.
Here is also a somewhat representative example of various grid initialization pay attention to version 3 where the compiler unrolls the loop in O3 its likely the fastest version. https://godbolt.org/g/mMBhuW
Often I find myself solving problems in a single performant SQL with lateral/cross joins before hitting the business logic code in order to simplify the logic part into a single loop with no conditionals/edge cases.
Turns out this is not the best practice because you will have to explain all about your clever use of olap functions and lateral joins to someone less knowledgeable who has to append to your code.
I would argue that having developers that don't understand and won't bother to learn SQL working on application dependent on SQL-based DBs is the not-best-practice there, not proper and efficient use of SQL by developers who do know what they are doing.
You are right, of course, but they have "working knowledge" of sql which is adequate for most reports and operations.
Just not the "high level" SQL someone armed with the knowledge of functional programming could conjure when faced with the alternative of writing lots of nested conditional statements and loops in an imperative language because it would bore him to pieces.
You can think of your grid array as a contiguous piece of memory. I would do:
bzero(grid, sizeof(int) * COLS);
bzero(grid + COLS * (ROWS - 1), sizeof(int) * COLS);
for (int i=1; i < ROWS-1; i++) {
*(grid + (i * COLS)) = 0; /* set left col to 0 */
*(grid + (i * COLS) + COLS - 1) = 0; /* set right col to 0 */
}
> To the best of my ability to discern, the crux of the “good taste” requirement is the elimination of edge cases, which tend to reveal themselves as conditional statements. The fewer conditions you test for, the better your code “tastes”.
I'm an anonymous internet poster, I don't have a suggestion for who you should idolize. But picking Linus is a red flag. His man-child entitled attitude, condescension, arrogance, etc, make him a parody of a toxic developer that ruins teams from the inside out. Normalizing and uplifting that behavior makes us all worse off.
Does it follow that attempting to write code that is closer to functional style also improves the code's "tastefulness?" I'm under the impression that better functional code contains fewer branches.
I thought that too. I found it hard to believe that anyone would write either of the first two versions without having thought of the 3rd - or, you know, just having 2 or 4 separate for loops. Maybe there was something about the problem's context that the author left out of the post though?
Both are correct, one is considered better based on a subjective assessment. People who disagree with that the version a person selects is objectively better have no taste.
Speaking of coding niceties, when I started branching out from bash into a 'real' language, Python, I couldn't find a switch statement. A colleague of mine said that Python didn't have one, and that switch statements were a 'code smell'. I didn't really understand that, and asked about those times that you genuinely could use a switch statement, and the answer was "just use a long if-else function". I can't remember his justifaction for it, so clearly it didn't stick
I still don't see the real pragmatic difference between a switch statement and a long if-else function - anyone feel like ELI5'ing it for me? Switch statements just seem more concise and readable to me...
If your switch is more than a few lines, the Pythonic way is to use a dictionary, rather than many if-else statements. A dict is roughly as concise as a switch, and it's also much easier to work with and extend.
Following the principle of "There should be one--and preferably only one--obvious way to do it," switches in Python are redundant. If you want branching logic, then use branching statements (if-else). If you want mapping, use a dict. The hiccup is that many programmers new to Python don't actually know what a dictionary is--or at least haven't used one before--so it's far from "obvious" to them to use it.
Switch statements have fall-through behavior that you need `break` to avoid (in most languages); sometimes this is what you want, but only rarely.
One trick I've seen people do in Python is to use a dict; define lambdas for each case, and then key the dict on your value that you would switch on, and invoke the lambda (or use existing functions).
I am doing a poor job of explaining _why_ one might want to do that, but one advantage is that you can verify that the right callbacks were called in tests, and also verify that each callback behaves right when invoked, since they are just references to methods or functions. I'm not sure if doing this would get marks for cleverness and testability, or would get one criticized for excessive cleverness. As the reviewer of the code when a coworker wrote it, I recall liking it, though.
There are multiple alternatives to switch (or if) statements and I would generally agree switch statements are mostly a code smell. As one posters described, using the fall-through behavior is more what justifies it and the real difference. I know you asked for ELI5, but let me give you some options to think about how you code on a broader level and how to eliminate both if and switch or at least improve them.
If you think of a switch statement as a pattern matching construct, then you will realize there are many, many alternatives in any programming language, including Python. For instance, the dict method works, as can anything that operates a collection-oriented data structure. For example, you could just as easily loop on a list and do this too, but for most lists this would require a worst case of O(n) iterations where n is the size of the list to match, thus a dict is better. A dict would not work if you want fall-through since you would only be matching on a single key usually, unless once again you do lookups of multiple keys (dict still wins). But a list would support this fall-through behavior with minimum effort and a small list would preform alright.
If your usage is lets say more sophisticated than a key lookup, there may be alternative data structures that you can use to achieve similar results (b-tree, red-black tree, skip list, etc.) though that is of course getting further from the usual behaviors of switch statements.
A functional way to go about it would be to reduce or fold on some collection. If you think about the items that don't match, they wouldn't add anything into the final reduction much in the way map/reduce works traditionally. Many times this would just consolidate the entirety of the function you are calling the switch with the result it is producing. Generally, I'd encourage thinking of writing code that operates on data and thus tends to make good reduce of things like reduce, map, filter, etc. as this often simplifies things and in some cases can actually lead to nice performance if done right. It also tends to force you to write things atomically, with less side-effects, and as pure functions. One of the problems people have with if-statements is they end up burying unrelated concerns or bug-inducing side-effects in each if/else or each branch. This code smell is easy to detect by simply pretending you are looking at new functions for each piece of code under an if/else or case and seeing if they are returning the same "type" in general sense of thing, how much there is in common between each piece, and if they are doing 1 or multiple things each. Most of the time, you are really doing the same thing with one slight difference like an input parameter, and you never really needed an if or at the very least, it could be handled differently. If you are doing more than one thing per if, it often means you are doing too much. Furthermore, you should test that if you were to repeatedly pass the same data to each, would you get the same result?
Another way of handling this is to use multi-methods. Note that in truth, it's the same as above because all you are doing depending on your implementation is pattern-matching. It just depends if your behavior is match one or match multiple (fall-through-like). Python can use attributes to do multi-methods among a few other ways. It's been awhile and mostly I'd avoid using them for performance reasons, but it's another option when thinking of more advanced ways to get rid of switch or if constructs.
In general, it's worth noting that in many languages such as Python, though ifs/switch might be ugly, they can often perform pretty well. It is also worth knowing that if/switch are not very good for functional styles sometimes. Making lists or dicts or other constructs is not always free, or slower/faster so it can sometimes just be a balance between performance, clarity, and composition.
Hopefully that gets you thinking and is not too confusing. A bit exhausted so I'm not thinking my best, though I think I am sending you down a track to explore to help you grow.
Thanks for the write-up. I've had to re-read a couple of bits, but that's how you learn :)
My switch use to date has almost entirely been about parsing commandline args - one of the two time I didn't do that was when my colleague talked about the code smell.
It's been interesting watching how new areas in programming just unfold potential in front of you as you learn. My bash scripts used to be relatively simple, serial things, then a mentor forced me to start using functions - and that was eye-opening. Things made more sense, and not least because I had to keep less 'state' in my head. You mention map and similar, and this is something I haven't really touched yet, but it sounds like it'll help some of the things I do (mostly ops scripts).
It sounds to me like you also need to start focusing on atomic functions and abstractions more in general. Your functions should do one things as I mentioned.
Regarding "map," "reduce" is probably the one you want to learn first because you can express many functional constructs like "map" in terms of "reduce."
As a general word, parsing command lines almost always tends to be ugly. My general advice here would be to use the built-in stuff or at least a well-used library as much as possible. If you are finding that you are doing a lot of work yourself or using reg-exs that you made, that's often a side that you are doing something wrong.
Anyway, lots more but I don't want to overwhelm. Good luck!
I think the main lesson that's there, is that in edge cases, it is sometimes helpful to work with pointers which point to the structures you're actually working with, instead of considering the structures themselves. This especially seems to work for getting rid of null checks.
This takes some getting used to, but it allows you to write more efficient code. I would do this in kernel development (smart people, high demands on performance), but I would not recommend to write code like this is enterprise software.
When you zoom out a bit, and describe the task with natural language, you can also see that this might be a good idea: "Find the node that is equal to entry, then, if the previous node exists, set the 'next' pointer of the previous node to the 'next' pointer of the current node." sounds a lot more tedious than "Find the pointer that points to entry, and set it to the 'next' pointer of entry.".
This also works for more complicated tasks:
// removes all instances from the linked list and return the number of entries removed
int removeentries(valuetoremove, list)
{
removedentries = 0; // how many entries we've removed
prevpt = NULL; // pointer to previous
entrypt = list.head; // get pointer to first node
// walk the list (be careful, head can be a nullpointer)
while (entrypt) {
if (*entrypt == valuetoremove)
if (prevpt) {
prevpt->next = entrypt->next;
removedentries++;
}
prevpt = entrypt; // save current node as prev for next node
entrypt = entrypt->next; // move to next node
}
return removedentries;
}
can be re-written to:
int removeentries(valuetoremove)
{
removedentries = 0; // how many entries we've removed
indirect = &head; // points to the current node
// walk the list
while (indirect) {
// remove current entry from list if its value equals valuetoremove
if (indirect->value == valuetoremove) {
*indirect = *indirect->nextpt;
removedentries++;
}
indirect = indirect->nextpt;
}
return removedentries;
}
Thanks for the link. I found the talk very insightful.
I would imagine Linus to disagree with Sandi's approach, though. She is never eliminating the if (as in: the conditional jump), just moving it from plain sight into the magic of dynamic method dispatch.
"A lot of conditionals arise from fuzzy thinking about the problem. In servo-control theory, a lot of people think that the algorithm for the servo ought to be different when the distance is great than when it is close. Far away, you’re in slew mode; closer to the target you’re in decelerate mode; very close you’re in hunt mode. You have to test how far you are to know which algorithm to apply."
"I’ve worked out a non-linear servo-control algorithm that will handle full range. This approach eliminates the glitches at the transitioning points between one mode and the other. It eliminates the logic necessary to decide which algorithm to use. It eliminates your having to empirically determine the transition points. And of course, you have a much simpler program with one algorithm instead of three."
"Instead of trying to get rid of conditionals, you’re best to question the underlying theory that led to the conditionals."
That's part of a chapter of the book called Minimizing Control Structures. Forth guys are crazy about taste, and if I've learned anything from reading their stuff, it's that chasing tasteful programming to its end gets very hard.
OP is right on the money. The hard thing is that it is a creative process, and takes a real understanding of the problem you're solving to do it. Worst of all, aside from the feeling of solving a puzzle well, the benefits only begin appearing much later. I'm glad the kernel team takes it seriously.