Ring algorithm with fewer cache misses

Ring algorithm with fewer cache misses

[Morten Brørup]

Hi Honnappa, Konstantin, Bruce and Gavin,

You might find this ring algorithm optimization article interesting:
https://rigtorp.se/ringbuffer/


It adds the following optimization:

The single-producer put() operation keeps a cache of the consumer's index. If the cached consumer index indicates that there was still sufficient room in the ring after the previous put() operation, it doesn't need to fetch the actual consumer index, and thus avoids a potential L1 cache miss (because the actual consumer index is written by the consumer threads).

If the cached index doesn't indicate that there is sufficient room in the ring, the operation behaves like without the optimization, i.e. it proceeds to fetch the actual consumer index (and writes it to its cache) and determines if there is sufficient room in the ring.


Similarly, the single-consumer get() operation caches the producer's index to determine if there were still sufficient objects present in the ring after the previous get() operation.


Med venlig hilsen / Kind regards,
-Morten Brørup

RE: Ring algorithm with fewer cache misses

[Konstantin Ananyev]

Hi Morten,
 
> Hi Honnappa, Konstantin, Bruce and Gavin,
> 
> You might find this ring algorithm optimization article interesting:
> https://rigtorp.se/ringbuffer/
> 
> 
> It adds the following optimization:
> 
> The single-producer put() operation keeps a cache of the consumer's index. If the cached consumer index indicates that there was still
> sufficient room in the ring after the previous put() operation, it doesn't need to fetch the actual consumer index, and thus avoids a
> potential L1 cache miss (because the actual consumer index is written by the consumer threads).
> 
> If the cached index doesn't indicate that there is sufficient room in the ring, the operation behaves like without the optimization, i.e. it
> proceeds to fetch the actual consumer index (and writes it to its cache) and determines if there is sufficient room in the ring.
> 
> 
> Similarly, the single-consumer get() operation caches the producer's index to determine if there were still sufficient objects present in
> the ring after the previous get() operation.
> 

Indeed, that sounds like an interesting idea and worth to explore.
Thinking a bit more - it probably could be extended to classic MP/MC case too -
If we can update cons/prod head and this cached value atomically (CAS64?).
Thanks
Konstantin