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

231–240 of 339 posts

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

#231

Post by huhtenberg »

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.

Well, yeah. This sort of code acts as a natural filter.

Someone's who finds it difficult to learn or to use it may not be ready for the kernel development. So it works as expected on more than one level.

The same goes for intrusive containers and few other things that many people learn in school, but get at first confused by in practice. If this creates a friction at the group level, then it's the problem with the average group skill rather than the code. And it's the former that (ideally) needs addressing. Just like you wouldn't use bubble sort because the "group" has trouble understanding the alternatives.

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

#233

Post by aidos »

larsrc wrote: post #229
adrianN wrote: post #224

Earlier quoted context omitted.

And instead of adding a check and crashing visibly here you wait even longer until your program misbehaves due to the error? The longer the program runs after something went wrong, the harder it is to debug, and the more likely it becomes that you get an exploitable bug.

Are you arguing that we should leave known crash bugs in the code?

It’s not a bug, in this case. It depends on the behaviour the library is specified to handle, but if you ask me to remove a specific item from a list, and that item isn’t in the list, what should I do?

I can fail so you can catch it, or if you don’t catch it, you’ll at least see exactly what went wrong. You expected the item to be in the list and it wasn’t. Your preconditions were wrong from the beginning and you have an (unknown) bug in the code.

The alternative is that I can’t find the item and I silently suck it up and don’t notify you. If that’s the api we’ve all agreed on, that’s fine. It was on you to check for the thing in the list first and then remove it. But it’s a bit weird if you think about it - now you need to traverse the list twice. Once to check for the existence (and fail out yourself) and once to remove.

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

#234

Post by threatofrain »

bigyikes wrote: post #71
eloff wrote: post #26

Earlier quoted context omitted.

Looking at the code there are not just fewer lines, but fewer conditionals too. It's much simpler to read and understand. I got it at a glance, whereas I skimmed the typical approach and would still need to go over it more carefully to be sure it is correct. I think Linus is correct on this one.

Linus’ solution seems to add a layer of indirection, which I think is harder to grok than a simple condition.

IMO harder to initially acquire but easier to grok at scale. Imagine combing through the behavior of blocks of code with conditionals in a larger system.

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

#235

Post by adrianN »

larsrc wrote: post #229
adrianN wrote: post #224

Earlier quoted context omitted.

And instead of adding a check and crashing visibly here you wait even longer until your program misbehaves due to the error? The longer the program runs after something went wrong, the harder it is to debug, and the more likely it becomes that you get an exploitable bug.

Are you arguing that we should leave known crash bugs in the code?

I'm arguing that we should use asserts or similar defensive coding mechanisms to ensure that preconditions are met instead of merrily continuing to run our program with cascading error effects.

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

#236

Post by tgv »

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…

Without the container struct, you'd have to pass the pointer to the pointer of the first element, remove(&head, elem), or assign the return value back to it, head = remove(head, elem). A container also allows you to maintain a counter and a tail pointer, for fast append and insert. Above all, a container makes it harder to return a pointer to just somewhere in the middle of the list and treat that as the head.

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

#237

Post by kzrdude »

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 Linux kernel uses intrusively linked lists a whole lot - that means memory management is a separate concern from managing the list links.

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

#238

Post by _flux »

crazygringo wrote: post #14

Like others here, I prefer the first. The first one -- I read it, I know what it does, it seems intuitive to understand, and I expect it to be bug-free especially because the edge case is explicitly accounted for. If someone else has to modify it later, I'm not particularly worried they'll mess it up. The second one -- it took me about 4x longer to understand what it does. It works too, but it doesn't match how my br…

Consider though you would need to extend both versions to use doubly-linked lists.

I would much rather extend the latter than the former. (Though it could be I've used a similar solution in the past.)

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

#239

Post by kleiba »

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

A 1992 poem Bukowski originally entitled “stone tiger, frozen sea,” was completely reworked with just two lines left unchanged. Its new title: “like a dolphin.”

https://www.pbs.org/newshour/arts/poetry/bukowksis-poems-wer...

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

#240

Post by larschdk »

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…

How I wish more programmers would understand this. It's like learning to eat broccoli. At first, its bitter and unfamiliar, but if you are exposed to it, you learn to recognize it and like it, and it's actually good for you despite the initial unpleasant taste.
Post reply on HN