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

91–100 of 339 posts

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

#91

Post by jariel »

btilly wrote: post #48

Most people prefer the first over the second. But I think that Linus really should prefer the second over the first. Let me try to explain why. There is a well-known saying attributed to David Wheeler, "All problems in computer science can be solved by another level of indirection." Except the problem of having too many layers of indirection. Also both quotes are often seeing with "abstraction" instead of "indirectio…

You make a very good point, and that it has to do with the relative foundational conceptualisational ability of the types of mainteners.

That's great because it kind of speaks to the crux of the problem.

But the first solution does use pointers :)

The second uses double pointers.

I'd argue that 'even kernel maintainers' may not be so easy with the second in reality.

It's probably worth it if there is a performance gain, because it's so low level. But not otherwise.

But good point.

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

#93

Post by erik_seaberg »

tcoff91 wrote: post #67
0xdeadbeefbabe wrote: post #40

Earlier quoted context omitted.

I completely disagree. Lines of code, long variable names, and meaningless hierarchies are some tasteless taxes. Some people like each of them(!), and I don't get it.

Why are long variable names a tax when there are such good auto completion tools? I get short variable names in algorithm code but in business logic long variable names can make code vastly more self-documenting.

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.

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

#94

Post by jagged-chisel »

jamesdsadler wrote: post #75
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…

Both of these implementations seem to be missing a call to `free`, or is that something that the caller should be taking care of?

Depends on whether the list owns the nodes. I tend to write mine such that it does. Perhaps this code is demonstrative rather than complete.

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

#95

Post by rossitblt »

alisonkisk wrote: post #72
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…

The author also misunderstands what "head" of a list is, adding more bad clutter to the code. (Granted, the code in the original TED talk is broken, as it doesn't define "head".) A linked list in C isn't a struct with a "head"; "head" is just a pointer pointing to the head element. The OP article should be retracted.

How likely it is for code to be misunderstood depends on the code readability as well, not just on the person who gets it wrong. Personally, I find the style of Linux lists unintuitive. To me it seems a case of sacrificing code readability to workaround limitations of the C language.

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

#96

Post by bfung »

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 case "indirect = &head", and the inductive step which is the rest of the program.

It'd take a lot more work to mathematically prove that the branching program "works" due to the if statement -- you'd have to construct a proof of each branch and prove that the combination works.

I'm not a mathematician, but this was a major point in CS courses at university. Being able to prove an algorithm works can extend into automated program checking / auditing, etc.

It's not just "taste" -- there's a lot of practical theory to be applied.

https://en.wikipedia.org/wiki/Mathematical_induction

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

#97

Post by [deleted] »

jcranmer wrote: post #65
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…

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…

[deleted]

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

#99

Post by arjun-menon »

jcranmer wrote: post #65
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…

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.

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

#100

Post by arka2147483647 »

jamesdsadler wrote: post #75
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…

Both of these implementations seem to be missing a call to `free`, or is that something that the caller should be taking care of?

The caller could want to move the element from one list to another, in which case the optimum impl would not free or copy the element.
Post reply on HN