Asynchronous Queue

Question

implemented a basic Asynchronous Queue so, that I can do

await queue.push(item);
const item = await queue.pop();

basically I'm trying to convert a synchronous queue implementation into asynchronous one by using listeners for every pop operation if the queue is empty.

class Queue {
 constructor() {
 this.dict = {};
 this.start = 0;
 this.end = 0;
 }
 /**
 *
 * todo: if the number of operations exceed Number.MAX_SAFE_INTEGER (~ 2**53)
 * todo: there will be overflow errors, so shift the elements
 * todo: and make the operations asymptotically O(1)
 *
 * @param {*} item
 */
 push (item) {
 this.dict[this.end] = item;
 this.end += 1;
 }
 get length() {
 return this.end - this.start;
 }
 /**
 *
 * @returns {*}
 */
 pop () {
 if (this.start === this.end) {
 throw "OutOfBounds Exception, can't pop from an empty queue";
 }
 const item = this.dict[this.start];
 this.start += 1;
 return item;
 }
}
class AsyncQueue {
 constructor() {
 this.sync_queue = new Queue();
 this.waiting_minions = new Queue();
 }
 async push(item) {
 if (this.waiting_minions.length > 0) {
 const signal = this.waiting_minions.pop();
 await signal(item);
 } else {
 this.sync_queue.push(item);
 }
 }
 get length() {
 return this.sync_queue.length;
 }
 pop() {
 return new Promise((resolve) => {
 if (this.sync_queue.length > 0) {
 return resolve(this.sync_queue.pop());
 }
 this.waiting_minions.push(resolve);
 });
 }
}
module.exports = AsyncQueue;

Answer 1

• Queue: Is there a reason why you manually use shifting inside the array instead of Array#push() and Array#shift()?
  I do not know the internal implementations of them in JS engines, but I would use them unless profiling told be to do otherwise.

• AsyncQueue#pop():

  • Declare it as async even though you do not use await, it will serve readability.

  • Prefer if-else over early return (in this specific situation). Especially, return resolve(...) looks like you forward the return value of resolve (it doesn't have one AFAIK), but you are actually only using return for control flow management.

    async pop() {
     return new Promise(resolve => {
     if (this.sync_queue.length > 0) {
     resolve(this.sync_queue.pop());
     }
     else {
     this.waiting_minions.push(resolve);
     }
     });
    }
    

• AsyncQueue#push(): Do you have a use case for it being async? In case there are no pending pop() operations, it immediately resolves. In case there are some, it waits for the caller code from the pop() operation to complete, if I am not mistaken:

  setTimeout(async () => {
   await queue.pop();
   while (1);
  }, 100);
  await queue.push(42);
  // This line will never be reached
  

• (Async)Queue#length: I would declare it as a function for the same reasons I outlined in another review.

• AsyncQueue#length: this.arr does not exist. Did you mean to write this.sync_queue.length?

• eightnoteight: Array#shift complexity is high that it is inefficient for larger queue size
• ComFreek: @eightnoteight V8 does some trickery (ref) to make Array#shift O(1) for arrays unless they become larger than a specific limit. However, have you profiled that your code using a dictionary (might not get optimized as an array) instead of an array is really faster?
• eightnoteight: and yeah, should not have awaited for resolve of pop function

Answer 2

Some issues that would black list your module in some organisations.

Untrusted state

The whole thing is unsafe due to exposed properties. Exposed properties should be protected from improper use via code that either

1. Vets unsafe state properties before using them.
2. Hides them so that they are not accessible.
3. Uses setters to prevent mutation or improper state.

Some basic examples of misuse after expected invocation

const aQueue = new AsyncQueue(); // invocation 

Any one of the following makes state unusable or erroneous

aQueue.sync_queue = new AsyncQueue();
aQueue.sync_queue.push("monkey");
aQueue.sync_queue.start = "0"; // start will concat rather than add 1
aQueue.sync_queue.start = 2; // pop untrusted
aQueue.sync_queue.end = -1; // push can overwrite queue items
aQueue.sync_queue.dict = null; // complete destruction
// and many other ways

Unclean

You do not deference popped items in effect creating a pseudo memory leak. Long term use of an instance of AsyncQueue would present a degrading service that will eventually crash the host context with a Out of memory error

Ambiguity

You throw an exception that implies you expect Queue to be used independent of AsyncQueue interface. AsyncQueue will never pop from sync_queue if its length is zero, so why the throw?

Yet if Queue's interface is to be used why is the main interface not protected against misaligned queues?

Unsafe throw

Nor should you throw.

undefined is the accepted return for pop functions on an empty list / queue / array / etc... in JS. Throwing is a last resort when no other way is available to protect the application state. You can not know if pop on an empty queue will damage the using objects state, so you should not be throwing an error as that is way more likely to do damage.

Summery

This review is harsh and is primarily an argument against the use of class to define object prototypes.

Currently JS class syntax is incomplete and violates OO encapsulation paradigm by not providing a language mechanism to hide encapsulated properties. You should not use the class syntax to define objects that have a vulnerable state.

Without a use case I will not comment on the modules functionality apart from, it does not function as I would expect an async queue to.

• ComFreek: +1, on the argument against pop() returning undefined: You cannot store undefined values anymore (but nulls can be). This might be a valid decision, but then I would throw in push() when the caller tries to insert an undefined value. Actually, it is problematic when using arrays: without further inspection of array.length, one cannot determine whether one called array.shift() on an empty array or just on one containing an undefined head value.
• Blindman67: ComFreek? Why throw when pushing undefined. JS does not throw var a; [].push(a) Throwing in such case is a speculative preempt of an error. You should never do that.
• ComFreek: queue.push(undefined); console.log(queue.pop() === undefined) will print true. Now you cannot infer whether the queue was empty or whether it contained an element whose value was undefined. The only solution is to a) prevent undefined insertion into the queue or b) throw in pop() on an empty queue.
• Blindman67: @ComFreek Why would anyone use undefined to test for empty if they knew there might be an undefined on the queue. The "only solution" is, its none of the queue's business how it is used. Only throw on an errors that make an object's (queue's) state impossible to maintain (Encapsulation). Objects should not be intruding on another object's state management by second guessing how they are used. You would make the following illegal and require a try catch...; queue.push("A"); var aCount = 0; while(queue.pop()==="A") { aCount ++ }, Why? it does not effect the queue.
• ComFreek: E.g. because the insertion of undefined resulted from a bug. This is especially true for languages like JS without type checking => apply defensive programming. I agree with you, it kind of abuses exceptions and uglifies the code a bit. Consider adding an iterator + for-of-loop (cf. the same commonly accepted solution in Python). (If you would like to continue this discussion, I think we should do in chat.)