FIFO

[Ferhat Kurtulmuş]

On Monday, 13 May 2024 at 15:07:39 UTC, Andy Valencia wrote:
> 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();
> }
>         }
>     }
> }

thank you for sharing the results. Everything I read about queues 
recommends doublylinked lists. With your array based 
implementatio if you are consuming the elements faster than 
pushing new elements, your array buffer never resize which is 
costly. This should explain why your array based queue is more 
performant.