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

301–310 of 339 posts

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

#301

Post by asdfasgasdgasdg »

Cthulhu_ wrote: post #263
asdfasgasdgasdg wrote: post #175

Earlier quoted context omitted.

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.

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

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

#302

Post by entropicdrifter »

gjulianm wrote: post #6

Although I liked the 'elegant' code after reading it, in general I would try to shy away from 'elegant' solutions that are actually harder to understand. Unless you are working with high-performance programs, most of the time you don't care about one or two extra branches. It's usually more beneficial to write code that can be easily understood by a future-you or by another person in your team: less time invested in…

In general, this is good practice for working on a team.

However, given that we're talking about Linus Torvalds' opinions on what makes code 'elegant' or 'good taste', I'd say it's implicit that we're talking within the domain of low level, high performance code, such as kernel code.

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

#303

Post by [deleted] »

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.

[deleted]

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

#304

Post by freemint »

pmart123 wrote: post #296
stuff4ben wrote: post #291

Earlier quoted context omitted.

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

Adding checks creates more code branches and tests. Passing null in is the bug.

Can you show it has any impact on benchmarks? This is something speculative execution should take care of that quickly?

"Premature optimization.... " you get the drift.

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

#305

Post by throwaway_pdp09 »

andrepd wrote: post #287
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.

Asserts have run-time cost. What you need is to ensure ensure those preconditions are met in the first place, statically, by formal methods for example.

Which is ideal, but generally beyond reach for now. So assertions it is.

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

#306

Post by Animats »

souprock wrote: post #126
Animats wrote: post #78

Earlier quoted context omitted.

Um, yes. That jumped out at me. If there's a no-find, the code will de-reference null and crash. That's just not acceptable. Try to write that in Rust, using Some(ref) for the forward link, and the compiler will force you to test for None and detect the end of the list. This is pre-1990s programming style. I've seen such code in assembly programs. Because I was reading crash dumps where it failed.

It's 100% acceptable. You should not remove something from a list unless you know it is there. Since you won't attempt to remove something that doesn't exist, any code to check for that situation is an unjustified performance loss. (separate code exists for searching a list) This... is not Python. C programmers, particularly kernel developers, have that style even in 2020.

I hope not. Kernel programmers need to be paranoid.

This is a classic idea for doubly linked lists. The empty list has the head element linked to itself in both directions. Buffer rings are sometimes organized that way. The cases for doubly linked lists are messier.

Bear in mind that in modern CPUs, branches to nearby code are almost free, but indirection to far memory is expensive.

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

#307

Post by benibela »

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

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

#308

Post by lostmsu » 

  item** find_parent(item** list, item* item) {
    item** potential_parent = list;
    while(*potential_parent != item) {
      potential_parent = &(*potential_parent)->next;
    }
    return potential_parent;
  }
  
  void remove_item(item** list, item* item) {
    item** parent = find_parent(list, item);
    *parent = item->next;
  }

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

#309

Post by hinkley »

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.

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

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

#310

Post by xpe »

ajarmst wrote: post #227
xpe wrote: post #210

Earlier quoted context omitted.

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

Nod, nod, nod. Thanks for clarifying :)
Post reply on HN