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

321–330 of 339 posts

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

#321

Post by nybble41 »

zem wrote: post #120
alisonkisk wrote: post #81

Earlier quoted context omitted.

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.

Sure, in those other languages you could just define a single-field class to wrap the reference to the next node, since you can only pass objects by reference and references themselves are (usually) not objects. Unfortunately this adds a lot of overhead, both in lines of code and runtime. Instead you would probably just use the less efficient algorithm with more special cases to work around the lack of indirect references.

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

#322

Post by Dylan16807 »

azernik wrote: post #318
asdfasgasdgasdg wrote: post #301

Earlier quoted context omitted.

If you want speed, you don't use a linked list in the first place.

Yeah you do - the kernel uses linked lists to store everything from running tasks to memory pages . Insertion and deletion of entries are much faster in a linked list than in an array, and that's a very performance-sensitive operation in the kernel.

> Insertion and deletion of entries are much faster in a linked list than in an array

That's a really broad statement. Arrays can get surprisingly big while being faster. Performance-wise, you'd usually want to use arrays up to a certain size and then link between entire arrays. I'd say the biggest advantage of a standard linked list is that it can be intrusive.

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

#323

Post by Thorrez »

ndand wrote: post #184
Thorrez wrote: post #180

Earlier quoted context omitted.

This comment seems wrong to me: // The "indirect" pointer points to the // *address* of the thing we'll update The "indirect" pointer points to the thing we'll update. See at the bottom, it's updating *indirect, so "indirect" points to the thing being updated. On the other hand, "indirect" points to the address of the thing we'll remove. There's a specific item being removed, and there's a specific thing that will be…

The comment is correct. The "thing" is the variable that holds the "entry". The entry is removed by updating the "thing".

> The "thing" is the variable that holds the "entry".

What does "holds" mean? If holds means actually contains the memory, then I don't see the distinction between "thing" and "entry". They both refer to the exact same piece of memory.

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

#324

Post by Thorrez »

cmroanirgo wrote: post #192
ndand wrote: post #184

Earlier quoted context omitted.

The comment is correct. The "thing" is the variable that holds the "entry". The entry is removed by updating the "thing".

Agreed. The 'indirect pointer' points to the memory address of the previous 'next' (or the head). So, as long as neither are NULL, then dereferencing the pointer is the actual head (or the previous 'next').

> The 'indirect pointer' points to the memory address of the previous 'next' (or the head).

I don't think so. I think the 'indirect pointer' points to the previous 'next' (or the head). It doesn't point to the address of the previous 'next' (or the head). What you say is adding an additional level of indirection that doesn't exist.

Reality:

indirect -> previous next -> first element

What you're saying:

indirect -> address of previous next -> previous next -> first element

In reality indirect contains the address of the previous next, but it doesn't point to the address of the previous next.

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

#325

Post by dhanna »

mkirchner wrote: post #223

Author here. To add context that seems lost on some: this is a cleaned-up version of my own notes from when I tried to understand the technical detail behind what Linus called "good taste" in the TED talk. The main contributions of the writeup (if any) are the two conceptual insights that using an indirect pointer yields a homogeneous data structure and a convenient handle to the list item and its predecessor. The ar…

FWIW, I think you get way more correct than some of the comments here give you credit for.

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

#326

Post by ndand »

Thorrez wrote: post #324
cmroanirgo wrote: post #192

Earlier quoted context omitted.

Agreed. The 'indirect pointer' points to the memory address of the previous 'next' (or the head). So, as long as neither are NULL, then dereferencing the pointer is the actual head (or the previous 'next').

> The 'indirect pointer' points to the memory address of the previous 'next' (or the head). I don't think so. I think the 'indirect pointer' points to the previous 'next' (or the head). It doesn't point to the address of the previous 'next' (or the head). What you say is adding an additional level of indirection that doesn't exist. Reality: indirect -> previous next -> first element What you're saying: indirect -> ad…

