“Usually” SPSC means it is optimized for that case but it doesn’t fail in case of multiple writers. It it usually easier to prevent multiple readers as the reader can be controlled during init and hidden.
> On Mar 11, 2022, at 4:41 PM, 'Axel Wagner' via golang-nuts > <golang-nuts@googlegroups.com> wrote: > > > > >> On Fri, Mar 11, 2022 at 4:51 PM Gregg Townsend <gtowns...@gmail.com> wrote: >> Well, the suggested code passes the race detector, but shouldn't it also be >> *correct*? >> Two concurrent calls of Put can load identical head and tail values and then >> store in the same slot. > > The premise is that there is a single consumer and a single producer (hence > "SPSC"). > The assumption was that OP specifically wanted something fitting that > use-case. > If you have multiple producers/consumers, a buffered channel is obviously a > better alternative. > >> See >> https://go.dev/play/p/gagBCCj2n2g?v=gotip >> for a demonstration. >> >> >>> On Friday, March 11, 2022 at 12:24:42 AM UTC-7 axel.wa...@googlemail.com >>> wrote: >>> I found a lock-free ringbuffer implementation written in C, which seems to >>> do what you want: >>> https://github.com/QuantumLeaps/lock-free-ring-buffer/blob/main/src/ >>> This is a relatively direct translation to Go, using generics from go 1.18 >>> (to be released very soon): >>> https://go.dev/play/p/nNEt66r71Yf?v=gotip >>> I tried running it with -race and got no complaints. >>> >>>> On Fri, Mar 11, 2022 at 7:52 AM Axel Wagner <axel.wa...@googlemail.com> >>>> wrote: >>>> Uhm, I just actually looked at the code. >>>> You still use `r.start %= N`, which is a non-atomic access to r.start. >>>> AIUI, SPSC stands for "single producer, single consumer", i.e. you know >>>> that Get and Put will only be called from a single goroutine, >>>> respectively? In that case, you wouldn't even need atomics to manipulate >>>> r.start/r.end. Of course, you can't have a guarantee that your ringbuffer >>>> does not overflow, that way. >>>> But ISTM to make the conceptual code work with the race detector, you >>>> should use atomic.Values for the elements of the slice and then can use >>>> non-atomic accesses to r.start/r.end. >>>> >>>>> On Fri, Mar 11, 2022 at 7:45 AM Axel Wagner <axel.wa...@googlemail.com> >>>>> wrote: >>>>> You probably want to make the element type of the slice an atomic.Value, >>>>> instead of an interface{}. You shouldn't need a mutex then. >>>>> >>>>>> On Fri, Mar 11, 2022 at 7:31 AM Cameron Elliott <gar...@gmail.com> wrote: >>>>>> >>>>>> >>>>>> Ian, thank you very much for the suggestion to use atomics. >>>>>> Unfortunately, for a standard SPSC ring buffer, I don't think it does >>>>>> the trick. >>>>>> >>>>>> >>>>>> I am attaching a simple ring buffer program at the end. >>>>>> >>>>>> If you run 'go run -race main.go' on the example, >>>>>> a race will occur. >>>>>> The race that occurs is a write, then read to the >>>>>> same element of a slice on two different goroutines. >>>>>> >>>>>> Of course a race-detected is expected. >>>>>> >>>>>> This can be fixed by mutexing Put() and Get(), >>>>>> because through some magic, mutexs affect the tables/tags >>>>>> the race detector maintains in order to catch races. >>>>>> >>>>>> Using sync.atomic on the ring buffer indexes doesn't >>>>>> affect the race-detector state for read and writes. >>>>>> >>>>>> I spent more time investigating, it seems there are >>>>>> two ways to make a traditional ring buffer compatible >>>>>> with the race detector: >>>>>> >>>>>> 1. Use build tags to conditionally Lock/Unlock mutexes >>>>>> where you would not actually need them, in order to reset >>>>>> the race detector on the object crossing goroutines. >>>>>> >>>>>> 2. Use the pragma //go:linkname to get access to the 'runtime.race' >>>>>> functions, in order to call Enable()/Disable/ReleaseMerge/Aquire >>>>>> as sync.Pool does in order to make the race detector happy. >>>>>> >>>>>> If there are other methods, please let me know! >>>>>> Thanks for any feedback! >>>>>> >>>>>> Cameron/Seattle >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> >>>>>> package main >>>>>> >>>>>> import ( >>>>>> "sync/atomic" >>>>>> "time" >>>>>> ) >>>>>> >>>>>> type RB struct { >>>>>> //mu sync.Mutex >>>>>> buf []interface{} >>>>>> start, end int64 >>>>>> } >>>>>> >>>>>> >>>>>> const N = 10 >>>>>> >>>>>> func NewRB() *RB { >>>>>> return &RB{buf: make([]interface{}, N)} >>>>>> } >>>>>> >>>>>> func (r *RB) Put(x interface{}) { >>>>>> // mu.Lock() >>>>>> // defer mu.Unlock() >>>>>> >>>>>> r.buf[r.end] = x >>>>>> atomic.AddInt64(&r.end,1) >>>>>> //r.end++ >>>>>> r.end %= N >>>>>> >>>>>> } >>>>>> >>>>>> func (r *RB) Get() interface{} { >>>>>> // mu.Lock() >>>>>> // defer mu.Unlock() >>>>>> >>>>>> v := r.buf[r.start] >>>>>> atomic.AddInt64(&r.start,1) >>>>>> //r.start++ >>>>>> r.start %= N >>>>>> >>>>>> return v >>>>>> } >>>>>> >>>>>> func main() { >>>>>> >>>>>> r := NewRB() >>>>>> >>>>>> go func() { >>>>>> r.Put(12345) >>>>>> }() >>>>>> >>>>>> time.Sleep(time.Millisecond) >>>>>> >>>>>> a := r.Get().(int) >>>>>> println(a) >>>>>> } >>>>>> >>>>>> >>>>>> -- >>>>>> You received this message because you are subscribed to the Google >>>>>> Groups "golang-nuts" group. >>>>>> To unsubscribe from this group and stop receiving emails from it, send >>>>>> an email to golang-nuts...@googlegroups.com. >>>>>> To view this discussion on the web visit >>>>>> https://groups.google.com/d/msgid/golang-nuts/d7cc3410-c0bb-40d6-bf75-5e655ba3136en%40googlegroups.com. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "golang-nuts" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to golang-nuts+unsubscr...@googlegroups.com. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/golang-nuts/900d07ba-ce11-4f1a-94d2-609b5b8260c7n%40googlegroups.com. > > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/golang-nuts/CAEkBMfFmgxpJpj8zSpMWtnAK6qkkvzuR4%3DFUJriZF_Jku6PGDg%40mail.gmail.com. -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/A4D780AA-9A4A-4330-AF2B-E54B8C0A1A6D%40ix.netcom.com.
