10 ms·

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 a

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. (Earlier version posted on reddit: https://www.reddit.com/r/programming/comments/59cq8r/applying_the_linus_tarvolds_good_taste_coding/d97pcrl https://www.reddit.com/r/programming/comments/59cq8r/applyin... )

dwenzek 10y ago
> 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.
- mobiuscog 10y ago
  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.
crazy2be 10y ago
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. remove_list_entry(node** head, node* entry) { [...] } 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. Double pointers for life!
- deleted 10y ago
  [deleted]
- akkartik 10y ago
  I have nothing against double pointers: https://news.ycombinator.com/item?id=12798604 https://news.ycombinator.com/item?id=12798604 (please don't consider the flamey bits there to be directed at you). That last bit, though, I wouldn't recommend it as a slogan :) How about something like "adapt to the situation for life"?
tempestn 10y ago
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).
- akkartik 10y ago
  Yes, I'd be ok with a `while` that checked for the end of the list: https://news.ycombinator.com/item?id=12798192 https://news.ycombinator.com/item?id=12798192 I really try not to be a nazi about this sort of thing. Very few things matter enough to get into a HN conversation about "taste".
  - tempestn 10y ago
    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.
marcell 10y ago
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.
- akkartik 10y ago
  See my comments regarding blindly removing "duplication" at https://news.ycombinator.com/item?id=12798796 https://news.ycombinator.com/item?id=12798796 (point 4)
- alkoumpa 10y ago
  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.
Dylan16807 10y ago
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.
- akkartik 10y ago
  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. 2. My point wasn't about the `for` loop: https://news.ycombinator.com/item?id=12798192 https://news.ycombinator.com/item?id=12798192 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-abstraction 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.)
rukuu001 10y ago
Screw 'taste', go for obvious. If you're at BigCo and your codes going to be maintained by disinterested drones/ random contractors/etc, obvious code is better. And lack of checking on entry pissed me off too.
- Sir_Substance 10y ago
  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.
  - deleted 10y ago
    [deleted]
- acdha 10y ago
  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
- blowski 10y ago
  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.
- agentgt 10y ago
  I say screw 'taste' and 'obvious' and instead go for it has high coverage unit tests and lots of them. You can always go back and make it look pretty safely with good tests. I just love code snobs that think their code is so good they don't need tests.
coldtea 10y ago
>What is "tasteful" about hiding the fact that one of the cases is far simpler than the other? The fact that this is an implementation detail and not a universally true fact about the two cases?
reacweb 10y ago
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.
adrianratnapala 10y ago
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.
- akkartik 10y ago
  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.
rndgermandude 10y ago
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.
- jakobegger 10y ago
  I can't see why the code from akkartik would segfault when entry is NULL? What am I missing?
  - Nursie 10y ago
    If entry and head are null, segfault on line 4. If entry is null and head is valid segfault on line 10. --edit-- As pointed out by my esteemed colleagues below, I didn't read the loop conditional properly. Only the first fault applies
    - A1kmm 10y ago
      > 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.
    - jakobegger 10y ago
      How can you reach line 10 when entry is NULL? (prev->next==entry) can only be true at the end of the list, but the for-condition already checks that.
deleted 10y ago
[deleted]
zAy0LfpBZLC8mAC 10y ago
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. How about this: subtract(n){ if(n==0){ return m; } r=m; for(x=0;x<n;x++){ r--; } return r; } 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.
- akkartik 10y ago
  ".. 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]. https://github.com/akkartik/mu/blob/a90faae990/edit/003-shortcuts.mu#L87 https://github.com/akkartik/mu/blob/a90faae990/edit/003-shor... [2] 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.) [1] https://github.com/akkartik/mu https://github.com/akkartik/mu [2] Hard to read, I admit. There's a colorized version at http://akkartik.github.io/mu/html/edit/003-shortcuts.mu.html http://akkartik.github.io/mu/html/edit/003-shortcuts.mu.html, but I only host the most recent version there. [3] https://github.com/akkartik/mu/commit/ea5e7fd4cb https://github.com/akkartik/mu/commit/ea5e7fd4cb from Apr 2016. The previous version was from Sep 2015. [4] https://en.wikipedia.org/wiki/Shuhari https://en.wikipedia.org/wiki/Shuhari
deleted 10y ago
[deleted]
illys 10y ago
Independently of style, taste, BigCo, edge cases, assumptions and other considerations, I still find a major regression in your version: Instead of one variable allocation and one test in the loop, your version has one allocation and TWO tests. Adding weight in loops has a major performance impact.
- akkartik 10y ago
  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. [1] My guru in this regard is DJ Bernstein: https://cr.yp.to/qmail/qmailsec-20071101.pdf https://cr.yp.to/qmail/qmailsec-20071101.pdf
