Just interviewed for an embedded dev position. The interviewer told me it is rare to find a candidate that can tell why a linked list is a bad data structure choice for embedded systems. I guess it goes down to a fine knowledge gap between CS and EE curriculum.

There is a "Computer Engineering" major in my university. C/C++ and state machines are taught in a freshmen year course. However, digital electronics / communication protocols / debugging is never taught in class. Practically everyone who know what SPI or I2C means is either an electronics hobbyist or member of a student competition team.

Part of the problem that I sense in the embedded systems world is that there is often huge differences in philosophical outlooks and development perspectives. In that, many in that world want to always be in the nuts and bolts of everything. For me, the perspective is to always be as high-level as possible when you can get away with it, leaving FPGAs and real-time OSs for things that actually need to be on an FPGA or real-time. The problem with this is that there are not very many who can bridge the gap between FPGAs, real-time programming, and high-level software.

I personally am very interested in the "software for hardware" realm, but it is a little difficult to find people doing interesting approaches. It's usually all Verilog or all VHDL on FPGAs with a smattering of HLS, all C/C++ embedded software, all high-level programming languages with soft real-time on single-board computers or something similar, or somewhere in between with something like LabVIEW. But there's usually almost no overlap between the people that do work in each of those categories.

There's a lot of constraints in these systems and almost all of the innovation has come at sort of the chip level in terms of hardware performance. The design and development process, tools, and experience have seen little innovation, as far as I can tell. Everything remains hard in embedded systems. I don't see any reason why it needs to be that way though.

You're right that it doesn't have to be that way, but there are good reasons it's remained so. Code re-use in ES is fiendishly difficult because every system is a special little snowflake. Moreover, ES teams are fantastically understaffed relative to the complexity of the systems they own.

Because nothing works by default on ES systems, you have to implement it yourself most of the time. If you can clear that hurdle, your company is unlikely to be open source friendly. If you can clear that hurdle, people on other teams won't have time to adopt it for their systems, so it won't spread. If you can clear all of that, all you've won is a single tool. In the meantime, the rest of the industry as written half a dozen.

There are things you can do here, but... yeah.

I'll bite: why shouldn't you use a linked list for an embedded system? As opposed to a contiguous, dynamically allocated data structure, I mean.

A couple of reasons, both to do with the fact that data memory is scarce on embedded systems. One is that it has high memory overhead (every entry includes a pointer), two is that making many small allocations can cause memory fragmentation, especially with the kinds of allocators commonly used in embedded systems.

Also if time is scarce, following pointers is slower than calculating offsets, but that's usually not an issue worth thinking about.

Oh ok. Counterpoint: allocating a single node if memory is already fragmented will succeed where growing a vector would fail. But I suppose the point of the question is being able to discuss the issues involved.

You don't have to worry about dozens of other applications fragmenting your memory. You keep your threads neat and your memory neat, and you don't have to worry about failed allocations.

Another reason to keep memory contiguous is that fragmentation can be much more punishing (sometimes), especially when latency is important. On large devices it doesn't matter much if you're under-utilizing the CPU while waiting for RAM, because the OS will do other things and then let you do a lot of work all at once. Embedded processors will have nothing else to do.

I feel like in many embedded systems you'd use a fix sized vector/buffer rather than a growable one.

I think it's the dynamic allocation that's considered bad? Other than at initialization.

It seems like allocating nodes out of a fixed size array wouldn't be too bad, though.

I used to interview embedded engineers, and I was one for a very short time. I think the issue is that many embedded engineers are not good at articulating when a linked list is preferable compared to a continuous data structure. The times when a linked list is better are getting increasingly rare as "embedded" increasingly means "includes a raspberry pi."

On devices with 1 GB of memory, the contiguous structures are usually better, but embedded developers often still reach for linked lists. On devices with 1 kB of memory, trained software engineers will scoff at linked lists and instead waste hundreds of bytes on large buffers sized for peak usage.

I'd say a linked list is preferable when you're writing a `malloc` implementation. It makes the code simple to understand (and small), you don't have any dynamic memory allocation available (because you're writing your system's allocator), and the size overhead is lower than alternatives. Linked lists aren't that bad in processors that lack cache, since then walking the list won't incur cache misses (every memory access is equally slow).

There are alternatives, of course. Your particular target might perform poorly with linked lists, so you might make your malloc use a different internal data structure. Or you might have plenty of flash but not much RAM, so you might trade code size for runtime overhead. Or... There are lots of alternatives, but a linked list is the simple default.

