Linus Torvalds' good taste argument for linked lists, explained

https://github.com/mkirchner/linked-list-good-taste

by mkirchner • 6 years ago

717 326 6 years ago

github.com

abhinav22• 6 years ago

Thank you, very well written.

priyanshuraj• 6 years ago

Good post. Not a "show hn" though, is it?

dang• 6 years 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.

mkirchner2• 6 years ago

Author here. Thanks for fixing the title, I should have seen that!

carstenhag• 6 years 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• 6 years ago

When I interview prospective employees I sometimes ask them to explain the rudiments of linked lists in C.

gjulianm• 6 years 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• 6 years 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.

foobarian2• 6 years 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• 6 years 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.

entropicdrifter• 6 years ago

In general, this is good practice for working on a team.

However, given that we're talking about Linus Torvalds' opinions on what makes code 'elegant' or 'good taste', I'd say it's implicit that we're talking within the domain of low level, high performance code, such as kernel code.

macspoofing• 6 years 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_ppp2• 6 years 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• 6 years 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.

commandlinefan• 6 years ago

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.

R0b0t1• 6 years ago

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?

eloff2• 6 years ago

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.

bigyikes• 6 years ago

Linus’ solution seems to add a layer of indirection, which I think is harder to grok than a simple condition.

ewindal• 6 years ago

Conditionals are so simple it’s basically the first thing anyone learns. Anyone can understand the first approach. The latter requires knowledge that is specific to lower level languages,concepts that are certainly not taught universally.

The latter approach is definitely not the easiest to understand. It is, however, what Linus considers «good taste in coding.»

jodrellblank2• 6 years ago

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

jodrellblank2• 6 years ago

For example, right now it's Advent of Code, day 6. The puzzles are still reasonably simple. Have a look around today's Reddit thread where people can post their answers:

https://old.reddit.com/r/adventofcode/comments/k7ndux/2020_d...

These are self-selected people, free to use a language of their choice. Ask yourself some questions:

- Which of these do I think is "most readable" vs "least readable"?

- Which of these am I happy is correct, and bug-free as far as it goes?

- Which of these would I like to make a change to, confident that it won't break?

- Which took the author most / least time?

- If I could only pick one to run on my puzzle input and submit the one answer which came out, which of these would I pick?

- Which of these would I like to maintain long term?

Another way to see the same ideas is to pick a task on RosettaCode - https://rosettacode.org/wiki/Category:Programming_Tasks - and see how much / little code people write in various languages to solve the same problem.

IMHO it isn't "the longest one" that is clearest, by a long shot. Nor the golfiest one. But it tends to be the shorter ones done in languages that have higher levels of abstraction, more libraries, nicer looking naming, more standard patterns.

paulmd• 6 years ago

your comment about "short" vs "code golf" gets to the point of the comment you are responding to, which is one that Linus is downplaying - not all lines of code have an equal "cost".

Potentially, using a code-golf implementation where you're using pointer-to-pointer to get rid of a single, easily understandable "special case", is more "expensive" in coder-time than just using the standard off-the-shelf linked-list that (even Linus admits) everyone knows from their data structures 110 class. Because now every developer who ever reads that bit of code for years into the future, now has to understand your code-golf solution, how it works, why it was done, and the implications for the rest of the code. Whereas they could probably skim the "standard" solution and say "yes, that is a standard linked list" and move on to solving the actual problem instead of trying to understand the code golf.

In many cases: your clever solution isn't solving a difficult enough problem that it's worth the cleverness, because cleverness is often expensive.

edit: I agree elsewhere that this is probably a question of "vocabulary" and whether a particular bit is "clever" or "code golf" depends on your particular team.

fsloth• 6 years ago

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_seaberg4• 6 years ago

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• 6 years ago

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

0xdeadbeefbabe• 6 years ago

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• 6 years ago

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• 6 years ago

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

petergeoghegan2• 6 years ago

I think that you're on to something here.

I write C full time, and have done so for many years. It didn't occur to me that the pointer to a pointer aspect was the source of any of the confusion until just now. Actually, I don't think that I consciously registered its presence when I read the code. There is only one interpretation of the code that makes any sense, and that's at least easy for an expert to see quickly.

I am sure that people that think that the terser variant is overly clever don't get it. To be fair, it's hard to generalize from this one example. But I think that I know exactly what Torvalds intended to draw attention to.