colanderman 10y ago
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.)
- cfallin 10y ago
  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.
  - colanderman 10y ago
    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.
    - 10y ago
avip 10y ago
I'd add something like assert (head && entry) up there.
- eatbitseveryday 10y ago
  A NULL head is not an error (= empty list) and 'assert' would be better as a BUG_ON or panic if it is technically an error.
  - deleted 10y ago
    [deleted]
  - avip 10y ago
    It is an error though if your code SEGFAULT on NULL head (and this one does). I wouldn't care, but if you claim to be defensive, go full monty.
    - eatbitseveryday 10y ago
      > It is an error though if your code SEGFAULT on NULL head (and this one does). There is no "SEGFAULT" in kernel code. SIGSEGV is a signal, which is only used at user-level. NULL dereference in the kernel results in an "oops". I believe it is also assumed in their code that "entry" is not going to be NULL, meaning "if (head == entry)" will never succeed if head is NULL.
      - avip 10y ago
        The code crashes if head is NULL, regardless of entry.
RandomOpinion 10y ago
Bog-standard, humdrum enterprise programming != kernel programming 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. [0] See https://en.wikipedia.org/wiki/Bubble_(computing) https://en.wikipedia.org/wiki/Bubble_(computing) and https://software.intel.com/en-us/articles/avoiding-the-cost-of-branch-misprediction https://software.intel.com/en-us/articles/avoiding-the-cost-.... And, yes, instruction reordering[1] might be able to fill the slots but you don't get to be where Linus is by relying on that. Plus, Linux runs on processors that don't have OOO, like Intel's Atom and microcontrollers. [1] https://en.wikipedia.org/wiki/Out-of-order_execution https://en.wikipedia.org/wiki/Out-of-order_execution
- ant6n 10y ago
  But now you're making argument about performance, not "good taste". Often, performant code is not very tasty.
  - RandomOpinion 10y ago
    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.
    - ant6n 10y ago
sriku 10y ago
Btw the second "tasty" solution in the article may not taste well to cache lines. May just be better to do three separate loops.
firethief 10y ago
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.
- zwieback 10y ago
  That was my first thought, my basic algorithms book specifically mentions sentinel as a way to eliminate the head boundary condition. Linus basic point stands although his example isn't very good.

dwenzek 10y ago

> 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.

mobiuscog 10y ago
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.

crazy2be 10y ago

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. remove_list_entry(node** head, node* entry) { [...] } 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. Double pointers for life!

deleted 10y ago
[deleted]
akkartik 10y ago
I have nothing against double pointers: https://news.ycombinator.com/item?id=12798604 https://news.ycombinator.com/item?id=12798604 (please don't consider the flamey bits there to be directed at you). That last bit, though, I wouldn't recommend it as a slogan :) How about something like "adapt to the situation for life"?

tempestn 10y ago

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).

akkartik 10y ago
Yes, I'd be ok with a `while` that checked for the end of the list: https://news.ycombinator.com/item?id=12798192 https://news.ycombinator.com/item?id=12798192 I really try not to be a nazi about this sort of thing. Very few things matter enough to get into a HN conversation about "taste".
- tempestn 10y ago
  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.

marcell 10y ago

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.

akkartik 10y ago
See my comments regarding blindly removing "duplication" at https://news.ycombinator.com/item?id=12798796 https://news.ycombinator.com/item?id=12798796 (point 4)
alkoumpa 10y ago
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.

Dylan16807 10y ago

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.

akkartik 10y ago
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. 2. My point wasn't about the `for` loop: https://news.ycombinator.com/item?id=12798192 https://news.ycombinator.com/item?id=12798192 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-abstraction 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.)

rukuu001 10y ago

Screw 'taste', go for obvious. If you're at BigCo and your codes going to be maintained by disinterested drones/ random contractors/etc, obvious code is better. And lack of checking on entry pissed me off too.

Sir_Substance 10y ago
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.
- deleted 10y ago
  [deleted]
acdha 10y ago
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
blowski 10y ago
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.
agentgt 10y ago
I say screw 'taste' and 'obvious' and instead go for it has high coverage unit tests and lots of them. You can always go back and make it look pretty safely with good tests. I just love code snobs that think their code is so good they don't need tests.

coldtea 10y ago

>What is "tasteful" about hiding the fact that one of the cases is far simpler than the other? The fact that this is an implementation detail and not a universally true fact about the two cases?

