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.
Linus Torvalds' good taste argument for linked lists, explained
221–230 of 339 posts
Re: Linus Torvalds' good taste argument for linked lists, explained
#222Earlier quoted context omitted.
That's a pretty big freakin thing to leave out, though. Code that depends on its context is, some would say, bad.
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.
Re: Linus Torvalds' good taste argument for linked lists, explained
#223Author 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!
Re: Linus Torvalds' good taste argument for linked lists, explained
#224Earlier quoted context omitted.
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; } or while (!!indirect && !!(*indirect) && (*indirect) != entry) indirect = &(*indirect)->next; ...because without those checks it's pretty easy to see where you'll crash... but by putt…
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.
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.
Re: Linus Torvalds' good taste argument for linked lists, explained
#225Earlier 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.
If you're writing a linear algebra library, then the bulk of executing code should be floating point vector operations in tight loops with known bounds. A NULL pointer check in the prolog where you set up the loop is going to be negligible.
This is very different from kernel code, which by its nature isn't very computational but doing resource management all day long and pretty much all it does is stuff that looks like walking linked lists.
Re: Linus Torvalds' good taste argument for linked lists, explained
#226Earlier quoted context omitted.
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.
If you're writing a linear algebra library, then the bulk of executing code should be floating point vector operations in tight loops with known bounds. A NULL pointer check in the prolog where you set up the loop is going to be negligible. This is very different from kernel code, which by its nature isn't very computational but doing resource management all day long and pretty much all it does is stuff that looks li…
That was a very specific linear algebra, we toyed around with huge but sparse matrices. Not anything graphics-related, rather number theory-related. But there was a lot of integer comparisons in there.
This was around 2001-2002 anyway. Things might have changed.
Re: Linus Torvalds' good taste argument for linked lists, explained
#227I'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 8…
> 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 n…
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.
Re: Linus Torvalds' good taste argument for linked lists, explained
#228Earlier quoted context omitted.
That's a pretty big freakin thing to leave out, though. Code that depends on its context is, some would say, bad.
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.
It's written in C because C is popular, has platform support and the code was originally written in C, not because the kernel should be a security nightmare.
Re: Linus Torvalds' good taste argument for linked lists, explained
#229Earlier 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.
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?
Re: Linus Torvalds' good taste argument for linked lists, explained
#230I 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…
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.
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.