3 ms·

I think the key advantage they are describing for their bag is that it allows you to claim a element then operate on that element independently. This avoids hea

by Veserv 1y ago

I think the key advantage they are describing for their bag is that it allows you to claim a element then operate on that element independently. This avoids head-of-line blocking caused by things like random context switching mid-processing. However, that can be implemented with a MPMC queue with no exotic operations with precise O(1) behavior with no size bounds. For a bag with two N-bit bit-vectors, just have two N-bit queues of indexs. Dequeue on acquire (giving you a unused index) and enqueue on release (releasing your now used index). If anybody finishes processing quickly, they release back to the queue for new processing which means there is no head-of-line blocking. Only by having all N actively processing do you wait. I guess you also still have the tiny window on enqueue between reserving the slot and actually writing out the index where you could tear due to a perfectly sub-optimal context switch.

Veserv 1y ago
If you want a exotic operation to make this better, then you would want a uninterruptible two-instruction sequence of: "atomic modify, then use old value as index for indexed store". So that would be a instruction with 4 parameters: memory location for atomic, atomic modify argument, base memory location for store, register value to store; and the instruction itself would encode the operation and store scale/stride. Importantly, the indexed store does not need to be atomic with respect to the first, it merely needs to be ordered after it with a guarantee that a context switch or interrupt can not result in partial completion. This is a much weaker requirement than making multiple cache-line loads/stores fully atomic with respect to each other. Such a operation would improve multi-producer queues with fixed-size elements smaller than a word and would likely be fairly trivial to implement, merely requiring fusion of two existing instructions in a way that prevents interruption between them.

by Veserv 1y ago

Veserv 1y ago

If you want a exotic operation to make this better, then you would want a uninterruptible two-instruction sequence of: "atomic modify, then use old value as index for indexed store". So that would be a instruction with 4 parameters: memory location for atomic, atomic modify argument, base memory location for store, register value to store; and the instruction itself would encode the operation and store scale/stride. Importantly, the indexed store does not need to be atomic with respect to the first, it merely needs to be ordered after it with a guarantee that a context switch or interrupt can not result in partial completion. This is a much weaker requirement than making multiple cache-line loads/stores fully atomic with respect to each other. Such a operation would improve multi-producer queues with fixed-size elements smaller than a word and would likely be fairly trivial to implement, merely requiring fusion of two existing instructions in a way that prevents interruption between them.