ring / fifo buffer
ring / fifo buffer
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 ??
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 ??
Re: ring / fifo buffer
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 ??
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 ??
Re: ring / fifo buffer
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.
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.
Re: ring / fifo buffer
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.
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
- pythoncoder
- Posts: 5956
- Joined: Fri Jul 18, 2014 8:01 am
- Location: UK
- Contact:
Re: ring / fifo buffer
@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.
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.
Index to my micropython libraries.
Re: ring / fifo buffer
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.
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.
Re: ring / fifo buffer
Hello Roberthh,Roberthh wrote: ↑Mon Jun 25, 2018 7:31 pmRingbuffers 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
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)
Re: ring / fifo buffer
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.
- pythoncoder
- Posts: 5956
- Joined: Fri Jul 18, 2014 8:01 am
- Location: UK
- Contact:
Re: ring / fifo buffer
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.
Index to my micropython libraries.