Out-of-bounds checking for circular buffer

Tsaukpaetra

So, my multi-position ring buffer seems to be going fine, except when it has actually wrapped around and the head of the buffer has an index less than the tail.

Specifically, the GetNext() function uses a isOOB() function to detect when the element it's attempting to retrieve is out of bounds of the current available buffer. In simple terms, it's supposed to check if the desired index is not in between the head and the tail.

Since it is a ring, the head might be before the tail and that's where my current attempt to calculate falls apart:


        private bool isOOB(int index)
        {
            int normalized_Tail = m_Head < m_Tail ? m_Tail - Length : m_Tail;
            int normalized_x = (index > m_Tail) ? index - Length : index;
            return (index > m_Head || normalized_x < normalized_Tail)
                
                ;
        }

Tsaukpaetra

Decided to split out the codes.

Revised:

        private bool isOOB(int index)
        {
            //Is head before tail?
            if(m_Head < m_Tail)
            {
                //Is the index between the head and tail? That's OOB
                return (index > m_Head && index < m_Tail);
            }
            else
            {
                //Is the index past the head or before the tail? That's OOB
                return (index > m_Head || index < m_Tail);

            }
            
        }

This seems to be verified using my little truthy table:

0_1532566286086_cb4ffe90-d431-4e31-81d9-9fee29caa9ed-image.png

But... It still doesn't seem to work in the code version? What am I doing wrong?

Tsaukpaetra

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

What am I doing wrong?

Who knows. I just replaced it with a "Is it one slot in front of the head" because that's all the function was being used for anyways...

Good enough.

anotherusername

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

I just replaced it with a "Is it one slot in front of the head" because that's all the function was being used for anyways...

I was gonna say... it sounded like that was all you needed to do.

anotherusername

But generally, if m_Head and m_Tail are the first/last items, Length is the size of the circular buffer, and index is the item that you're wanting to check...

int normalized_Tail = m_Tail < m_Head ? m_Tail + Length : m_Tail;
int normalized_x = index < m_Head ? index + Length : index;
return normalized_x <= normalized_Tail;

edit: although it won't work to tell if you've wrapped around and completely filled the buffer, for reasons which should be obvious: if your ring buffer is completely full, then every index is "in bounds".

Tsaukpaetra

@anotherusername said in Out-of-bounds checking for circular buffer:

edit: although it won't work to tell if you've wrapped around and completely filled the buffer, for reasons which should be obvious: if your ring buffer is completely full, then every index is "in bounds".

Yeah, once I put in a test case for that I was totally and just rationalized that, really, no need to check the tail, since you're never going backwards anyways...

blakeyrat

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

Who knows. I just replaced it with a "Is it one slot in front of the head" because that's all the function was being used for anyways...

That only works if you only insert one item at a time, right?

Is this in C#? (Why the m_ for local members?) If so you may need some lock() to ensure those members aren't changing in the middle of your if() statements. C# is thoroughly threadedified. That may be the cause of your problem.

Generic C# RingBuffer

Here's a generic one with heavy comments you can crib from, but note it also doesn't do any locking so it's not thread-safe.

There's also not really much of a point to a circular buffer in C# if you're storing objects, since you're just storing a bunch of references. Why not just subclass a Queue and Dequeue if the length exceeds your "maximum buffer size"? Trust that the smart eggheads at Microsoft already implemented it in the most efficient way possible.

Tsaukpaetra

@blakeyrat said in Out-of-bounds checking for circular buffer:

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

Who knows. I just replaced it with a "Is it one slot in front of the head" because that's all the function was being used for anyways...

That only works if you only insert one item at a time, right?

Correct, and that's fine.

Is this in C#? (Why the m_ for local members?) If so you may need some lock() to ensure those members aren't changing in the middle of your if() statements. C# is thoroughly threadedified. That may be the cause of your problem.

Other person's code I butchered. Will probably have to revisit thread safety.

Generic C# RingBuffer

Will check it out, but I don't think it will satisfy my needs.

Here's a generic one with heavy comments you can crib from, but note it also doesn't do any locking so it's not thread-safe.

There's also not really much of a point to a circular buffer in C# if you're storing objects, since you're just storing a bunch of references. Why not just subclass a Queue and Dequeue if the length exceeds your "maximum buffer size"? Trust that the smart eggheads at Microsoft already implemented it in the most efficient way possible.

