Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Intrusive linked lists (2019)

data-structures-in-practice.com

Post reply on HN
Print view View original

51–60 of 80 posts

Re: Intrusive linked lists (2019)

#51

Post by icedchai »

el_pollo_diablo wrote: post #48
Joker_vD wrote: post #41

Earlier quoted context omitted.

> Now you have a naming problem. You need a naming convention that every user of the list library must follow, or else their types will be incompatible. Oh, that's simple: just have empty struct tags. > And what about typedefs? The names introduced by the typedefs are irrelevant. > A and B are typedef-related (their normal forms, obtained by following all typedefs, are the same), lists of A and B will be incompatible…

> The structs list_of_A and list_of_B are compatible. No, they are not. From C23, 6.7.3.4 Tags: Each declaration of a structure, union, or enumerated type which does not include a tag declares a distinct type.

It depends what is meant by "compatible." Is the memory layout the same? Yes. Can I memcpy between them? Yes...

Re: Intrusive linked lists (2019)

#53

Post by el_pollo_diablo »

icedchai wrote: post #51
el_pollo_diablo wrote: post #48

Earlier quoted context omitted.

> The structs list_of_A and list_of_B are compatible. No, they are not. From C23, 6.7.3.4 Tags: Each declaration of a structure, union, or enumerated type which does not include a tag declares a distinct type.

It depends what is meant by "compatible." Is the memory layout the same? Yes. Can I memcpy between them? Yes...

We mean compatible as defined by the C language standard. It is much more restrictive than having the same layout. In particular, you may not pass a pointer to a type where a pointer to an incompatible type is expected, even if the types have the same layout, which prevents the sort of sharing between two libraries that is being discussed.

Moreover, there is no guarantee that two distinct structure types with the same list of members have the same size or alignment (although in practice they do). The members must nevertheless be laid out in the same way (same offsets, and in the case of bit-fields, same layout inside storage units) due to an obscure constraint on common initial sequences. So the layouts of the structures may differ in the alignment requirement and the amount of trailing padding.

Re: Intrusive linked lists (2019)

#54

Post by dcrazy »

drdexebtjl wrote: post #50
el_pollo_diablo wrote: post #42

Earlier quoted context omitted.

> It does matter, for malloc-returned storage. You can put whatever objects you want into that storage as long as it fits and the pointer is properly aligned. You can certainly store an object of arbitrary type, but here it is done through a pointer to an object with pointer arithmetic going beyond the allowed bounds. > memcpy takes a void pointer as its destination, sets the effective type of the storage behind it A…

If payload was ever dereferenced as a char array as well, I would buy the strict aliasing argument. But it’s not, it exists as a char pointer solely for pointer arithmetic. AFAIK The purpose of strict aliasing rules is to let the compiler assume that dereferencing pointers of different types never refer to the same memory. If ISO C treats this as UB, shouldn’t ISO C be fixed?

No, you should fix your code to be compliant with ISO C. The optimizer isn’t going to wait for you to convince WG14.

Re: Intrusive linked lists (2019)

#55

Post by icedchai »

el_pollo_diablo wrote: post #53
icedchai wrote: post #51

Earlier quoted context omitted.

It depends what is meant by "compatible." Is the memory layout the same? Yes. Can I memcpy between them? Yes...

We mean compatible as defined by the C language standard. It is much more restrictive than having the same layout. In particular, you may not pass a pointer to a type where a pointer to an incompatible type is expected, even if the types have the same layout, which prevents the sort of sharing between two libraries that is being discussed. Moreover, there is no guarantee that two distinct structure types with the sam…

Yes, I figured that's what you meant... I wasn't sure about the other guy.

Re: Intrusive linked lists (2019)

#56

Post by drdexebtjl »

dcrazy wrote: post #54
drdexebtjl wrote: post #50

Earlier quoted context omitted.

If payload was ever dereferenced as a char array as well, I would buy the strict aliasing argument. But it’s not, it exists as a char pointer solely for pointer arithmetic. AFAIK The purpose of strict aliasing rules is to let the compiler assume that dereferencing pointers of different types never refer to the same memory. If ISO C treats this as UB, shouldn’t ISO C be fixed?

No, you should fix your code to be compliant with ISO C. The optimizer isn’t going to wait for you to convince WG14.

I’m not chasing theoretical portability and checking off a box saying my code is 100% pure ISO C. If that’s important to you, don’t do this (and also don’t use pretty much any allocator!)

Every sufficiently useful C codebase assumes specific implementations.

Re: Intrusive linked lists (2019)

#57

Post by dahart »

apple1417 wrote: post #17
dahart wrote: post #8

Earlier quoted context omitted.

> It is awkward in C, where the implementation has to be macro-generated I assume this is why they are putting the list pointer and payload in separate structs and doing pointer math to access the payload, so that it’s easy to build a set of macros that act like a generic list class for building lists out of any payload, right? > One other advantage of intrusive data structures is the ability to link a payload into s…

> If I do address math on the pointer in order to find a payload, then isn’t the payload tied into exactly one next pointer, and thus exactly one list? The container_of macro takes the type and member - so for a different member it can subtract a different offset. Going more basic, you could imagine creating something like: struct Node { Node* next; Node* next_10th; Node* next_100th; }; The normal, 10ths, and 100ths…

Ah yes if all collections are explicitly listed in the list node type, that makes sense. I thought the suggestion was that you could somehow link any given payload entry into multiple independent lists each with their own list node type.

Re: Intrusive linked lists (2019)

#59

Post by steveklabnik »

nick_ wrote: post #49
amelius wrote: post #23

Now try to do them in safe Rust.

Are the Rust devs not expanding the surface area of safe Rust over time? Just curious.

Sort of but also no. Intrusive lists are not likely to ever be possible in safe code, almost by definition.

Re: Intrusive linked lists (2019)

#60

Post by el_pollo_diablo »

dahart wrote: post #8
el_pollo_diablo wrote: post #2

The go a bit further than the article on the advantages of intrusive data structures, taking linked lists as an example: As the article mentions, intrusive data structures naturally lead to one fewer indirection. To do the same with a traditional list (where the list node owns the payload), a different node type is needed for each payload type. This is easy to do with the proper support for monomorphized generics, se…

> It is awkward in C, where the implementation has to be macro-generated I assume this is why they are putting the list pointer and payload in separate structs and doing pointer math to access the payload, so that it’s easy to build a set of macros that act like a generic list class for building lists out of any payload, right? > One other advantage of intrusive data structures is the ability to link a payload into s…

> how does this work?

Like this:

  struct thread {
      // Entry in the list of threads of the containing process
      list_node process_entry;
      // Entry in this thread's scheduling queue
      list_node sched_entry;
      // ...
  };
Each struct thread is linked in two lists. When we need to get from a list_node * to the enclosing struct thread, we know from the context which list is being inspected, so we know which one of process_entry or sched_entry to consider for offsetting the pointer.
Post reply on HN