Linus Torvalds' good taste argument for linked lists, explained • Hacker News Board

Re: Linus Torvalds' good taste argument for linked lists, explained

#141

Post by h0l0cube » Mon, Dec 07, 2020, 1:07 AM UTC

macspoofing wrote: post #7

I understand the general point (and value) of reframing the problem or the solution in a way that removes special cases ... but in this case I would actually prefer the first solution over the second. The second solutions reminds me of the old-school perl culture, and JavaScript culture, where 'cleverness' (which always manifests itself as terseness as if lines of code were expensive), takes precedence over maintaina…

It's not cleverness for cleverness sake, it reduces complexity, and yet the code is still self explanatory. The extra level of indirection means one variable can be used to access what was previously stored in two. The only confounding part of it is that this didn't become the canonical way to manipulate a linked list over the naive implementation.

Re: Linus Torvalds' good taste argument for linked lists, explained

#142

Post by javajosh » Mon, Dec 07, 2020, 1:09 AM UTC

defaultcompany wrote: post #133

Semi-relevant side note: Within some constraints its possible to remove an element in a singly linked list without walking the list. The purpose of walking the list is not to find the element (which you already have) but to find it's previous element so you can fix the "next" pointer on the previous element. What you can do instead is to copy the data from the next element onto the one to delete, making it a "copy" o…

Neat idea, but yeah like you say you break referential integrity pretty hard with this solution. And tbh I feel like everyone prefers tons of local links in their data, and since we have memory to spare with wasteful representations, we pick the convenient, link heavy one, a world in which this algorithm variant does not apply.

Re: Linus Torvalds' good taste argument for linked lists, explained

#143

Post by brundolf » Mon, Dec 07, 2020, 1:13 AM UTC

vips7L wrote: post #140

brundolf wrote: post #124

This certainly falls under Rich Hickey's definition of "simple", which is one virtue. But: > it is not immediately evident how the more elegant solution actually works another virtue is ease of comprehension, and the more elegant solution lacks that in my (and seemingly Linus') opinion. Maybe if you're used to working with pointers to pointers you might have an intuituon for them, but I at least had a difficult time…

Wouldn't you end up with a Box of Null? Wouldn't it be better to: struct Node { value: i32 next: Option > }

Yeah that's true, but the problem with your version is it loses the homogeny because an empty list can't simply be a Node, it has to be represented in some other way (as an Option or something), so we're back to square one. Maybe I was wrong and this can't be done perfectly even with union types.

Re: Linus Torvalds' good taste argument for linked lists, explained

#144

Post by sltkr » Mon, Dec 07, 2020, 1:13 AM UTC

andy_threos_io wrote: post #68

