www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - FIFO

reply Andy Valencia <dont spam.me> writes:
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()
     {
     }
}
May 11
next sibling parent reply Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
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
May 12
parent reply Andy Valencia <dont spam.me> writes:
On Sunday, 12 May 2024 at 19:45:44 UTC, Ferhat Kurtulmuş wrote:

 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.


 ...
 https://dlang.org/phobos/std_container_slist.html


This is a stack, isn't it?  LIFO?

Andy
May 12
parent reply Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
On Sunday, 12 May 2024 at 21:08:24 UTC, Andy Valencia wrote:

 On Sunday, 12 May 2024 at 19:45:44 UTC, Ferhat Kurtulmuş wrote:

 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.


 ...
 https://dlang.org/phobos/std_container_slist.html


 This is a stack, isn't it?  LIFO?

 Andy


Ahh yes. Then use dlist
May 12
parent reply Andy Valencia <dont spam.me> writes:
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();
}
         }
     }
}
May 13
next sibling parent Salih Dincer <salihdb hotmail.com> writes:
On Monday, 13 May 2024 at 15:07:39 UTC, Andy Valencia wrote:

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


I know you want FIFO, I usually keep this on hand for fixed size 
LIFO; It can easily convert to FIFO and doesn't use LinkedList:

```d
class LIFO(T)
{
   T * element;
   size_t length, size;
   this(size_t s) {
     element = cast(T*)new T[s];
     length = s;
   }
   auto rewind() => size = length;

   bool empty() => !size;
   auto front() => element[size - 1];
   auto popFront() => --size;

   auto pop() => empty ? T(0) : element[--size];
   alias push = insertFront;
   auto insertFront(T value)
   in(size < length, "Stack is overflow!")
     => element[size++] = value;

   auto ref opDollar() => length;
   auto ref opIndex(size_t i) => element[i];
   auto ref opSlice(size_t first, size_t last)
     => element[first..last];

} unittest {

   enum test = 7;
   auto stack = new LIFO!size_t(test);

   assert(!stack.size);
   foreach (prime; 1..test + 1)
   {
     stack.insertFront(prime);
   }
   assert(stack.size == test); // == 7

   stack.writeln(": ", stack.length); // [7, 6, 5, 4, 3, 2, 1]: 7
   stack[$/2].writeln("-", stack[0]); // 4-1


   stack.rewind();
   stack.size.write(": ["); // 10:
   while (auto next = stack.pop)
   {
     if (next == 1) next.writeln("]");
     else next.write(", ");
   }
   stack.size.writeln; // 0
   stack.rewind();
   assert(stack.size == test);
}

SDB 79
May 13
prev sibling next sibling parent Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
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.
May 13
prev sibling parent Salih Dincer <salihdb hotmail.com> writes:
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
May 14
prev sibling next sibling parent Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
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.
May 12
prev sibling parent Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
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
May 13