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

111–120 of 339 posts

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

#111

Post by nemetroid »

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.

At the end of the function curr == entry, so the caller already has a separate reference to the object. Also, removing a node from a list does not necessarily mean that you want to delete it. For example, you might want to put it in a different list.

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

#112

Post by identity0 »

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…

The top pattern is extremely common so comments are somewhat unnecessary since everyone would know what you're doing. In the second one, comments would be less necessary with a type annotation and perhaps a better name. Maybe "next_ptr" instead of "indirect"---all pointers are indirection, so that name is redundant. But the comments are necessary, to me at least.

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

#113

Post by asdfasgasdgasdg »

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.

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.cplusplus.com/reference/list/list/erase/ If you look at most "remove this object from yourself" APIs in low-level code, it behaves this way, because it's unnecessarily complex to check for presence when that is a fact the program can condition on instead.

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

#114

Post by m463 »

brainwipe wrote: post #33
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…

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

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

#115

Post by trhway »

>The standard CS101 approach makes use of two traversal pointers cur and prev

times has changed. Back then the indirect was the standard approach (in particular you wouldn't want to waste registers). It requires just a bit more complicated reasoning, and the CS and the people in it were just a bit closer to math back then. Today it is basic engineering/craft, and thus the standard is the much simpler for reasoning approach with simple pointers and the simple explicit special case handling - ie our modern enterprise C code.

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

#116

Post by erik_seaberg »

varjag wrote: post #69
Taniwha wrote: post #53

Earlier quoted context omitted.

While I mostly agree with you, I think that use of double indirect pointers is rare enough that in effect each use of one probably counts as a "line of code" when trying to understand what's going on. The one Linus doesn't like likely runs faster (at a microarchitectural level), it's also the thing I've done for 40 years now, it's what comes out of my fingers when I code linked lists, for me at least it's more unders…

It's very unlikely it is faster.

A good compiler should keep *p in a register because there are no aliases that might modify it, but a poor compiler might follow p a second time.

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

#117

Post by jodrellblank »

jodrellblank wrote: post #28
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…

> " which always manifests itself as terseness as if lines of code were expensive) " They are expensive! Your code maintained years in the future, every developer has to potentially read every damn line. The alternative to "clever" code isn't Java and FactoryFactoryFactories, it's short clear code, which is different from short codegolfed code. The main difference is nicely designed libraries and abstractions.

For example, right now it's Advent of Code, day 6. The puzzles are still reasonably simple. Have a look around today's Reddit thread where people can post their answers:

https://old.reddit.com/r/adventofcode/comments/k7ndux/2020_d...

These are self-selected people, free to use a language of their choice. Ask yourself some questions:

- Which of these do I think is "most readable" vs "least readable"?

- Which of these am I happy is correct, and bug-free as far as it goes?

- Which of these would I like to make a change to, confident that it won't break?

- Which took the author most / least time?

- If I could only pick one to run on my puzzle input and submit the one answer which came out, which of these would I pick?

- Which of these would I like to maintain long term?

Another way to see the same ideas is to pick a task on RosettaCode - https://rosettacode.org/wiki/Category:Programming_Tasks - and see how much / little code people write in various languages to solve the same problem.

IMHO it isn't "the longest one" that is clearest, by a long shot. Nor the golfiest one. But it tends to be the shorter ones done in languages that have higher levels of abstraction, more libraries, nicer looking naming, more standard patterns.

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

#118

Post by Mirioron »

erik_seaberg wrote: post #93
tcoff91 wrote: post #67

Earlier quoted context omitted.

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.

That's not how reading works. You don't parse every character like a computer does. You look at the starting letter (maybe the ending one too) and then recognize the shape of the word used. There isn't too much difference in reading a long or short variable name as long as there aren't variable names that are too similar to one another.

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

#119

Post by eperdew »

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?

As others have said, often you don't want to free the node, you want to do something else with it. E.g., put it in a free list. However, usually if you're not freeing it, you'd null out the next field so that you don't accidentally access it when it's not part of the list (at least I would).

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

#120

Post by zem »

alisonkisk wrote: post #81
zem wrote: post #49

Earlier quoted context omitted.

i think a lot of the reason it looks more "clever" than elegant is because c's syntax makes the "get the address of this field in a struct" operation so hard to read at a glance.

It's a lot easier to "get the address of this field in a struct" in C than in Java or Python or JavaScript.

in a lot of other languages you would be passing things by reference; the concept of an address would not be needed to implement a linked list.
Post reply on HN