jfpoilpret/fast-arduino-lib

Queue buffer size waste improvement needed (was: Queue full bug)

Closed this issue · 6 comments

ab2121 commented

Hi!
False is returning when pushing the last item to the queue. The queue is full.

	char testBuf[8];
	containers::Queue<char, char> q(testBuf);

	q.clear();
	q.push(0x32); // 1
	q.push(0x33); // 2
	q.push(0x34); // 3
	q.push(0x35); // 4
	q.push(0x36); // 5
	q.push(0x37); // 6
	q.push(0xd); // 7
	auto result = q.push(0xa); // 8  Bug! False is returning.
	if (!result)
	{
		cout << ("Failed") << endl;
	}
	else
	{
		cout << ("Success") << endl;
	}
jfpoilpret commented

Hello @ab2121 , thank you for using FastArduino and reporting encountered issues.
Regarding the queue being full before its SIZE is reached, this is actually well known and documented here.
Here is an excerpt of this documentation of the Queue constructor:
image

As mentioned a queue built with a buffer of size N can contain only N-1 items, for optimization purposes.
Hence this problem cannot be considered a bug as the behavior fits Queue documentation.
Cheers

ab2121 commented

Hello @jfpoilpret! Thank you for the answer. I got it.

I looked for the sources, may be it is a good idea to hold the incremented size of the buffer.
Thus, the behavior of the queue will be more clear.

template<uint8_t SIZE> explicit Queue(T (&buffer)[SIZE], bool locked = false)
: buffer_{buffer}, size_{SIZE + 1}, locked_{locked} {}

jfpoilpret commented

Hi @ab2121 , thanks for your suggestion.
However, I am not sure such a simple change would be enough. Incrementing size_ here would probably break most Queue methods (except size() itself).
Currently, I do not have much time to test such improvement unfortunately.

But FastArduino library source code has "unit tests" for queues, you can find it in examples/misc/QueueCheck/queuecheck.cpp.
In order to check it, you need to upload it to an Arduino UNO and connect a serial console to your Arduino to see results.
If you perform your suggested changes on a local Git repo clone, you may be able to check if this still works or not.

Cheers

ab2121 commented

Hi @jfpoilpret. Sorry, I was too busy.

I made those changes on a local Git repo clone and fixed a buffer size in the test.
Is it Ok?

New empty queue
Comparing size() OK: 10
Comparing empty() OK: true
Comparing full() OK: false
Comparing items() OK: 0
Comparing free() OK: 10
Comparing peek(c) OK: false
Comparing empty() OK: true
Comparing full() OK: false
Comparing items() OK: 0
Comparing free() OK: 10
Push 1 char
Comparing empty() OK: false
Comparing full() OK: false
Comparing items() OK: 1
Comparing free() OK: 9
Pull 1 char
Comparing pull() OK: true
Comparing empty() OK: true
Comparing full() OK: false
Comparing items() OK: 0
Comparing free() OK: 10
Push 10 chars
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 10
Comparing free() OK: 0
Peek functions
Comparing peek(c) OK: true
Comparing peeked c OK: 1
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 10
Comparing free() OK: 0
Comparing peek(c) OK: true
Comparing peeked c OK: 1
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 10
Comparing free() OK: 0
Comparing peek(buf[5]) OK: 5
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 10
Comparing free() OK: 0
Comparing peek(buf[15]) OK: 10
Comparing peeked buf[15] Vs "123456789A" OK: 0
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 10
Comparing free() OK: 0
Comparing peek(buf, 5) OK: 5
Comparing peeked buf Vs "12345" OK: 0
peek_buffer20 = '12345'
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 10
Comparing free() OK: 0
Pull 8 chars
Comparing pull() 1 OK: true
Comparing pull() 2 OK: true
Comparing pull() 3 OK: true
Comparing pull() 4 OK: true
Comparing pull() 5 OK: true
Comparing pull() 6 OK: true
Comparing pull() 7 OK: true
Comparing pull() 8 OK: true
Comparing pull() 9 OK: true
Comparing empty() OK: false
Comparing full() OK: false
Comparing items() OK: 1
Comparing free() OK: 9
Pull last char
Comparing pull() A OK: true
Comparing empty() OK: true
Comparing full() OK: false
Comparing items() OK: 0
Comparing free() OK: 10
Pull no char
Comparing pull() OK: false
Comparing empty() OK: true
Comparing full() OK: false
Comparing items() OK: 0
Comparing free() OK: 10

