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

71–80 of 339 posts

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

#71

Post by bigyikes »

eloff wrote: post #26
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…

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.

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

#72

Post by alisonkisk »

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.

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

#73

Post by eloff »

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.

There's no accounting for taste ;)

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

#74

Post by alisonkisk »

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.

The cs101 solution adds an unecessary extra variable "prev" that you have to study to figure out what it means. That's harder for me to grok.

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

#75

Post by jamesdsadler »

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?

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

#76

Post by alisonkisk »

qualityonly wrote: post #64
xorcist wrote: post #50

Earlier quoted context omitted.

Fever lines aren't automatically better, but fewer lines means less code to maintain. More often than not, fewer lines is easier to read too. The example here is a good one. The shorter version reads much better and is more obviously right.

I have one to bring up "for loops". I think they are infinitely worse than while loops. (I ran into this specifically with Pandas dataframes/series) You save 1 or 2 lines and have ambiguity on wherever "each" is. Maybe static typing solves this, but I've decided I hate syntax sugar and dynamic typing.

You might have a good point, but you haven't given enough code to expresss your idea.

What is "each" ?

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

#77

Post by alisonkisk »

R0b0t1 wrote: post #57
andy_ppp wrote: post #23

Earlier quoted context omitted.

I totally agree, it’s about proving you’re clever rather than communicating ideas. Maybe for something hard like Linux kernel development this is a good thing but in most cases it just leads to messy code that people can’t understand or follow.

I was only ever taught the second, more concise one, so this discussion is kind of confusing. How is it not shorter and more explicit?

Many Programmers who don't use C are afraid of pointers and prefer superficially simpler (but overall more complicated) things like Java's abstraction towers, despite the extra expense.

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

#78

Post by Animats »

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.

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

#79

Post by matvore »

cjaybo wrote: post #31
dvt wrote: post #10

> A particularly beautiful outcome is that the implementation has consistent semantics for the edge cases Not sure if this is actually a benefit or not. Edge cases are notoriously hard to debug, so it's sometimes actually nice to have a branch that specifically handles edge cases. Conceptually, it's also much more difficult to wrap one's head around. I would be interested to see how much of the cs101 solution is comp…

> PS: If the linked list is stored in contiguous memory (if you're using a slab allocator, for example), you can actually be even more clever (I'll leave that as an exercise to the reader). This might be a dumb question, but if list elements are stored contiguously, is there any advantage to using a linked list instead of a data structure that is designed for contiguous storage (something like C++'s std::vector)?

  > if list elements are stored contiguously, is there any advantage to using a linked list
Storing them contiguously probably implies that you consider "freed" space in the middle to also be part of the contiguous area. Otherwise you can't remove in O(1) time.

It is straightforward to maintain a list of freed nodes which you can add back later.

If you don't mind not being able to remove in O(1) time, you still have the advantage of passing the handi-capped (contiguous) linked list to interfaces that expect a linked list, but still get the cache locality of a plain vector.

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

#80

Post by Arnavion »

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?

It's pseudocode. The code as-is is not valid C anyway.
Post reply on HN