5 ms·

Implementation of a RingBuffer in Java with optional FIFO like semantics

23 points by todsacerdoti 2y ago

PaulHoule 2y ago
Can't you get either behavior out of a Deque?
- n1b0m 2y ago
  A deque is an abstract data type, because it is defined by what you can do with it; what operations it supports. You can add and remove elements at either end of a deque. A RingBuffer is a data structure, because it defined by how it is represented in memory, and how its state should be manipulated to fulfil the deque operations.
  - PaulHoule 2y ago
    I looked at the source. Is it right that it overwrites when it reaches full capacity? That's scary! Aren't there concurrent versions of this that block writers until space frees up?
hoppp 2y ago
Targeting java 8... Last updated 5 days ago... What... Stuck forever at java 8?
- tracer4201 2y ago
  [dead]
- cosmotic 2y ago
  If it doesn't use any new features then there's no reason to target anything newer, and you'd just be restricting who could use the library.
o11c 2y ago
This implementation should be avoided; it is weird, buggy, and unnecessarily complicated. In particular, using some pseudocode to simplify: rb = new RingBuffer(... capacity=3, orderedReads=false/*the default*/) rb.put_all(A, B, C, D) rb.get() // D rb.put(E) rb.get_all(3) // E, C, D again I haven't looked for bugs with orderedReads=true (besides the obvious memory leak), but given the footguns and unnecessarily complications this should be avoided regardless.
stickfigure 2y ago
final RingBuffer<String> ringBuffer = new RingBuffer<>(String.class, capacity); Why does the constructor need the Class<?> parameter?
- o11c 2y ago
  That's about the least-bad thing about the code here - it's a workaround for the fact that Java lacks runtime support for generics. Other than its indirect use in `copy` (which in Java normally takes the parameter itself), it's probably not actually necessary here since you could just use `Object[]`? But I don't spend enough time in Java (thankfully) so I'm not sure if there are intricacies involving the runtime overhead of casting.
- jcrites 2y ago
  Looking at the source, I don't think there's an actual need for the constructor to take a `Class<T>` type. It's used internally to initialize an array [1]: this.entries = (T[]) Array.newInstance(type, capacity); However, I think this alternative would work equally well, and would not require a `Class<T>` parameter: this.entries = (T[]) new Object[capacity]; There are some other choices in the library that I don't understand, such as the choice to have a static constructor with this signature: public static RingBuffer<Object> create(final int capacity) { return create(capacity, false); } This returns the type `RingBuffer<Object>`, which isn't as useful as it could be; with appropriate idiomatic use of generics it could return a `RingBuffer<T>`: public static <T> RingBuffer<T> create(final int capacity, final boolean orderedReads) { return new RingBuffer<>(capacity, orderedReads); } It's possible that this code was written by someone who is still learning idiomatic Java style, or effective use of generics. I'm also curious about the choice to have `get()` return `null`. I think I'd rather have seen this modeled with `Optional`. My preferred style when writing Java code is to employ non-nullable references wherever possible (though the return from `get()` is marked `@Nullable` at least). [1] https://github.com/evolvedbinary/j8cu/blob/94d64cfc0ec49a34002aae136b6f080c10976748/src/main/java/com/evolvedbinary/j8cu/RingBuffer.java#L115C9-L115C64 https://github.com/evolvedbinary/j8cu/blob/94d64cfc0ec49a340...
- IncreasePosts 2y ago
  Line 115: this.entries = (T[]) Array.newInstance(type, capacity) You can't just say new T[capacity] in java.
beastman82 2y ago
there's also the Disruptor https://github.com/LMAX-Exchange/disruptor https://github.com/LMAX-Exchange/disruptor
asgeirn 2y ago
I wrote this guy a few years back. It's lock free for both consumers and producers. Blocking variants are also available, but with significantly poorer performance. https://github.com/asgeirn/circular-buffer https://github.com/asgeirn/circular-buffer
dave1999x 2y ago
I did one for C# about 10 years ago - https://github.com/dave-hillier/disruptor-unity3d https://github.com/dave-hillier/disruptor-unity3d

