ring / fifo buffer

General discussions and questions abound development of code with MicroPython that is not hardware specific.
Target audience: MicroPython Users.
Post Reply
User avatar
devnull
Posts: 218
Joined: Sat Jan 07, 2017 1:52 am
Location: Singapore / Cornwall
Contact:

ring / fifo buffer

Post by devnull » Mon Jun 25, 2018 1:06 pm

I have an application that reads and writes to the uart and needs it's own fifo buffer, I have used lists to do this with append() and pop(0) to push to the end and pop off the beginning.

It works, but uses a lot of memory, when slicing of single line, or the entire contents as I believe this creates copy of the original list.

So after doing some research, I figure the way to go is to use bytearrays and memoryview to eliminate the copy when slicing the buffer, but I have no experience with these and the documentation seems a little sparse.

So how would you go about creating a ring buffer which appends output from the uart allowing me to extract single bytes, lines (with crlf terminators) and the entire buffer ?

It needs to behave pretty much identically to the uart buffer, however I cannot directly uses the uart buffer as there are raw data packets and control characters that need to be parsed / filtered from the uart.

I have never done this before and have to admit that I am a little out of my depth, is there a simple way of doing this or am I going to have to write a class to do this ??

User avatar
devnull
Posts: 218
Joined: Sat Jan 07, 2017 1:52 am
Location: Singapore / Cornwall
Contact:

Re: ring / fifo buffer

Post by devnull » Mon Jun 25, 2018 1:41 pm

Thinking about this some more, if the bytearray is fixed size then I guess you need to maintain a index or pointer to the first element, and as you pop data off the front, null the sliced vales and shift the index.

So assuming a very simple 10 byte array, if I pop off an element the pointer will shift:

pointer=0
0,1,2,3,4,5,6,7,8,A
=,=,=,=,=,=,=,=
A,B,C,D,E,F,G,H,I,J
pop() = A
-,B,C,D,E,F,G,H,I,J
pointer=1
pop() = B
-,-,C,D,E,F,G,H,I,J
pointer = 2 (C)

So if I push fresh data to the buffer, I always start at index 0:

Pushing 2 bytes (K,L) would fill the null elements:
K,L,C,D,E,F,G,H,I,J

Pushing 3 bytes would fill the first 3 slots, and would overwrite C
K,L,M,D,E,F,G,H,I,J

Is this correct ??

cefn
Posts: 205
Joined: Tue Aug 09, 2016 10:58 am

Re: ring / fifo buffer

Post by cefn » Mon Jun 25, 2018 7:10 pm

According to viewtopic.php?f=6&t=4410&p=25630&hilit=deque#p25630 there is a deque implementation which may be useful for managing a queue where you are putting values in one end and removing on the other. However it is not obvious since there's no documentation at https://docs.micropython.org/en/latest/ ... ollections

See https://docs.python.org/2/library/colle ... ions.deque for documentation of the equivalent python collection.

However, while it may be more suitable a structure for managing lists of objects, it will not address the need for a data structure which appears as a byte buffer if you are restricted to using literally a buffer ( https://docs.python.org/2/c-api/buffer.html ). Without some code indicating your use, it's hard to know what constraints you have to satisfy.

User avatar
Roberthh
Posts: 1007
Joined: Sat May 09, 2015 4:13 pm
Location: Rhineland, Europe

Re: ring / fifo buffer

Post by Roberthh » Mon Jun 25, 2018 7:31 pm

Ringbuffers are pretty basic. attached a simple class, which can be varied in various ways. i just sketched it. It has three methods,
The parameter to the constructor is the size of the buffer. put() puts a byte into the buffer, not overwriting previous content. get() returns the first value. None is returned if either not data can be put or no data is to be retrieved.

Code: Select all

#
class RINGBUFFER:
    def __init__(self, size):
        self.data = bytearray(size)
        self.size = size
        self.index_put = 0
        self.index_get = 0
        
    def put(self, value):
        next_index = (self.index_put + 1) % self.size
        # check for overflow
        if self.index_get != next_index: 
            self.data[self.index_put] = value
            self.index_put = next_index
            return value
        else:
            return None
        
    def get(self):
        if self.index_get == self.index_put:
            return None  ## buffer empty
        else:
            value = self.data[self.index_get]
            self.index_get = (self.index_get + 1) % self.size
            return value

User avatar
pythoncoder
Posts: 2889
Joined: Fri Jul 18, 2014 8:01 am
Location: UK
Contact:

Re: ring / fifo buffer

Post by pythoncoder » Tue Jun 26, 2018 7:00 am

@devnull Are you sure you aren't overcomplicating this? The normal approach to this problem is to read the UART data one character at a time. Examine the character and use its value to determine how the next N characters are processed (where N varies depending on the first character). Read and process those characters, then repeat.

In other words do the parsing as characters are received. There is no gain in putting data into a buffer before parsing it, unless the protocol is deeply weird. By that I mean one where you can't determine what to do with a set of data until some subsequent data is received. In which case the designer of the protocol should be shot ;) Slowly.

Even then, if the size of that set is known in advance you only need to buffer that number of characters. If the size of the set isn't known in advance parsing is challenging. Only then would I start thinking about a buffer.
Peter Hinch

User avatar
devnull
Posts: 218
Joined: Sat Jan 07, 2017 1:52 am
Location: Singapore / Cornwall
Contact:

Re: ring / fifo buffer

Post by devnull » Tue Jun 26, 2018 11:13 am

Thanks for the suggestions & help.

I have written a wlan and socket class for the esp8266 AT firmware for use on the PYBOARD, I have it working in both client and server mode with multiple connections in server mode.

The uart receive buffer contains:

1) Unsolicited Messages (CONNECT, CLOSE)
2) Ack and prompts, replies to AT commands
3) IPD Data packets (Incoming Data)

Now all of this currently works quite well both as a Multi-connection (max 5) Server and single connection Client.

For the client I am able to make http, wget requests and use umqtt_simple successfully.

But I am running into memory problems when receiving large ( > 10K) pages, probably because of the fact that I am using lists rather than bytearrays to store the inbound IPD data which is received for multiple inbound connections from the same client, i.e. a web browser requesting a page that has several javascript and css files.

My web server already supports the eTag and therefore is quite fast provided the pages have been served before and they have not changed, as the browser will load these page from it['s cache if the eTag is unchanged.

So I am looking to replace the list that currently holds the inbound data for each connection, hence this request.

Using bytearrays seems the way to go, but it adds more complications as the bytearray does not support find, index and needs to deque as well as the ability to get a single byte, the entire buffer or a line (terminated with crlf).

I don't have a lot of time to process this incoming data as it is coming in very fast, so any classes that are doing this dequing need to be fast.

Peter's class was helpful as a starter, but I need to expand that so that I can 'efficiently' retrieve bytes, lines and the entire buffer contents.

I have looked at ucollections.deque() but this uses tuples and tuples compared to bytearrays appear to take a lot more memory.

Post Reply