19 ms·

Linus Torvalds' good taste argument for linked lists, explained

• int_19h 6y ago
  Which one required writing an article about to explain?
• abhinav22 6y ago
  Thank you, very well written.
• priyanshuraj 6y ago
  Good post. Not a "show hn" though, is it?
  • dang 6y ago
    Correct—reading material doesn't qualify for Show HN. Otherwise every submission could have "Show HN" on it. We've taken that out of the title now. Submitters: before putting Show HN on a title, please read the rules: https://news.ycombinator.com/showhn.html https://news.ycombinator.com/showhn.html.
    • mkirchner 6y ago
      Author here. Thanks for fixing the title, I should have seen that!
• carstenhag 6y ago
  I don't disagree with it being written well. I don't feel like using C and pointers is helpful for getting the point across. After reading for a minute I realized it's all about pointer and C specific stuff, I am not going to revisit that just for an article...
  • tigerlily 6y ago
    When I interview prospective employees I sometimes ask them to explain the rudiments of linked lists in C.
• gjulianm 6y ago
  Although I liked the 'elegant' code after reading it, in general I would try to shy away from 'elegant' solutions that are actually harder to understand. Unless you are working with high-performance programs, most of the time you don't care about one or two extra branches. It's usually more beneficial to write code that can be easily understood by a future-you or by another person in your team: less time invested in understanding code, more time dedicated to actually fixing issues that matter. If performance becomes an issue, you'll catch that in profiling easily (because everybody here is profiling before trying to improve the performance of a piece of code, right?).
  • kbenson 6y ago
    There's usually a trade off between easiness of understanding and elegance, because elegance usually means "works very well given advanced understanding of the domain, task and tools". You can usually shift the problem a bit and get a bit more of both elegance and easy understanding with a good comment giving the general idea. That isn't to say things shouldn't be laid out and named sanely to make thing obvious where possible, but any time you make assumptions about what someone else looking at your code know or is thinking, you're opening up the future for more bugs. It makes sense to attempt to limit that in some respect. The fact that we have all looked at code and not known WTF is going on and stepped away and come back a little later and it was obvious should be all the evidence needed not to to assume too much about what some other programmer will understand just by looking the code itself, especially elegant code.
  • foobarian 6y ago
    I think this particular case has two reasons the optimization makes sense; first, it's some core kernel code that possibly gets called a ton - so high performance code. And then second, profiling this kind of code is not easy; I don't know what tooling there is nowadays but when I was playing with Linux in the 90s each iteration would involve a reboot, and staring at printk output. So there is a tendency to write code the author thinks is faster - which may or may not be true but is probably likely for experienced developers.
  • eptcyka 6y ago
    The more succint version of that code is easier to read and review and it makes the code surrounding it easier to read and review. The extra conditional blocks are superfluous and take up a lot of lines. This is most definitely not about performance but about coding style.
• macspoofing 6y ago
  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 maintainability and understandability. Your code is going to be potentially maintained years in the future by developers of all levels - make it easy on them by practicing the principle of least surprise. In this case, this means using a traditional implementation of a linked list that most developers would be familiar with.
  • andy_ppp 6y ago
    I totally agree, it’s about proving you’re clever rather than communicating ideas. Maybe for something hard like Linux kernel development this is a good thing but in most cases it just leads to messy code that people can’t understand or follow.
    • m_mueller 6y ago
      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.
      • andy_ppp 6y ago
        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.
        • saagarjha 6y ago
• runawaybottle 6y ago
  How does an interviewer measure good taste? You the interviewer could have been the result of a variety of metrics, none of which are good taste related. Bad taste is endemic in corporate and corporate startups(if you enter the millions in funding budget) for the simple reason that adequate taste is more reliable. Edit: Within 30 seconds this got downvoted by cowards with no response. Enough with lurker culture. Say something.
  • axegon_ 6y ago
    This is actually really easy imo. 1. For people who have worked on open source - just look through their code, their commit and you'll see how they think and operate. 2. If 1 isn't applicable, give them homework, not a test. Give them a very simple but very well documented task. Something along the lines of an authentication system, with password reset which is time restricted, basic encryption and security and that's it. This can be easily achieved in just about any language in several hundred lines of code. But given the adequate amount of time to think it through and develop it, you'll see if they come up with clever solutions to simple problems or a pile of duct tape hacks.
