3 ms·

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

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