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

271–280 of 339 posts

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

#271

Post by veets »

adrianN wrote: post #267
veets wrote: post #261

Earlier quoted context omitted.

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.

This is nice in theory but a bad idea in practice (as a blanket statement, I am all for checking preconditions in general). An easy example is binary search, which I think is a reasonable "piece" of code by your definition. One should never check its preconditions _inside_ the binary search function (that the list of elements being searched is partitioned by the search predicate). Checking the precondition is O(n) while the algorithm is O(lg n).

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

#272

Post by oblio »

antirez wrote: post #221

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.

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

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

#274

Post by adrianN »

veets wrote: post #271
adrianN wrote: post #267

Earlier quoted context omitted.

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.

This is nice in theory but a bad idea in practice (as a blanket statement, I am all for checking preconditions in general). An easy example is binary search, which I think is a reasonable "piece" of code by your definition. One should never check its preconditions _inside_ the binary search function (that the list of elements being searched is partitioned by the search predicate). Checking the precondition is O(n) wh…

You're right, but checking for null is not terribly expensive compared to iterating over a linked list.

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

#275

Post by scoutt »

adrianN wrote: post #267
veets wrote: post #261

Earlier quoted context omitted.

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.

It's a bad idea, especially in kernel/low-level/performant code. It's OK to check some values at specific points (like when a value is passed from user space), but in general it's bad practice to check it at every single function. You trust in your program flow.

Imagine if at every function down a complex stack you go with:

    if (!ptr1 || !*ptr1 || *ptr1 > 5 || param1
(used arbitrary names and values).

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

#276

Post by scoutt »

inglor_cz wrote: post #222
axaxs wrote: post #213

Earlier quoted context omitted.

Simply put, safety slows code down. It's a matter of whether you know what's happening underneath or not. The more you try to make C completely safe, the more you slow it down and therefore remove the need to have written it in C in the first place. Whether that's a good thing or not is an exercise for the implementer.

True, but costs of comparison to NULL aren't massive. It is one of the fastest things out there. It was my experience when tuning a linear algebra library (just for internal use) that such comparisons are almost unobservable in total performance tests.

> costs of comparison to NULL aren't massive

Depends on how often you are doing the comparison. Is it 1 time/second, or 10 million times a second?

There is a difference.

If the code above is the one in charge of putting/removing network packets in a queue, or putting threads ordered by priority for the scheduler, then you should consider the side effects of checking for NULL.

If you are going to implement this function in a library for Jimmy The Programmer[1], then check for NULL.

[1] https://blog.codinghorror.com/new-programming-jargon/

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

#277

Post by scoutt »

jamesdsadler wrote: post #75
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…

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

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

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

#278

Post by DonHopkins »

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.

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

#279

Post by zabzonk »

adrianN wrote: post #267
veets wrote: post #261

Earlier quoted context omitted.

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.

This isn't possible in many cases - consider the simple C library function strlen, one of who's preconditions is that it must only be called on a zero-terminated string. There is no way to write code in strlen to check that this is true.

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

#280

Post by Rexxar »

landhar wrote: post #145
bfung wrote: post #96

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

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.

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.

Post reply on HN