Hacker News Reader

Comment by person_of_color | Hacker News Reader

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.

View on HN

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.

Self driving car company

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

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.

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

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#Probl...

Its not hard but Ive never used CAS instrinsics.

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

Reply on news.ycombinator.com