Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

FixedCircularBuffer isFull(), isEmpty() and wrapping off by one #53139

Closed
jerome-benoit opened this issue May 24, 2024 · 6 comments
Closed

FixedCircularBuffer isFull(), isEmpty() and wrapping off by one #53139

jerome-benoit opened this issue May 24, 2024 · 6 comments
Labels
buffer Issues and PRs related to the buffer subsystem.

Comments

@jerome-benoit
Copy link
Contributor

jerome-benoit commented May 24, 2024

Version

Not relevant

Platform

Not relevant

Subsystem

Not relevant

What steps will reproduce the bug?

No response

How often does it reproduce? Is there a required condition?

No response

What is the expected behavior? Why is that the expected behavior?

No response

What do you see instead?

Implementation copied from lib/internal/fixed_queue.js:

const kSize = 4;
const kMask = kSize - 1;


class FixedCircularBuffer {
  constructor() {
    this.bottom = 0;
    this.top = 0;
    this.list = new Array(kSize);
    this.next = null;
  }

  isEmpty() {
    return this.top === this.bottom;
  }

  isFull() {
    return ((this.top + 1) & kMask) === this.bottom;
  }

  push(data) {
    this.list[this.top] = data;
    this.top = (this.top + 1) & kMask;
  }

  shift() {
    const nextItem = this.list[this.bottom];
    if (nextItem === undefined)
      return null;
    this.list[this.bottom] = undefined;
    this.bottom = (this.bottom + 1) & kMask;
    return nextItem;
  }
}

const circularBuffer = new FixedCircularBuffer();
console.log(circularBuffer.isFull()); // false
console.log(circularBuffer.isEmpty()); // true
circularBuffer.push(1);
console.log(circularBuffer.list);
console.log(circularBuffer.isFull()); // false
console.log(circularBuffer.isEmpty()); // false
circularBuffer.push(2);
console.log(circularBuffer.list);
console.log(circularBuffer.isFull()); // false
console.log(circularBuffer.isEmpty()); // false
circularBuffer.push(3);
console.log(circularBuffer.list);
console.log(circularBuffer.isFull()); // false, received true
console.log(circularBuffer.isEmpty()); // false
circularBuffer.push(4);
console.log(circularBuffer.list);
console.log(circularBuffer.isFull()); // true, received false
console.log(circularBuffer.isEmpty()); // false, received true

One way to fix it to count the number of elements in list at push() and shift() and test it against zero or the 'list` fixed array size.

It's current usage in FixedQueue does not expose the issue with wrapping when full and the resulting incorrect FIFO semantic at shift() because a new buffer is created. But the trade off at losing one array space each 2047 elements is debatable vs. integer property increment/decrement + branching one more.

Additional information

No response

@jerome-benoit jerome-benoit changed the title FixedCircularBuffer isFull(), isEmpty() off by one FixedCircularBuffer isFull(), isEmpty() and wrapping off by one May 24, 2024
@RedYetiDev RedYetiDev added the buffer Issues and PRs related to the buffer subsystem. label May 24, 2024
@climba03003
Copy link
Contributor

climba03003 commented May 27, 2024

Your example is demonstrating how buffer overflow exist. When people is pushing to a buffer stack without caring the state, then all the information will be messed up.

In a proper case, the buffer should throw when pushing new data in full state. So, the .push(4) is not possible.
But, if everyone knows what he is doing it can be skipped.

For example, the below usage shows it is properly skip pushing when a FixedCircularBuffer is full.

push(data) {
if (this.head.isFull()) {
// Head is full: Creates a new queue, sets the old queue's `.next` to it,
// and sets it as the new main queue.
this.head = this.head.next = new FixedCircularBuffer();
}
this.head.push(data);
}
shift() {
const tail = this.tail;
const next = tail.shift();
if (tail.isEmpty() && tail.next !== null) {
// If there is another queue, it forms the new tail.
this.tail = tail.next;
tail.next = null;
}
return next;
}

@jerome-benoit
Copy link
Contributor Author

jerome-benoit commented May 27, 2024

