www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Is it possible to append to a local buffer without reallocating?

reply tipdbmp <email example.com> writes:
string push_stuff(char[] buf, int x) {
     if (x == 1) {
         buf ~= 'A';
         buf ~= 'B';
         buf ~= 'C';
         return cast(string) buf[0 .. 3];
     }
     else {
         buf ~= 'A';
         buf ~= 'B';
         return cast(string) buf[0 .. 2];
     }
}

void foo() {
     {
         char[2] buf;
         string result = push_stuff(buf, 1);
         assert(buf.ptr != result.ptr);
     }

     {
         char[2] buf;
         string result = push_stuff(buf, 0);
         assert(buf.ptr == result.ptr); // <-- this assert fails
     }
}
Jan 11 2018
next sibling parent Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Thursday, 11 January 2018 at 11:21:08 UTC, tipdbmp wrote:

 string push_stuff(char[] buf, int x) {
     if (x == 1) {
         buf ~= 'A';
         buf ~= 'B';
         buf ~= 'C';
         return cast(string) buf[0 .. 3];
     }
     else {
         buf ~= 'A';
         buf ~= 'B';
         return cast(string) buf[0 .. 2];
     }
 }

 void foo() {
     {
         char[2] buf;
         string result = push_stuff(buf, 1);
         assert(buf.ptr != result.ptr);
     }

     {
         char[2] buf;
         string result = push_stuff(buf, 0);
         assert(buf.ptr == result.ptr); // <-- this assert fails
     }
 }


Have you checked what push_stuff actually returns with those 
inputs?

When you pass buf to push_stuff, it contains [255,255], and 
already has a length of 2. It's not possible to append to that 
without reallocating.

Now, that's not the whole problem. When you append to an array, 
the GC checks if there's any free space in the block that's been 
allocated. Since this is on the stack, the GC doesn't have a 
blockinfo for it, and even if it did, the layout would change so 
often that the overhead would be immense.

So, the answer is no, it's not possible.

--
   Simen
Jan 11 2018
prev sibling next sibling parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Thursday, January 11, 2018 11:21:08 tipdbmp via Digitalmars-d-learn 
wrote:

 string push_stuff(char[] buf, int x) {
      if (x == 1) {
          buf ~= 'A';
          buf ~= 'B';
          buf ~= 'C';
          return cast(string) buf[0 .. 3];
      }
      else {
          buf ~= 'A';
          buf ~= 'B';
          return cast(string) buf[0 .. 2];
      }
 }

 void foo() {
      {
          char[2] buf;
          string result = push_stuff(buf, 1);
          assert(buf.ptr != result.ptr);
      }

      {
          char[2] buf;
          string result = push_stuff(buf, 0);
          assert(buf.ptr == result.ptr); // <-- this assert fails
      }
 }


A dynamic array can only expand in place without reallocating if its memory
was allocated by the GC for a dynamic array, and it's the farthest slice
into that block of memory (so that appending to it wouldn't overlap with
another array). A dynamic array which is a slice of a static array is not
allocated by the GC to be a dynamic array; it was allocated on the stack to
be a stack array. So, appending to it even once would cause it to be
reallocated.

But if you want to know whether reallocation is going to occur, then check
the array's capacity. If the capacity is the length of the dynamic array or
less, then appending will cause it to reallocate. For a dynamic array backed
by a static array or malloc-ed memory or anything other than memory
allocated by the GC to be a dynamic array, the capacity will be 0.

- Jonathan M Davis
Jan 11 2018
parent tipdbmp <email example.com> writes:
 Have you checked what push_stuff actually returns with those 
 inputs?


Right, we get [0xFF, 0xFF, 'A'] and [0xFF, 0xFF].

I think the following is a pretty easy workaround though:

alias usize = size_t;

struct Push_Buf(T, usize stack_size) {
     T[stack_size] stack_buf;
     T[] heap_buf;
     usize p = 0;