So, background, the entire point of this buffer is to store logs in memory so that newly connecting users to the interface can receive a dump of the last 200 log lines or so. The reason I can't use a queue (or friends) is that popping the queue means the object of whatever is removed from the stack, not good for keeping a history. I could also use some kind of linked list (if I could figure out how to do so in c#), but that seems worse. And using a normal List or whatever seems like it would get inefficient really quick....

blakeyrat

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

So, background, the entire point of this buffer is to store logs in memory so that newly connecting users to the interface can receive a dump of the last 200 log lines or so.

Sounds like a Queue to me.

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

The reason I can't use a queue (or friends) is that popping the queue means the object of whatever is removed from the stack, not good for keeping a history.

So you want to keep the last 200 but also want to keep all of them ever? I don't understand this at all.

Just subclass Queue, and add this:

public Enqueue(T item)
{
  base(item);
  if(this.length > 200)
  {
    this.Dequeue();
  }
}

(Code not compiled or checked for completeness.)

Right? Keeps the last 200 items, throws away anything more, no "rings" required.

If you need to keep the items permanently just give their references to like a normal List in addition to the Queue. Don't worry, C# won't delete it from the List when it's gone from the Queue.

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

I could also use some kind of linked list (if I could figure out how to do so in c#), but that seems worse

I still don't get your requirements, but pretty much everything in C# (except an array of Structs) is equivalent to a linked list of some sort or another.

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

And using a normal List or whatever seems like it would get inefficient really quick....

Not sure why you think so, but again I'm confused over your requirements here.

I think we need a rule in Coding Help that you need to actually say what you're trying to accomplish. Especially with SQL questions, sometimes it takes like 20 posts of back and forth just for people to figure out what the requirements are.

mott555

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

And using a normal List or whatever seems like it would get inefficient really quick....

I wouldn't think so, for the same reasons mentioned before. .NET collections are pretty well-designed.

myList.Add(newItem);
while (myList.Count > 200)
    myList.RemoveAt(0);

blakeyrat

@mott555 It wouldn't surprise me to learn:

Queue uses List behind-the-scenes
It does that because .RemoveAt(0) is already as efficient as it can possibly be made, so there's no performance penalty to that

I'm not sure what Tsauk means by "keeping history on the stack" (the actual memory stack? Or the collection known as 'stack'?) but if he wants to keep both a Queue of the last 200 items and a permanent list of every item, he can just put the reference into two collections. Since it's just a reference, it's not like it'll bloat-up memory or anything.

... arguments about performance aside, the whole ring buffer thing just seems like needless complexity to me, and I love to KISS. (Unless it's a ring buffer which operates on an array of bytes or structs, then it would make sense...)

Tsaukpaetra

@blakeyrat said in Out-of-bounds checking for circular buffer:

So you want to keep the last 200 but also want to keep all of them ever?

No, just the first part.

@blakeyrat said in Out-of-bounds checking for circular buffer:

Right? Keeps the last 200 items, throws away anything more, no "rings" required.

The problem is, things watching the queue (consuming it, whatever) can't possibly know if they're at the end of the queue. And the normal method of determining that (dequeue until you can't) only works with a single consumer.

Tsaukpaetra

@blakeyrat said in Out-of-bounds checking for circular buffer:

I think we need a rule in Coding Help that you need to actually say what you're trying to accomplish

I mean, the original topic was "out-of-bounds checking for circular buffer" until Y'all started questioning other things. Don't you dare blame topic drift on me!

mott555

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

The problem is, things watching the queue (consuming it, whatever) can't possibly know if they're at the end of the queue. And the normal method of determining that (dequeue until you can't) only works with a single consumer.

Can you give each consumer its own queue, and have a list of queues for the logger to append items to? Then each consumer can pop items and display them without affecting anything else.

blakeyrat

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

The problem is, things watching the queue (consuming it, whatever) can't possibly know if they're at the end of the queue.

... why not? They have an iterator, right? (Edit: also how is that situation different with the ring buffer, which would have the same problem?)

Also if you have multiple consumers then the threading stuff is going to be more mega-important.

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

I mean, the original topic was "out-of-bounds checking for circular buffer" until Y'all started questioning other things. Don't you dare blame topic drift on me!

Well hopefully you're more interested in having a quality product than in implementing a ring buffer specifically.

@mott555 said in Out-of-bounds checking for circular buffer:

Can you give each consumer its own queue, and have a list of queues for the logger to append items to? Then each consumer can pop items and display them without affecting anything else.

They don't need their own copy of the queue, just an iterator to the single queue. (Again: make sure stuff's thread-safe here.)

Tsaukpaetra

@mott555 said in Out-of-bounds checking for circular buffer:

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

The problem is, things watching the queue (consuming it, whatever) can't possibly know if they're at the end of the queue. And the normal method of determining that (dequeue until you can't) only works with a single consumer.

Can you give each consumer its own queue, and have a list of queues for the logger to append items to? Then each consumer can pop items and display them without affecting anything else.

Would that work? The idea here is to maintain a rolling history, creating a separate queue for each would work for going-forwards, but not let you retrieve past items (to my knowledge). I think Blakeyrat was probably closer to the desired behavior (and I'll try and incorporate that).

Tsaukpaetra

@blakeyrat said in Out-of-bounds checking for circular buffer:

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

The problem is, things watching the queue (consuming it, whatever) can't possibly know if they're at the end of the queue.

... why not? They have an iterator, right?

The iterator is what I've implemented, yes. Each consumer basically gets a token (essentially an automatically incrementing number, no not technically thread-safe) that it uses to call into the GetNext() function until it reaches the end, which end is determined by the topic's code.

Also if you have multiple consumers then the threading stuff is going to be more mega-important.

Yes, but I'm getting basic functionality laid down first. Making all the tokens thread-safe will just be nice once the proof-of-concept works.

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

I mean, the original topic was "out-of-bounds checking for circular buffer" until Y'all started questioning other things. Don't you dare blame topic drift on me!

Well hopefully you're more interested in having a quality product than in implementing a ring buffer specifically.

Sure, but getting angry at me for you shifting in my thread is doing nobody any favors.

@mott555 said in Out-of-bounds checking for circular buffer:

Can you give each consumer its own queue, and have a list of queues for the logger to append items to? Then each consumer can pop items and display them without affecting anything else.

They don't need their own copy of the queue, just an iterator to the single queue. (Again: make sure stuff's thread-safe here.)

Correct.

blakeyrat

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

Sure, but getting angry at me

I didn't get angry with you in this topic.

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

for you shifting in my thread is doing nobody any favors.

I honestly don't know what this means.

Tsaukpaetra

So I ended up kinda doing this

@blakeyrat said in Out-of-bounds checking for circular buffer:

Why not just subclass a Queue and Dequeue if the length exceeds your "maximum buffer size"? Trust that the smart eggheads at Microsoft already implemented it in the most efficient way possible.

but not really.

Taking off the complicators gloves and putting me "Trust that the smart eggheads at Microsoft already implemented it in the most efficient way possible.", this is now my (full disclosure) code:

Teh codez

public class HistoricalConcurrentQueue<T> : IEnumerable<T>
{
    public int MaxItems { get; set; } = 1;
    ConcurrentQueue<T> buffer = new ConcurrentQueue<T>();

    public HistoricalConcurrentQueue(int MaxItems)
    {
        this.MaxItems = MaxItems;
    }

    public void Add(T obj)
    {
        buffer.Enqueue(obj);
        //Check if we need to dequeue due to too many items
        CutTail();
    }

    private void CutTail()
    {
        T garbage;
        int numToRemove = buffer.Count - MaxItems;
        while (numToRemove > 0)
        {
            if(buffer.TryDequeue(out garbage)) numToRemove--;
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        return buffer.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return ((IEnumerable<T>)buffer).GetEnumerator();
    }
}

The original concept was that multiple users may potentially be in the middle of consuming the history. Using a Queue for this would not work, because multiple threads should not share the same queue, and dequeueing an item would remove it from the list for everyone in a normal ConcurrentQueue. Therefore it was necessary to find/create a system that would allow multiple consumers to begin at the end of the queue so they could work their way up to the head, whereupon they would simply disconnect.
The concept of the Ring buffer was chosen because we'd know precisely how many "slots" we'd have for items, and would never have to spend time resizing the array when "adding"/"removing" items from the history (something that List says it does explicitly in the docs, for example, and presumably any collection for that matter). Additionally this would grant the ability to consume the history at that thread's own pace.
The issue came when it was time to determine when a particular consumer was outside the bounds of the history list, which check was used to determine if the consumer hit the head of the list (and should therefore stop consuming).

Tl;dr: Was trying to implement features that weren't really needed in the end. We don't really need tracking of where consumers are, so long as they start at the beginning and reach the end prior to another element getting added.

Good game, thanks for fish, fun stuff.

Tsaukpaetra

For anyone interested in the stupid-version I'm about to hit Delete on:

The dumb codez

using System;
using System.Collections.Generic;

namespace CircularBuffer
{
    public class CircularBuffer<T>
    {
        T[] m_Buffer;
        int m_NextWrite, m_Tail, m_Head;
        Dictionary<int, int> Tokens = new Dictionary<int, int>();
        int LastTokenGiven = 0;
        public bool ThrowOnOverflow { get; set; } = true;

        public CircularBuffer(int length)
        {
            m_Buffer = new T[length];
            m_NextWrite = 0;
            m_Head = m_Tail  = length;
        }

        public int Length { get { return m_Buffer.Length; } }

        private void UpdateTail()
        {
            //Advance the tail to the last token
            int lastPosition = m_Head + Length - 1;
            foreach (int position in Tokens.Values)
            {
                if (position > -1)
                {
                    int NormalizedPosition = position < m_Head ? position : position - Length;
                    lastPosition = lastPosition < NormalizedPosition ? lastPosition : NormalizedPosition;
                }
            }

            System.Diagnostics.Debug.WriteLine("UpdateTail: Head is " + m_Head + " Tail was " + m_Tail + " now " + mod(lastPosition));
            m_Tail = mod(lastPosition);

            //Special case: Is our tail 0 and we're apparently at the initial state?
            if(m_Tail == 0 && m_Head == Length)
            {
                m_Tail = -1;
            }
        }

        public void Add(T o)
        {
                UpdateTail();


                //Check if the next write will eat the tail
                if (m_Tail == m_NextWrite && ThrowOnOverflow)
                {
                    throw new IndexOutOfRangeException("At least one token is too far behind.");
                }
                m_Head = m_NextWrite;

            System.Diagnostics.Debug.WriteLine("Adding to buffer at " + m_NextWrite + ", Head is " + m_Head + ", Tail is " + m_Tail + ". : "  + o.ToString());

            m_Buffer[m_NextWrite] = o;
            m_NextWrite = mod(m_NextWrite + 1);
        }
        
        /// <summary>
        /// Get a token to participate in the buffer's tracking
        /// </summary>
        /// <param name="offset">Offset from the head</param>
        /// <returns>The token number used for GetNext</returns>
        public int GetToken(int offset = 0)
        {
            int UsedOffset = -1;
            if(offset > 0)
            {
                UsedOffset = mod(m_Head - offset);

                //Loop to check that we're on a valid point
                while (m_Buffer[mod(UsedOffset + 1)] == null && offset >0)
                    UsedOffset = mod(m_Head - --offset);

                //Special case: Is our head the same as the length, apparently at the initial state?
                if (m_Head == Length)
                {
                    UsedOffset = -1;
                }
            }
            else
            {
                UsedOffset = mod(m_Head);
            }

            Tokens.Add(++LastTokenGiven, UsedOffset);
            UpdateTail();
            return LastTokenGiven;
        }
        public bool returnToken(int TokenID)
        {
            bool success = Tokens.Remove(TokenID);

            UpdateTail();
            return success;
        }

        public T GetNext(int TokenID)
        {
            if (m_Head == -1 || -1 == m_Tail)
                return default(T);
            if(!Tokens.ContainsKey(TokenID))
                return default(T);
            string DiagPretext = "GetNext for " + TokenID + ", which is at " + Tokens[TokenID];
            
            int m_CurrRead = Tokens[TokenID];

            m_CurrRead = mod(m_CurrRead + 1);
            if (!(m_CurrRead == mod(m_Head + 1)))
            {
                Tokens[TokenID] = m_CurrRead;
                System.Diagnostics.Debug.WriteLine(DiagPretext + " and moved to " + m_CurrRead);
                return m_Buffer[m_CurrRead];

            }
            else
            {
                System.Diagnostics.Debug.WriteLine(DiagPretext + " and went OOB to " + m_CurrRead);
                return default(T);

            }
        }


        private int mod(int x) // ensures a positive mod.
        {
            return (x % Length + Length) % Length;
        }
        

    }
}

Not guaranteed to be thread safe or anything, since I didn't get that far in testing, but it should technically work (inasmuch as it was working fine at the moment).

Gribnit

@Tsaukpaetra Hold onto it in a branch, if near-zero memory movement ever matters you might want it. Although, to be safe, you should name the branch something like "low memory movement recent buffer, haha, you didn't need it, delete the branch and get me the Coke you owe me".

The dictionary of client cursors belongs in another scope than the core circular buffer. I assume you were okay with different clients seeing different amounts of recent history and/or that 200 was an overprovisioning.

Tsaukpaetra

@Gribnit said in Out-of-bounds checking for circular buffer:

Hold onto it in a branch

I'll hold it here. ;) But yeah, it's saved in the source control if ever I decide to revisit it.

@Gribnit said in Out-of-bounds checking for circular buffer:

The dictionary of client cursors belongs in another scope than the core circular buffer.

I'm not entirely sure what you mean by this. The buffer is keeping track of the consumers, where else would it be?

@Gribnit said in Out-of-bounds checking for circular buffer:

I assume you were okay with different clients seeing different amounts of recent history and/or that 200 was an overprovisioning.

In theory they could receive up-to Count-1 entries. The exact amount isn't important as much as long as it gets about that many (if there were that many) and that any future entries that would be added (potentially while reading the history) would not be lost while reading them. Immediately after said reading an event handler is tied to the original log source event thing so future entries would go straight to the clients, but it's that gap of reading-the-history to now-we're-live that's the minor concern.

Of course, the log isn't really all that busy so the point is probably

Gribnit

@Tsaukpaetra I was way lazier last time I did anything like this. I completely bagged real time - if anything hit after read, it would be read next time was as far as I was willing to go.

Clarifying on the dictionary - the circular buffer itself could be made more canonical and more reusable if the multiple cursors aspect was a subclass or some other kind of bolt-on. But, this is a matter of taste.

Tsaukpaetra

@Gribnit said in Out-of-bounds checking for circular buffer:

multiple cursors aspect was a subclass or some other kind of bolt-on

That's 78 percent of the functionality of that class. Removing it let me use a wrapped Queue.

Gribnit

@Tsaukpaetra Yar. If you ever need near-zero movement again (and aren't already getting it) you could always implement a circular buffer to Queue semantics now.

OloEopia

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

private void CutTail()
{
    T garbage;
    int numToRemove = buffer.Count - MaxItems;
    while (numToRemove > 0)
    {
        if(buffer.TryDequeue(out garbage)) numToRemove--;
    }
}

This is bound to have funky concurrency issues. If you have concurrent inserts which make the numToRemove > 1 you will once in a while remove numToRemove * concurrentInsertsThatHappened

You only ever enqueue one item at a time so cut tail should remove one item at most. Removal of the other items > 200 should happen in the thread that added those

edit: bonus edge case: init that queue with size 1 and manage to hit the concurrency sweet spot inserting 2 items while the queue is "full" now you have one thread looping on TryDequeue

blakeyrat

@oloeopia Oh yeah sorry I posted the concurrency stuff to Tsauk on Discord but didn't put it here, I probably should have. He added a lock() to that method.

Tsaukpaetra

@OloEopia said in Out-of-bounds checking for circular buffer:

edit: bonus edge case: init that queue with size 1 and manage to hit the concurrency sweet spot inserting 2 items while the queue is "full" now you have one thread looping on TryDequeue

Ooh that's interesting.

OloEopia

@blakeyrat heh, lockfree queue and then lock() on it

blakeyrat

@OloEopia Yeah. I know. I also told him to add a comment saying "yes this looks stupid, but I know what I'm doing" or something similar, because it does look wrong as shit, doesn't it?

The alternative is to make a bullshit private object lockObj = new object(); and lock on that. Which looks less wrong, but isn't really necessary.

OloEopia

@blakeyrat https://msdn.microsoft.com/en-us/library/dd287208.aspx says
TryDequeue tries to remove an element from the queue. If the method is successful, the item is removed and the method returns true; otherwise, it returns false. That happens atomically with respect to other operations on the queue.

So a simple if count > maxitems => TryDequeue should be lock-free and enough

Tsaukpaetra

@OloEopia said in Out-of-bounds checking for circular buffer:

should be lock-free and enough

Yes, the primary reason the tryDequeue is in a loop is for accidents where that happened to fail.

Gribnit

@Tsaukpaetra said in Out-of-bounds checking for circular buffer:

accidents

??? - either the concurrency primitives work or you're fucked.