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: 473
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: 473
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: 230
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: 3667
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: 5956
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
Index to my micropython libraries.

User avatar
devnull
Posts: 473
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.

Kleriger
Posts: 6
Joined: Mon Dec 30, 2019 9:16 am

Re: ring / fifo buffer

Post by Kleriger » Mon Dec 30, 2019 10:02 am

Roberthh wrote:
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
Hello Roberthh,
I was looking for a buffer to cache changes to the GPIOs and came across your post.
The GPIOs are currently saved in a list before they are transferred to my broker via umqtt. With a buffer I want to prevent changes that are close in time from being lost.
So far I had transferred the data directly as a list via json. Is it also possible to save an entire list in a buffer? Your code works as far as I can see only for one byte at a time.

My relevant code so far:

Code: Select all


pins = [16, 17, 18, 19, 21, 22, 23] #GPIO pins
pin_sensors = [machine.Pin(pin, machine.Pin.IN, machine.Pin.PULL_UP) for pin in pins] #declare GPIOs
value_sensor_list = [0,0,0,0,0,0,0] #initialize sensor_0 -> sensor_6
value_sensor_list_prev = [0,0,0,0,0,0,0] #initialize sensor_0 -> sensor_6

buffer = RINGBUFFER(10)

#get values
value_sensor_list_prev = value_sensor_list
value_sensor_list = [pin.value() for pin in pin_sensors] #get list of all pin values
if (value_sensor_list != value_sensor_list_prev) | (time.time() - publish_time_prev >= mqtt_keep_alive):

        #mqtt
        publish_time_prev = time.time()
        client.publish("test_channel", json.dumps(value_sensor_list), qos=0)
        
Instead of asking if the list has changed, I would simply ask whether there is a new value in the buffer and, accordingly, write the list to the buffer beforehand when changing the GPIOs.

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

Re: ring / fifo buffer

Post by Roberthh » Wed Jan 01, 2020 7:29 pm

The code is just an example for byte sized objects, to provide a buffering between a writer and a reader, which is not always as fast as the writer. Obviously, the buffer for the ring could also be a fixed size list, where every list element can contain arbitrary objects, for instance a list. Only this will not be fast.

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

Re: ring / fifo buffer

Post by pythoncoder » Thu Jan 02, 2020 1:11 pm

An alternative approach would be to use uasyncio. Each incoming message would initialise a task which would process that message and terminate. Effectively you are using the uasyncio task queue to ensure nothing is lost.
Peter Hinch
Index to my micropython libraries.

Post Reply