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

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

#201

Post by emerged » Mon, Dec 07, 2020, 6:00 AM UTC

pacaro wrote: post #193

emerged wrote: post #163

Earlier quoted context omitted.

For my tastes there is way too much whitespace and I usually only use multi-line comments to describe the high level algorithm for a full function. I prefer to pepper single-line comments which describe the sequence of events in a human-readable way. I've been C/C++ for about 25 years.

My taste is that function level comments describe the "what" and inline comments describe the "why". So at a function level the comments is giving a highlevel description to the reader as to the functionality contained, and at the line level comments exist only to say describe the programmers intentionality, why it was implemented this way rather than some other way. I have generally found (there are always exception…

The main takeaway here might be that two 25 year veterans both make function level and line level comments. The particulars are somewhat of a matter of flavor preference :)

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

#202

Post by dhanna » Mon, Dec 07, 2020, 6:01 AM UTC

maweki wrote: post #29

I think what's missing in the mental model of the elegant solution is, that the IntList-pointer does not point to a complete list or an element of the list, but to a tail of some list (that might be the complete list). This explains why the head is not really a special case, as it points to the tail that is complete. And you can just exchange a tail. So I think the image with the blue boxes is misleading and it shoul…

Right, I think the key insight is that the special case is simply unnecessary if you have the abstract model of the data structure correct. A linkedlist is just x::xs.

The c code being weird is more of an implementation detail that shouldn’t be of much focus.

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

#203

Post by adwn » Mon, Dec 07, 2020, 6:01 AM UTC

fnord77 wrote: post #172

2013 - stop using linked lists: https://news.ycombinator.com/item?id=5751702

Your knee-jerk reaction is misplaced. There are valid use cases for intrusive linked lists [1]:

a) When your nodes can belong to multiple lists. You can't do this with arrays.

b) When you need fast removal from the middle of the list and you already have a pointer to the list node [2].

[1] In an intrusive linked list, the prev/next pointers are members of the payload node, as opposed to a "simple" linked list, in which the list nodes contain a pointer to the payload.

[2] This happens all the time in kernels. For example, you receive an interrupt and need to remove the corresponding task from the IDLE queue and append it to the RUNNING queue.

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

#204

Post by aidenn0 » Mon, Dec 07, 2020, 6:05 AM UTC

aksjfnkajsnd wrote: post #186

greenkey wrote: post #148

Earlier quoted context omitted.

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.

Who is little Jimmy?

Jimmy is a diminutive form of James. It's the sort of thing where parents would call a kid "jimmy" and when they grow up they will ask people to call them "Jim" or "James."

Adding "little" in front just stresses the fact that we are talking about a kid, so the references are about dumbing it down for kids.

Johnny is probably a bit more common than Jimmy, but I've seen both. See e.g. [1]

1: https://en.wikipedia.org/wiki/Why_Johnny_Can%27t_Read

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

#205

Post by r-w » Mon, Dec 07, 2020, 6:17 AM UTC

Jasper_ wrote: post #153

javajosh wrote: post #137

Earlier quoted context omitted.

What happens at the end of the list? Is next null? And if so, how do either of these methods behave?

This is a circular linked list, where the ->next pointer points back to the head of the list. It's helpful for iteration tasks, since you can always walk the full list when you get access to one node. In most cases you use a linked list like this, you don't care about the order of things, just that you can iterate over all items in the list.

No, it's not, as can be seen from the diagrams in the article.

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

#206

Post by xpe » Mon, Dec 07, 2020, 6:20 AM UTC

convolvatron wrote: post #36

mrloba wrote: post #30

Maybe slightly off topic, but.. I don't think this is really about taste. It's about "common ground" between programmers. If you've seen and used the second pattern many times before, it becomes part of your vocabulary. You're then able to express yourself more succinctly. It is then obviously a better solution to you. If you see another programmer use the same pattern, it is common ground between you, and you like i…

this is the big point. when coding alone I strongly prefer Linus's version. but it seems to cause friction and get called out whenever I use it in a group environment. so I don't. or I change it. the code itself isn't important. its about the functioning of the group, the velocity, and the ownership.

> the code itself isn't important. its about the functioning of the group, the velocity, and the ownership.

It isn't either/or. It can be all of the above, to varying degrees, that change over time.

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

#207

Post by xpe » Mon, Dec 07, 2020, 6:23 AM UTC

ajarmst wrote: post #159

I've been teaching CS101 for two decades. I've never shown (nor seen another instructor show) a two pointer implementation for list traversal, except perhaps as an example of bad practice (probably by someone who doesn't understand the syntactic sugar of the -> operator). "Every pointer to node is a list, including the trivial case of a null pointer being an empty list" is the way I was taught in CS101 in the early 8…

> Finally, the use of two structs is unnecessary. IntList is just a wrapper around a pointer to IntListNode. Why not just use a naked pointer to IntListNode like the gods intended?

So Say We All.

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

#208

Post by ankurdhama » Mon, Dec 07, 2020, 6:26 AM UTC

The second solution may not be obvious at first but the idea is that in the first solution you are finding the node that needs to be removed whereas in the second solution you are finding the "next" of a node that points to the node to be removed.

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

#209

Post by shallowthought » Mon, Dec 07, 2020, 6:30 AM UTC

mjevans wrote: post #195

cmroanirgo wrote: post #191

Earlier quoted context omitted.

I can't help but notice how this code, as well as in the article, there's no checks for a) a NULL list or b) that the item is in fact part of the list. A simple fix is: while (!!walk && walk != entry) { prev = walk; walk = walk->next; } or while (!!indirect && !!(*indirect) && (*indirect) != entry) indirect = &(*indirect)->next; ...because without those checks it's pretty easy to see where you'll crash... but by putt…

I believe the implicit requirement is that the item is known to exist within the list. With that requirement in place the extra guards aren't requisite (they're implicit) and in kernel code this probably offers a performance edge and is a reasonable requirement. Either having an implementation that has an extra check once at the end of the list, or that verifies the presence of the item and passes that node through t…

That's a pretty big freakin thing to leave out, though. Code that depends on its context is, some would say, bad.

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

#210

Post by xpe » Mon, Dec 07, 2020, 6:32 AM UTC

ajarmst wrote: post #159

I've been teaching CS101 for two decades. I've never shown (nor seen another instructor show) a two pointer implementation for list traversal, except perhaps as an example of bad practice (probably by someone who doesn't understand the syntactic sugar of the -> operator). "Every pointer to node is a list, including the trivial case of a null pointer being an empty list" is the way I was taught in CS101 in the early 8…

> As a side note: I don't like the "elegant" version's use of double indirection. It's not necessary if you return a pointer instead of void, which is also nice because you can treat calls to your list functions as lists themselves and chain them together.

Agreed.

> It also allows you to avoid warts like `p = &(p)->next;`

Does it? Isn't having `p = &(p)->next;` in the while loop necessary?

> at the modest cost of needing `p=remove(p,t)` instead of `remove(p,t)`.

I may disagree since an API is used many more times than the API function is written.