petergeoghegan2• 6 years ago

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

zem2• 6 years ago

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.

alisonkisk5• 6 years ago

It's a lot easier to "get the address of this field in a struct" in C than in Java or Python or JavaScript.

xorcist2• 6 years ago

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• 6 years ago

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.

larsrc2• 6 years ago

Having been programming for almost forty years, in everything from machine code over C to functional languages, I do not find the shorter version "more obviously" right. It requires more commentary to explain here and depends on pointer manipulation above and beyond understanding the structure of the list and the actions of the algorithm. It may be easier if you think about pointer manipulation all the time, but I would consider such code a land mine, just waiting for someone to accidentally change something without enough understanding.

baby2• 6 years ago

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• 6 years ago

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.

Cthulhu_3• 6 years ago

I'd also add that in this particular case, it's not so much cleverness as performance; readability should be a priority for "business" level code, but performance for, well, performance level code.

Think of how often the code will be executed; this particular code, or kernel level code, will be in the order of millions in a regular working day. Most code that I for example write will be tens, maybe hundreds; it's mostly glue code between a database and REST api for a relatively low-traffic internal management application.

But it runs on a Linux machine which, for every HTTP request between the browser and my back-end, will run thousands of lines of code and iterations (I guess?). I really don't mind if the code looks clever if it means it's ten times faster than the readable code.

Besides, clever does not exclude clarity.

yetanotherjosh• 6 years ago

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

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

jcranmer3• 6 years ago

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.

arjun-menon• 6 years ago

That does make it a bit clearer, but I do hope the compiler optimizes away the redundant curr variable.

Now, on a different note, I am a bit puzzled because I don’t see a free(*ptr) call in Linus’ or anyone else’s code. The code, as-is, would cause a memory leak.

There’s a need to capture the curr_ref before it’s overwritten, and free it after it’s overwritten.

coldtea3• 6 years ago

Only in this case the second solution is clearer, and not clever in the "old school Perl" way...

User23• 6 years ago

Human beings are bad at case analysis, so removing case analysis makes the code much more comprehensible. It's a huge improvement. Dijkstra wrote extensively on the subject and his arguments are compelling[1].

[1] https://www.cs.utexas.edu/users/EWD/transcriptions/EWD07xx/E... and https://www.google.com/search?q=site%3Ahttps%3A%2F%2Fwww.cs.... for more

munificent• 6 years ago

One way to define "clever" is something you can do but that relies on something you don't expect most readers to have already loaded into their head. Like a riddle, it makes sense if you know the trick it relies on but is baffling if you don't. The difference between "clever" and "smart" then is based in large part on what you expect your readers to already know. Different people have different expectations there and they reasonably vary across teams and time.

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

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

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

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

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

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

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

kortex• 6 years ago

What really made monads click for me is when I read Monads for Go Programmers [0], drawing a comparison between pointers and functors:

We can think of a functor as a container, which contains one type of item. ... A pointer: *T is a container that may be empty or contain one item;

Despite that comparison probably making seasoned FPers groan, that was a big clicking moment for me.

Thinking along the lines of nullary-function:pointer::return:dereference, frames Linus' abstraction in an interesting light. You're manipulating the "function which yields the struct", not the struct itself. In fact it looks much closer to a map than the cs101 blurb in that now all nodes can be treated symmetrically.

[0] https://awalterschulze.github.io/blog/post/monads-for-goprog...

veddox• 6 years ago

Yes, I think that's the key.

I'm not a C programmer, and though I do have a basic understanding of pointers, I still find them rather confusing because of the indirection they introduce. I could follow the first example just fine (because I know how to deal with linked lists from Lisp), but the second gave me rather a headache (two levels of indirection!).

However, I think that once you've really understood the concept of pointers - and I'd expect that from all kernel developers - the second example really wouldn't be any harder to understand than the first. And yes, then it is the cleaner way of doing things, and therefore to be preferred.

h0l0cube• 6 years ago

It's not cleverness for cleverness sake, it reduces complexity, and yet the code is still self explanatory. The extra level of indirection means one variable can be used to access what was previously stored in two. The only confounding part of it is that this didn't become the canonical way to manipulate a linked list over the naive implementation.

kelnos• 6 years ago

