[HN Gopher] Linus Torvalds' good taste argument for linked lists...
___________________________________________________________________
Linus Torvalds' good taste argument for linked lists, explained
Author : mkirchner
Score : 131 points
Date : 2020-12-06 20:57 UTC (2 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| smitty1e wrote:
| 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
| m4lvin wrote:
| 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 wrote:
| > 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.
| baby wrote:
| 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 wrote:
| 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
| abhinav22 wrote:
| Thank you, very well written.
| userbinator wrote:
| 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
|
| It's interesting to see how divisive the opinions are. I see it
| as the difference between the "growth mindset" and not.
| wanderer2323 wrote:
| 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.
| whack wrote:
| 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-i...
| maweki wrote:
| 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.
| mrloba wrote:
| 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 wrote:
| 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 wrote:
| 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.
| convolvatron wrote:
| this is the big point. when coding alone I strongly prefer
| Linus's version.
|
| but it seems to cause friction and get called out whenever I
| use it in a group environment. so I don't. or I change it.
|
| the code itself isn't important. its about the functioning of
| the group, the velocity, and the ownership.
| priyanshuraj wrote:
| Good post. Not a "show hn" though, is it?
| dang wrote:
| 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.
| mkirchner wrote:
| Author here. Thanks for fixing the title, I should have seen
| that!
| int_19h wrote:
| Which one required writing an article about to explain?
| seanwilson wrote:
| I used to ask candidates to just describe what a linked list was
| during interviews and less than half the candidates for
| mid/senior positions could. I think it's a really revealing
| question.
| jraph wrote:
| 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 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. Actually hard to argue against.
|
| Also see the original code with comments, which is way more
| readable: https://news.ycombinator.com/item?id=25327066
| loopz wrote:
| > [...] 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.
| carstenhag wrote:
| 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 wrote:
| When I interview prospective employees I sometimes ask them to
| explain the rudiments of linked lists in C.
| gjulianm wrote:
| 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?).
| eptcyka wrote:
| 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.
| kbenson wrote:
| 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 wrote:
| 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.
| macspoofing wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| R0b0t1 wrote:
| I was only ever taught the second, more concise one, so this
| discussion is kind of confusing. How is it not shorter and
| more explicit?
| tent3n3 wrote:
| What if someone only ever learns what looks to be too clever
| to you?
|
| You make it sound as if some universal utilitarianism exists.
|
| Everyone's personal event log is going to look just different
| enough to make that unreasonable.
| commandlinefan wrote:
| I've written code like the first example many times, and I
| always felt a little "dirty" for doing it - I could tell
| there _had_ to be some way to avoid treating head as a
| special case, but I was too lazy to actually work out how.
| The author of the second example may be "clever", but he
| also didn't give up.
| zem wrote:
| 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.
| xorcist wrote:
| Fever lines aren't automatically better, but fewer lines means
| less code to maintain. More often than not, fewer lines is
| easier to read too.
|
| The example here is a good one. The shorter version reads much
| better and is more obviously right.
| qualityonly wrote:
| I have one to bring up "for loops".
|
| I think they are infinitely worse than while loops. (I ran
| into this specifically with Pandas dataframes/series)
|
| You save 1 or 2 lines and have ambiguity on wherever "each"
| is.
|
| Maybe static typing solves this, but I've decided I hate
| syntax sugar and dynamic typing.
| baby wrote:
| I think your problem is with C as a language, which can look
| really ugly to the untrained (or trained) eyes, and is way too
| permissible in terms of what you can with pointers and memory
| in general.
|
| But I see this as a paradigm that you can apply in more
| programming languages: you should aim at writing code that
| removes edge-cases. This is not about code reduction in my
| opinion, I would have been equally happy if the code had been
| longer. It's about more secure code: because there is no edge-
| cases to think about.
| joe_the_user wrote:
| 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
| operation indirectly, you do things uniformly, _you should do
| things uniformly, since the linked list has a uniform
| structure_.
|
| Here, it's not much about combining cases overly cleverly, not
| leveraging "while (x=y){...}"-type stuff but removing what is
| an unnecessary kludge; that you have to treat head differently
| 'cause it's the value you happen to have and you need to update
| it while preserving it.
| eloff wrote:
| Looking at the code there are not just fewer lines, but fewer
| conditionals too. It's much simpler to read and understand. I
| got it at a glance, whereas I skimmed the typical approach and
| would still need to go over it more carefully to be sure it is
| correct.
|
| I think Linus is correct on this one.
| jodrellblank wrote:
| > " _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.
| jcranmer wrote:
| 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 curr node_t **curr_ref
| = &head; node_t *curr = *curr_ref; while
| (curr != NULL && curr != entry) { // Advance
| curr_ref and curr curr_ref = &curr->next;
| curr = *curr_ref; } if (curr) { *curr_ref =
| curr->next; } }
|
| Choosing names somewhat more rationally, and making it clear
| that "curr" always points to the current node, and that
| "curr_ref" is the address of whatever pointer we followed to
| arrive at curr, makes it easier to establish the invariant that
| updating curr_ref is sufficient to insert or remove curr into a
| list, no matter if it's referring to the head link of a list or
| the next link of the prior node.
| fsloth wrote:
| I have to disagree. This code is simply concise and elegant.
|
| Generally less code is better, since there are fever lines that
| can have a bug.
|
| While pathological terse code can be obscure - to prove that
| the author is clever - and then it really is a pathology -
| simple terse code is just beautiful.
| erik_seaberg wrote:
| Lines of code are expensive, because we expect human beings to
| reread them with almost no help from tools. Concise code is a
| temporary problem for novices, until they grow into experts.
| Bulky code is an ongoing problem for _everyone_ and we don't
| have a solution.
| Taniwha wrote:
| 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 understandable
| because I already understand it
| varjag wrote:
| It's very unlikely it is faster.
| 0xdeadbeefbabe wrote:
| I completely disagree. Lines of code, long variable names, and
| meaningless hierarchies are some tasteless taxes. Some people
| like each of them(!), and I don't get it.
| tcoff91 wrote:
| 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.
| deanCommie wrote:
| I started reading the article agreeing with you. Hearing Linus
| talk about "taste" made me expect something obscure and
| esoteric, with a marginal performance benefit, and a
| subjective/objective debate about whether the value of micro-
| optimizations at scale throughout the linux kernel adds up to
| meaningful benefits, and if they are traded-off with less
| readable code.
|
| Surprisingly, I ended up in a different spot.
|
| I actually think this is a low-level C-version example of the
| best practice of "use idiomatic language concepts".
|
| When C# first got LINQ, when Java first got Streams, and when
| both got inline anonymous Lambda functions a lot of old-school
| developers resisted both.
|
| "The syntax is confusing!". "The behaviour is hidden!". "What's
| wrong with a good ol'd for/while loop?"
|
| I know because that was my first instinct too.
|
| But I quickly embarced these ideas because they allowed me to
| write more terse declarative code and spend a larger percentage
| of my TLOC on business logic. There was a small learning curve
| to new developers to understand the libraries, but after that
| everyone was more performant.
|
| I feel the same way about C and pointers and address
| manipulation magic. No, it has no place in Java or C#. But for
| C developers, these are their idiomatic principles and
| concepts. Pretending otherwise, and not leveraging all the
| capabilities possible with direct pointer and address
| manipulation is not utilizing the benefits of C to it's full
| potential.
|
| NOTE: I am not a C developer. This is just how this comes off
| to me. I'd love to hear from actual C developers if they would
| say that this is the equivalent of running around with a loaded
| shotgun and languages like Rust have been designed with solving
| these things in mind (or something).
| petergeoghegan wrote:
| It seems to me that what is at issue here is the difference
| between easy to understand and simple. They're not always the
| same thing. Simpler code tends to be easier to audit for bugs
| (as a practical matter).
| andy_threos_io wrote:
| 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:</br> 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
| runawaybottle wrote:
| 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_ wrote:
| 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 wrote:
| > 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 wrote:
| > 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)?
| axegon_ wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| Like others here, I prefer the first.
|
| The first one -- I read it, I know what it does, it seems
| intuitive to understand and expect it to be bug-free. 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 ideas into
| code. Not "transforming" them into something more "elegant".
| toast0 wrote:
| > 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.
| foobarian wrote:
| 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.
| warmfuzzykitten wrote:
| 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.
| nemetroid wrote:
| 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;
| }
| forrestthewoods wrote:
| Perfect. I almost commented to complain that the "elegant"
| version is harder to read and understand. This is much much
| better. Comments are important!
| brainwipe wrote:
| Thank you, I found that much easier to read than the article
| posted.
| [deleted]
| btilly wrote:
| 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 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.
___________________________________________________________________
(page generated 2020-12-06 23:00 UTC)