Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Linus Torvalds' good taste argument for linked lists, explained

github.com

Post reply on HN
Print view View original

121–130 of 339 posts

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

#121

Post by jcranmer »

smitty1e wrote: post #21

This seems like the classic argument of whether approaches like Duff's Device[1] are a good implementation idea. I would offer that there is no shame in doing something a bit more advanced, as long as there are test cases and documentation proportional to the advanced nature of the technique available. [1] https://en.m.wikipedia.org/wiki/Duff's_device

Duff's device is a bad idea in modern code, because it's effectively a sign to compilers saying "Hi, please don't optimize my code or this loop in any way." In general, microoptimization of code to produce particular assembly sequences is a bad idea, because the actual assembly the compiler generates is only loosely related to the actual code.

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

#122

Post by eperdew »

identity0 wrote: post #112
hyperpape wrote: post #105

Earlier quoted context omitted.

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

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

#123

Post by phkahler »

I have an odd structure that links objects into "boxes" where each object can be in more than one box and each box can contain multiple objects. I made a struct to link an object to a box via a pointer to both the object and the box. These links are each part of 2 lists, one from the object and one from the box. The main job is to find all the objects in a given box, which is done by following the list from the box. To delete an object involves following the list off the object and removing all the links - each of which is in a list from a box. Each link needs two next pointers since it's part of 2 lists. It also needs a PREV pointer for the list from the box for easy deletion. I originally had an empty link object within the box object to be the previous node, but then realized a better way was to have the PREV pointer point to the previous NEXT pointer which means a box only has a pointer instead of a link. This pointer is why I decided to post.

Lastly my link object contained 5 pointers, so I XORed the object and box pointer to cut it down to 4. I always start traversal from one of those, so the XORed value can always be used to reach the other. This did not really impact performance much.

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

#124

Post by brundolf »

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 gaining an intuitive grasp on the second solution, which could potentially nullify the bug-resistance of having fewer branching cases. In short, calling the second one objectively better is overstating it I think.

It's worth noting that in a language with union types, you can have the best of both worlds (using Rust here because it's the one I'm most familiar with):

  enum LinkedList {
    Null,
    Node { value: i32, next: Box }
  }
In the same way that the pointer to a pointer homogenizes the head-case with the rest, a union type means that any given linked list "is just a node", and the head can therefore be treated the same way as any later node

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

#125

Post by jonahx »

Good article. The key insight was a bit buried though:

By using the pointer to the current element, you lose information (that element's ancestor), forcing you to introduce a "prev", and to track and update 2 variables.

By using a pointer to the pointer of the current element, you have access to all the information you need -- the "prev" and the "cur" -- just by following the pointer trail one or two steps.

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

#126

Post by souprock »

Animats wrote: post #78
m4lvin wrote: post #22

The second version seems more elegant but will scare non-C people away with all those pointers ;-) What I do not understand is why one should use an "IntList" struct in the first place? As the explanation of the second method suggests, a List is the same thing as a pointer to its first element, so why not do this?: typedef struct IntListItem* IntList; Also, could it be that both methods fail terribly (infinite loops?…

Um, yes. That jumped out at me. If there's a no-find, the code will de-reference null and crash. That's just not acceptable. Try to write that in Rust, using Some(ref) for the forward link, and the compiler will force you to test for None and detect the end of the list. This is pre-1990s programming style. I've seen such code in assembly programs. Because I was reading crash dumps where it failed.

It's 100% acceptable. You should not remove something from a list unless you know it is there. Since you won't attempt to remove something that doesn't exist, any code to check for that situation is an unjustified performance loss.

(separate code exists for searching a list)

This... is not Python. C programmers, particularly kernel developers, have that style even in 2020.

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

#127

Post by helloycombinat »

forrestthewoods wrote: post #62
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…

Perfect. I almost commented to complain that the “elegant” version is harder to read and understand. This is much much better. Comments are important!

I don't think it's the comment.

Usually variable names in a loop is the object being manipulated not the address of that pointer which means p isn't a pointer to the object which makes it completely confusing.

If the article used pp which is the typical way you describe a pointer to pointer it'd help

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

#128

Post by jcranmer »

arjun-menon wrote: post #99
jcranmer wrote: post #65

Earlier quoted context omitted.

There's arguments to be made on both sides, but I think the problem with Linus's solution here is that it doesn't quite clearly establish the assumption being made, which gives it a bit too much of the 'cleverness' flavor that you allude to. A better implementation would be one that does establish why the use of pointers make sense: void remove_entry(node_t *entry) { // curr_ref is the address of the link pointing to…

That does make it a bit clearer, but I do hope the compiler optimizes away the redundant curr variable. Now, on a different note, I am a bit puzzled because I don’t see a free(*ptr) call in Linus’ or anyone else’s code. The code, as-is, would cause a memory leak. There’s a need to capture the curr_ref before it’s overwritten, and free it after it’s overwritten.

The assembly code produced by my variant and Linus's variant is exactly equivalent, assuming you write the guards the same way. This effectively means that both curr_ref and curr will be live, although the compiler will note that it can substitute entry for curr and short curr's lifetime to only exist within the loop body in the form written here.

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

#129

Post by User23 »

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…

Human beings are bad at case analysis, so removing case analysis makes the code much more comprehensible. It's a huge improvement. Dijkstra wrote extensively on the subject and his arguments are compelling[1].

[1] https://www.cs.utexas.edu/users/EWD/transcriptions/EWD07xx/E... and https://www.google.com/search?q=site%3Ahttps%3A%2F%2Fwww.cs.... for more

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

#130

Post by magoghm »

Mirioron wrote: post #118
erik_seaberg wrote: post #93

Earlier quoted context omitted.

A tool can write the name for you once, but you have to reread it many times and we don’t have a tool to help with that.

That's not how reading works. You don't parse every character like a computer does. You look at the starting letter (maybe the ending one too) and then recognize the shape of the word used. There isn't too much difference in reading a long or short variable name as long as there aren't variable names that are too similar to one another.

Actually what you need to recognize are expressions, and expressions with short variable names are much easier to recognize. For example, if I write:

  theDependentVariable = theCoefficient * theIndependentVariable + theIntercept
it is much harder to recognize than if I write:

  y = a*x + b
So, longer variable names might be "autodocumenting" but they also make code harder to read.
Post reply on HN