I’m starting to use the juce::AbstractFifo, but got hang up on the following: When using the FIFO, the available space seems to be always the size minus 1:
juce::AbstractFifo fifo(512);
DBG("Free space: " << fifo.getFreeSpace());
DBG("Samples ready: " << fifo.getNumReady());
output:
Free space: 511
Samples ready: 0
Perhaps I’m missing some point here?
The valid region is stored as a start and an end. My guess is that when validStart == validEnd, this could indicate that the buffer is either completely empty, or completely full. To avoid this uncertainty, the buffer is not allowed to fill to the point where validStart and validEnd are equal. This means that the start and end being equal always indicates that the buffer is empty.
Ok, makes sense. I’d love to see it mentioned in the docs though (if I didn’t miss it).
This just tripped up some tangential unit tests I was writing. Very misleading to not have this written anywhere.
AbstractFifo (int capacity) noexcept
Creates a FIFO to manage a buffer with the specified capacity
Technically capacity - 1? Is this typical of FIFO’s or is this a quirk worth documenting?
Thank you for reporting:
Is this typical of FIFO’s or is this a quirk worth documenting?
fwiw, this is a known problem of ring buffers when you don’t limit the capacity to a power of 2. If the capacity is a power of 2 then you can store the read/write regions with a pair of unsigned counters. The buffer is empty when writeCounter == readCounter and the buffer is full when readCounter + capacity == writeCounter. This works even when the counters overflow. You convert to read/write indices with counter % capacity (which is counter & (capacity - 1) for a power of 2).
The power of two is a total red herring.
What you are doing is effectively allowing the writePointer to point behind the managed buffer.
That means you need to add a special case before writing.
Once you added the wrap around, then the ambiguity of full and empty is back.
Here’s an article that’s lays out the implementation better than I:
there’s no ambiguity between full/empty because the read counter (not pointer) will always be “behind” the write pointer by the number of items in the queue. It will only be “empty” when the counters match. the edge case is when the capacity of the queue is equal to 2^N where N is the size of the counter, which isn’t really feasible.
Perfectly valid, but that implementation can’t be implemented atomically. The read operation needs to both increment the read index and decrement the capacity. So it’s only useful for single-threaded use with extra synchronization. The way AbstractFifo does it, it’s lock-free, but comes at the cost of one element of capacity.
I disagree, I’m using this design in a lock-free FIFO. There’s no need to decrement the capacity - read transactions bump the read counter, write transactions bump the write counter.
Argh, I’m sorry that’s on me. Should’ve read the article to the end instead of just up to the first alternate solution. Must still be under the influence of some nasty germs that the little one brought home from daycare last week.