• dvt 6y ago
  > A particularly beautiful outcome is that the implementation has consistent semantics for the edge cases Not sure if this is actually a benefit or not. Edge cases are notoriously hard to debug, so it's sometimes actually nice to have a branch that specifically handles edge cases. Conceptually, it's also much more difficult to wrap one's head around. I would be interested to see how much of the cs101 solution is compiled away and if there are any tangible benefits of being clever here. PS: If the linked list is stored in contiguous memory (if you're using a slab allocator, for example), you can actually be even more clever (I'll leave that as an exercise to the reader).
  • cjaybo 6y ago
    > PS: If the linked list is stored in contiguous memory (if you're using a slab allocator, for example), you can actually be even more clever (I'll leave that as an exercise to the reader). This might be a dumb question, but if list elements are stored contiguously, is there any advantage to using a linked list instead of a data structure that is designed for contiguous storage (something like C++'s std::vector)?
    • matvore 6y ago
      > if list elements are stored contiguously, is there any advantage to using a linked list Storing them contiguously probably implies that you consider "freed" space in the middle to also be part of the contiguous area. Otherwise you can't remove in O(1) time. It is straightforward to maintain a list of freed nodes which you can add back later. If you don't mind not being able to remove in O(1) time, you still have the advantage of passing the handi-capped (contiguous) linked list to interfaces that expect a linked list, but still get the cache locality of a plain vector.
• axegon_ 6y ago
  I gave a lot of thought on that example when I first watched the video many many years ago. And I think it all comes down to experience and it has far less to do with good taste. To a junior developer the first solution is perfectly valid and easy to read for everyone. And it is true to a certain degree. But it takes some experience and sooner or later you start getting this feeling that doing something like this probably has a simpler and easier solution, for after all, this is a common thing. Once people wrap their head around that concept(the "surely I'm not the only one that's faced that" thought), they start finding it very easy to jump between languages and learn new ones with ease.
  • setr 6y ago
    Another aspect is that as a codebase develops, memes inevitably appear; patterns and strategies that replicate themselves throughout the codebase. The elegant utility may be difficult to deal with standing alone, but when you see it 2,3,4 different places (by same author, or mimics) it becomes normalized, and once normal there’s really no reason not to use it. The main problem with clever code is when it stands alone. Which is also the context in which these debates occur.
• geophile 6y ago
  I agree that the if-less solution is more elegant, but I was surprised at the way it was achieved. I was expecting to see head implemented as an IntListItem. I.e., an empty list would be just the head IntListItem, with next = NULL, and value undefined. I believe that this approach has the advantage of being clearer. Admittedly, one drawback of this approach is that it uses more space, which could be an issue in an application where you have many lists, nearly all empty.
  • xiphias2 6y ago
    There shouldn't even be an IntListItem type, just IntList, or it could be typedef-ed to make the API clearer. In that case there no need to be for special case, and NULL is the empty list.
• crazygringo 6y ago
  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 brain naturally thinks about it, so it leaves me with the uneasy feeling "what if there's a bug?" and I'd be more worried someone else would introduce a bug if they had to modify it later. I don't want "elegance" or "good taste" in code. Unless it has a good reason to be hand-tuned for performance, I want code that is written the way you'd expect an average programmer to write it. Nothing clever, just a straightforward translation of requirements into code. Not "transforming" them into something more "elegant".
  • foobarian 6y ago
    In case of the optimized version, I would have liked to see comments explaining how much faster it was vs. the obvious one in a profiling experiment, and see it accompanied by a unit test to take care of the "what if there is a bug" concern.
  • toast0 6y ago
    > so it leaves me with the uneasy feeling "what if there's a bug?" The second solution takes me a bit longer to wrap my head around, but once I do, I like it more, because there's fewer conditionals, and so there's less chance that the function breaks on unusual conditions. Using fewer local variables is also a nice plus.
  • billsix 6y ago
    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-and-processes-with-clone/ https://eli.thegreenplace.net/2018/launching-linux-threads-a...
• nemetroid 6y ago
  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 = entry->next; } remove_list_entry(entry) { // The "indirect" pointer points to the // *address* of the thing we'll update indirect = &head; // Walk the list, looking for the thing that // points to the entry we want to remove while ((*indirect) != entry) indirect = &(*indirect)->next; // .. and just remove it *indirect = entry->next; }
  • brainwipe 6y ago
    Thank you, I found that much easier to read than the article posted.
    • m463 6y ago
      Much clearer when read as Linus intended. Reminds me of the editor(s) who helped "fix" bukowski's poems
      • greenkey 6y ago
        I’m not a fan of everything Bukowski wrote, but I wouldn’t try to censor him so that little Jimmy could read it, and I liked the movie Barfly. Similarly, I’m not a fan of everything Linus wrote, but I wouldn’t enforce bad CS101 code on him so that little Jimmy could read it, and I like Linux.
        • aksjfnkajsnd 6y ago
          Who is little Jimmy?
• smitty1e 6y ago
  This seems like the classic argument of whether approaches like Duff's Device[1] are a good implementation idea. I would offer that there is no shame in doing something a bit more advanced, as long as there are test cases and documentation proportional to the advanced nature of the technique available. [1] https://en.m.wikipedia.org/wiki/Duff's_device https://en.m.wikipedia.org/wiki/Duff's_device
  • jcranmer 6y ago
    Duff's device is a bad idea in modern code, because it's effectively a sign to compilers saying "Hi, please don't optimize my code or this loop in any way." In general, microoptimization of code to produce particular assembly sequences is a bad idea, because the actual assembly the compiler generates is only loosely related to the actual code.
• m4lvin 6y ago
  The second version seems more elegant but will scare non-C people away with all those pointers ;-) What I do not understand is why one should use an "IntList" struct in the first place? As the explanation of the second method suggests, a List is the same thing as a pointer to its first element, so why not do this?: typedef struct IntListItem* IntList; Also, could it be that both methods fail terribly (infinite loops?) when they are given wrong input such as elements not in the list at all?
  • MauranKilom 6y ago
    > Also, could it be that both methods fail terribly (infinite loops?) when they are given wrong input such as elements not in the list at all? You could just say "has undefined behavior unless target is an element of the list". Whatever your choice though - this is slide code. It should be obvious that it's not production ready.
  • Animats 6y ago
    Um, yes. That jumped out at me. If there's a no-find, the code will de-reference null and crash. That's just not acceptable. Try to write that in Rust, using Some(ref) for the forward link, and the compiler will force you to test for None and detect the end of the list. This is pre-1990s programming style. I've seen such code in assembly programs. Because I was reading crash dumps where it failed.
    • souprock 6y ago
      It's 100% acceptable. You should not remove something from a list unless you know it is there. Since you won't attempt to remove something that doesn't exist, any code to check for that situation is an unjustified performance loss. (separate code exists for searching a list) This... is not Python. C programmers, particularly kernel developers, have that style even in 2020.
      • Animats 6y ago
        I hope not. Kernel programmers need to be paranoid. This is a classic idea for doubly linked lists. The empty list has the head element linked to itself in both directions. Buffer rings are sometimes organized that way. The cases for doubly linked lists are messier. Bear in mind that in modern CPUs, branches to nearby code are almost free, but indirection to far memory is expensive.
• wanderer2323 6y ago
  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 Next {get;set;} } class IntListItem : IListItem { int Value {get; set;} IntListItem Next {get; set;} } class IntList : IListItem { IntListItem Head {get; set;} IntListItem Next { get { return Head; } set { Head = value; } } } then our cs101 code simplifies itself, folding into a prettier algorithm: void remove_cs102(IntList l, IntListItem target) { IListItem p = (IListItem) l; while (p.Next != target) { p = (IListItem) p.Next; } p.Next = p.Next.Next; } the use of indirect pointers was masking the real issue: some algorithms look better if you add a virtual head (or a virtual tail) to your linked list. Emphasis on look though -- they work almost the same.
  • ghusbands 6y ago
    You've just introduced the extra indirection of virtual function pointers, perhaps through an extra indirection layer of interfaces, which will be a big performance hit, so you've hardly hit upon the "real issue".
  • scscsc 6y ago
    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.
    • wanderer2323 6y ago
      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.
