5 ms·

As the other person said, it's not really about complexity. Complexity isn't all that different here; personally I'd find something like the following to be sim

As the other person said, it's not really about complexity. Complexity isn't all that different here; personally I'd find something like the following to be simpler (I imagine others might disagree): remove_list_entry(entry) { for (p = &head; *p; p = &(*p)->next) { if (*p == entry) { *p = entry->next; break; } } } However, what the choice does objectively impact is performance. Being able to assume the object exists allows you to avoid checking against NULL, which removes instructions in the loop. I'd guess they anticipate this code might be called from performance-critical code, and that might be why they coded it like this.

azernik 6y ago
Not just an instruction, but a branching instruction. Branch predictors will probably do pretty well on this, but still.
- asdfasgasdgasdg 6y ago
  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.
  - Cthulhu_ 6y ago
    > 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.
    - asdfasgasdgasdg 6y ago
      If you want speed, you don't use a linked list in the first place.
      - azernik 6y ago
        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.
        Dylan16807 6y ago
        > Insertion and deletion of entries are much faster in a linked list than in an array That's a really broad statement. Arrays can get surprisingly big while being faster. Performance-wise, you'd usually want to use arrays up to a certain size and then link between entire arrays. I'd say the biggest advantage of a standard linked list is that it can be intrusive.
        dr_zoidberg 6y ago
        > I'd say the biggest advantage of a standard linked list is that it can be intrusive. That's one big benefit. I teach operating systems and, when the semester has been good, we dig into physical memory dumps with a few python scripts, and show the students how to parse Windows process list following _EPROCESS structures. That's one of the big things they find themselves surprised every year: that the process list is a chain of LIST_ENTRY structures embedded within the _EPROCESSes[0] (or any other structure that is doubly-linked in memory). And LIST_ENTRY is just 2 pointers going hand in hand with list_entry->flink and list_entry->blink attributes and nothing more. [0] You can read some about this structures here https://www.nirsoft.net/kernel_struct/vista/index.html https://www.nirsoft.net/kernel_struct/vista/index.html but beware this is based on Vista and a bit old. Kernel data structures vary with versions of the OS (and not even major versions at that) and target processor (x86, x86-64, ARM too would be reasonable).

azernik 6y ago

Not just an instruction, but a branching instruction. Branch predictors will probably do pretty well on this, but still.

asdfasgasdgasdg 6y ago
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.
- Cthulhu_ 6y ago
  > 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.
  - asdfasgasdgasdg 6y ago
    If you want speed, you don't use a linked list in the first place.
    - azernik 6y ago
      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.
      - Dylan16807 6y ago
        > Insertion and deletion of entries are much faster in a linked list than in an array That's a really broad statement. Arrays can get surprisingly big while being faster. Performance-wise, you'd usually want to use arrays up to a certain size and then link between entire arrays. I'd say the biggest advantage of a standard linked list is that it can be intrusive.
        dr_zoidberg 6y ago
        > I'd say the biggest advantage of a standard linked list is that it can be intrusive. That's one big benefit. I teach operating systems and, when the semester has been good, we dig into physical memory dumps with a few python scripts, and show the students how to parse Windows process list following _EPROCESS structures. That's one of the big things they find themselves surprised every year: that the process list is a chain of LIST_ENTRY structures embedded within the _EPROCESSes[0] (or any other structure that is doubly-linked in memory). And LIST_ENTRY is just 2 pointers going hand in hand with list_entry->flink and list_entry->blink attributes and nothing more. [0] You can read some about this structures here https://www.nirsoft.net/kernel_struct/vista/index.html https://www.nirsoft.net/kernel_struct/vista/index.html but beware this is based on Vista and a bit old. Kernel data structures vary with versions of the OS (and not even major versions at that) and target processor (x86, x86-64, ARM too would be reasonable).