Issues with our "queue" interface and implementation(s)

[fingolfin]

• What we call a "queue" is actually a "deque" (double-ended queue) -> rename it
• replace Length by Size
• the code in lqueue.{gi,gd} was taken from HPC-GAP, and that code now is in the GAP master branch, see lib/queue.g. There is a name conflict for NewQueue, too... Resolve this
• possibly copy any HPC-GAP specific changes from there into our implementation?!
• consider re-implementing this in C -- should be straightforward
• document the internals of lqueue.gi, to help people debug it. It is actually a circular buffer, which is dynamically grown.
• consider providing a second Deque implementation based on the doubly linked list code

[stevelinton]

A few thoughts. Absent HPC there is very little reason ever to use any queue implementation except this (suitably cleaned up). So if we want to rename this Deque we might want to maintain synonyms as Queue -- I can see no reason to implement a one-way queue separately -- if someone wants one just give them a deque.

I'm also not sure there is much to be gained by reimplementing this in C. Except for resizing, the cost of the queue operations is so tiny that they will be dwarfed by anything I can think of that you might be doing with the data before or after queueing it.

If it isn't there, I would add an Operation to shrink the queue so it's memory usage is closeish to its current size. Also maybe some policy options for when if ever this happens automatically.

In a multi-threaded world this is a far bigger deal. There are good reasons for wanting DLL-based queues and for knowing which ends of the queue produce and consume. A lot of the time you also don't really need strict FIFO -- some kind of pool with stealing where most of the time each thread consumes only what it produces meets a lot of needs.

[fingolfin]

@stevelinton as to implementing in C or not: My experience is that the resizing operation can be substantially faster in C once the datastructure contains a few hundred thousand elements. Of course ideally, resizing shouldn't happen that often.

But also foo![1][2] can cost a substantial overhead. To get an idea, here is a very naive comparison of the binary heap, first the C version, then the GAP version (which no longer is in the repos):

gap> heap:=BinaryHeap();
<binary heap with 0 entries>
gap> for i in [1..1000000] do Push(heap, i); od; time;
98
gap> heap:=BinaryHeap();
<binary heap with 0 entries>
gap> for i in [1..1000000] do PCQL_Heap_Insert(heap, i); od; time;
2265

So that is noticeable. But then again, if one uses a heap with a million elements, one may have bigger issues elsewhere ;-).

Another advantage of writing this on the C level has the advantage is that there, nobody will keep automatically shrinking our plists if they have unbound entries ;-).

[stevelinton]

Resizing can be done with CopyListEntries which is pretty much optimal modulo a constant addition to get started (it reduces the loop to memmove in this case).

My thinking is that not that a C implementation will not be a noticeable constant factor faster, but rather that the GAP implementation should be fast enough that it should never be a factor in the performance of any real code. The situation with a priority queue is very different because (a) the work at each node is more complex and (b) each access will require about O(log n) nodes to be visited.