     void opOpAssign(string op)(T e) if (op == "~") {
         if (p < stack_size) {
             stack_buf[p] = e;
             p += 1;
         }
         else {
             if (p == stack_size) {
                 heap_buf = stack_buf.dup();
                 p += 1;
             }
             heap_buf ~= e;
         }
     }

     void opOpAssign(string op)(immutable(T)[] es) if (op == "~") {
         if (p + es.length <= stack_size) {
             import core.stdc.string : memcpy;
             memcpy(&stack_buf[p], es.ptr, es.length);
             p += es.length;
         }
         else {
             if (p < stack_size) {
                 heap_buf = stack_buf[0 .. p].dup();
                 p += es.length;
             }
             heap_buf ~= es;
         }
     }

     U opCast(U: T[])() { return as_slice(); }
     U opCast(U: immutable(T)[])() { return cast(immutable(T)[]) 
as_slice(); }

      property T[] as_slice() {
         if (p <= stack_size) { return stack_buf[0 .. p]; }
         else return heap_buf;
     }

     alias as_slice this;
}

string push_stuff(usize buf_size)(ref Push_Buf!(char, buf_size) 
buf, int x) {
     if (x == 1) {
         buf ~= 'A';
         buf ~= 'B';
         buf ~= 'C';
     }
     else {
         buf ~= 'A';
         buf ~= 'B';
     }
     return cast(string) buf;
}

void foo() {
     {
         Push_Buf!(char, 2) buf;
         string result = push_stuff(buf, 1);
         assert(buf.heap_buf.ptr == result.ptr);
     }
     {
         Push_Buf!(char, 2) buf;
         string result = push_stuff(buf, 0);
         assert(buf.stack_buf.ptr == result.ptr);
     }
}
Jan 11 2018
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/11/18 6:21 AM, tipdbmp wrote:

 string push_stuff(char[] buf, int x) {
      if (x == 1) {
          buf ~= 'A';
          buf ~= 'B';
          buf ~= 'C';
          return cast(string) buf[0 .. 3];
      }
      else {
          buf ~= 'A';
          buf ~= 'B';
          return cast(string) buf[0 .. 2];
      }
 }
 
 void foo() {
      {
          char[2] buf;
          string result = push_stuff(buf, 1);
          assert(buf.ptr != result.ptr);
      }
 
      {
          char[2] buf;
          string result = push_stuff(buf, 0);
          assert(buf.ptr == result.ptr); // <-- this assert fails
      }
 }
 


Appender is able to do this:

import std.array;

void main()
{
     char[2] buf;
     auto app = appender(buf[]);
     app.clear; // resets the buffer so it can be used again.
     app ~= 'A';
     app ~= 'B';
     assert(buf[] == "AB");
     assert(app.data.ptr == buf.ptr);
     app ~= 'C';
     assert(app.data.ptr != buf.ptr);
}

-Steve
Jan 11 2018
parent reply tipdbmp <email example.com> writes:
 Appender is able to do this:


It seems that Appender allocates its own private data:

private struct Data
{
     size_t capacity;
     Unqual!T[] arr;
     bool canExtend = false;
}
...
private Data* _data;
...
_data = new Data;

But hopefully its bug free unlike what I posted (missing 
`T.sizeof *` in the memcpy call).
Jan 11 2018
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/11/18 12:41 PM, tipdbmp wrote:

 Appender is able to do this:


 
 It seems that Appender allocates its own private data:
 
 private struct Data
 {
      size_t capacity;
      Unqual!T[] arr;
      bool canExtend = false;
 }
 ....
 private Data* _data;
 ....
 _data = new Data;
 
 But hopefully its bug free unlike what I posted (missing `T.sizeof *` in 
 the memcpy call).
 
 


Hm... I thought it was using C malloc, or at least there was a version 
where it wasn't allocating an impl struct (I thought that had gone in a 
while ago?)

But you can see how to accomplish what you seek by reading the code.

-Steve
Jan 11 2018