• maweki 6y ago
  I think what's missing in the mental model of the elegant solution is, that the IntList-pointer does not point to a complete list or an element of the list, but to a tail of some list (that might be the complete list). This explains why the head is not really a special case, as it points to the tail that is complete. And you can just exchange a tail. So I think the image with the blue boxes is misleading and it should be ->[4->[12->[3->[6->[2->[]]]]]] It is now obvious that you can always point -> to a different [...] And as it turns out, that is basically the Cons/Nil view of a list from functional programming or lisp, if you're so inclined. And in those languages you would pattern match on the constructor once and do the tail-recursive call.
  • dhanna 6y ago
    Right, I think the key insight is that the special case is simply unnecessary if you have the abstract model of the data structure correct. A linkedlist is just x::xs. The c code being weird is more of an implementation detail that shouldn’t be of much focus.
• mrloba 6y ago
  Maybe slightly off topic, but.. I don't think this is really about taste. It's about "common ground" between programmers. If you've seen and used the second pattern many times before, it becomes part of your vocabulary. You're then able to express yourself more succinctly. It is then obviously a better solution to you. If you see another programmer use the same pattern, it is common ground between you, and you like it. As long as every or most programmers on the team share the same common ground, you are more effective for using it. If you don't share it, you're less effective. Everyone here commenting that they like the first solution better probably doesn't share the necessary common ground with Linus. The big question is: what common grounds should you expect when writing your code?
  • xorcist 6y ago
    Also it's the other way around! Using common idioms builds culture how we structure our code. Then that common culture help make the idioms part of the shared vocabulary. Working with such a large piece of code as the kernel, it's invaluable to have a certain sense of shared ideals how the code should read, and it's probably a good thing to have maintainers that nitpicks about such details. People sometimes say things like "just a matter of taste" as if that somehow made it less important, but taste is probably the most important trait we can share when programming.
  • galoisgirl 6y ago
    The same argument was made recently about the reduce function: it's a known pattern for some and a hard to understand trick for others.
    • jraph 6y ago
      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!)
      • 6y ago
• seanwilson 6y ago
  I used to ask during interviews to just describe what a linked list was and less than half the candidates for mid/senior positions could. I think it's a really revealing question. Same with hash tables.
  • temac 6y ago
    Switch to B-Trees if you ever need to reject all candidates :P (And astonishingly, a comprehensive description of them including the tools for complexity analysis in a form practical for real-world implementers - not just CS student writing toy exercise projects - is very hard to find.)
• warmfuzzykitten 6y ago
  The trick employed by the "good taste" solution is to ignore the type of the object containing the pointer, which is different for the head, and focus only on the type of the object pointed to, which is the same for all the pointers. This frame of reference shift makes the solution look tricky to people unaccustomed to working with pointers, or languages in which pointers are not explicitly represented. It is also not quite true, as the pointer in the last element in the list does not point to a list element.
