Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Lockless Ringbuffer Built with Go Generics

github.com

Post reply on HN
Print view View original

11–20 of 23 posts

Re: Show HN: Lockless Ringbuffer Built with Go Generics

#11

Post by travisby »

spoiler wrote: post #5
throwaway77384 wrote: post #2

Please excuse my ignorance, but here goes: Been a Go dev for almost 3 years now. I am basically shitting myself over the prospect of all the Go code out there turning from something I understand, to something riddled with generics, of which I have no concept whatsoever. I've built some pretty complex stuff entirely without them and never felt there was anything missing, but maybe I just never knew what I was missing.…

I won't go into super much detail, but think of generics as functions over types that generate new types based on type inputs (gross oversimplification). Comparable to functions that take value and return values, also it happens before your program runs (during compilation/build time). A ring buffer is just a normal buffer, except that when it "runs out" of space instead of overflowing or returning an error, it "loop…

It might also be worth comparing to the stdlib's `container/ring` implementation of a non-generic ring buffer, to see how your code might differ between `RingBuffer[string]` and how the `interface{}` version of container/ring works!

https://pkg.go.dev/container/ring#example-Ring.Do

The casting back and forth from T and `interface{}` is expensive, boilerplatey/extracode, and panic-prone.

Re: Show HN: Lockless Ringbuffer Built with Go Generics

#12

Post by holografix »

throwaway77384 wrote: post #8
stevefan1999 wrote: post #6

Earlier quoted context omitted.

if you have not known what a ring buffer is, may I suspect you to be a developer who taught yourself?

I certainly am, yes. Spent about 12 years in the wrong career and then realised my love for programming (after a lifelong love of computers. Not sure how I missed that...) I started with Python (and Kivy). Then went on to Go (which felt like a revelation over Python. For me, anyway). Along with that came JS, HTML, CSS and React. Because of Go, I had become prejudiced against interpreted, dynamically typed languages.…

That’s a cool background. Can you share more about your product?

I’m also struggling to see the great benefit of generics apart from “it’s quicker than using interface types, trust us”.

I didn’t know a ring buffer was a “formal” data structure thingy but implemented one for a toy multiplayer game I’m building very slowly. There’s a “circular list” of the 5 last received messages from the server and if the position as indicated by the server deviated above a certain threshold I warp the player back to where they should be according to the server.

I knew these message objects were gonna be allocated/nuked constantly so I just have 5 one pointing to the other and the last pointing back to the first and I go around overwriting them.

Re: Show HN: Lockless Ringbuffer Built with Go Generics

#13

Post by ithkuil »

pjmlp wrote: post #4
throwaway77384 wrote: post #2

Please excuse my ignorance, but here goes: Been a Go dev for almost 3 years now. I am basically shitting myself over the prospect of all the Go code out there turning from something I understand, to something riddled with generics, of which I have no concept whatsoever. I've built some pretty complex stuff entirely without them and never felt there was anything missing, but maybe I just never knew what I was missing.…

A memory bound queue and by making use of generics, it has more performance due to having one indirection less per element and being able to store all of them in a continuous memory segment.

That doesn't answer the question though.

Go channels (and slices and maps) are special built-in types that are already "generic", i.e. they have type parameters: "make(chan Foo, 10)".

Is there some property of the built-in buffered channel contract that makes it hard to implement as efficiently as this ring buffer?

Anyway. The ability to implement user-defined data structures with the full power of the language (e.g. building your own 'chan T') allows one to choose some different guarantees and target different use cases

Re: Show HN: Lockless Ringbuffer Built with Go Generics

#14

Post by gavinclarke0 »

jrockway wrote: post #10

