I need a FIFO for a work scheduler, and nothing suitable jumped out at me.  I wrote the following, but as a newbie, would be happy to receive any suggestions or observations.  TIA!

/*
 * fifo.d
 *      FIFO data structure
 */
module tiny.fifo;
import std.exception : enforce;

const uint GROWBY = 16;

/*
 * This is a FIFO, with "hd" walking forward and "tl" trailing
 *  behind:
 *            tl              hd /Add here next
 *            v               v
 *  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
 *
 * Mildly complicated by a module-size indexing.
 */
struct FIFO(T) {
    T[] items;
    ulong hd, tl, length;

    void
    add(T t) {
        // Make more room when needed
        if (this.items.length == this.length) {
            assert(this.hd == this.tl);

            // Add room and shuffle current contents
            auto olen = this.items.length;
            auto newlen = olen + GROWBY;
            this.items.length = newlen;
            this.tl = (this.tl + GROWBY) % newlen;

            // Shuffle what we're butted up against to their
            //  new position at the top of this.items[]
            ulong moved = olen - this.hd;
            this.items[$ - moved .. $] =
                this.items[this.hd .. this.hd + moved];
        }

        // Add item at next position
        this.items[hd] = t;
        this.hd = (this.hd + 1) % this.items.length;
        this.length += 1;
    }

    // Give back next
    T
    next() {
        enforce(this.length > 0, "next() from empty FIFO");
        this.length -= 1;
        auto res = this.items[this.tl];
        this.tl = (this.tl + 1) % this.items.length;
        return res;
    }
}

unittest {
    auto f = FIFO!uint();
    f.add(1);
    f.add(2);
    f.add(3);
    assert(f.next() == 1);
    assert(f.next() == 2);
    assert(f.next() == 3);
    assert(f.length == 0);

    // Now overflow several times
    f = FIFO!uint();
    foreach(x; 0 .. GROWBY * 3 + GROWBY/2) {
        f.add(x);
    }
    foreach(x; 0 .. GROWBY * 3 + GROWBY/2) {
        assert(f.next() == x);
    }
    assert(f.length == 0);
}

version(unittest) {
    void
    main()
    {
    }
}

On Saturday, 11 May 2024 at 23:44:28 UTC, Andy Valencia wrote:
> I need a FIFO for a work scheduler, and nothing suitable jumped out at me.  I wrote the following, but as a newbie, would be happy to receive any suggestions or observations.  TIA!
>
> [...]
https://dlang.org/phobos/std_container_slist.html

On Saturday, 11 May 2024 at 23:44:28 UTC, Andy Valencia wrote:
> I need a FIFO for a work scheduler, and nothing suitable jumped out at me.  I wrote the following, but as a newbie, would be happy to receive any suggestions or observations.  TIA!
>
> [...]

"next" is not a usual range primitive word in dlang. Why not just using slist.

On Saturday, 11 May 2024 at 23:44:28 UTC, Andy Valencia wrote:
> I need a FIFO for a work scheduler, and nothing suitable jumped out at me.  I wrote the following, but as a newbie, would be happy to receive any suggestions or observations.  TIA!
>
> [...]

I don't know your use case, maybe you have a similar problem I had to solve years ago.

https://forum.dlang.org/post/xktftztisodpngcownkw@forum.dlang.org

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();
}
        }
    }
}

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.

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:

Also try the code I gave in this thread:
https://forum.dlang.org/post/fgzvdhkdyevtzznyaacc@forum.dlang.org

In fact, please use this facility in the standard library: https://dlang.org/phobos/std_datetime_stopwatch.html#benchmark

SDB@79