I find the "elegant" version easier to read and understand. But I think it also requires the reader to understand pointers pretty well, which, frankly, the majority of developers (who tend to work with interpreted or GC'd languages that don't have pointers / pointer arithmetic) probably don't have much familiarity with.

If a beginner C programmer reads this code, they might not understand until they have a little more experience under their belt. But I think that's ok; if we limited ourselves to writing code that beginners in the language can easily understand, we're going to miss out on a lot of important, useful techniques.

I do absolutely agree that cleverness should be avoided. We should optimize for later readers of our code. But I don't really see this as falling into the "clever" camp, at least not in way we mean "unmaintainable code".

Existenceblinks• 6 years ago

I was about to post a comment but then I think someone propably post this view already, and yes. When I quickly perceive visual of:

  block
    prev = cur
  /block

  if(prev)

It immediately tells the taste that's bad. Especially for ones who come from writing expression rather than statement

emodendroket• 6 years ago

On the other hand, "clever code" repeated enough times is a "design pattern."

lmm• 6 years ago

Lines of code are expensive! They're the only thing that's ever been shown to be correlated with the number of bugs in a given codebase.

runawaybottle• 6 years 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_2• 6 years 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• 6 years 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• 6 years 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• 6 years 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_2• 6 years 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• 6 years 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• 6 years 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• 6 years 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• 6 years 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".

foobarian2• 6 years 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• 6 years 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• 6 years 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-a...

Volt• 6 years ago

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

I believe this comes from Plan 9.

_flux• 6 years ago

Consider though you would need to extend both versions to use doubly-linked lists.

