3 ms·

multithreading with shared state introduces several limitations: 1. random jumps in memory and branch misses 2. L1/L2 cache flush 3. context switch cost

by slt2021 3y ago

multithreading with shared state introduces several limitations: 1. random jumps in memory and branch misses 2. L1/L2 cache flush 3. context switch cost 4. concurrency locks cost my understanding is that LMAX eliminated these costs: 1. pre-allocated arena ensures cache locality of operations 2. we dont jump form one sector of memory into another. Algorithm more resembles linear scanning of working memory set, and mostly within L1/L2 cache 3. no context switches, no cache flushes 4. no concurrency control costs

opportune 3y ago
Yes, but LMAX is a constrained model. With a producer:consumer dichotomy you don’t have to consider synchronization among consumers. Let’s say you did try to implement that in LMAX. It’s common for consumers/“workers”/what have you to require synchronizations amongst themselves, for example if they are operating on a shared k:v store of strings (operating an in-memory db let’s say). You can’t do atomic reads or writes on the thing so you need a locking mechanism; under LMAX you’d have to introduce another layer of producers to control reads and writes and then have another layer of consumers afterwards to handle the rest of your “consumer flow”, or wait in the original consumer thread for the producer to complete, which starts getting very wasteful and is certainly no better than a typical regular locks and context switching. Again, this is not even a new thing. Lock free queues and “local atomic concurrent pub-sub” have existed for a long time - we have an implementation where I work. It’s not a perfect model even for where that concurrency pattern is wholly sufficient for what you’re doing either - the performance boost from the cache and context switching improvements have to be greater than the slack (in cost or throughput) introduced from producers or consumers sitting idle waiting for upstream data. Also, context switches/cache invalidation/concurrency overhead can be avoided or at least greatly reduced by smart userspace scheduling a la fibers. With hand tuning it can potentially be completely eliminated (you can control which concurrency units to collocate on a thread and resume concurrency units/threads immediately after their waiting locks free) which is basically the same idea as LMAX. The problem of course, like with LMAX, is that doesn’t generalize.

opportune 3y ago

Yes, but LMAX is a constrained model. With a producer:consumer dichotomy you don’t have to consider synchronization among consumers. Let’s say you did try to implement that in LMAX. It’s common for consumers/“workers”/what have you to require synchronizations amongst themselves, for example if they are operating on a shared k:v store of strings (operating an in-memory db let’s say). You can’t do atomic reads or writes on the thing so you need a locking mechanism; under LMAX you’d have to introduce another layer of producers to control reads and writes and then have another layer of consumers afterwards to handle the rest of your “consumer flow”, or wait in the original consumer thread for the producer to complete, which starts getting very wasteful and is certainly no better than a typical regular locks and context switching. Again, this is not even a new thing. Lock free queues and “local atomic concurrent pub-sub” have existed for a long time - we have an implementation where I work. It’s not a perfect model even for where that concurrency pattern is wholly sufficient for what you’re doing either - the performance boost from the cache and context switching improvements have to be greater than the slack (in cost or throughput) introduced from producers or consumers sitting idle waiting for upstream data. Also, context switches/cache invalidation/concurrency overhead can be avoided or at least greatly reduced by smart userspace scheduling a la fibers. With hand tuning it can potentially be completely eliminated (you can control which concurrency units to collocate on a thread and resume concurrency units/threads immediately after their waiting locks free) which is basically the same idea as LMAX. The problem of course, like with LMAX, is that doesn’t generalize.