• btilly 6y ago
  Most people prefer the first over the second. But I think that Linus really should prefer the second over the first. Let me try to explain why. There is a well-known saying attributed to David Wheeler, "All problems in computer science can be solved by another level of indirection." Except the problem of having too many layers of indirection. Also both quotes are often seeing with "abstraction" instead of "indirection". There is a not well-known saying that you can attribute to me, "Any method of abstraction that you have internalized becomes conceptually free to you." (So for the sake of others, choose wisely which you will expect maintenance programmers to have internalized!) The key to the elegant solution is understanding how to manipulate data through pointers. That makes the elegant solution inappropriate to use in CS 101. It involves a method of indirection/abstraction that is emphatically NOT free to beginning programmers. It also makes the elegant solution inappropriate for most people on HN. We do not directly deal with manipulating things through pointers very much. Therefore most of us have not internalized how to do that, and the technique is very much not free to us. However Linus is a kernel developer. Anyone maintaining his code will also be a kernel developer. Kernel developers have to internalize how to handle manipulating data through pointers because their APIs require it. For example look at https://www.kernel.org/doc/html/v4.14/filesystems/index.html https://www.kernel.org/doc/html/v4.14/filesystems/index.html and see that pretty much every function gets a pointer to a data structure, and then manipulates that data structure through the pointer. Therefore every kernel developer should internalize how to manipulate data through pointers. And the elegant solution therefore becomes not just less code, it becomes conceptually simpler! And yes, any time you can replace a block of code with less code that is conceptually simpler, this shows good taste. BUT, and this is very important, it is only conceptually simpler if you've already internalized concepts around manipulating data through the indirection of a pointer. Which makes it conceptually simpler for kernel developers like Linus, but not for most programmers in other languages.
  • jariel 6y ago
    You make a very good point, and that it has to do with the relative foundational conceptualisational ability of the types of mainteners. That's great because it kind of speaks to the crux of the problem. But the first solution does use pointers :) The second uses double pointers. I'd argue that 'even kernel maintainers' may not be so easy with the second in reality. It's probably worth it if there is a performance gain, because it's so low level. But not otherwise. But good point.
• baby 6y ago
  This is great, I often run into these type of things in Rust where an unwrap() is used when there doesn't need to be if you refactor the code correctly. EDIT: interestingly, I see a lot of comments here focusing on the reduction of lines of code (LOC). But IMO, the solution would still have been deemed "better code "if it had increase the LOC instead of reducing it. The idea is about eliminating edge-cases, not about reducing the number of LOC.
• danielg0 6y ago
  Computerphile has a video showing a nice visual explanation of this technique, albeit for inserting values into a linked list rather than deleting them. https://youtu.be/0ZEX_l0DFK0 https://youtu.be/0ZEX_l0DFK0
• userbinator 6y ago
  Linus isn't the first nor only person to discover this simplification, although I've usually encountered it as a "virtual head" using only a single indirection: https://news.ycombinator.com/item?id=18997420 https://news.ycombinator.com/item?id=18997420 It's interesting to see how divisive the opinions are. I see it as the difference between the "growth mindset" and not.
  • Animats 6y ago
    Isn't it in Knuth, vol. 1?
• whack 6y ago
  This sounds like a classic case of "simplicity is in the eye of the beholder". If you're someone who has experience with, or can easily grok concepts such as "pointer to a pointer", then the second snippet seems obviously simpler. After all, there are fewer branches to consider. Unfortunately, as someone who stopped working with pointers a long time ago, my mind has to work in overdrive to understand any implementation that relies on a "pointer to a pointer". Hence why the first implementation is far easier for me to understand. I'm sure we'll see many debates around which solution is simpler, but these debates will never reach a resolution. Depending on the skills and experiences you bring to the table, different people will objectively benefit from very different implementations. https://software.rajivprab.com/2019/08/29/abstractions-are-in-the-eye-of-the-beholder/ https://software.rajivprab.com/2019/08/29/abstractions-are-i...
• jraph 6y ago
  I've seen this presentation, and if I remember correctly, this example was more an attempt to convey what good taste can relate to, more than a definitive answer on whether the second is actually better than the first. Many comments here are arguing that the first answer is actually better because it is clearer. I think it feels clearer to many of us not because it is actually simpler, but because it is the one we learnt at school / are used to see and therefore know by heart. Linus is probably aware of this and may have meant to surprise the public with the second solution. Why the second solution is better? Not because it does less branching and is more efficient. This misses the point. Not because there are fewer lines of codes and is terser. This also misses the point. Fewer special cases means less ways to screw up, and also easier to follow. In the general case. Not only in this specific linked list example. And also clearer code. It's just that in this specific case, we are used to the first solution that we are able to recognize at a glance (we "pattern-match" it). Do you remember when you had to grasp this first solution the first time you encountered it or tried to write it? Many of us probably screwed it up and wasted time making it work. We might have forgotten the exact edge case Linus Torvalds was pointing out in this presentation. At least for me, I remember it was hard. I probably would have had easier time understanding the second solution by the way. The difficulty is a pointer indirection, but you better really understand pointers correctly when you are manipulating linked lists in C anyway. Comments here also speak about leaving maintainable code for future developers on the project and avoid clever solutions to make their life easier, but it is the whole point of the second solution: let them not have to think about edge cases as much as possible. Don't stop on this linked list example. We are all used to the first solution and Linus Torvalds probably picked this example because many people know linked lists. The message is: fewer edge cases is better. The goal is not to be "clever", in the negative sense. Also see the original code with comments, which is way more readable: https://news.ycombinator.com/item?id=25327066 https://news.ycombinator.com/item?id=25327066
