Lockless Parallel Work Distribution

  • 0
    Sounds nice.
  • 1
    @Root I have a list of items to be processed in parallel so I need a way to distribute them to threads without starving any thread of work while also doing as little synchronization as possible

    One way is a work-stealing scheduler I guess
  • 1
    @12bitfloat I know what it is. I'm curious about your plans for it. Sorry if that wasn't clear!
  • 1
    @Root It's for my entity component system thingy.
    To avoid shared mutable state I give access to entity data in a for-each way (based on assigned components and some other filters). This is great because this allows for complete automatic parallelization without any synchronization on the entity data

    But now I have the problem of a parallel iterator: All the work threads need to consume the next entity for processing. Using locks or even an atomically incremented index variable won't do though for performance reasons.
    That's where I'm stuck :(
  • 1
    @12bitfloat I don't know if this goes well with the paradigms of your current language, but that do you think about back pressure?

    Basically, you have one thread that distributes batches of entities to worker threads and when the worker thread realizes it's running low it on work, it requests the next batch. Asynchronously, if possible

    It's called back pressure, because the worker threads are not overloaded with work,because they only request as much work as they can handle and the pressure is on the scheduler, because he has to constantly supply the items.

    Idea from Elixir GenStage
  • 0
    @Awlex That does sound like a really good idea actually. Maybe have like two small local queues per thread that get flipped atomically. While one is being refilled, the worker thread works on the other one. This should also help a lot with work balancing without having to work steal
Add Comment