4 ms·

What if entry doesn't exist in the list? You need a special case to handle that too.

by 762236 6y ago

asdfasgasdgasdg 6y ago
Normally with an identity-based API like this, you can put it as a requirement that you must not remove items other than those which actually exist in the collection. Another example of an API that doesn't check for presence: c++ iterator-based removal. If you ask a C++ list to remove an iterator element outside its range, it may crash the program. See the exception safety section of this documentation: http://www.cplusplus.com/reference/list/list/erase/ http://www.cplusplus.com/reference/list/list/erase/ If you look at most "remove this object from yourself" APIs in low-level code, it behaves this way, because it's unnecessarily complex to check for presence when that is a fact the program can condition on instead.
- Retric 6y ago
  Unnecessary is not really the correct term, it’s one of a huge number of tradeoffs. The you don’t want it for safety critical systems, but Linux isn’t designed to be used for such things.
- mehrdadn 6y ago
  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.
kbumsik 6y ago
Well, both implementations will crash in that case anyway. You can take that case as out of scope of this discussion. The purpose of the OP and the Linux's talk is to show a better way to walk through linked list, not to show a full implementation.

What if entry doesn't exist in the list? You need a special case to handle that too.

by 762236 6y ago

What if entry doesn't exist in the list? You need a special case to handle that too.

Normally with an identity-based API like this, you can put it as a requirement that you must not remove items other than those which actually exist in the collection. Another example of an API that doesn't check for presence: c++ iterator-based removal. If you ask a C++ list to remove an iterator element outside its range, it may crash the program. See the exception safety section of this documentation: http://www.cplusplus.com/reference/list/list/erase/ http://www.cplusplus.com/reference/list/list/erase/ If you look at most "remove this object from yourself" APIs in low-level code, it behaves this way, because it's unnecessarily complex to check for presence when that is a fact the program can condition on instead.

Retric 6y ago
Unnecessary is not really the correct term, it’s one of a huge number of tradeoffs. The you don’t want it for safety critical systems, but Linux isn’t designed to be used for such things.
mehrdadn 6y ago
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.

kbumsik 6y ago

Well, both implementations will crash in that case anyway. You can take that case as out of scope of this discussion. The purpose of the OP and the Linux's talk is to show a better way to walk through linked list, not to show a full implementation.