3 ms·

I often write code destined to run on a microcontroller, and linked lists are great for avoiding dynamic memory. It's nice to be able to statically or transient

I often write code destined to run on a microcontroller, and linked lists are great for avoiding dynamic memory. It's nice to be able to statically or transiently allocate storage without having to bound the size of anything. Of course, the same unintuitive tradeoffs tend to apply even if there isn't much caching to worry about. A trivial linear iteration is often faster than a more elaborate algorithm when the input is small.

bitexploder 4y ago
Carmack is a fan of this approach. Allocate some reasonably large number as your design constraint and if you start approaching it that is a time to ask why and is this data structure still reasonable here
KerrAvon 4y ago
A memory-constrained microcontroller is actually one of the valid exceptions to the rule.
- Sirened 4y ago
  Well, yes, and a lot of people treat kernel development as if they were developing for a constrained microcontroller. I don't think this is even a bad thing, we want the kernel to be as lean as possible because every page and cycle the kernel burns is one that users don't get to use.
  - jstimpfle 4y ago
    I suppose a more important reason is the "not have to bound anything" part. OS kernels almost definition don't know how many objects will be created. Implementing queues as vectors of pointers will require dynamic allocation and/or introduce many more failure points when going out of resources. With linked lists, once you have an object you can always append it to a linked-list queue.
  - Dylan16807 4y ago
    This is a memory vs. time tradeoff. And the time cost gets worse as the machine gets bigger. Designing for embedded is not the same thing as being lean.
- rcxdude 4y ago
  It's also an area where the costs are a lot less significant either: a cortex m4 and below often doesn't have a cache (at least for RAM: flash often has a cache and predictive lookup, but the perfomance difference is small enough that the cache can basically render executing code from flash as identical to RAM), and the RAM is about as fast as the processor, so random access and sequential access are pretty similar performance wise. (And with the speed of modern microcontroller cores the size of the data is rarely even an issue: most STM32s can iterate through their entire RAM in under a millisecond). That said, in my embedded work I still rarely find a linked list to be a useful data structure (but I know FreeRTOS, which I use a lot, uses them extremely heavily internally).
G3rn0ti 4y ago
That‘s why the Amiga OS (Exec) used linked lists as its primary data structure. It was one of the first micro computer operating systems using dynamic memory mapping (i.e. no fixed addresses for OS calls and data structures) and supported multi tasking. Any object you received from Exec basically was a pointer to a list node. And, yes, the Amiga‘s biggest problem was memory fragmentation and leakage because unreachable linked list nodes would be starting to accumulate whenever working with a buggy program.

bitexploder 4y ago

Carmack is a fan of this approach. Allocate some reasonably large number as your design constraint and if you start approaching it that is a time to ask why and is this data structure still reasonable here

KerrAvon 4y ago

A memory-constrained microcontroller is actually one of the valid exceptions to the rule.

Sirened 4y ago
Well, yes, and a lot of people treat kernel development as if they were developing for a constrained microcontroller. I don't think this is even a bad thing, we want the kernel to be as lean as possible because every page and cycle the kernel burns is one that users don't get to use.
- jstimpfle 4y ago
  I suppose a more important reason is the "not have to bound anything" part. OS kernels almost definition don't know how many objects will be created. Implementing queues as vectors of pointers will require dynamic allocation and/or introduce many more failure points when going out of resources. With linked lists, once you have an object you can always append it to a linked-list queue.
- Dylan16807 4y ago
  This is a memory vs. time tradeoff. And the time cost gets worse as the machine gets bigger. Designing for embedded is not the same thing as being lean.
rcxdude 4y ago
It's also an area where the costs are a lot less significant either: a cortex m4 and below often doesn't have a cache (at least for RAM: flash often has a cache and predictive lookup, but the perfomance difference is small enough that the cache can basically render executing code from flash as identical to RAM), and the RAM is about as fast as the processor, so random access and sequential access are pretty similar performance wise. (And with the speed of modern microcontroller cores the size of the data is rarely even an issue: most STM32s can iterate through their entire RAM in under a millisecond). That said, in my embedded work I still rarely find a linked list to be a useful data structure (but I know FreeRTOS, which I use a lot, uses them extremely heavily internally).

G3rn0ti 4y ago

That‘s why the Amiga OS (Exec) used linked lists as its primary data structure. It was one of the first micro computer operating systems using dynamic memory mapping (i.e. no fixed addresses for OS calls and data structures) and supported multi tasking. Any object you received from Exec basically was a pointer to a list node. And, yes, the Amiga‘s biggest problem was memory fragmentation and leakage because unreachable linked list nodes would be starting to accumulate whenever working with a buggy program.