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

331–339 of 339 posts

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

#331

Post by jraph »

doubletgl wrote: post #295
jraph wrote: post #70

Earlier quoted context omitted.

Yes, and you get used to reduce. map, filter and reduce were hard for me to follow… until I used them two or three times and now I understand them easily and they naturally come to my mind when I need to solve a problem which they can help solving. They are good tools (especially in codebases shared with people who are allergic to loop statements!)

Agreed for map, filter etc. but reduce is the exception. There has been a fad of overusing it, until that article popped up which called it out.

I "got" reduce not long ago. It's occasionally handy, and it makes sense, but sure, it should not be overused. It is the most complicated between the three.

A good old loop in code bases that are not afraid of them are totally fine and probably clearer in many cases.

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

#332

Post by vips7L »

brundolf wrote: post #173
vips7L wrote: post #167

Earlier quoted context omitted.

In that case wouldn't you just: struct List { head: Option } struct Node { value: i32, next: Option > }

Yep, but this replicates the original inelegancy (from the article): Option and Option > are not the same type, and so they can't be treated the same way.

I guess you could just allocate the head node on the heap too.

I think rust probably has better tools for this.

Probably some sort of

   let node = node.next;
   while let Some(n) = node {
       node = n.next
   }

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

#333

Post by Thorrez »

ndand wrote: post #326
Thorrez wrote: post #324

Earlier quoted context omitted.

> 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".

I agree:

indirect -> previous next -> first element

"indirect" points to "previous next". "previous next" isn't a list entry. "previous next" points to "first element", which is a list entry.

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

#334

Post by Volt »

billsix wrote: post #164
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 diffe…

> I’m unaware of any other OS which implements threads this cleanly.

I believe this comes from Plan 9.

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

#335

Post by agapon »

buserror wrote: post #258

I used to use linux's list.h quite a bit, that is the "good taste" implementation, where the head is the same as the elements. My only problem with that implementation is the fact it is non-typed. Heads are generic, and the code using them has to use container_of() macros to recover the containing type. I've since discovered bsd/queue.h [0], which is very similar in purpose, but is not "good taste" (which I don't min…

It's also worth noting that in sys/queue.h double-linked containers have an elegant trick where 'prev' is not the traditional pointer to the previous element. Instead, 'prev' is a pointer to a pointer, it's an address of 'next' pointer in the previous element (or the head).

As a result, remove_element() is as simple as *(e->prev) = e->next;

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

#336

Post by scscsc »

wanderer2323 wrote: post #25

Let's draw a list IntListItem -> IntListItem -> IntListItem and then draw the position of the list head: IntList -> IntListItem -> IntListItem -> IntListItem You can see that the if-branch in the cs101 answer comes because there is a ('virtual') element of the list (the IntList head) that is different from the other elements of the list. If we were to make them the same (C# code): interface IListItem { IntListItem Ne…

That looks interesting. The code is not simpler to understand nor is it more efficient, but it seems to work, assuming target is in the list. How would you represent the empty list?

Not sure why you are being downvoted.

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

#337

Post by scscsc »

andy_threos_io wrote: post #68

Pointless and bad article. I compiled the presented code out curiosity on arm gcc 8.2 on godbolt.org with -O3 op and the results are: (the original remove is even faster then the so called elegant or the elegant with inline) remove_cs101: ldr r2, [r0] cmp r2, r1 bne .L3 b .L9 .L6: mov r2, r3 .L3: ldr r3, [r2, #4] cmp r1, r3 bne .L6 ldr r3, [r1, #4] str r3, [r2, #4] bx lr .L9: ldr r3, [r2, #4] str r3, [r0] bx lr remov…

You are probably right regarding speed, but the article is definitely not pointless and bad.

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

#338

Post by scscsc »

sltkr wrote: post #144
andy_threos_io wrote: post #68

Pointless and bad article. I compiled the presented code out curiosity on arm gcc 8.2 on godbolt.org with -O3 op and the results are: (the original remove is even faster then the so called elegant or the elegant with inline) remove_cs101: ldr r2, [r0] cmp r2, r1 bne .L3 b .L9 .L6: mov r2, r3 .L3: ldr r3, [r2, #4] cmp r1, r3 bne .L6 ldr r3, [r1, #4] str r3, [r2, #4] bx lr .L9: ldr r3, [r2, #4] str r3, [r0] bx lr remov…

First, you haven't demonstrated at all that the "elegant" solution is slower. Between `remove_cs101` and `remove_elegant`, it looks like they are equivalent (in particular, the inner loop has the same number of instructions) except the former uses more instructions. Second, I think you're missing the point by focusing on the code generated by the compiler. Clearly the two algorithms are equivalent, and a good compile…

The key here is "it looks like they are equivalent".

In fact, I am not sure they are equivalent (in general, without taking into account the context), and even if they were, proving this would be S.F. for a compiler today (2020). Even coming up with such an optimisation without hardcoding it does not seem plausible.

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

#339

Post by wanderer2323 »

scscsc wrote: post #336
wanderer2323 wrote: post #25

Let's draw a list IntListItem -> IntListItem -> IntListItem and then draw the position of the list head: IntList -> IntListItem -> IntListItem -> IntListItem You can see that the if-branch in the cs101 answer comes because there is a ('virtual') element of the list (the IntList head) that is different from the other elements of the list. If we were to make them the same (C# code): interface IListItem { IntListItem Ne…

That looks interesting. The code is not simpler to understand nor is it more efficient, but it seems to work, assuming target is in the list. How would you represent the empty list? Not sure why you are being downvoted.

The representation of the empty list does not change, it's still an IntList object with a null Head field.

The downvotes probably come from my blatant disregard of the real-world performance in the search of what I considered the real take-away from the article.

Post reply on HN