5 ms·

This is now fundamental apparently. I was failed out of an interview because I wasn’t able to make a lockless linked list using atomics.

nyanpasu64 6y ago
I mean, I can do it, I've done it... but yikes. Where did you interview at, and for what kind of position?
ddlutz 6y ago
I'm curious where this is? Unless you are interviewing for a very specific position that listed lockeless programming as a requirement or you claimed to have 'very advanced multithreading' experience I can't see this being reasonable.
- person_of_color 6y ago
  Self driving car company
  - earthboundkid 6y ago
    It must be noted that if self driving cars can't rely on library implementations of locking/lockless structures, they're even further from reality than it seems. I feel like for all these questions the "correct" answer should be "I would never waste company time by faffing around reading papers about implementing lockless structures when I could be solving an actual business problem."
    - nyanpasu64 6y ago
      When you're dealing with low-latency real-time systems (I've worked with audio programming but not embedded systems, and self-driving cars are even more safety-critical), lock-free algorithms can be useful for solving the business problem of guaranteed maximum response times. (The issue is that lock-free algorithms are easy to design/implement incorrectly, resulting in heisenbugs which could be dangerous in a self-driving car.) Many ad-hoc queues/channels available in pre-existing libraries contain locks, and are unsuited for real-time applications. Even among lock-free data structures, there are many tradeoffs (fixed-size ring buffers vs. dynamically allocated linked lists, SPSC, MPMC, and everything in between, or even using triple buffering instead of queues). Sometimes it's worth implementing an algorithm yourself, instead of scouring the Internet for suitable libraries. Though I don't know if an embedded RTOS's compiler libraries will supply headers for lock-free algorithms, or make you find your own.
millstone 6y ago
Can you say more? Lockless linked lists are unreasonably hard for an interview problem.
NavinF 6y ago
I'm probably not the only one wondering why this is hard: Why not just declare prev/next as atomic pointers, CAS to delete, copy-and-CAS to insert, and call it a day right? Turns out that doesn't work if you want to delete a node while another thread is inserting a node in that spot: https://en.wikipedia.org/wiki/Non-blocking_linked_list#Problems https://en.wikipedia.org/wiki/Non-blocking_linked_list#Probl...
- person_of_color 6y ago
  Its not hard but Ive never used CAS instrinsics.

nyanpasu64 6y ago

I mean, I can do it, I've done it... but yikes. Where did you interview at, and for what kind of position?

ddlutz 6y ago

I'm curious where this is? Unless you are interviewing for a very specific position that listed lockeless programming as a requirement or you claimed to have 'very advanced multithreading' experience I can't see this being reasonable.

person_of_color 6y ago
Self driving car company
- earthboundkid 6y ago
  It must be noted that if self driving cars can't rely on library implementations of locking/lockless structures, they're even further from reality than it seems. I feel like for all these questions the "correct" answer should be "I would never waste company time by faffing around reading papers about implementing lockless structures when I could be solving an actual business problem."
  - nyanpasu64 6y ago
    When you're dealing with low-latency real-time systems (I've worked with audio programming but not embedded systems, and self-driving cars are even more safety-critical), lock-free algorithms can be useful for solving the business problem of guaranteed maximum response times. (The issue is that lock-free algorithms are easy to design/implement incorrectly, resulting in heisenbugs which could be dangerous in a self-driving car.) Many ad-hoc queues/channels available in pre-existing libraries contain locks, and are unsuited for real-time applications. Even among lock-free data structures, there are many tradeoffs (fixed-size ring buffers vs. dynamically allocated linked lists, SPSC, MPMC, and everything in between, or even using triple buffering instead of queues). Sometimes it's worth implementing an algorithm yourself, instead of scouring the Internet for suitable libraries. Though I don't know if an embedded RTOS's compiler libraries will supply headers for lock-free algorithms, or make you find your own.

millstone 6y ago

Can you say more? Lockless linked lists are unreasonably hard for an interview problem.

NavinF 6y ago

I'm probably not the only one wondering why this is hard: Why not just declare prev/next as atomic pointers, CAS to delete, copy-and-CAS to insert, and call it a day right? Turns out that doesn't work if you want to delete a node while another thread is inserting a node in that spot: https://en.wikipedia.org/wiki/Non-blocking_linked_list#Problems https://en.wikipedia.org/wiki/Non-blocking_linked_list#Probl...

person_of_color 6y ago
Its not hard but Ive never used CAS instrinsics.