Linked list on Arduino

Programming
1

I’d like to implement a linked list data structure in Kaleidoscope that would be efficient for small numbers of items (typically ≤ 4), but is capable of growing to the size of the total number of keys on the keyboard if necessary. It would get updated (or recreated?) ~once per scan cycle. I’d appreciate advice regarding the best way to implement this from those with more Arduino and/or C++ experience than I have.

(And maybe a linked list is the wrong data structure entirely for what I have in mind. If it slows down substantially when there are more than ~8 items, but it still works, that’s acceptable in my opinion. What I’m after is a list of currently-pressed keys, and if someone’s cat is lying down on the keyboard, I don’t really care if it becomes a bit slower to respond to “input”.)

2

I cannot answer this question for Arduino, but for atmega32u4 and C++ in general.

First of all, it depends what you mean with growing. On other platform this could be conveniently done using dynamic memory allocation. But this is not a good idea on atmegas as its RAM is too limited and many consecutive allocations would require extra RAM for the bookkeeping of the malloc system. That’s even worse when memory is freed as this can lead to fragmentation. Also malloc uses a lot of PROGMEM. That’s why dynamic allocation is usually not used on embedded systems.

Which leaves us with static memory allocation. Your data structure, no matter how it is exactly designed would need to reserve the maximum amount of RAM needed at compile time, e.g. by using statically sized arrays.

The choice of container depends on the type of application (iteration vs. insertion/removal). In your case, a set-type data structure would be optimal (due to the volatile size), but you also probably want to iterate over the list.

If the order of the data stored does not matter, a simple array can hold the entries and there could be an additional index variable that would store the current largest array index used. Any unused items could be tagged with some sort of ‘unused’ value, e.g. 255. When used alone, the iteration complexity always equals the size of the list. Another approach can be to have an auxiliary vector that holds the indices that are currently unused. Thus there would not be any holes in the list and both, iteration and insertion would be fast. I have implemented such a thing probably a hundred times, but currently I do not find an appropriate source code that is simple enough to serve as an example.

Another approach, a static sized doubly linked list can be implemented using two arrays and one or two additional uint8_t as follows.

struct ListEntry {
   FooType value_;
   uint8_t nextEntry_;
   uint8_t prevEntry_;
};
...
ListEntry list[maxKeys];

uint8_t freeEntries[maxKeys];

for(uint8_t id = 0; id < maxKeys; ++id) { freeEntries[id] = id; }

uint8_t nextEntry = 0;

uint8_t listStart = 0;
uint8_t listEnd = 0;

Adding list entries: The next entry will stored at list[freeEntries[nextEntry]], then nextEntry will be incremented. Then .prevEntry and .nextEntry will be set accordingly.

Removing entries: nextEntry will be decremented and the position of the entry removed will be stored in freeEntries[nextEntry]. listStart and listEnd are adjusted if removing at front of back.

A singly linked list is even simpler to implement.

1 Like
3

Thanks; that’s very helpful. I think what I need most is help in narrowing my options. If you think it’s best to avoid dynamic allocation entirely, I’ll just use a simple array instead of a linked list (even a singly-linked list triples the size of what I want to store).

In looking around, I’ve seen quite a few Arduino libraries that seem to use dynamic allocation, but I was quite suspicious of that. I did wonder if it might make sense to use new rather than malloc, which would make it easy to allocate memory for one item at a time, but I think I recall hearing that doing that is very expensive on the ATMega32u4.

Incidentally, a singly-linked list would be sufficient for my purposes (if I were doing dynamic allocation), and would keep the storage size much smaller under all but extreme conditions vs static allocation, so I thought maybe it would be preferable.

4

new in general uses malloc under the hood. Both can be used to allocate single entities or arrays.

5

Just add a single one byte malloc to your sketch, just to see how it affects code size.

6

I guess I’ll have to try that!

In fact, I just came up with a way to do what I want without increasing the storage size at all, by changing the way liveCompositeKeymap[] is used. I’m experimenting with some radical changes.

1 Like
7

As an aside, Arduino is often described as a language of its own, related to C++, but somehow different. This isn’t really accurate. Under the hood, Arduino is just a bunch of conveniences that hides some of the complexity of C++; the language is C++, and the code ultimately gets compiled by gcc-avr, and uploaded by avrdude, just like you’d do with ‘normal’ atmega development.

As a newcomer to embedded development and C++, this was really confusing. A one-paragraph intro to Arduino for C programmers, explaining how Arduino transforms an .ino file to make it compilable by gcc-avr, would have save me a lot of confusion early on.

2 Likes
8

What I meant is that I am new to the Arduino ecosystem. There might be a suitable Arduino library for list data structures out there.

9

Yes, understood. Your answer demonstrates you’ve got a much stronger grasp of this stuff than I do!

I didn’t intend to criticize your point at all, only clarify. I’m sure the relationship between Arduino and C++ is obvious for anyone with some experience with embedded development, but given the way it’s often presented (elsewhere), it took me a while to figure it out.

1 Like
10

Your post was certainly helpful to other readers.

I just wanted to emphasize that it might be worthwile searching the huge amount of Arduino libraries out there. We might not be the first ones that are confronted with the platform’s limited resources and others might have needed a list container, before.

11

The trouble I have with grabbing those contributed libraries (I had looked around) is that I’m suspicious of their quality. They tend to be re-implementations of things from the STL which were left out of Arduino on purpose, and they use malloc and/or new liberally.

12

That’s an impressive difference. 630 bytes of program memory, 11 bytes of data. (For new, it’s 634 more bytes of program).

1 Like
13

Do you really need it to be dynamically large? Could you just set a max size and statically allocate an array for all the data? You could easily build a linked list type structure on that by keeping a start and end index and looping around.

14

Yes, I could (and it turns out that’s what I’ll do). But when I posed the question, I was considering something that would typically only require a few entries (rarely more than 4), but needed to be able to grow (in theory) to accommodate up to the number of keys on the keyboard, which seemed wasteful, since it basically never happens that all of the keys are pressed simultaneously. It turns out that just including malloc or new anywhere in a sketch uses far more memory than would be saved, however, so it’s pointless to try being frugal by using dynamic allocation.

15

i’d also be curious to know what the cost of malloc/free is processing wise. it’s gotta be pretty intense.

16

That I cannot easily answer; I haven’t tried measuring any kind of performance metrics. I can say that I don’t really care, if I need to sacrifice that many bytes just to get it.