jfpoilpret commented

Hi @ab2121 I reopen this issue in order to further check your proposed changes.

jfpoilpret commented

Hi @ab2121 I have performed several checks.

For testing, I have first extended the queuecheck.cpp to be more complete than before.

I have then tested it with the current Queue implementation (https://github.com/jfpoilpret/fast-arduino-lib/tree/master) and with your change (branch https://github.com/jfpoilpret/fast-arduino-lib/tree/queue_buffer_size_waste_investigation).

As a matter of fact, with your change, many problems occur, here is what I got (with CuteCom utility):

New empty queue
Comparing size() OK: 9
Comparing empty() OK: true
Comparing full() OK: false
<0xfe><0x88><0xb8><0x8d>}<0xde>'<0xc8><0xe0><0xc3><0xd2><0xdb><0x7f>]<0x7f><0xfc><0xf3><0xfb><0xe2>V/<0x1f><0x99><0xed><0xad><0xdd><0xe4><0xd8><0xe2><0xd5>^=<0x14><0xff><0xdc><0xfe><0xff><0xde><0xe5><0xbe><0xd9>G4<0xa6><0xc0><0xd3>.w<0x1d><0xdf><0x1e><0xf9><0xf1>b<0xb5><0x96><0xdf>['<0xed><0xfe><0x88><0xb8><0x8d>}<0xde>'<0xc8><0xe0><0xc3><0xd2><0xdb><0x7f>]<0x7f><0xfc><0xf3><0xfb><0xe2>V/<0x1f><0x99><0xed><0xad><0xdd><0xe4><0xd8><0xe2><0xd5>^=<0x14><0xff><0xdc><0xfe><0xff><0xde><0xe5><0xbe><0xd9>G4<0xa6><0xc0><0xd3>.w<0x1d><0xdf><0x1e><0xf9><0xf1>b<0xb5><0x96><0xdf>['<0xed><0xfe><0x88><0xb8><0x8d>}<0xde>'<0xc8><0xe0><0xc3><0xd2><0xdb><0x7f>]<0x7f><0xfc><0xf3><0xfb><0xe2>V/<0x1f><0x99><0xed><0xad><0xdd><0xe4><0xd8><0xe2><0xd5>^=<0x14><0xff><0xdc><0xfe><0xff><0xde><0xe5><0xbe><0xd9>G4<0xa6><0xc0><0xd3>.w<0x1d><0xdf><0x1e><0xf9><0xf1>b<0xb5>_<0x96><0xdf>['<0xed><0xfe><0x88><0xb8><0x8d>}

[Note that I have cut down the output, which is full of garbage like this until the end]

Here is the full output with current implementation:

