Btw, for those interesting in some neat highly optimized queue patterns check out https://lmax-exchange.github.io/disruptor/
> On Mar 11, 2022, at 5:58 PM, Robert Engels <reng...@ix.netcom.com> wrote: > > > “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/26682F46-21BC-41CF-BC0D-58622DE3120B%40ix.netcom.com.