• loopz 6y ago
  > [...] I don't want you to understand why it doesn't have the if statement. But I want you to understand that sometimes you can see a problem in a different way and rewrite it so that a special case goes away and becomes the normal case, and that's good code. [...] -- L. Torvalds I think the idea of this extends much beyond a linked-list implementation, into software design and architecture. Sometimes, you find more elegant solutions to something, that inherently do away with edge cases. I think this is the original intent, to show that you can find beauty, much as chessplayers do in chess. These solutions may be harder to understand completely, but you can actually encapsulate them in a function or use them as patterns! A point is also made, there's often a rewrite involved. You usually don't need to find this stuff on first try.
• andy_threos_io 6y ago
  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 remove_elegant: ldr r2, [r0] cmp r1, r2 bne .L12 b .L13 .L14: mov r2, r3 .L12: ldr r3, [r2, #4] cmp r1, r3 bne .L14 add r0, r2, #4 .L13: ldr r3, [r1, #4] str r3, [r0] bx lr remove_elegant_with_inline: ldr r2, [r0] cmp r1, r2 cmpne r2, #0 bne .L17 b .L18 .L19: mov r2, r3 .L17: ldr r3, [r2, #4] cmp r1, r3 cmpne r3, #0 bne .L19 add r0, r2, #4 .L18: ldr r3, [r1, #4] str r3, [r0] bx lr EDIT: Hmmm, so much downvote without any reply. Well if your code needs an article to be explained, rather than the plain solution and brings nothing, even 1 instruction slower, as the compiler can't make the same (faster) result as the plain solution, than your code is pointless. And stating that this is the elegant solution is IMO bad practice.
  • sltkr 6y ago
    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 compiler can generate equivalent code for them, up to an instruction more or less. The bigger concern here is about the source code: how can we express the algorithm in the most elegant (think: clear, concise, and correct) way? The exact generated bytecode is irrelevant, so long as the compiler is able to generate something reasonable, which is clearly the case here, as you've demonstrated.
• GnarfGnarf 6y ago
  Been programming since 1965. Strongly object to #2. I respect the cleverness of Linus' solution. However, it really has no place in production code where not all journeymen are at the same lofty level. The fact that it requires a detailed explanation exposes its impracticality.
• jariel 6y ago
  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.e. a pragmatic performance optimization that was realized in the real world, due to the pervasive utilization of the code ... this would be acceptable. But for the vast majority of what we do, this won't be the case. Double-pointers are like flame throwers - they are very 'cool' to some, and technically, they do 'burn things faster', but are just excessively dangerous and almost assuredly not the right too. Unless, they actually are, wherein you get to be the dude who uses the flamethrower, but again, that's rare. Reading this it seems more clear to me why git has such tremendous - and mostly unnecessary UX problems. There's a dimensionality of the craft being ignored.
  • souprock 6y ago
    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.
    • jariel 6y ago
      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.
• bfung 6y ago
  To relate this topic back to Computer Science and Math, the linked list traversal problem can be related back to Proof by Induction -- There's a base case (a starting condition) and then the inductive steps: "...proves that if the statement holds for any given case n = k, then it must also hold for the next case n = k + 1" We can prove using proof by induction that Linus's implementation works because of the base case "indirect = &head", and the inductive step which is the rest of the program. It'd take a lot more work to mathematically prove that the branching program "works" due to the if statement -- you'd have to construct a proof of each branch and prove that the combination works. I'm not a mathematician, but this was a major point in CS courses at university. Being able to prove an algorithm works can extend into automated program checking / auditing, etc. It's not just "taste" -- there's a lot of practical theory to be applied. https://en.wikipedia.org/wiki/Mathematical_induction https://en.wikipedia.org/wiki/Mathematical_induction
  • landhar 6y ago
    I think this hits the nail in the head. Lots of comments here seem to dislike option 2 on the basis that it’s a “clever trick” and that those should be avoided for reasons of readability and maintainability. But this second approach would be the _right_ answer in a exam about algorithms, and that’s what Linus is really hinting at here.
    • Rexxar 6y ago
      Indeed. It also show us that using "good taste" or "code smell" arguments are wrong because there should always be good technical reason to justify the choice. Sometimes we have the good intuition and the technical is hard to express but we have to try understand why we think something is good taste and express it in a technical way. Arguments on good taste will always finish in ego fight when people disagree.
• vaxman 6y ago
  Congratulations on THE stupidest post of 2020! Linus Torvalds on linked list, stop the presses!
• BMSmnqXAE4yfe1 6y ago
  Both algos will crash if the target is not on the list, so both are equally bad :)
• furyofantares 6y ago
  These functions can be thought of as two steps: 1. Find the thing to update 2. Update it Linus's version does just that. But the first version is more complex because step 1 instead emits something that may or may not be the thing to update, and so step 2 has to reason about that. Additionally, it introduces a bookkeeping variable -- cur -- which becomes redundant before step 2 (by which point it's equal to target). IMO Linus is right here. The form of his solution directly matches the problem and allows you to look at the code as two clean steps -- no reasoning about the output of the first step and no bookkeeping cruft variable that you have to ignore or remind yourself that it's the same as another variable after some point in the function. At least once you're used to working with double pointers I think that's a much easier function to read.
