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

261–270 of 339 posts

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

#261

Post by veets »

adrianN wrote: post #235
larsrc wrote: post #229

Earlier quoted context omitted.

Are you arguing that we should leave known crash bugs in the code?

I'm arguing that we should use asserts or similar defensive coding mechanisms to ensure that preconditions are met instead of merrily continuing to run our program with cascading error effects.

Yes - and that is the point the OP you responded to is making. This is not a generic library function. It used in a specific setting where preconditions exist and presumably are checked _prior_ to calling this code.

Sure you could make the argument that we don't _know_ they are being checked, but it's a pointless discussion. Who cares? _If_ preconditions are met, this code is safe, if they aren't, it's not safe. Since we don't know one way or the other, there's no point in discussing further. The kernel developers know their stuff...

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

#262

Post by Cthulhu_ »

JulianMorrison wrote: post #251
yarcob wrote: post #216

Earlier quoted context omitted.

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.

Then it ought to document that it assumes that entry exists and that this walk will not hit the end of the list. Which also implies the list is not empty.

It should, yeah, but if it can safely assume there will be no nulls, it will save a nontrivial amount of defensive programming checks for each cycle. And IIRC, the Linux kernel uses tons of linked lists, millions of items per second sometimes; any operation that can be removed will make a big impact. Relatively.

But for general purpose code, e.g. libraries where performance isn't super important but stability is, more defensive programming would be a thing to do.

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

#263

Post by Cthulhu_ »

asdfasgasdgasdg wrote: post #175
azernik wrote: post #166

Earlier quoted context omitted.

Not just an instruction, but a branching instruction. Branch predictors will probably do pretty well on this, but still.

With linked lists, memory latency dominates, since you're chasing pointers all over the heap. I guess the null check costs nothing most of the time. On the other hand, removing random objects from lists that you don't know are actually in those lists is a smell.

> I guess > most of the time

Two terms that would not fly in kernel level programming; with kernel programming, low-level libraries, you want both optimized speed and predictability.

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

#264

Post by mjburgess »

haskman wrote: post #249
hadcomplained wrote: post #245

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

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.

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.

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

#265

Post by Cthulhu_ »

joe_the_user wrote: post #58
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 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 ope…

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.

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

#266

Post by Upvoter33 »

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.

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

#267

Post by adrianN »

veets wrote: post #261
adrianN wrote: post #235

Earlier quoted context omitted.

I'm arguing that we should use asserts or similar defensive coding mechanisms to ensure that preconditions are met instead of merrily continuing to run our program with cascading error effects.

Yes - and that is the point the OP you responded to is making. This is not a generic library function. It used in a specific setting where preconditions exist and presumably are checked _prior_ to calling this code. Sure you could make the argument that we don't _know_ they are being checked, but it's a pointless discussion. Who cares? _If_ preconditions are met, this code is safe, if they aren't, it's not safe. Sinc…

Imo every piece of code (for reasonable definitions of "piece") is supposed to check its own preconditions and not rely on the caller to check them.

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

#268

Post by arh68 »

hadcomplained wrote: post #245

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

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;

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

#269

Post by banachtarski »

larsrc wrote: post #229
adrianN wrote: post #224

Earlier quoted context omitted.

And instead of adding a check and crashing visibly here you wait even longer until your program misbehaves due to the error? The longer the program runs after something went wrong, the harder it is to debug, and the more likely it becomes that you get an exploitable bug.

Are you arguing that we should leave known crash bugs in the code?

What you are espousing is known as “defensive programming” which is very much a bad thing (tm).

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

#270

Post by christophilus »

aidos wrote: post #233
larsrc wrote: post #229

Earlier quoted context omitted.

Are you arguing that we should leave known crash bugs in the code?

It’s not a bug, in this case. It depends on the behaviour the library is specified to handle, but if you ask me to remove a specific item from a list, and that item isn’t in the list, what should I do? I can fail so you can catch it, or if you don’t catch it, you’ll at least see exactly what went wrong. You expected the item to be in the list and it wasn’t. Your preconditions were wrong from the beginning and you hav…

I think a better approach is to return a bool or something like that, rather than crashing. But I agree that silently handling this case is the worst of the options.
Post reply on HN