I would much rather extend the latter than the former. (Though it could be I've used a similar solution in the past.)

nemetroid2• 6 years 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• 6 years ago

Thank you, I found that much easier to read than the article posted.

m463• 6 years ago

Much clearer when read as Linus intended.

Reminds me of the editor(s) who helped "fix" bukowski's poems

cambalache• 6 years ago

It's a small class in good coding 101. Concise, well commented/documented, good variables names vs verbose in explanation , terse in code.

forrestthewoods• 6 years ago

Perfect. I almost commented to complain that the “elegant” version is harder to read and understand. This is much much better. Comments are important!

helloycombinat• 6 years ago

I don't think it's the comment.

Usually variable names in a loop is the object being manipulated not the address of that pointer which means p isn't a pointer to the object which makes it completely confusing.

If the article used pp which is the typical way you describe a pointer to pointer it'd help

alisonkisk5• 6 years ago

The author also misunderstands what "head" of a list is, adding more bad clutter to the code.

(Granted, the code in the original TED talk is broken, as it doesn't define "head".)

A linked list in C isn't a struct with a "head"; "head" is just a pointer pointing to the head element.

The OP article should be retracted.

rossitblt• 6 years ago

How likely it is for code to be misunderstood depends on the code readability as well, not just on the person who gets it wrong. Personally, I find the style of Linux lists unintuitive. To me it seems a case of sacrificing code readability to workaround limitations of the C language.

djeiasbsbo• 6 years ago

I don't see what you're saying.. the OP added that bit (the IntList struct) himself but it doesn't really change the scenario or take away from what he is trying to explain.

But it should be retracted? Really?

jamesdsadler• 6 years ago

Both of these implementations seem to be missing a call to `free`, or is that something that the caller should be taking care of?

Arnavion• 6 years ago

It's pseudocode. The code as-is is not valid C anyway.

jagged-chisel• 6 years ago

Depends on whether the list owns the nodes. I tend to write mine such that it does. Perhaps this code is demonstrative rather than complete.

arka2147483647• 6 years ago

The caller could want to move the element from one list to another, in which case the optimum impl would not free or copy the element.

eperdew2• 6 years ago

As others have said, often you don't want to free the node, you want to do something else with it. E.g., put it in a free list. However, usually if you're not freeing it, you'd null out the next field so that you don't accidentally access it when it's not part of the list (at least I would).

scoutt3• 6 years ago

Why do you think the values were allocated in the heap?

hyperpape• 6 years ago

Question for experienced C programmers (I'm not one). The comments for remove_list_entry strike me as fluff, only suitable for a didactic piece.

Would you find the comments in the second version helpful, or should they also be removed?

Edit: let me lay my cards on the table. If the comments really are necessary, it doesn’t seem elegant. I’m pro-comments, but that’s because not all code can be readable and elegant all the time.

identity02• 6 years ago

The top pattern is extremely common so comments are somewhat unnecessary since everyone would know what you're doing. In the second one, comments would be less necessary with a type annotation and perhaps a better name. Maybe "next_ptr" instead of "indirect"---all pointers are indirection, so that name is redundant. But the comments are necessary, to me at least.

valtism• 6 years ago

The comments certainly don't detract from the code in my opinion. They may not be _helpful_ per se to an experienced developer, but there may be a chance that a more inexperienced developer will read this code in the future, and it could benefit them.

tooltower• 6 years ago

While I wouldn't write this much comment, I can see a use for this: navigation. If I'm trying to quickly find the part I want to modify, the comments do help me skim through quickly and zoom in on the part I care about. It's the same reason a blog post is often broken up into section headings. Without the comments, I'd have to spend a few extra seconds trying to map chunks of the code with my mental model of how linked lists work. Those few seconds can interrupt the flow of work.

So I'll disagree with the notion that only illegible or unreadable code needs comment.

emerged2• 6 years ago

For my tastes there is way too much whitespace and I usually only use multi-line comments to describe the high level algorithm for a full function. I prefer to pepper single-line comments which describe the sequence of events in a human-readable way.

I've been C/C++ for about 25 years.

munchbunny• 6 years ago

I would expect to see barely any comments in the "in production" version, other than a comment like:

    // indirect is either &head or &(node->next), so *indirect is equivalent to "next node"

Someone who knows their C should be able to figure it out in a few minutes by just reading the code.

762236• 6 years ago

What if entry doesn't exist in the list? You need a special case to handle that too.

asdfasgasdgasdg3• 6 years ago

Normally with an identity-based API like this, you can put it as a requirement that you must not remove items other than those which actually exist in the collection. Another example of an API that doesn't check for presence: c++ iterator-based removal. If you ask a C++ list to remove an iterator element outside its range, it may crash the program. See the exception safety section of this documentation: http://www.cplusplus.com/reference/list/list/erase/ If you look at most "remove this object from yourself" APIs in low-level code, it behaves this way, because it's unnecessarily complex to check for presence when that is a fact the program can condition on instead.

kbumsik3• 6 years ago

Well, both implementations will crash in that case anyway. You can take that case as out of scope of this discussion.

The purpose of the OP and the Linux's talk is to show a better way to walk through linked list, not to show a full implementation.

javajosh2• 6 years ago

What happens at the end of the list? Is next null? And if so, how do either of these methods behave?

Jasper_• 6 years ago

This is a circular linked list, where the ->next pointer points back to the head of the list. It's helpful for iteration tasks, since you can always walk the full list when you get access to one node.

In most cases you use a linked list like this, you don't care about the order of things, just that you can iterate over all items in the list.

BalinKing• 6 years ago

I'm kinda confused on how this will behave if we want to remove `head`—if `head` is in the stack frame (assuming it's a parameter to `remove_list_entry`), wouldn't `*(&head) = entry->next;` be a no-op as far as the caller is concerned? (Sorry for the n00b question.)

kbumsik3• 6 years ago

Then you will escape from while((* indirect) != entry) check in the first place and ignore * (&head) = entry->next;.

foota• 6 years ago

No, this copies the value from next into the memory occupied by head.

For example if the linked list was:

&next: (100, 0xFFFF)

0xFFFF: (101, 0xDEFF)

0XDEFF: (102, 0)

Then calling remove on head would leave us with:

&next: (101, 0xDEFF)

0xFFFF: (101, 0xDEFF)

0XDEFF: (102, 0)

(It would be on the caller to free the memory address 0XFFFF)

Thorrez4• 6 years ago

This comment seems wrong to me:

      // The "indirect" pointer points to the
      // *address* of the thing we'll update

The "indirect" pointer points to the thing we'll update. See at the bottom, it's updating *indirect, so "indirect" points to the thing being updated. On the other hand, "indirect" points to the address of the thing we'll remove. There's a specific item being removed, and there's a specific thing that will be updated; the thing being updated comes immediately before the thing being removed; they're not the same thing.

ndand2• 6 years ago

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

cmroanirgo6• 6 years ago

I can't help but notice how this code, as well as in the article, there's no checks for a) a NULL list or b) that the item is in fact part of the list. A simple fix is:

  while (!!walk && walk != entry) {
     prev = walk;
     walk = walk->next;
  }

  while (!!indirect && !!(*indirect) && (*indirect) != entry)
          indirect = &(*indirect)->next;

