Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Linus Torvalds' good taste argument for linked lists, explained

github.com

Post reply on HN
Print view View original

151–160 of 339 posts

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

#151

Post by andy_threos_io »

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

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

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

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

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

#152

Post by kelnos »

macspoofing wrote: post #7

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 maintaina…

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

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

#153

Post by Jasper_ »

javajosh wrote: post #137
nemetroid wrote: post #19

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…

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

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.

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

#154

Post by cgriswald »

qualityonly wrote: post #64
xorcist wrote: post #50

Earlier quoted context omitted.

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.

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.

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.

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

#155

Post by andy_threos_io »

jariel wrote: post #91
btilly wrote: post #48

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 "indirectio…

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 ga…

The simple solution is faster.

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

#156

Post by tooltower »

hyperpape wrote: post #105
nemetroid wrote: post #19

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…

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…

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.

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

#157

Post by cgriswald »

magoghm wrote: post #130
Mirioron wrote: post #118

Earlier quoted context omitted.

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.

Actually what you need to recognize are expressions, and expressions with short variable names are much easier to recognize. For example, if I write: theDependentVariable = theCoefficient * theIndependentVariable + theIntercept it is much harder to recognize than if I write: y = a*x + b So, longer variable names might be "autodocumenting" but they also make code harder to read.

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.

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

#158

Post by paulmd »

jodrellblank wrote: post #28
macspoofing wrote: post #7

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 maintaina…

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

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.

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

#159

Post by ajarmst »

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?

Post reply on HN