23 points by todsacerdoti 2y ago

PaulHoule 2y ago

Can't you get either behavior out of a Deque?

n1b0m 2y ago
A deque is an abstract data type, because it is defined by what you can do with it; what operations it supports. You can add and remove elements at either end of a deque. A RingBuffer is a data structure, because it defined by how it is represented in memory, and how its state should be manipulated to fulfil the deque operations.
- PaulHoule 2y ago
  I looked at the source. Is it right that it overwrites when it reaches full capacity? That's scary! Aren't there concurrent versions of this that block writers until space frees up?

hoppp 2y ago

Targeting java 8... Last updated 5 days ago... What... Stuck forever at java 8?

tracer4201 2y ago
[dead]
cosmotic 2y ago
If it doesn't use any new features then there's no reason to target anything newer, and you'd just be restricting who could use the library.

o11c 2y ago

This implementation should be avoided; it is weird, buggy, and unnecessarily complicated. In particular, using some pseudocode to simplify: rb = new RingBuffer(... capacity=3, orderedReads=false/*the default*/) rb.put_all(A, B, C, D) rb.get() // D rb.put(E) rb.get_all(3) // E, C, D again I haven't looked for bugs with orderedReads=true (besides the obvious memory leak), but given the footguns and unnecessarily complications this should be avoided regardless.

stickfigure 2y ago

final RingBuffer<String> ringBuffer = new RingBuffer<>(String.class, capacity); Why does the constructor need the Class<?> parameter?

o11c 2y ago
That's about the least-bad thing about the code here - it's a workaround for the fact that Java lacks runtime support for generics. Other than its indirect use in `copy` (which in Java normally takes the parameter itself), it's probably not actually necessary here since you could just use `Object[]`? But I don't spend enough time in Java (thankfully) so I'm not sure if there are intricacies involving the runtime overhead of casting.
jcrites 2y ago
Looking at the source, I don't think there's an actual need for the constructor to take a `Class<T>` type. It's used internally to initialize an array [1]: this.entries = (T[]) Array.newInstance(type, capacity); However, I think this alternative would work equally well, and would not require a `Class<T>` parameter: this.entries = (T[]) new Object[capacity]; There are some other choices in the library that I don't understand, such as the choice to have a static constructor with this signature: public static RingBuffer<Object> create(final int capacity) { return create(capacity, false); } This returns the type `RingBuffer<Object>`, which isn't as useful as it could be; with appropriate idiomatic use of generics it could return a `RingBuffer<T>`: public static <T> RingBuffer<T> create(final int capacity, final boolean orderedReads) { return new RingBuffer<>(capacity, orderedReads); } It's possible that this code was written by someone who is still learning idiomatic Java style, or effective use of generics. I'm also curious about the choice to have `get()` return `null`. I think I'd rather have seen this modeled with `Optional`. My preferred style when writing Java code is to employ non-nullable references wherever possible (though the return from `get()` is marked `@Nullable` at least). [1] https://github.com/evolvedbinary/j8cu/blob/94d64cfc0ec49a34002aae136b6f080c10976748/src/main/java/com/evolvedbinary/j8cu/RingBuffer.java#L115C9-L115C64 https://github.com/evolvedbinary/j8cu/blob/94d64cfc0ec49a340...
IncreasePosts 2y ago
Line 115: this.entries = (T[]) Array.newInstance(type, capacity) You can't just say new T[capacity] in java.

beastman82 2y ago

there's also the Disruptor https://github.com/LMAX-Exchange/disruptor https://github.com/LMAX-Exchange/disruptor

asgeirn 2y ago

I wrote this guy a few years back. It's lock free for both consumers and producers. Blocking variants are also available, but with significantly poorer performance. https://github.com/asgeirn/circular-buffer https://github.com/asgeirn/circular-buffer

dave1999x 2y ago

I did one for C# about 10 years ago - https://github.com/dave-hillier/disruptor-unity3d https://github.com/dave-hillier/disruptor-unity3d