5 ms·

Lock free algorithms and data structures are even harder to get right! And most of the canonical descriptions of them assume that you have a garbage collector a

by qppo 6y ago

Lock free algorithms and data structures are even harder to get right! And most of the canonical descriptions of them assume that you have a garbage collector and that memory allocation is a bounded operation. Neither of which is really true when you're working in constrained situations. On top of that, locking is faster than most lock-free strategies unless you deal with high contention or deterimistic guarantees (90% of the latter is solved with bounded fifos).

overgard 6y ago
When I say lock free, im suggesting concurrency that doesn't assume shared memory. I think the notion of multiple cores working on nearby memory blocks just is a bad way to do this, and so threaded models are not great. More along the lines of an actor model or how gpus subdivide work.
- adwn 6y ago
  > [...] how gpus subdivide work. That's a bad example: GPUs are all about shared memory, concurrently accessed by many threads. It's up to the programmer to make sure that there are no read/write or write/write data races.
  - overgard 6y ago
    We're probably talking different GPU coding techniques... I'm not talking about things like annotating C++ code to run on a GPU, I'm thinking shaders where it's very hard/impossible to have side effects outside of what that shader is run on.
- dkersten 6y ago
  So a task/job system with explicit dataflow, where data is handed off to the task that uses it, rather than being shared? A lot of game engines do this nowadays and it works quite well. It doesn't eliminate synchronisation completely, but it does simplify things a good bit. Ideally, any shared data is immutable (and modifying it would then need to be done in a coordinated synchronised fashion) while most mutable state is only ever owned by one task/thread, with ownership explicitly passed between them as others need access, unique_ptr style. Reality doesn't always match with the ideal though.
  - Chris_Newton 6y ago
    most mutable state is only ever owned by one task/thread For many applications, this is the way I prefer to structure code these days. If you know that the only part of your program that will touch certain state directly is always running in a single thread, a lot of problems just go away, because whatever you do in response to any given message or other signal is effectively an atomic transaction, regardless of any concurrency or asynchronous behaviour you have going on elsewhere in your system. You still need to figure out how your message passing or other signalling infrastructure is going to work and in particular what will block and what won’t, so it doesn’t answer all of the usual questions with concurrency, but it’s a widely useful strategy and it goes a long way toward keeping things manageable.

by qppo 6y ago

overgard 6y ago

When I say lock free, im suggesting concurrency that doesn't assume shared memory. I think the notion of multiple cores working on nearby memory blocks just is a bad way to do this, and so threaded models are not great. More along the lines of an actor model or how gpus subdivide work.

adwn 6y ago
> [...] how gpus subdivide work. That's a bad example: GPUs are all about shared memory, concurrently accessed by many threads. It's up to the programmer to make sure that there are no read/write or write/write data races.
- overgard 6y ago
  We're probably talking different GPU coding techniques... I'm not talking about things like annotating C++ code to run on a GPU, I'm thinking shaders where it's very hard/impossible to have side effects outside of what that shader is run on.
dkersten 6y ago
So a task/job system with explicit dataflow, where data is handed off to the task that uses it, rather than being shared? A lot of game engines do this nowadays and it works quite well. It doesn't eliminate synchronisation completely, but it does simplify things a good bit. Ideally, any shared data is immutable (and modifying it would then need to be done in a coordinated synchronised fashion) while most mutable state is only ever owned by one task/thread, with ownership explicitly passed between them as others need access, unique_ptr style. Reality doesn't always match with the ideal though.
- Chris_Newton 6y ago
  most mutable state is only ever owned by one task/thread For many applications, this is the way I prefer to structure code these days. If you know that the only part of your program that will touch certain state directly is always running in a single thread, a lot of problems just go away, because whatever you do in response to any given message or other signal is effectively an atomic transaction, regardless of any concurrency or asynchronous behaviour you have going on elsewhere in your system. You still need to figure out how your message passing or other signalling infrastructure is going to work and in particular what will block and what won’t, so it doesn’t answer all of the usual questions with concurrency, but it’s a widely useful strategy and it goes a long way toward keeping things manageable.