atomic.AddInt32 feels a lot like locking to me. You end up with a write barrier and all the associated consequences, so you can kill throughput (in a way that is more difficult to notice in the profiler, though you'll probably notice it when it's a problem if you ask pprof for a line-by-line profile). sync.Mutex.Lock is implemented like this: func (m *Mutex) Lock() { // Fast path: grab unlocked mutex. if atomic.Compa…

Using atomic instructions is still generally considered lockless with the idea that since the lock is at the instruction level and thus progress can still be guaranteed it is "lockless". If this is true in practice depends on a whole host of factors.

I do not doubt majority of cases a mutex is faster/more appropriate. However the key there is looking at what m.lockslow() or unlockSlow() does which is called on lock contention. They become spinlocks that are not entirely dissimilar to my implementation.

The idea is that a lockless algorithm is trading a worse best case i.e m.lockSlow is not called for a better worse case. Again if this is true in this exact case, I am not sure as I have not benchmarked it against a naive mutex based ringbuffer.

Re: Show HN: Lockless Ringbuffer Built with Go Generics

#15

Post by styluss »

holografix wrote: post #12
throwaway77384 wrote: post #8

Earlier quoted context omitted.

I certainly am, yes. Spent about 12 years in the wrong career and then realised my love for programming (after a lifelong love of computers. Not sure how I missed that...) I started with Python (and Kivy). Then went on to Go (which felt like a revelation over Python. For me, anyway). Along with that came JS, HTML, CSS and React. Because of Go, I had become prejudiced against interpreted, dynamically typed languages.…

That’s a cool background. Can you share more about your product? I’m also struggling to see the great benefit of generics apart from “it’s quicker than using interface types, trust us”. I didn’t know a ring buffer was a “formal” data structure thingy but implemented one for a toy multiplayer game I’m building very slowly. There’s a “circular list” of the 5 last received messages from the server and if the position as…

> "it’s quicker than using interface types, trust us

During runtime, the program doesn't know the actual type of the variable, it just knows it's a io.Reader and dereferences to the actual type vs generating the code for the type that is actually being used.

Here's an interesting read on issues with interfaces at scale https://segment.com/blog/allocation-efficiency-in-high-perfo...

Re: Show HN: Lockless Ringbuffer Built with Go Generics

#16

Post by lijogdfljk »

ithkuil wrote: post #13
pjmlp wrote: post #4

Earlier quoted context omitted.

A memory bound queue and by making use of generics, it has more performance due to having one indirection less per element and being able to store all of them in a continuous memory segment.

That doesn't answer the question though. Go channels (and slices and maps) are special built-in types that are already "generic", i.e. they have type parameters: "make(chan Foo, 10)". Is there some property of the built-in buffered channel contract that makes it hard to implement as efficiently as this ring buffer? Anyway. The ability to implement user-defined data structures with the full power of the language (e.g.…

If it is indeed faster, my gut is that it wasn't generic, it was "generic" hah. Ie runtime reflection was used instead of true compile-time generics. Runtime reflection has a cost, and is (was!) one the strongest arguments against Go. All powerful "generic" code you'd write in Go heavily relied on reflection over interfaces that caused memory behavior commonly associated with worse performance.

Compile-time generics can often perform similar behavior but with a far better memory layout resulting in better performance.

Purely speculation though about `chan`, i have no clue.

Re: Show HN: Lockless Ringbuffer Built with Go Generics

#17

Post by lijogdfljk »

throwaway77384 wrote: post #8
stevefan1999 wrote: post #6

Earlier quoted context omitted.

if you have not known what a ring buffer is, may I suspect you to be a developer who taught yourself?

I certainly am, yes. Spent about 12 years in the wrong career and then realised my love for programming (after a lifelong love of computers. Not sure how I missed that...) I started with Python (and Kivy). Then went on to Go (which felt like a revelation over Python. For me, anyway). Along with that came JS, HTML, CSS and React. Because of Go, I had become prejudiced against interpreted, dynamically typed languages.…

Boy your progress sounds super similar to mine. Though with swapped order on JS and Go. Mine was primarily Python->JS->Go->Rust. I've been a Rust fanatic for maybe ~2 years now.

It was a natural progression for me, and i quite enjoyed it. I also love Rust, the stdlib (and supporting crates) gave me a UX quite similar to Go's batteries-included stdlib.

Re: Show HN: Lockless Ringbuffer Built with Go Generics

#18

Post by gavinclarke0 »

spoiler wrote: post #5
throwaway77384 wrote: post #2

Please excuse my ignorance, but here goes: Been a Go dev for almost 3 years now. I am basically shitting myself over the prospect of all the Go code out there turning from something I understand, to something riddled with generics, of which I have no concept whatsoever. I've built some pretty complex stuff entirely without them and never felt there was anything missing, but maybe I just never knew what I was missing.…

I won't go into super much detail, but think of generics as functions over types that generate new types based on type inputs (gross oversimplification). Comparable to functions that take value and return values, also it happens before your program runs (during compilation/build time). A ring buffer is just a normal buffer, except that when it "runs out" of space instead of overflowing or returning an error, it "loop…

I implemented it using generics not for performance gains but to avoid type assertions and interfaces which I find are a major source of error and side step many of the benefits of a type safe language. Any performance gains is merely a side affect.

Re: Show HN: Lockless Ringbuffer Built with Go Generics

#19

Post by dfawcus »

lijogdfljk wrote: post #16
ithkuil wrote: post #13

Earlier quoted context omitted.

That doesn't answer the question though. Go channels (and slices and maps) are special built-in types that are already "generic", i.e. they have type parameters: "make(chan Foo, 10)". Is there some property of the built-in buffered channel contract that makes it hard to implement as efficiently as this ring buffer? Anyway. The ability to implement user-defined data structures with the full power of the language (e.g.…

If it is indeed faster, my gut is that it wasn't generic, it was "generic" hah. Ie runtime reflection was used instead of true compile-time generics. Runtime reflection has a cost, and is (was!) one the strongest arguments against Go. All powerful "generic" code you'd write in Go heavily relied on reflection over interfaces that caused memory behavior commonly associated with worse performance. Compile-time generics…

Have a look at the runtime, on my system the code is in

   /usr/local/go/src/runtime/chan.go
There are some reflection calls in there, together with mutex lock/unlock and calls to 'typedmemmove' which seems to involve the use of memory barriers (mbarrier.go in the same directory).
Post reply on HN