FIFO

[Andy Valencia]

On Sunday, 12 May 2024 at 22:03:21 UTC, Ferhat Kurtulmuş wrote:
>>> https://dlang.org/phobos/std_container_slist.html
>> This is a stack, isn't it?  LIFO?
> Ahh yes. Then use dlist

Thank you.  I read its source, and was curious so I wrote a small 
performance measurement: put 10,000 things in a FIFO, pull them 
back out, and loop around that 10,000 times.  My FIFO resulted in:

real    0m1.589s
user    0m1.585s
sys     0m0.004s

And the dlist based one:

real    0m4.731s
user    0m5.211s
sys     0m0.308s

Representing the FIFO as a linked list clearly has its cost, but 
I found the increased system time interesting.  OS memory 
allocations maybe?

The code is spaghetti, fifo/dlist, but it seemed the easiest way 
to see the two API's being used side by side:

version(fifo) {
import tiny.fifo : FIFO;
} else {
import std.container.dlist : DList;
}

const uint ITERS = 10_000;
const uint DEPTH = 10_000;

void
main()
{
version(fifo) {
     auto d = FIFO!uint();
} else {
     auto d = DList!uint();
}
     foreach(_; 0 .. ITERS) {
         foreach(x; 0 .. DEPTH) {
version(fifo) {
             d.add(x);
} else {
             d.insertBack(x);
}
         }
         foreach(x; 0 .. DEPTH) {
version(fifo) {
             assert(x == d.next());
} else {
             assert(x == d.front());
             d.removeFront();
}
         }
     }
}