New empty queue
Comparing size() OK: 9
Comparing empty() OK: true
Comparing full() OK: false
Comparing items() OK: 0
Comparing free() OK: 9
Comparing peek(c) OK: false
Comparing empty() OK: true
Comparing full() OK: false
Comparing items() OK: 0
Comparing free() OK: 9
Push 1 char
Comparing empty() OK: false
Comparing full() OK: false
Comparing items() OK: 1
Comparing free() OK: 8
Pull 1 char
Comparing pull() OK: true
Comparing empty() OK: true
Comparing full() OK: false
Comparing items() OK: 0
Comparing free() OK: 9
Push 9 chars
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 9
Comparing free() OK: 0
Push extra char
Comparing 1st extra push OK: false
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 9
Comparing free() OK: 0
Push extra char
Comparing 2nd extra push OK: false
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 9
Comparing free() OK: 0
Peek functions
Comparing peek(c) OK: true
Comparing peeked c OK: 1
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 9
Comparing free() OK: 0
Comparing peek(c) OK: true
Comparing peeked c OK: 1
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 9
Comparing free() OK: 0
Comparing peek(buf[5]) OK: 5
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 9
Comparing free() OK: 0
Comparing peek(buf[15]) OK: 9
Comparing peeked buf[15] Vs "123456789" OK: 0
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 9
Comparing free() OK: 0
Comparing peek(buf, 5) OK: 5
Comparing peeked buf Vs "12345" OK: 0
peek_buffer20 = '12345'
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 9
Comparing free() OK: 0
Pull 8 chars
Comparing pull() 1 OK: true
Comparing pull() 2 OK: true
Comparing pull() 3 OK: true
Comparing pull() 4 OK: true
Comparing pull() 5 OK: true
Comparing pull() 6 OK: true
Comparing pull() 7 OK: true
Comparing pull() 8 OK: true
Comparing empty() OK: false
Comparing full() OK: false
Comparing items() OK: 1
Comparing free() OK: 8
Push 3 chars
Comparing empty() OK: false
Comparing full() OK: false
Comparing items() OK: 4
Comparing free() OK: 5
Comparing peek(buf[5]) OK: 4
Comparing peeked buf[5] Vs "9ABC" OK: 0
Comparing empty() OK: false
Comparing full() OK: false
Comparing items() OK: 4
Comparing free() OK: 5
Push 5 chars
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 9
Comparing free() OK: 0
Push extra char
Comparing extra push OK: false
Comparing empty() OK: false
Comparing full() OK: true
Comparing items() OK: 9
Comparing free() OK: 0
Pull 8 chars
Comparing pull() 9 OK: true
Comparing pull() 9 OK: 9
Comparing pull() A OK: true
Comparing pull() A OK: A
Comparing pull() B OK: true
Comparing pull() B OK: B
Comparing pull() C OK: true
Comparing pull() C OK: C
Comparing pull() D OK: true
Comparing pull() D OK: D
Comparing pull() E OK: true
Comparing pull() E OK: E
Comparing pull() F OK: true
Comparing pull() F OK: F
Comparing pull() G OK: true
Comparing pull() G OK: G
Comparing empty() OK: false
Comparing full() OK: false
Comparing items() OK: 1
Comparing free() OK: 8
Pull last char
Comparing pull() H OK: true
Comparing pull() H OK: H
Comparing empty() OK: true
Comparing full() OK: false
Comparing items() OK: 0
Comparing free() OK: 9
Pull no char
Comparing pull() OK: false
Comparing empty() OK: true
Comparing full() OK: false
Comparing items() OK: 0
Comparing free() OK: 9

The display issue is due to the fact that UART itself is based on a Queue: if the Queue fails, the UART will fail!

The Queue issue actually can be easily understood:

  • the Queue is considered empty when (head_ == tail_)
  • the Queue is considered full when (tail_ + 1) == head_ (if head_ != 0) or when (tail_ + 1) == size_ (if head_ == 0)
  • now if you push size_ items (without pulling), what happens is that head_ does not change (0 initially), whereas tail_ is incremented size_ times, but it then reaches size_ (which would make it point to invalid buffer cell), hence is set back to 0: in the end head_ == tail_ which means the Queue is empty although it is actually full!

This change cannot work without a complete refactoring of Queue implementation.
Such a change would require:

  • adding one extra member (some current_size_ member)
  • adding code to deal with that extra member, at least in push_() and pull_() methods

Current Queue implementation actually tries to optimize code in push_() and pull_() methods, because these methods are likely to be used often inside ISR functions, hence they must:

  • run fast (be as simple as possible)
  • use as few registers as possible (otherwise the ISR will have a lot of assembly PUSH and POP instructions, each using 2 clock cycles)

Adding an extra member and the related code would definitely break those 2 goals above.

I think in the end, wasting one item in buffer is a good trade-off, compared with the gained optimizations.
For this reason, I am afraid I'll close this issue as not possible with the current constraints.