3 ms·
Honest question: What's the value, if any, of using intrusive linked lists in this context? That is, I would have handled linked lists as something like: s
by jdmichal 11y ago
Honest question: What's the value, if any, of using intrusive linked lists in this context? That is, I would have handled linked lists as something like:
struct TN_ListItem {
TN_ListItem * prev;
TN_ListItem * next;
void * data;
}
I can immediately see that each TN_ListItem would take up an extra word of memory in order to store the pointer to the data. Is that the main crux of the issue, or is there something more?
- AnimalMuppet 11y agoTwice the allocations? That can matter for performance reasons.
- Gracana 11y agoOr even more if the item is included in multiple lists.
- gliptic 11y agoFor instance, more allocations necessary, extra pointer indirection, higher memory use, worse cache locality, needing the TN_ListItem* to perform list operations.
- dimonomid 11y agoTNeo never allocates memory from heap: it only operates on objects that are given as parameters to some system services. And this is really good: a great deal of embedded systems don't use heap at all (since heap behaviour is not deterministic enough). So, for example, when task is waiting for some mutex, this task is added to the list of waiting tasks of this mutex, and this operation is O(1), that is, it is always done in constant time. With the implementation you proposed, we have two options: 1) When adding new object to some linked list, TNeo should internally allocate this list item from heap (or from some preallocated pool); 2) The client should allocate TN_ListItem-s manually (in whatever way), and provide it to any system service that may need it. Both options are unacceptable.