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.
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.
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.
> 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.
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.
The idea here is to make the "p" pointer point on the "next" field of the current element instead of at the structure itself. There is the same amount of indirection in both solutions.
The first solution does pointer->structure->pointer, the "elegant" solution does pointer->pointer->structure. The reason the first one may be easier to read is because the C syntax "prefers" it, as it is a more common construct.
But there's comments that explain it, so I think it's okay. I wouldn't leave a thing that has a mix of &, *, and -> without saying what it was supposed to do, but he does explain it.
I'm ok with clever code when it's explained in words.
IMO harder to initially acquire but easier to grok at scale. Imagine combing through the behavior of blocks of code with conditionals in a larger system.
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.»
>Conditionals are so simple it’s basically the first thing anyone learns.
That's neither here, nor there though.
The simplicity of a concept does not directly translate to how hard it makes the code (assembly is simpler in the sense of having fewer and simpler constructs than e.g. Python but much much harder to code in).
Conditionals, and the exponential increase in state space they bring, are still one of the biggest source of errors and complexity in code.
Yes, excellently put. That's exactly why Linus' code is easier to understand. The extra control flow operations really increases the time to understand if the code is correct and likewise introduces many opportunities for error.
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.
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.
Usually those lists are intrusive -- their nodes are meant to be part of larger objects. They will be freed in other contexts, e.g. if protected by RCU, memory reclamation is postponed until all threads have quiesced. Or the nodes are allocated by one amongst many allocators (i.e. for performance, or better concurrence), so it is best for the structure itself not to make any assumption about where the memory should be returned to.
So generally, list implementations in C will not free the node, only remove references to it and return it.
The assembly code produced by my variant and Linus's variant is exactly equivalent, assuming you write the guards the same way. This effectively means that both curr_ref and curr will be live, although the compiler will note that it can substitute entry for curr and short curr's lifetime to only exist within the loop body in the form written here.
At the end of the function curr == entry, so the caller already has a separate reference to the object. Also, removing a node from a list does not necessarily mean that you want to delete it. For example, you might want to put it in a different list.
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.
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.
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.
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.
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).
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.
> "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.
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:
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.
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.
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.
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
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].
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.
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".
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.
Although for loops might all be while loops at heart, I think the distinction is more than just syntactic. Properly used, the use of a for loop conveys particular information: the code block is intended to run a set number of times or over a particular group of objects. This allows while loops in general to be used specifically for running the code block an indefinite number of times until the criteria is met. (Certainly both types of loops can be misused and abused.)
It also splits apart two different kinds of criteria. "Has this run ten times" is a different sort of question than "is the error within the given margin" or "does the temperature now read 60 degrees". (At least, if you're intentionally running the thing 10 times. If it's running incidentally so you don't even know if it will run 10 times then it can be the same sort of question, but in that case I'd argue you should use a while loop….)
> You save 1 or 2 lines and have ambiguity on wherever "each" is.
Like the sibling poster, I'm not certain what you mean by this.
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).
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.
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.
Sure, in those other languages you could just define a single-field class to wrap the reference to the next node, since you can only pass objects by reference and references themselves are (usually) not objects. Unfortunately this adds a lot of overhead, both in lines of code and runtime. Instead you would probably just use the less efficient algorithm with more special cases to work around the lack of indirect references.
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.
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.
Fortunately or unfortunately you don’t always get to decide who touches the code, so unless performance is a concern as it is in kernel development optimising like this in the day job will eventually lead people making mistakes. Basically I say be as explicit and clear as you dare, even at the cost of some CPU cycles.
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.
Many Programmers who don't use C are afraid of pointers and prefer superficially simpler (but overall more complicated) things like Java's abstraction towers, despite the extra expense.
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.
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.
That's not how reading works. You don't parse every character like a computer does. You look at the starting letter (maybe the ending one too) and then recognize the shape of the word used. There isn't too much difference in reading a long or short variable name as long as there aren't variable names that are too similar to one another.
I think you're offering a very particular case with a well-known idiomatic presentation and trying to apply it to the general case. In this case a, b, x, and y are both letters and good variable names for their purpose because of their long, familiar use in mathematics. But calling your main GUI window "m", your data "d", and your server connection object "b" doesn't make for readable code.
Yeah, letters don’t have much of a cost, but extra words do, which is why people complain so much about needing to plow through SimpleBeanFactoryAwareAspectInstanceFactories.
