www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Stack-based nogc dynamic array

reply Marco de Wild <mdwild sogyo.nl> writes:
Hey all,

I want to create a small collection of items to store 
intermediate results of a calculation. It runs on a background 
thread, so it does not need to be the most efficient 
implementation. However, I want to prevent my background thread 
introducing a stop-the-world garbage collection.
In my program (rules and an AI for a mahjong game), the 
collection size is at most 14 (tiles in hand). I figured it would 
be the most simple to just keep it stack based. MY first attempt 
looks like:
```
struct NoGcArray(size_t maxSize, T)
{
     private T[maxSize] _buffer;
     private size_t _length;
     size_t length() pure const  nogc nothrow
     {
         return _length;
     }

     void opOpAssign(string op)(T element) pure  nogc nothrow
     in(_length < maxSize, "Cannot append if the buffer is fully 
filled.")
     {
         static if(op == "~")
         {
             _buffer[_length] = element;
             ++_length;
         }
         else
         {
             static assert(false, "Only concatenation supported");
         }
     }

     T opIndex(size_t index)
     in(index < _length, "Cannot access index greater than length")
     {
         return _buffer[index];
     }

     auto range() pure const  nogc nothrow
     {
         return Range(this);
     }

     alias range this;

     static struct Range
     {
         this(NoGcArray src)
         {
             _src = src;
         }
         private NoGcArray _src;
         private size_t _index;

         T front() pure  nogc nothrow
         {
             return _src[_index];
         }

         void popFront() pure  nogc nothrow
         {
             _index++;
         }

         bool empty() pure  nogc nothrow
         {
             return _src._length <= _index;
         }
     }
}
```
However,
```
unittest
{
     import std.algorithm : sum, map;
     import fluent.asserts;
     NoGcArray!(4, int) array;
     array ~= 420;
     array ~= 42;
     array.map!(x => x*2).sum.should.equal(924);
}
```
fails. The test will run in an infinite loop. After some digging, 
I realise that the `alias this` is foiling with my plan rather 
than helping it. Is there a recommended way to achieve
- std.algorithm functions should Just Work (tm)
- appending as if it were a dynamic array
- preferably index-based access and .length should also work.

Is there a dub package that achieves this? Or are there any tips 
to roll my own implementation?
May 16 2019
next sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
I think you have overcomplicated something quite simple.

int[4] buffer;
int bufferLength;

buffer[bufferLength++] = item_to_append;
buffer[bufferLength++] = item_to_append;

int[] slice = buffer[0 .. bufferLength];

// you can use slice to any std.algorithm calls etc
// just remember it is on the stack so don't store it beyond a 
function call
May 16 2019
parent Marco de Wild <mdwild sogyo.nl> writes:
On Thursday, 16 May 2019 at 12:45:03 UTC, Adam D. Ruppe wrote:

 I think you have overcomplicated something quite simple.

 int[4] buffer;
 int bufferLength;

 buffer[bufferLength++] = item_to_append;
 buffer[bufferLength++] = item_to_append;

 int[] slice = buffer[0 .. bufferLength];

 // you can use slice to any std.algorithm calls etc
 // just remember it is on the stack so don't store it beyond a 
 function call


Thanks. It's really a lot simpler than I thought. It's slightly 
error prone (i.e., the code doesn't work if I use 
++bufferLength), but its simplicity might be worth the trade-off.
May 16 2019
prev sibling next sibling parent reply Kagamin <spam here.lot> writes:
Try mach.d https://github.com/pineapplemachine/mach.d it uses 
explicit range accessors for iteration.
May 16 2019
parent reply Marco de Wild <mdwild sogyo.nl> writes:
Thank you both for the quick replies.

On Thursday, 16 May 2019 at 12:55:34 UTC, Kagamin wrote:

 Try mach.d https://github.com/pineapplemachine/mach.d it uses 
 explicit range accessors for iteration.


Thank you. I've looked into it, and it appears to be quite a big 
library. I've looked into mach.collect and mach.range, but I 
didn't manage to find what I was looking for (a simple array data 
structure). Do you recommend to look into any specific module?
May 16 2019
parent Kagamin <spam here.lot> writes:
On Friday, 17 May 2019 at 06:58:54 UTC, Marco de Wild wrote:

 Thank you. I've looked into it, and it appears to be quite a 
 big library. I've looked into mach.collect and mach.range, but 
 I didn't manage to find what I was looking for (a simple array 
 data structure). Do you recommend to look into any specific 
 module?


You use your array with math.range, but without alias this, it 
uses explicit accessor `asrange` for iteration.
May 17 2019
prev sibling parent Mike Franklin <slavo5150 yahoo.com> writes:
On Thursday, 16 May 2019 at 12:16:26 UTC, Marco de Wild wrote:


 Or are there any tips to roll my own implementation?


I took a stab at it:

---
 nogc:
nothrow:
pure:

struct NoGcArray(size_t maxSize, T)
{
     private T[maxSize] _buffer;
     private T[] _slice;
     private size_t _frontIndex;

     size_t length() const
     {
         return _slice.length;
     }

     void opOpAssign(string op)(T element)
     {
         static if(op == "~")
         {
             _buffer[_frontIndex + length] = element;
             _slice = _buffer[_frontIndex..(length + 1)];
         }
         else
         {
             static assert(false, "Only concatenation supported");
         }
     }

     T opIndex(size_t index) const
     {
         return _slice[index];
     }

     T front() const
     {
         return _slice[0];
     }

     void popFront()
     {
         _frontIndex++;
         _slice = _slice[1..$];
     }

     bool empty() const
     {
         return _slice.length == 0;
     }
}

void main()
{
     import std.algorithm : sum, map;
     NoGcArray!(4, int) array;
     array ~= 420;
     array ~= 42;
     assert(array.map!(x => x*2).sum == 924);
}
---

Mike
May 17 2019