Linus Torvalds' good taste argument for linked lists, explained • Hacker News Board

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

#311

Post by DonHopkins » Mon, Dec 07, 2020, 8:17 PM UTC

benibela wrote: post #307

DonHopkins wrote: post #278

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…

That must have been a very old Pascal Nowadays there is the @ operator

Yes, very old Pascal, not even TurboPascal! I started with Apple ][ UCSD Pascal, but that program was for HP3000 Pascal, which might be even older.

There was a trick for doing PEEK and POKE in Apple Pascal, using a union that contained a pointer to some type you could dereference to read and write, and also an integer so you could set the pointer. I had the hardest time understanding it, and just could not get my head around the "record case boolean of", but I just typed in the magic code with a bunch of weird ^'s and it worked somehow.

You can use type punning tricks with "union" to implement arbitrary unsafe pointer arithmetic in Pascal, since it lets you convert between pointers and integers.

https://en.wikipedia.org/wiki/Type_punning#Pascal

Here's an article about that trick, in German (which makes it sound even cooler):

https://www.robert-tolksdorf.de/book/Tolksdorf-UCSD-Pascal-C...

p. 63: 3.1 "PEEK" und "POKE" auch in Pascal

[...]

    type byte = 0..255
    spchrinhalt = packed array [0..0] of byte;
    spchrstelle = record case boolean of
                    true: (adresse:integer); ( Zieger )
                    false: (inhalt:^spchrinhalt) ( Inhalt )
                  end;

    procedure poke(adresse:integer; inhalt:byte);
    var dummy:spchrstelle;
    begin
      dummy.adresse := adresse;
      dummy.inhalt^[0] := inhalt;
    end;

    function peek(adresse:integer): byte;
    var dummy:spchrstelle;
    begin
      dummy.adresse := adresse;
      peek := dummy.inhalt^[0];
    end;

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

#312

Post by cmroanirgo » Mon, Dec 07, 2020, 8:34 PM UTC

snarfy wrote: post #290

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.

Performance is a feature and that null check has a cost. The code is correct. The null check is unnecessary. The bug is passing null in.

NULL being passed in is not the only problem. Dangling pointers, coding mistakes by other team members and race conditions during initialisation can all contribute to this blowing up. Some argue (correctly) that it's best to have it blow up, other that assertions are the way to go. I'm of the latter ideology. Make your debug build do assertions, but release code be crash proof by doing NULL checks.

There are several comments indicating the performance cost of a NULL check. Go and look at the disassembler and see the code. You should find that it equates to JZ, which at worst case costs 1 clock cycle. Am I incorrect?

So, another comment below mentioned 10 million deletions per second. Ignoring the fact that you should be using a double linked list at that point (like the kernel does), in a single threaded 2.4GHz CPU a 1 step opcode (JZ) equates to a bit over 4ms/sec. With branch prediction, I expect to be far less.

So, the NULL check is almost free. Even on embedded systems, it'd still be a good idea to keep it in, to insulate yourself from flipped bits (eg, solar flares, or degrading memory) and coding mistakes elsewhere.

In these days of security research, I strongly advise for defensive code: it means that each function has had it's edge cases thought about, which means the developer has spent time thinking about the stability of their program, which cannot be a bad thing. Don't make your code a deliberate point of exploitation.

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

#313

Post by hyperdimension » Mon, Dec 07, 2020, 9:10 PM UTC

stuff4ben wrote: post #293

banachtarski wrote: post #269

Earlier quoted context omitted.

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

Clearly you've never worked with contract developers whose only purpose is to write a crap ton of code to get a "feature" out that crashes as soon as it encounters the real world. As they say, "doveryay, no proveryay" and it's served me well.

> As they say, "doveryay, no proveryay"

I'm sorry if this might be common knowledge, but I've honestly never heard this and can't understand it.

Is it saying that it's better to do something than to (formally) prove it, like the opposite of (I think) Knuth's famous quote?

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

#314

Post by DanBC » Mon, Dec 07, 2020, 9:12 PM UTC

hyperdimension wrote: post #313

stuff4ben wrote: post #293

Earlier quoted context omitted.

Clearly you've never worked with contract developers whose only purpose is to write a crap ton of code to get a "feature" out that crashes as soon as it encounters the real world. As they say, "doveryay, no proveryay" and it's served me well.

> As they say, "doveryay, no proveryay" I'm sorry if this might be common knowledge, but I've honestly never heard this and can't understand it. Is it saying that it's better to do something than to (formally) prove it, like the opposite of (I think) Knuth's famous quote?

"trust, but verify". https://en.wikipedia.org/wiki/Trust,_but_verify

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

#315

Post by s1dev » Mon, Dec 07, 2020, 9:40 PM UTC

cmroanirgo wrote: post #312

snarfy wrote: post #290

Earlier quoted context omitted.

Performance is a feature and that null check has a cost. The code is correct. The null check is unnecessary. The bug is passing null in.

NULL being passed in is not the only problem. Dangling pointers, coding mistakes by other team members and race conditions during initialisation can all contribute to this blowing up. Some argue (correctly) that it's best to have it blow up, other that assertions are the way to go. I'm of the latter ideology. Make your debug build do assertions, but release code be crash proof by doing NULL checks. There are several…

it's one instruction in the generated code and we can reasonably expect the branch predictor to do the right thing, but branches and error handling can inhibit vectorization which is a much higher performance cost. While in this particular case you probably aren't vectorizing much, it is not always the case that error handling is almost free

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

#316

Post by Sohcahtoa82 » Mon, Dec 07, 2020, 10:02 PM UTC

hinkley wrote: post #309

snarfy wrote: post #290

Earlier quoted context omitted.

Performance is a feature and that null check has a cost. The code is correct. The null check is unnecessary. The bug is passing null in.

Make it work Make it right Make it fast This is an ordered list, and the people who forget that make a lot of work for the people who don’t

I would argue that if you have code that is trying to remove a non-existent item from a list, then making it silently fail is only giving the appearance of making it work.

It's definitely not right, while probably not really working either. The immaterial performance gain from removing the null check is completely irrelevant.

It's a foot-gun for sure, but it's up to you to not pull the trigger.

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

#317

Post by Sohcahtoa82 » Mon, Dec 07, 2020, 10:06 PM UTC

stuff4ben wrote: post #291

snarfy wrote: post #290

Earlier quoted context omitted.

Performance is a feature and that null check has a cost. The code is correct. The null check is unnecessary. The bug is passing null in.

Safety is a feature and that null check prevents bugs. I'd rather have slow but safe code rather than fast but buggy code.

If the null check silently ignores the attempt to remove a non-existent item from the list, then the null check did not prevent a bug, it merely hid it.

IMO, even though this is C, the Zen of Python still applies, which states:

> Errors should never pass silently unless explicitly silenced.

Its the caller with the bug, not the library code.

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

#318

Post by azernik » Mon, Dec 07, 2020, 10:55 PM UTC

asdfasgasdgasdg wrote: post #301

Cthulhu_ wrote: post #263

Earlier quoted context omitted.

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

If you want speed, you don't use a linked list in the first place.

Yeah you do - the kernel uses linked lists to store everything from running tasks to memory pages. Insertion and deletion of entries are much faster in a linked list than in an array, and that's a very performance-sensitive operation in the kernel.

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

#319

Post by isochronous » Mon, Dec 07, 2020, 11:08 PM UTC

shallowthought wrote: post #292

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.

That's irrelevant to what Linus is saying. He's not saying "this is good code, but only with the caveat that it's written in C and run in the Linux Kernel". He's saying that changing it to make it far more difficult to read and modify, but cleverer, has made it better code in general.

See, and this is where I (and I'm guessing you) might beg to differ. I'm a web developer, so the vast majority of my time is spent working in JavaScript. Our team has been working in ES6 for the past ~2 years. Our lead developer just LOVES him some ES6 - destructuring, aliasing, lambdas, you name it, and he's all-in.

Me, though? Well, let's just put it like this: when we find some framework-level bug that's written in "clever" ES6 syntax, our first step in debugging is almost ALWAYS to rewrite the given function traditionally, without any of the ES6 shorthand. And the reason we do that is because reading and debugging a whole stack of anonymous lambda calls is a PAIN IN THE ASS. Or figuring out where a certain variable is coming from when someone uses overly-complex destructuring syntax to magically pull a value from deep within a nested object.

I mean, don't get me wrong, I do like and use almost all of the modern ES6 niceties, but I also feel like it's much more difficult to parse and understand code compared to what we were all writing a few years back. People will, I'm sure, be arguing about what constitutes "good code" for decades to come, but to me, when working in an evolving codebase, especially with other people, plain ol' human readability is paramount. If people can't figure out what your code is doing without throwing in a breakpoint and stepping through line-by-line, you've failed at writing good code. And this will be my opinion right up until the day humans stop writing code by hand.

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

#320

Post by nomel » Mon, Dec 07, 2020, 11:15 PM UTC

cmroanirgo wrote: post #312

snarfy wrote: post #290

Earlier quoted context omitted.

Performance is a feature and that null check has a cost. The code is correct. The null check is unnecessary. The bug is passing null in.

NULL being passed in is not the only problem. Dangling pointers, coding mistakes by other team members and race conditions during initialisation can all contribute to this blowing up. Some argue (correctly) that it's best to have it blow up, other that assertions are the way to go. I'm of the latter ideology. Make your debug build do assertions, but release code be crash proof by doing NULL checks. There are several…

This makes a big assumption that the null check, which is the result of a programmer error, can be recovered. What would you do once you catch the null? Log that there was a null, maybe with some debug information, then halt? I personally would prefer a proper crash handler to do all of that for me.

I guess my question is, what's wrong with crashing, in the case of a real screwup, where something has gone horrible wrong, assuming you have a proper crash handler?