The "indirect" variable does not point to a list entry directly, like what "head" and "next" variables do, that's why it's named "indirect".

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

#327

Post by goldsteinq »

hadcomplained wrote: post #245

The following is the code I wrote before reading the example pieces of code. void remove(IntList* l, IntListItem* target) { if (l->head == target) { l->head = l->head->next; return; } IntListItem* prev = l->head; while (prev->next != target) prev = prev->next; prev->next = prev->next->next; } Skimming the comments here, I was surprised not to see an equivalent piece of code mentioned. To me my code is more readable t…

Your version does a lot more memory writes.

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

#328

Post by ninkendo »

Sohcahtoa82 wrote: post #317
stuff4ben wrote: post #291

Earlier quoted context omitted.

Safety is a feature and that null check prevents bugs. I'd rather have slow but safe code rather than fast but buggy code.

If the null check silently ignores the attempt to remove a non-existent item from the list, then the null check did not prevent a bug, it merely hid it. IMO, even though this is C, the Zen of Python still applies, which states: > Errors should never pass silently unless explicitly silenced. Its the caller with the bug, not the library code.

Can we all at least agree that if the language could express non-nullable pointers, we'd all be better off? (Something like `Option` in Rust, or Swift's `?` sugar for their `Optional`, etc etc)

Then the type of the function would just declare a that the pointer can't be null, and code which sends a nullable pointer would refuse to compile.

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

#329

Post by dr_zoidberg »

Dylan16807 wrote: post #322
azernik wrote: post #318

Earlier quoted context omitted.

Yeah you do - the kernel uses linked lists to store everything from running tasks to memory pages . Insertion and deletion of entries are much faster in a linked list than in an array, and that's a very performance-sensitive operation in the kernel.

> Insertion and deletion of entries are much faster in a linked list than in an array That's a really broad statement. Arrays can get surprisingly big while being faster. Performance-wise, you'd usually want to use arrays up to a certain size and then link between entire arrays. I'd say the biggest advantage of a standard linked list is that it can be intrusive.

> I'd say the biggest advantage of a standard linked list is that it can be intrusive.

That's one big benefit. I teach operating systems and, when the semester has been good, we dig into physical memory dumps with a few python scripts, and show the students how to parse Windows process list following _EPROCESS structures.

That's one of the big things they find themselves surprised every year: that the process list is a chain of LIST_ENTRY structures embedded within the _EPROCESSes[0] (or any other structure that is doubly-linked in memory). And LIST_ENTRY is just 2 pointers going hand in hand with list_entry->flink and list_entry->blink attributes and nothing more.

[0] You can read some about this structures here https://www.nirsoft.net/kernel_struct/vista/index.html but beware this is based on Vista and a bit old. Kernel data structures vary with versions of the OS (and not even major versions at that) and target processor (x86, x86-64, ARM too would be reasonable).

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

#330

Post by yetanotherjosh »

joe_the_user wrote: post #58
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 generally agree about avoiding cleverness in code. But this particular finesse isn't necessarily about extra cleverness. Here the situation is that all the linked-list nodes look the same and can be/should be treated the same. The reason the first bit of code has to treat "head" differently is that head is the only node that the rest of the program keeps a pointer to. But that should be incidental, by doing the ope…

> you should do things uniformly, since the linked list has a uniform structure

Except that it actually isn't uniform, is it? A linked list has three kinds of nodes: the first node (to which nothing points), the middle nodes, and the last node (whose next pointer is null). Nulls vs populated values really do change the shape of data. Any code to handle a list needs to be well aware of those three cases, even if there's no IF statement for them. I would argue that having code that is organized around these actual differences is better than trying to normalize those differences into a single thing, at which point those meaningful differences risk being overlooked in code maintenance. At a minimum, this kind of code needs to really clearly explain why it is doing what it's doing in comments, and how the multiple cases are handled in the streamlined solution.

Post reply on HN