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

131–140 of 339 posts

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

#131

Post by souprock »

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.

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

#132

Post by grive »

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.

Usually those lists are intrusive -- their nodes are meant to be part of larger objects. They will be freed in other contexts, e.g. if protected by RCU, memory reclamation is postponed until all threads have quiesced. Or the nodes are allocated by one amongst many allocators (i.e. for performance, or better concurrence), so it is best for the structure itself not to make any assumption about where the memory should be returned to.

So generally, list implementations in C will not free the node, only remove references to it and return it.

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

#133

Post by defaultcompany »

Semi-relevant side note: Within some constraints its possible to remove an element in a singly linked list without walking the list. The purpose of walking the list is not to find the element (which you already have) but to find it's previous element so you can fix the "next" pointer on the previous element. What you can do instead is to copy the data from the next element onto the one to delete, making it a "copy" of the next one. And then delete the next one after fixing the pointers. Hard to say in english but here's the idea:

    remove_list_entry(entry)
    {
        next = entry->next;
        entry->data = next->data;
        entry->next = next->next;
        free(next);
    }
You do need to handle the case of deleting the last element in the list. That can be done by keeping an EOL element at the end just for this purpose. The real caveat is that it breaks external references to list elements. If you are managing the list yourself however and can deal with these issues you can avoid list traversal (or save a pointer on every list element vs a doubly linked list). Just something to keep in your bag of tricks.

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

#134

Post by Retric »

asdfasgasdgasdg wrote: post #113
762236 wrote: post #109

Earlier quoted context omitted.

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.cp…

Unnecessary is not really the correct term, it’s one of a huge number of tradeoffs. The you don’t want it for safety critical systems, but Linux isn’t designed to be used for such things.

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

#135

Post by munificent »

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 they reasonably vary across teams and time.

Pointers and addresses are pretty fundamental to C, but many C programmers only use them in certain fixed patterns: An address is what you get back from malloc() and pointers are variables to heap-allocated objects. Or pointers are the type you use for parameters when you don't want to copy the value.

There is a deeper understanding you can have: pointers make storage locations first class entities. A common refrain in programming is that if you want to increase the expressiveness and flexibility of your code, you make some concept first class because then you can abstract over it.

In C, storage locations are first class because you can take the address of anything. This lets you abstract over which storage location an operation modifies. Linus's "trick" relies on understanding that using a pointer (to a pointer in this case) lets you abstract over where the node pointer is the head pointer or a next pointer.

If you have Linus's mental model of C, what he's doing isn't clever. It's smart. It uses a fundamental concept of the language to avoid error-prone control flow and edge cases. But if you're only used to using pointers within a handful of proscribed patterns, it likely seems very strange.

I won't make any judgements as to whether thinking of C in this way should be something that people do. Anecdotally, a while back I wrote a blog post on writing a garbage collector from scratch: http://journal.stuffwithstuff.com/2013/12/08/babys-first-gar...

The mark-sweep algorithm isn't super sophisticated, but this is fairly tricky low-level stuff. A lot of people have read it over the years and basically the only negative feedback I've gotten is around where I use the same pointer-to-a-pointer to remove from a linked list. It confuses a lot of people.

So, in my own personal code, I'm fine with stuff like this. But when coding with others, I tend to avoid it.

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

#137

Post by javajosh »

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 happens at the end of the list? Is next null? And if so, how do either of these methods behave?

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

#138

Post by erik_seaberg »

magoghm wrote: post #130
Mirioron wrote: post #118

Earlier quoted context omitted.

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.

Actually what you need to recognize are expressions, and expressions with short variable names are much easier to recognize. For example, if I write: theDependentVariable = theCoefficient * theIndependentVariable + theIntercept it is much harder to recognize than if I write: y = a*x + b So, longer variable names might be "autodocumenting" but they also make code harder to read.

Yeah, letters don’t have much of a cost, but extra words do, which is why people complain so much about needing to plow through SimpleBeanFactoryAwareAspectInstanceFactories.

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

#139

Post by souprock »

Mirioron wrote: post #118
erik_seaberg wrote: post #93

Earlier quoted context omitted.

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.

Yes, "as long as there aren't variable names that are too similar to one another"...

It isn't safe to trust that to be true. That way lies bugs, including security holes. You have to carefully check the names.

EthAccHdlrSubsMacPhysRegWrite and EthAccHdlrSubsMacPhyRegWrite

Shorter is better, within reason.

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

#140

Post by vips7L »

brundolf wrote: post #124

This certainly falls under Rich Hickey's definition of "simple", which is one virtue. But: > it is not immediately evident how the more elegant solution actually works another virtue is ease of comprehension, and the more elegant solution lacks that in my (and seemingly Linus') opinion. Maybe if you're used to working with pointers to pointers you might have an intuituon for them, but I at least had a difficult time…

Wouldn't you end up with a Box of Null? Wouldn't it be better to:

    struct Node {
        value: i32
        next: Option>
    }
Post reply on HN