5 ms·

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 ch

by gaudat 4y ago

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.

shirleyquirk 4y ago
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.
- tines 4y ago
  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.
  - shirleyquirk 4y ago
    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.
    - nicoburns 4y ago
      I feel like in many embedded systems you'd use a fix sized vector/buffer rather than a growable one.
    - hwillis 4y ago
      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.
- skybrian 4y ago
  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.
- pclmulqdq 4y ago
  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.
  - smarx007 4y ago
    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.
  - SAI_Peregrinus 4y ago
    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.
cushychicken 4y ago
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.
kabdib 4y ago
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).
scollet 4y ago
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.
bmitc 4y ago
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.
- AlotOfReading 4y ago
  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.

by gaudat 4y ago

shirleyquirk 4y ago

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.

tines 4y ago
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.
- shirleyquirk 4y ago
  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.
  - nicoburns 4y ago
    I feel like in many embedded systems you'd use a fix sized vector/buffer rather than a growable one.
  - hwillis 4y ago
    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.
skybrian 4y ago
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.
pclmulqdq 4y ago
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.
- smarx007 4y ago
  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.
- SAI_Peregrinus 4y ago
  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.

cushychicken 4y ago

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.

kabdib 4y ago

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).

scollet 4y ago

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.

bmitc 4y ago

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.

AlotOfReading 4y ago
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.