reacweb 10y ago

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.

adrianratnapala 10y ago

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.

akkartik 10y ago
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.

rndgermandude 10y ago

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.

jakobegger 10y ago
I can't see why the code from akkartik would segfault when entry is NULL? What am I missing?
- Nursie 10y ago
  If entry and head are null, segfault on line 4. If entry is null and head is valid segfault on line 10. --edit-- As pointed out by my esteemed colleagues below, I didn't read the loop conditional properly. Only the first fault applies
  - A1kmm 10y ago
    > 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.
  - jakobegger 10y ago
    How can you reach line 10 when entry is NULL? (prev->next==entry) can only be true at the end of the list, but the for-condition already checks that.

deleted 10y ago

[deleted]

zAy0LfpBZLC8mAC 10y ago

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. How about this: subtract(n){ if(n==0){ return m; } r=m; for(x=0;x<n;x++){ r--; } return r; } 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.

akkartik 10y ago
".. 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]. https://github.com/akkartik/mu/blob/a90faae990/edit/003-shortcuts.mu#L87 https://github.com/akkartik/mu/blob/a90faae990/edit/003-shor... [2] 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.) [1] https://github.com/akkartik/mu https://github.com/akkartik/mu [2] Hard to read, I admit. There's a colorized version at http://akkartik.github.io/mu/html/edit/003-shortcuts.mu.html http://akkartik.github.io/mu/html/edit/003-shortcuts.mu.html, but I only host the most recent version there. [3] https://github.com/akkartik/mu/commit/ea5e7fd4cb https://github.com/akkartik/mu/commit/ea5e7fd4cb from Apr 2016. The previous version was from Sep 2015. [4] https://en.wikipedia.org/wiki/Shuhari https://en.wikipedia.org/wiki/Shuhari

deleted 10y ago

[deleted]

illys 10y ago

Independently of style, taste, BigCo, edge cases, assumptions and other considerations, I still find a major regression in your version: Instead of one variable allocation and one test in the loop, your version has one allocation and TWO tests. Adding weight in loops has a major performance impact.

akkartik 10y ago
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. [1] My guru in this regard is DJ Bernstein: https://cr.yp.to/qmail/qmailsec-20071101.pdf https://cr.yp.to/qmail/qmailsec-20071101.pdf

colanderman 10y ago

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.)

cfallin 10y ago
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.
- colanderman 10y ago
  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.
  - 10y ago

avip 10y ago

I'd add something like assert (head && entry) up there.

eatbitseveryday 10y ago
A NULL head is not an error (= empty list) and 'assert' would be better as a BUG_ON or panic if it is technically an error.
- deleted 10y ago
  [deleted]
- avip 10y ago
  It is an error though if your code SEGFAULT on NULL head (and this one does). I wouldn't care, but if you claim to be defensive, go full monty.
  - eatbitseveryday 10y ago
    > It is an error though if your code SEGFAULT on NULL head (and this one does). There is no "SEGFAULT" in kernel code. SIGSEGV is a signal, which is only used at user-level. NULL dereference in the kernel results in an "oops". I believe it is also assumed in their code that "entry" is not going to be NULL, meaning "if (head == entry)" will never succeed if head is NULL.
    - avip 10y ago
      The code crashes if head is NULL, regardless of entry.

RandomOpinion 10y ago

Bog-standard, humdrum enterprise programming != kernel programming 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. [0] See https://en.wikipedia.org/wiki/Bubble_(computing) https://en.wikipedia.org/wiki/Bubble_(computing) and https://software.intel.com/en-us/articles/avoiding-the-cost-of-branch-misprediction https://software.intel.com/en-us/articles/avoiding-the-cost-.... And, yes, instruction reordering[1] might be able to fill the slots but you don't get to be where Linus is by relying on that. Plus, Linux runs on processors that don't have OOO, like Intel's Atom and microcontrollers. [1] https://en.wikipedia.org/wiki/Out-of-order_execution https://en.wikipedia.org/wiki/Out-of-order_execution

ant6n 10y ago
But now you're making argument about performance, not "good taste". Often, performant code is not very tasty.
- RandomOpinion 10y ago
  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.
  - ant6n 10y ago

sriku 10y ago

Btw the second "tasty" solution in the article may not taste well to cache lines. May just be better to do three separate loops.

firethief 10y ago

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.

zwieback 10y ago
That was my first thought, my basic algorithms book specifically mentions sentinel as a way to eliminate the head boundary condition. Linus basic point stands although his example isn't very good.