...because without those checks it's pretty easy to see where you'll crash... but by putting in those checks, perhaps the second method might actually be less 'elegant'.

Edit: did I miss something? Re-checking this, the second method will still crash if/when next is NULL (because you can't get the address of NULL), which means the 'elegant' seems to be a quagmire of lurking faults.

mjevans• 6 years ago

I believe the implicit requirement is that the item is known to exist within the list. With that requirement in place the extra guards aren't requisite (they're implicit) and in kernel code this probably offers a performance edge and is a reasonable requirement. Either having an implementation that has an extra check once at the end of the list, or that verifies the presence of the item and passes that node through to a deletion subroutine, would be good alternatives but still utilize the same pointer to structure view.

kbumsik3• 6 years ago

You don't need to check !!indirect. There is no cases that the indirect pointer is NULL:

  while (!!(*indirect) && (*indirect) != entry)
    indirect = &(*indirect)->next;

Also I would rather use * indirect instead of !!(* indirect).

yarcob• 6 years ago

That code is not a general purpose library function; it assumes the element exists.

If you call that method and the element doesn't exist, presumably something has gone wrong already. Adding a NULL pointer check is not going to fix it. You just silently ignore the error. You'll prevent the crash, but there's no mechanism for handling the error.

Hammershaft• 6 years ago

Hacker news would benefit from code blocks.

rocqua• 6 years ago

Hacker news has code blocks. Have the block indented by for spaces.

    this line has 4 spaces in front of it.

What Hacker news could use instead are quote blocks. Now people often use the code blocks as quote blocks.

penteract• 6 years ago

The article refers to p about 30 times, including in a diagram, so I can understand why they'd pick a shorter name.

smitty1e• 6 years 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

jcranmer3• 6 years 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• 6 years 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• 6 years 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.

Animats3• 6 years 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.

souprock3• 6 years 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.

kevin_thibedeau• 6 years ago

Typedefing pointers was done so Pascal programmers didn't have to be scared by C syntax. This is why Microsoft went overboard with this practice. It unfortunately hides the language for no real benefit.

wanderer23232• 6 years 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.

ghusbands2• 6 years 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".

scscsc3• 6 years 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.

wanderer23232• 6 years 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• 6 years 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.

dhanna2• 6 years 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• 6 years 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?

galoisgirl• 6 years 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.

jraph3• 6 years 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!)

convolvatron• 6 years ago

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.

xpe4• 6 years ago

the code itself isn't important. its about the functioning of the group, the velocity, and the ownership.

It isn't either/or. It can be all of the above, to varying degrees, that change over time.

huhtenberg• 6 years ago

Well, yeah. This sort of code acts as a natural filter.

Someone's who finds it difficult to learn or to use it may not be ready for the kernel development. So it works as expected on more than one level.

The same goes for intrusive containers and few other things that many people learn in school, but get at first confused by in practice. If this creates a friction at the group level, then it's the problem with the average group skill rather than the code. And it's the former that (ideally) needs addressing. Just like you wouldn't use bubble sort because the "group" has trouble understanding the alternatives.

xorcist2• 6 years 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.

larschdk• 6 years ago

How I wish more programmers would understand this. It's like learning to eat broccoli. At first, its bitter and unfamiliar, but if you are exposed to it, you learn to recognize it and like it, and it's actually good for you despite the initial unpleasant taste.

seanwilson• 6 years 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• 6 years 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• 6 years 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.

btilly2• 6 years 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 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.

jariel3• 6 years 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.

andy_threos_io4• 6 years ago

The simple solution is faster.

baby2• 6 years 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• 6 years 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

userbinator• 6 years 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

It's interesting to see how divisive the opinions are. I see it as the difference between the "growth mindset" and not.

Animats3• 6 years ago

Isn't it in Knuth, vol. 1?

whack• 6 years 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-i...

int_19h• 6 years ago

Which one required writing an article about to explain?

jraph3• 6 years 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

_y5hn• 6 years 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_io4• 6 years 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• 6 years 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.

andy_threos_io4• 6 years ago