Arena/buffer-based allocation is also used to avoid an OOM at runtime not due to the lack of memory per se but due to fragmentation.

I recently interviewed for an embedded position, and had a set of similar questions. The right answer is, of course, "It depends".

If you've got 6 bytes of free code space and/or you're scrambling for RAM, you look at everything for space savings.

If the hardware team comes to you apologetically and says, "We're sorry, but for cost reasons we have to /double/ the amount of DRAM and flash and give you a faster, more power efficient SOC" then you may not have to worry about this level of detail.

Both of these have happened to me on prior projects. There are no fixed answers.

(Whenever I've gotten one of these types of questions in an interview, I try to have a broader conversation on the subject rather supply the answer they are looking for. If that goes badly, it's a big red flag).

That's not a particularly good interviewing question, in my opinion.

College curricula vary wildly in quality and content. I don't know of one that quite teaches you everything you need to know to be a functional embedded developer.

Seems like a linked list (and set dressing) is circumstantial.

Is it because linked lists can be slow and can sometimes pocket arbitrary data?

I feel like strong typing and limiting pointers in favor of runners combats this.

> I suspect it's because much of the field is actually quite junior

Most of the people I know in embedded development are greybeards. There aren't a lot of younger people going into the field. The schools don't seem to be prepping a lot of people for these kinds of jobs. (not sure what we're going to do because a lot of these guys are in their 60s and about ready to retire)

> These skills take years to accumulate.

Indeed. Which is why the low pay is all the more puzzling, but I have theories: As mentioned above, most embedded devs are greybeards. They don't move around much. They probably aren't as familiar with the much higher pay people are getting at the FAANGs, etc. They aren't as likely to have a LinkedIn profile or if they do they don't spend much time there. As an older dev myself, it's not like I'm clamoring for higher pay: my mortgage payment is quite low compared to rent (and will be paid off completely next year), my cars are old but paid off, don't have any debt other than the soon-to-be-paid off mortgage. All this to say that older devs maybe don't make as much money because they're not as aware of market rates and they don't really feel like they need a lot more money if they're happy where they're at.

I know at least five people doing embedded systems work in the greater Boston area who are comfortably pulling in north of $200k a year.

The pay is there. I'm not sure why there's this persistent notion that it's not.

That's well above the 95th percentile for Boston, and a bit above 90th for south bay. As someone who is in embedded above that level as well, I can assure you that it's a highly abnormal situation for the vast majority of ES devs. Most companies pay far below what they compensate other SWEs at. 100k-200k total compensation is about the norm for the majority of the market.

We can't even find anyone who knows what a cache line is...

That's what a CPU snorts before it goes to catch the bus.

maybe you shouldnt be interviewing people for specific terminology. People can learn. Experienced competent people can definitely learn. Maybe they know the concept, but not the term. Maybe they need a little guidance about what you want out of the question. Do you want them to know "cache line" the phrase? or do you want them to understand memory structure? etc...

> maybe you shouldnt be interviewing people for specific terminology. People can learn. Experienced competent people can definitely learn.

I generally agree, but "cache line" is a pretty low bar though, no? I'm a web developer with no formal CS background and I've known what a cache-line is since the first year I started to learn to code. Every textbook on my shelf that even tangentially relates to the kind of work embedded devs do makes reference to cache-lines, and god knows how many articles I've read over the years.

Training people from what is probably nothing is a pretty big bet on the part of a team and employer...

We all look up super simple stuff we learned in year one of engineering school. I'm not sure I would call reading a little "training". I just think interviewing should be a little more forgiving. Interviewers like to gate keep a little with little gotchas in an environment that is completely different than day to day work.

> We all look up super simple stuff we learned in year one of engineering school. I'm not sure I would call reading a little "training". I just think interviewing should be a little more forgiving. Interviewers like to gate keep a little with little gotchas in an environment that is completely different than day to day work.

I don't disagree with any of this, I just think there's a certain "base" of knowledge for certain jobs that needs to be so well understood that it's automatic. For an embedded engineers I think "cache line" is part of that base in much the same way I would consider it a hard requirement for any incoming frontend web-developer to know what the DOM is.

Somewhat disagree, depending on the embedded subset. Lots of MCUs don't have any cache, so they don't have any cache lines. If you're programming some sort of embedded Linux system you'll have a more powerful processor and almost certainly have cache.

So if you're hiring for MCU work (bare metal or RTOS) the concept of a cache line isn't important. If you're hiring for application processor work (often Linux), it's very important.