The expected circular buffer semantic is not to throw when full. Making it throw will follow a fixed queue semantic.

As I said, the current usage is not triggering the issue. And the buggy implementation is not exported. I understand the branching less optimization for a specific use case.

But the tradeoff is debatable with for example a 100k sized fixed queue. And I do not find any benchmarking code on fixed queue implementation in the repo.

Before I start to test optimization in that code with appropriate benchmarking, I want to make sure the semantic issues on well defined data structure are understood. The naming fixed queue on in fact a queue using several fixed arrays for storage is also debatable.

@climba03003
Copy link
Contributor

climba03003 commented May 27, 2024

Reference from https://wiki.c2.com/?CircularBuffer

A circular buffer makes a bounded queue when separate indices are used for inserting and removing data. The queue can be safely shared between threads (or processors) without further synchronization so long as one processor enqueues data and the other dequeues it. (Also, modifications to the read/write pointers must be atomic, and this is a non-blocking queue--an error is returned when trying to write to a full queue or read from an empty queue).

Despite it is expected for throwing in circular buffer or not.
I still incline to think that when circular buffer is implemented for queue, it should throw when the buffer is full.
Otherwise, the queue will be overwritten.

For the usage of FixedCircularBuffer in FixedQueue.

Note that a circular buffer with n elements is usually used to implement a queue with n-1 elements--there is always one empty element in the buffer. Otherwise, it becomes difficult to distinguish between a full and empty queue--the read and write pointers would be identical in both cases.

I believe it is acceptable to be n - 1 in actual size.
The implementation of FixedQueue using multiple FixedCircularBuffer is based on the optimal buffer size 2048 in v8 and allows unbounded queue size.

The original design is date back from PR 18617, throughout the conversation. The benefit are

  1. Reduce GC times
  2. Prevent object creation

Note: I am not a member from Node.js, I just want to discuses about it since I am interested in the implementation too.

@jerome-benoit
Copy link
Contributor Author

A circular buffer makes a bounded queue when separate indices are used for inserting and removing data. The queue can be safely shared between threads (or processors) without further synchronization so long as one processor enqueues data and the other dequeues it. (Also, modifications to the read/write pointers must be atomic, and this is a non-blocking queue--an error is returned when trying to write to a full queue or read from an empty queue).

Despite it is expected for throwing in circular buffer or not. I still incline to think that when circular buffer is implemented for queue, it should throw when the buffer is full. Otherwise, the queue will be overwritten.

A fixed queue can be implemented with a circular buffer design, at the cost of losing one 'space'. In that case, it's still called a fixed queue, not a circular buffer. The underlying design choice to implement a fixed queue semantic is not expected to change the name of the initial abstraction.
The usage of the term 'circular' expects a wrapping semantic when full.
The nitpicking on the naming is not that important here. One can find in the wild different definitions.

My concerns are more about the performance optimization of the implementation without benchmarking the alternatives:

  • Fixed array direct usage vs. fixed circular buffer (fixed queue in fact): native push()/shift() on array vs. class maintaining counters for the fixed array indexes
  • Bitwise operations vs. ternary operator for counters maintenance

I plan when time permits to add a benchmark for the fixed queue. Then start testing with performance regression detection some micro optimizations.

@jerome-benoit
Copy link
Contributor Author

jerome-benoit commented May 29, 2024

My concerns are more about the performance optimization of the implementation without benchmarking the alternatives:

  • Fixed array direct usage vs. fixed circular buffer (fixed queue in fact): native push()/shift() on array vs. class maintaining counters for the fixed array indexes

On that one, the current implementation is the most efficient and cannot change the size of the fixed size array without noticing.

  • Bitwise operations vs. ternary operator for counters maintenance

On that one, it's not that clear, the integer binary representation significant bits size seems to impact badly bitwise operation at a first glance, when the ternary operator behaves most consistently whatever its value is.

Benchmark results to come.

@jerome-benoit
Copy link
Contributor Author

Not enough FOSS time to dig further.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
buffer Issues and PRs related to the buffer subsystem.
Projects
None yet
Development

No branches or pull requests

3 participants