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

161–170 of 339 posts

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

#161

Post by saagarjha »

andy_ppp wrote: post #39
m_mueller wrote: post #24

Earlier quoted context omitted.

While there certainly are such cases, I think here it’s just about being proficient in a language. Pointers, referencing and dereferencing are the bread and butter of any C code, and applying them in a way to reduce complexity is certainly something to strive for - if this isn’t readable then I’d argue the reader shouldn’t be touching the codebase anyways.

Fortunately or unfortunately you don’t always get to decide who touches the code, so unless performance is a concern as it is in kernel development optimising like this in the day job will eventually lead people making mistakes. Basically I say be as explicit and clear as you dare, even at the cost of some CPU cycles.

Adding extra dereferences is rarely performant. The example is written this way because it's more elegant, not because it's faster.

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

#162

Post by kortex »

munificent wrote: post #135
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…

One way to define "clever" is something you can do but that relies on something you don't expect most readers to have already loaded into their head. Like a riddle, it makes sense if you know the trick it relies on but is baffling if you don't. The difference between "clever" and "smart" then is based in large part on what you expect your readers to already know. Different people have different expectations there and…

What really made monads click for me is when I read Monads for Go Programmers [0], drawing a comparison between pointers and functors:

> We can think of a functor as a container, which contains one type of item. ... > A pointer: *T is a container that may be empty or contain one item;

Despite that comparison probably making seasoned FPers groan, that was a big clicking moment for me.

Thinking along the lines of nullary-function:pointer::return:dereference, frames Linus' abstraction in an interesting light. You're manipulating the "function which yields the struct", not the struct itself. In fact it looks much closer to a map than the cs101 blurb in that now all nodes can be treated symmetrically.

[0] - https://awalterschulze.github.io/blog/post/monads-for-goprog...

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

#163

Post by emerged »

hyperpape wrote: post #105
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…

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…

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.

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

#164

Post by billsix »

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…

From watching the Ted talk, I think that Linus was using a cs101 example to effectively communicate to a large audience of programmers about good design for system level work such as for an Operating System.

His example, I think, can be extrapolated to explain the design of Linux’s “clone” system call for threads, which creates a new process that uses the same virtual address space as the parent process, with a different stack location; but more importantly, those “threads” are scheduled by the OS’s scheduler like any other process is. I’m unaware of any other OS which implements threads this cleanly.

From his talk, “Sometimes you can see a problem in a different way and rewrite it so that a special case goes away”

https://eli.thegreenplace.net/2018/launching-linux-threads-a...

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

#165

Post by Existenceblinks »

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…

I was about to post a comment but then I think someone propably post this view already, and yes. When I quickly perceive visual of:

  block
    prev = cur
  /block

  if(prev)
It immediately tells the taste that's bad. Especially for ones who come from writing expression rather than statement

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

#166

Post by azernik »

mehrdadn wrote: post #147
asdfasgasdgasdg wrote: post #113

Earlier quoted context omitted.

Normally with an identity-based API like this, you can put it as a requirement that you must not remove items other than those which actually exist in the collection. Another example of an API that doesn't check for presence: c++ iterator-based removal. If you ask a C++ list to remove an iterator element outside its range, it may crash the program. See the exception safety section of this documentation: http://www.cp…

As the other person said, it's not really about complexity. Complexity isn't all that different here; personally I'd find something like the following to be simpler (I imagine others might disagree): remove_list_entry(entry) { for (p = &head; *p; p = &(*p)->next) { if (*p == entry) { *p = entry->next; break; } } } However, what the choice does objectively impact is performance. Being able to assume the object exists…

Not just an instruction, but a branching instruction.

Branch predictors will probably do pretty well on this, but still.

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

#167

Post by vips7L »

brundolf wrote: post #143
vips7L wrote: post #140

Earlier quoted context omitted.

Wouldn't you end up with a Box of Null? Wouldn't it be better to: struct Node { value: i32 next: Option > }

Yeah that's true, but the problem with your version is it loses the homogeny because an empty list can't simply be a Node, it has to be represented in some other way (as an Option or something), so we're back to square one. Maybe I was wrong and this can't be done perfectly even with union types.

In that case wouldn't you just:

    struct List {
      head: Option
    }

    struct Node {
      value: i32,
      next: Option>
    }

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

#168

Post by kbumsik »

762236 wrote: post #109
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…

What if entry doesn't exist in the list? You need a special case to handle that too.

Well, both implementations will crash in that case anyway. You can take that case as out of scope of this discussion.

The purpose of the OP and the Linux's talk is to show a better way to walk through linked list, not to show a full implementation.

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

#169

Post by BalinKing »

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…

I'm kinda confused on how this will behave if we want to remove `head`—if `head` is in the stack frame (assuming it's a parameter to `remove_list_entry`), wouldn't `*(&head) = entry->next;` be a no-op as far as the caller is concerned? (Sorry for the n00b question.)

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

#170

Post by jariel »

souprock wrote: post #131
jariel wrote: post #88

In most cases clarity should win out over succinctness. (Sometimes succinct is more clear). I absolutely prefer the first one in almost all cases, and would probably reject the second one on a code review. Unless we're dealing with such a core, hyper-sensitive part of the system wherein the compiler would not find rough equivalence anyhow, and the material gains from supposedly 'fewer instructions' would be better. i…

Then there was the day I wrote a function that started off like this: char *fn(char **foo, char ***bar){ char *baz = *++*foo ? *foo : *++*bar; Double-pointers are just normal. The strtol function has one.

While that function may have utility in some context, I would immediately assume that there's something existentially wrong with the context in which such a function was needed.

Ok, it's possible the entirety of it makes sense, but given that C/C++ is full of absurd shenanigans, I think odds are something is wrong with a system that needs that kind of function in the first place.

That such things are common enough doesn't make them a good practice.

Post reply on HN