• trhway 6y ago
  >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.
• phkahler 6y ago
  I have an odd structure that links objects into "boxes" where each object can be in more than one box and each box can contain multiple objects. I made a struct to link an object to a box via a pointer to both the object and the box. These links are each part of 2 lists, one from the object and one from the box. The main job is to find all the objects in a given box, which is done by following the list from the box. To delete an object involves following the list off the object and removing all the links - each of which is in a list from a box. Each link needs two next pointers since it's part of 2 lists. It also needs a PREV pointer for the list from the box for easy deletion. I originally had an empty link object within the box object to be the previous node, but then realized a better way was to have the PREV pointer point to the previous NEXT pointer which means a box only has a pointer instead of a link. This pointer is why I decided to post. Lastly my link object contained 5 pointers, so I XORed the object and box pointer to cut it down to 4. I always start traversal from one of those, so the XORed value can always be used to reach the other. This did not really impact performance much.
• brundolf 6y ago
  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 gaining an intuitive grasp on the second solution, which could potentially nullify the bug-resistance of having fewer branching cases. In short, calling the second one objectively better is overstating it I think. It's worth noting that in a language with union types, you can have the best of both worlds (using Rust here because it's the one I'm most familiar with): enum LinkedList { Null, Node { value: i32, next: Box<LinkedList> } } In the same way that the pointer to a pointer homogenizes the head-case with the rest, a union type means that any given linked list "is just a node", and the head can therefore be treated the same way as any later node
  • vips7L 6y ago
    Wouldn't you end up with a Box of Null? Wouldn't it be better to: struct Node { value: i32 next: Option<Box<Node>> }
    • brundolf 6y ago
      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<Node> or something), so we're back to square one. Maybe I was wrong and this can't be done perfectly even with union types.
      • vips7L 6y ago
        In that case wouldn't you just: struct List { head: Option<Node> } struct Node { value: i32, next: Option<Box<Node>> }
        • brundolf 6y ago
