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.