I don't see the so called "elegant" solution any special at all, but if the level 1 programmer in your org needs more time to understand, and maybe making bugs or mistakes, coz of not fully understand the code, than it's a problem. See Occam razor.

The "elegant" solution tries to be smart, or optimize where there is no need at all. Yes the simple "elegant" solution is just 1 instruction slower, and longer only in the end, but the inline version is 1 instruction slower in the loop, which is stated more elegant in the article.

EDIT: Or you can get the same principle as the Occam's razor, which is KISS keep it simple, stupid, silly and straightforward

scscsc3• 6 years ago

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

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

scscsc3• 6 years ago

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

GnarfGnarf• 6 years 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.

jariel3• 6 years 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.

souprock3• 6 years 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.

jariel3• 6 years 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• 6 years 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

landhar• 6 years 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• 6 years 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.

BMSmnqXAE4yfe1• 6 years ago

Both algos will crash if the target is not on the list, so both are equally bad :)

furyofantares• 6 years 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• 6 years 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• 6 years 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.

brundolf3• 6 years 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

vips7L3• 6 years 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>>
    }

brundolf3• 6 years 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.

jonahx• 6 years 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• 6 years 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.

javajosh2• 6 years 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.

ajarmst2• 6 years 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?

xpe4• 6 years 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.

xpe4• 6 years 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.

ajarmst2• 6 years ago

The & isn't needed if you're returning a pointer and no longer need a pointer to pointer to return the list as an argument. Also, if you get rid of the struct containing a single pointer and just use pointers, you can have the following instead…

` p=p->next

As for the API, returning the pointer allows a function to be an argument for another function, which I find more flexible. ` p= remove(p,find(p,value))//

I also like the option to be able to do stuff like:

` p=remove(remove(p,t),t); //remove two

or:

` if (!remove(p,t)) {//that was my last node }

But that may be an artifact of my preference for functional programming.

tgv• 6 years ago

Without the container struct, you'd have to pass the pointer to the pointer of the first element, remove(&head, elem), or assign the return value back to it, head = remove(head, elem). A container also allows you to maintain a counter and a tail pointer, for fast append and insert. Above all, a container makes it harder to return a pointer to just somewhere in the middle of the list and treat that as the head.

fnord77• 6 years ago

2013 - stop using linked lists: https://news.ycombinator.com/item?id=5751702

adwn• 6 years 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.

avodonosov• 6 years ago

The most elegant way, imho, to join collection elements into a comma separated string: http://avodonosov.blogspot.com/2012/01/maybecomma.html

keyle• 6 years ago

off topic, I've enjoyed the talk referred to

https://www.ted.com/talks/linus_torvalds_the_mind_behind_lin...

zgs2• 6 years 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.

zgs2• 6 years ago

Why not the concise version?

for(p=NULL,q=head; q!=entry;p=q,q=q->next); *(p?&p->next:&head) = q->next;

oblio2• 6 years ago

Because we have big, high resolutions screens and we don't "list" (i.e. print) our source code anymore?

franzwong• 6 years 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• 6 years 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• 6 years 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• 6 years 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• 6 years 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.

oblio2• 6 years ago

Some would argue that the git UI falls into the same category.

mkirchner2• 6 years 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!

dhanna2• 6 years ago

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

totorovirus• 6 years ago

I seriously don't understand why this elegant example is a 'clever' code at all. It is just much easier to understand.

pwdisswordfish4• 6 years 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.

cNHciFHqCmd• 6 years 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

hadcomplained• 6 years 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• 6 years 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• 6 years 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• 6 years 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• 6 years ago

Your version does a lot more memory writes.

bnastic• 6 years 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• 6 years 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...

agapon• 6 years 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• 6 years 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• 6 years 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.

DonHopkins3• 6 years 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• 6 years 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.

DonHopkins3• 6 years 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• 6 years ago

That must have been a very old Pascal

Nowadays there is the @ operator

DonHopkins3• 6 years 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

Here's an article about that trick, in German (which makes it sound even cooler):

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• 6 years ago

Good code is code that everyone in a team can understand, safely modify and maintain.

ho_schi• 6 years 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-torva...

Here using actually "pp" ;)

kasajian• 6 years ago

Better link: https://gist.github.com/santisbon/42580049705ba3d8fbef7168e4...

lostmsu• 6 years 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;
  }

Linus Torvalds' good taste argument for linked lists, explained

Related Stories