• jonahx 6y ago
  Good article. The key insight was a bit buried though: By using the pointer to the current element, you lose information (that element's ancestor), forcing you to introduce a "prev", and to track and update 2 variables. By using a pointer to the pointer of the current element, you have access to all the information you need -- the "prev" and the "cur" -- just by following the pointer trail one or two steps.
• defaultcompany 6y ago
  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.
  • javajosh 6y ago
    Neat idea, but yeah like you say you break referential integrity pretty hard with this solution. And tbh I feel like everyone prefers tons of local links in their data, and since we have memory to spare with wasteful representations, we pick the convenient, link heavy one, a world in which this algorithm variant does not apply.
• T3RMINATED 6y ago
  Linus is a sore loser. Dont ever post anything from him.
• ajarmst 6y ago
  I've been teaching CS101 for two decades. I've never shown (nor seen another instructor show) a two pointer implementation for list traversal, except perhaps as an example of bad practice (probably by someone who doesn't understand the syntactic sugar of the -> operator). "Every pointer to node is a list, including the trivial case of a null pointer being an empty list" is the way I was taught in CS101 in the early 80s, including a one-pointer implementation of this algorithm in Pascal. I suspect this might a case similar to that of the "Waterfall Method", where we have this unexamined belief that in olden times or academia they just weren't capable of comprehending really obvious things. CompSci instructors, and most of their students, are quite capable of recognizing that two pointers aren't needed, if only because every algorithms textbook they've ever read discusses it. I think that this might be like Bubble Sort: it's discussed in class as a way of illustrating a point. In students' fuzzy memories of school, they remember that bubble sort and 2-pointer traversal were taught, but they forget that they were taught only to show why selection sort and single pointer ("look ahead") traversal are better algorithms. As a side note: I don't like the "elegant" version's use of double indirection. It's not necessary if you return a pointer instead of void, which is also nice because you can treat calls to your list functions as lists themselves and chain them together. It also allows you to avoid warts like `p = &(*p)->next;` at the modest cost of needing `p=remove(p,t)` instead of `remove(p,t)`. Finally, the use of two structs is unnecessary. IntList is just a wrapper around a pointer to IntListNode. Why not just use a naked pointer to IntListNode like the gods intended?
  • xpe 6y ago
    > Finally, the use of two structs is unnecessary. IntList is just a wrapper around a pointer to IntListNode. Why not just use a naked pointer to IntListNode like the gods intended? So Say We All.
  • xpe 6y ago
    > As a side note: I don't like the "elegant" version's use of double indirection. It's not necessary if you return a pointer instead of void, which is also nice because you can treat calls to your list functions as lists themselves and chain them together. Agreed. > It also allows you to avoid warts like `p = &(p)->next;` Does it? Isn't having `p = &(p)->next;` in the while loop necessary? > at the modest cost of needing `p=remove(p,t)` instead of `remove(p,t)`. I may disagree since an API is used many more times than the API function is written.
• ExcavateGrandMa 6y ago
  Now you can tell ya surrounding you are a programmer :Ð MOUHAAAAAAAAAAAAAAAHAHHAAHAHAH!
• fnord77 6y ago
  2013 - stop using linked lists: https://news.ycombinator.com/item?id=5751702 https://news.ycombinator.com/item?id=5751702
  • adwn 6y ago
    Your knee-jerk reaction is misplaced. There are valid use cases for intrusive linked lists [1]: a) When your nodes can belong to multiple lists. You can't do this with arrays. b) When you need fast removal from the middle of the list and you already have a pointer to the list node [2]. [1] In an intrusive linked list, the prev/next pointers are members of the payload node, as opposed to a "simple" linked list, in which the list nodes contain a pointer to the payload. [2] This happens all the time in kernels. For example, you receive an interrupt and need to remove the corresponding task from the IDLE queue and append it to the RUNNING queue.
• deleted 6y ago
  [deleted]
• avodonosov 6y ago
  The most elegant way, imho, to join collection elements into a comma separated string: http://avodonosov.blogspot.com/2012/01/maybecomma.html http://avodonosov.blogspot.com/2012/01/maybecomma.html
• keyle 6y ago
  off topic, I've enjoyed the talk referred to https://www.ted.com/talks/linus_torvalds_the_mind_behind_linux https://www.ted.com/talks/linus_torvalds_the_mind_behind_lin...
• zgs 6y ago
  I've seen the "better" version a few times before. I wrote something equivalent from first principles. It is NOT better. It is much more difficult to understand. Software engineering is about making the code intelligible for the people who follow you. The simple two pointer with conditional is MUCH easier to read and understand.
• zgs 6y ago
  Why not the concise version? for(p=NULL,q=head; q!=entry;p=q,q=q->next); *(p?&p->next:&head) = q->next;
  • oblio 6y ago
    Because we have big, high resolutions screens and we don't "list" (i.e. print) our source code anymore?
• franzwong 6y ago
  List of nodes vs List of pointers Data node with pointer vs Pointer node with data Sometimes I improved my code a few days after I wrote them, because I found another interpretation of the original problem.
• Mikhail_Edoshin 6y ago
  Solutions that feature extra levels of pointing naturally arise in many cases. E.g. you search some data structure for an element. Initially you may do this so that the search returns the element itself or NULL if it's not found, but then you realize you'll also need to use the same searching logic to insert and delete elements. In this light you rewrite the search to return a pointer to the location instead; this way you can use it as a subroutine for all the operations.
• ankurdhama 6y ago
  The second solution may not be obvious at first but the idea is that in the first solution you are finding the node that needs to be removed whereas in the second solution you are finding the "next" of a node that points to the node to be removed.
• nirui 6y ago
  So, as I gathered from this, Torvalds's solution takes advantage of the fact that the element scan is always started from the head, while the cs101 solution treats the head as a special case? Both are smart IMO.
• antirez 6y ago
  Can't forget the Linux kernel VFS interface of 20 years ago, designed by Linus. It was one of the worst abstraction I ever worked with. Linus is a genius, but not the kind of genius that is able to make things obvious and clean.
  • oblio 6y ago
    Some would argue that the git UI falls into the same category.
• mkirchner 6y ago
  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 article is not intended to show an example of clean code, there is no checking for NULLs, there are implicit expectations (the target needs to exist). It's just not the point. I also strongly agree with the sentiment in the discussion that simple is often better than elegant. If it takes an entire article to figure out what's happening, that says something about how careful you should be with putting it in production code. Anyways, thanks everyone on HN for a great discussion and for all the insights, comments and suggestions!
  • dhanna 6y ago
    FWIW, I think you get way more correct than some of the comments here give you credit for.
• totorovirus 6y ago
  I seriously don't understand why this elegant example is a 'clever' code at all. It is just much easier to understand.
• pwdisswordfish4 6y ago
  What Torvalds made is not a good taste argument for linked lists — he made a linked list argument for good taste. Or rather, a linked list argument about what good taste means. I assume the author of this article had spent too much time being confused by the ‘Windows Subsystem for Linux’ nomenclature.
• deleted 6y ago
  [deleted]
• cNHciFHqCmd 6y ago
  The elegant solution has two instructions less, but they are outside the loop. The performance difference is most likely minimal, no branch is eliminated. https://c.godbolt.org/z/fdh461 https://c.godbolt.org/z/fdh461
• hadcomplained 6y ago
  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 than both of the first and second examples presented in the article. Does that mean my taste is peculiar?
  • haskman 6y ago
    This is exactly the right answer. There are two cases here (1. when the target is at the front of the list and necessitates changing the head of list, and 2. when the head doesn't need to be changed.) You handle both the cases separately. Both the classical and the "elegant" versions are worse than this one.
    • mjburgess 6y ago
      Linus' point is that this way of thinking produces this "edge case". There is no "head case", all members of the list are the same. The head isn't a special element.
  • arh68 6y ago
    I kinda like this version best. It makes clear we're updating a ->head pointer in one case and ->next in the others. I like the elegant version, too, since it can update both kinds of pointers in one fell swoop, but you have to grok that p starts as a head pointer and later becomes something's next pointer. I'd say C syntax for double pointers is a lot less kind than the syntax for single pointers. Your version thankfully lacks any line like so, without making me think about parens p = &(*p)->next;
  • goldsteinq 6y ago
    Your version does a lot more memory writes.
• bnastic 6y ago
  This keeps getting reposted/rehashed regularly. And the code is there for those wanting to look into system include headers, like sys/queue.h (I haven't actually checked for chicken and egg scenario in commit history of various libc implementation, but would hope that double pointer has always been there)
• buserror 6y ago
  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 mind at all) on the other hand it is type safe, has quite a few variants for single and double lists, and oh also, it's not GPL. [0]: https://github.com/freebsd/freebsd/blob/master/sys/sys/queue.h https://github.com/freebsd/freebsd/blob/master/sys/sys/queue...
  • agapon 6y ago
    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;
• red_admiral 6y ago
  The "avoid special cases" argument comes up a lot in math too. For example in combinatorics, some people define 0^0 = 1, so that lots of formulas with "if x == 0 then this else that" just collapse into "that". (Other people insist on inventing a different symbol for this "special exponentiation", but I think that's unnecessary myself.) For the same reason, an empty sum is defined as 0 and an empty product as 1, so your base cases of some inductions don't require an extra "if".
• Upvoter33 6y ago
  I remember reading Sedgewick's algorithms book long ago. As I recall, he always suggested using a dummy node as the first entry in a list, which removed basically all head-based edge cases. But yeah, Linus's approach is pretty neat, esp. for fans of C.
• DonHopkins 6y ago
  Back in the 80's, I learned Pascal, and learned about its dynamically allocated records, then I went on to learn C, and got used to its pointers and arrays. Then I went back to Pascal, and designed a program in my head with some dynamically allocated linked list data structures, and another data structure that had a member that pointed to the head of the linked list. Then I started typing in the Pascal code, and hit a wall, because Pascal has ^ which is like C's * operator to dereference a pointer, but doesn't have anything like C's & operator to make a pointer to an arbitrary field in memory, so you can't actually make a pointer to anything except the beginning of a record that you dynamically allocated! That was when I gave up on Pascal. Programming Pascal is like riding a bicycle with only one leg.
  • augustk 6y ago
    Most programming languages don't have an "address of" operator. That's because it's a potentially unsafe operation. I think your usage of Pascal sounds more like trying to operate a motorcycle like a bicycle.
    • DonHopkins 6y ago
      Pascal has what it call pointers, but doesn't have what C calls pointer arithmetic, or a way to take the address of any field of a structure or any element of an array. So Linus's elegant linked list solution is possible in C, but not Pascal. I don't get your metaphor that Pascal is a motorcycle and C is a bicycle. Just the opposite.
  • benibela 6y ago
    That must have been a very old Pascal Nowadays there is the @ operator
    • DonHopkins 6y ago
      Yes, very old Pascal, not even TurboPascal! I started with Apple ][ UCSD Pascal, but that program was for HP3000 Pascal, which might be even older. There was a trick for doing PEEK and POKE in Apple Pascal, using a union that contained a pointer to some type you could dereference to read and write, and also an integer so you could set the pointer. I had the hardest time understanding it, and just could not get my head around the "record case boolean of", but I just typed in the magic code with a bunch of weird ^'s and it worked somehow. You can use type punning tricks with "union" to implement arbitrary unsafe pointer arithmetic in Pascal, since it lets you convert between pointers and integers. https://en.wikipedia.org/wiki/Type_punning#Pascal https://en.wikipedia.org/wiki/Type_punning#Pascal Here's an article about that trick, in German (which makes it sound even cooler): https://www.robert-tolksdorf.de/book/Tolksdorf-UCSD-Pascal-CC-BY-NC-ND-4.0.pdf https://www.robert-tolksdorf.de/book/Tolksdorf-UCSD-Pascal-C... p. 63: 3.1 "PEEK" und "POKE" auch in Pascal [...] type byte = 0..255 spchrinhalt = packed array [0..0] of byte; spchrstelle = record case boolean of true: (adresse:integer); ( Zieger ) false: (inhalt:^spchrinhalt) ( Inhalt ) end; procedure poke(adresse:integer; inhalt:byte); var dummy:spchrstelle; begin dummy.adresse := adresse; dummy.inhalt^[0] := inhalt; end; function peek(adresse:integer): byte; var dummy:spchrstelle; begin dummy.adresse := adresse; peek := dummy.inhalt^[0]; end;
• vorhemus 6y ago
  Good code is code that everyone in a team can understand, safely modify and maintain.
• kasajian 6y ago
  Better link: https://gist.github.com/santisbon/42580049705ba3d8fbef7168e4668e3c https://gist.github.com/santisbon/42580049705ba3d8fbef7168e4...
• ho_schi 6y ago
  I knew I have seen this code somewhere explained years ago and suspected Slashdot. Search for "favorite hack": https://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions https://meta.slashdot.org/story/12/10/11/0030249/linus-torva... Here using actually "pp" ;)
• lostmsu 6y ago
  item** find_parent(item** list, item* item) { item** potential_parent = list; while(*potential_parent != item) { potential_parent = &(*potential_parent)->next; } return potential_parent; } void remove_item(item** list, item* item) { item** parent = find_parent(list, item); *parent = item->next; }