Pointless and bad article. I compiled the presented code out curiosity on arm gcc 8.2 on godbolt.org with -O3 op and the results are: (the original remove is even faster then the so called elegant or the elegant with inline) remove_cs101: ldr r2, [r0] cmp r2, r1 bne .L3 b .L9 .L6: mov r2, r3 .L3: ldr r3, [r2, #4] cmp r1, r3 bne .L6 ldr r3, [r1, #4] str r3, [r2, #4] bx lr .L9: ldr r3, [r2, #4] str r3, [r0] bx lr remov…

First, you haven't demonstrated at all that the "elegant" solution is slower. Between `remove_cs101` and `remove_elegant`, it looks like they are equivalent (in particular, the inner loop has the same number of instructions) except the former uses more instructions.

Second, I think you're missing the point by focusing on the code generated by the compiler. Clearly the two algorithms are equivalent, and a good compiler can generate equivalent code for them, up to an instruction more or less. The bigger concern here is about the source code: how can we express the algorithm in the most elegant (think: clear, concise, and correct) way? The exact generated bytecode is irrelevant, so long as the compiler is able to generate something reasonable, which is clearly the case here, as you've demonstrated.

Re: Linus Torvalds' good taste argument for linked lists, explained

#145

Post by landhar » Mon, Dec 07, 2020, 1:15 AM UTC

bfung wrote: post #96

To relate this topic back to Computer Science and Math, the linked list traversal problem can be related back to Proof by Induction -- There's a base case (a starting condition) and then the inductive steps: "...proves that if the statement holds for any given case n = k, then it must also hold for the next case n = k + 1" We can prove using proof by induction that Linus's implementation works because of the base cas…

I think this hits the nail in the head. Lots of comments here seem to dislike option 2 on the basis that it’s a “clever trick” and that those should be avoided for reasons of readability and maintainability. But this second approach would be the _right_ answer in a exam about algorithms, and that’s what Linus is really hinting at here.

Re: Linus Torvalds' good taste argument for linked lists, explained

#146

Post by valtism » Mon, Dec 07, 2020, 1:16 AM UTC

hyperpape wrote: post #105

nemetroid wrote: post #19

I'm not sure why the article removed comments from the code and replaced variable names like "indirect" with "p". Here are the two code samples verbatim from Linus's presentation: remove_list_entry(entry) { prev = NULL; walk = head; // Walk the list while (walk != entry) { prev = walk; walk = walk->next; } // Remove the entry by updating the // head or the previous entry if (!prev) head = entry->next; else prev->next…

Question for experienced C programmers (I'm not one). The comments for remove_list_entry strike me as fluff, only suitable for a didactic piece. Would you find the comments in the second version helpful, or should they also be removed? Edit: let me lay my cards on the table. If the comments really are necessary, it doesn’t seem elegant. I’m pro-comments, but that’s because not all code can be readable and elegant all…

The comments certainly don't detract from the code in my opinion. They may not be _helpful_ per se to an experienced developer, but there may be a chance that a more inexperienced developer will read this code in the future, and it could benefit them.

Re: Linus Torvalds' good taste argument for linked lists, explained

#147

Post by mehrdadn » Mon, Dec 07, 2020, 1:17 AM UTC

asdfasgasdgasdg wrote: post #113

762236 wrote: post #109

Earlier quoted context omitted.

What if entry doesn't exist in the list? You need a special case to handle that too.

Normally with an identity-based API like this, you can put it as a requirement that you must not remove items other than those which actually exist in the collection. Another example of an API that doesn't check for presence: c++ iterator-based removal. If you ask a C++ list to remove an iterator element outside its range, it may crash the program. See the exception safety section of this documentation: http://www.cp…

As the other person said, it's not really about complexity. Complexity isn't all that different here; personally I'd find something like the following to be simpler (I imagine others might disagree):

  remove_list_entry(entry)
  {
      for (p = &head; *p; p = &(*p)->next)
      {
          if (*p == entry)
          {
              *p = entry->next;
              break;
          }
      }
  }

However, what the choice does objectively impact is performance. Being able to assume the object exists allows you to avoid checking against NULL, which removes instructions in the loop. I'd guess they anticipate this code might be called from performance-critical code, and that might be why they coded it like this.

Re: Linus Torvalds' good taste argument for linked lists, explained

#148

Post by greenkey » Mon, Dec 07, 2020, 1:20 AM UTC

m463 wrote: post #114

brainwipe wrote: post #33

Earlier quoted context omitted.

Thank you, I found that much easier to read than the article posted.

Much clearer when read as Linus intended. Reminds me of the editor(s) who helped "fix" bukowski's poems

I’m not a fan of everything Bukowski wrote, but I wouldn’t try to censor him so that little Jimmy could read it, and I liked the movie Barfly.

Similarly, I’m not a fan of everything Linus wrote, but I wouldn’t enforce bad CS101 code on him so that little Jimmy could read it, and I like Linux.

Re: Linus Torvalds' good taste argument for linked lists, explained

#149

Post by identity0 » Mon, Dec 07, 2020, 1:22 AM UTC

eperdew wrote: post #122

identity0 wrote: post #112

Earlier quoted context omitted.

The top pattern is extremely common so comments are somewhat unnecessary since everyone would know what you're doing. In the second one, comments would be less necessary with a type annotation and perhaps a better name. Maybe "next_ptr" instead of "indirect"---all pointers are indirection, so that name is redundant. But the comments are necessary, to me at least.

All pointers are pointers too, so I don't see much of a difference between "indirect" and "next_ptr", other than the "next" part. In similar situations at my job, I've drawn a small ASCII diagram in the comments, and named the variable something like "splice_point", with a corresponding label in the diagram.

Well "next_ptr" is also a bad name, I agree, but I'm trying to name it something that indicates "this is a pointer to the 'next' pointer in the linked list".

Re: Linus Torvalds' good taste argument for linked lists, explained

#150

Post by petergeoghegan » Mon, Dec 07, 2020, 1:30 AM UTC

deanCommie wrote: post #44

macspoofing wrote: post #7

I understand the general point (and value) of reframing the problem or the solution in a way that removes special cases ... but in this case I would actually prefer the first solution over the second. The second solutions reminds me of the old-school perl culture, and JavaScript culture, where 'cleverness' (which always manifests itself as terseness as if lines of code were expensive), takes precedence over maintaina…

I started reading the article agreeing with you. Hearing Linus talk about "taste" made me expect something obscure and esoteric, with a marginal performance benefit, and a subjective/objective debate about whether the value of micro-optimizations at scale throughout the linux kernel adds up to meaningful benefits, and if they are traded-off with less readable code. Surprisingly, I ended up in a different spot. I actu…

I think that you're on to something here.

I write C full time, and have done so for many years. It didn't occur to me that the pointer to a pointer aspect was the source of any of the confusion until just now. Actually, I don't think that I consciously registered its presence when I read the code. There is only one interpretation of the code that makes any sense, and that's at least easy for an expert to see quickly.

I am sure that people that think that the terser variant is overly clever don't get it. To be fair, it's hard to generalize from this one example. But I think that I know exactly what Torvalds intended to draw attention to.