www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Array efficiency & rendering buffers

reply Henrik Eneroth <Henrik_member pathlink.com> writes:
Hello!

I am right now staring at some C++ code about to be converted to D. It's a bunch
of renderers and rendering buffers. Now, in C++ it was implemented so that you
would allocate a bit of memory yourself and then send it to the rendering buffer
- basically saying "hey, use this". 
Operations were then done via this buffer, and after it was done, you just
passed the pointer to the next rendering buffer and so on, until your hearts
content. Multiple renderers could operate directly on the same bit of memory
this way, and little to no memory was actually copied anywhere. 
Now I am all for doing things the D way when porting to D, but I feel that I'm
not all that experienced with the language yet and thus I would like to hear
some opinions so that I don't implement anything unnecessary, naive or unstable.
Fast renderers and simplicity of code is of course what I am heading for here,
but in that order.
Could I use plain arrays to achieve this functionality, or will such an
implementation make it crawl at a snails pace compared to it's older C++ cousin?
Passing an array to a function and then using its return would involve quite a
bit of copying, no? Should I pass around pointers to arrays, or maybe just plain
pointers? What would be the data storage method of choice when implementing
renderers and rendering buffers where efficiency obviously is of the essence?

Best regards,

Henrik
Jun 07 2006
next sibling parent Sean Kelly <sean f4.ca> writes:
Henrik Eneroth wrote:

 Passing an array to a function and then using its return would involve quite a
 bit of copying, no? Should I pass around pointers to arrays, or maybe just
plain
 pointers?


Under the covers, arrays are stored as:

     struct Array {
         size_t len;
         void*  ptr;
     }

So passing by value is actually quite inexpensive.  If this wasn't 
enough, you could pass by reference via the 'inout' qualifier.

Sean
Jun 07 2006
prev sibling parent reply "Derek Parnell" <derek psych.ward> writes:
On Thu, 08 Jun 2006 08:08:20 +1000, Henrik Eneroth  
<Henrik_member pathlink.com> wrote:




 Could I use plain arrays to achieve this functionality, or will such an
 implementation make it crawl at a snails pace compared to it's older  
 C++ cousin?
 Passing an array to a function and then using its return would involve  
 quite a
 bit of copying, no? Should I pass around pointers to arrays, or maybe  
 just plain
 pointers?


In D, the only method you have to pass variable-length arrays is by  
reference. You cannot pass such an array by value even though the syntax  
*looks* like that's what you are doing. However the implementation of  
variable-length arrays is such that they have two components: the array  
data and the array descriptor (or reference). The array data is simply the  
amount of contiguous RAM needed to hold all the elements and this is  
allocated on the heap, and the descriptor is a two-member struct-like  
entity of eight bytes ...

   {
      int Length;
      void *Data;
   }

When you call a function using the array name as an argument, the compiler  
is actually passing the descriptor and not the data itself. Same with  
returning an array.

   char[] String = "some data in a char array";
   char[] Result = "init value";
   Result = foo(String);

In this case, the 'foo' function receives the array descriptor for  
'String' and returns an array descriptor that overwrites the current array  
descriptor for 'Result'. The original data referred to by Result is now  
unreferenced and will be automatically deallocated by the garbage  
collector at some stage.

   char[] foo(char[] arg)
   {
      for(int i = 0; i < arg.length; i++)
      {
         if (arg[i] == 'a')
              arg[i] = 'A';
      }
      return arg;
   }

As the 'foo' function receives an array descriptor, it is free to modify  
the data belonging to the array. However as it receives this arg as an  
'in' (by default) type of parameter passing it means that 'foo' does not  
pass back any modifications to the 'arg' array descriptor to the caller.  
As it stands, after this example 'foo' is called, the String and Result  
variables will both point/reference the exact same piece of RAM (data  
elements).

   Result[0] = 'Q';
   writefln("%s", String);

  ==> output is "Qome dAtA in A chAr ArrAy"

To avoid this effect, if its undesirable, you need to implement the  
Copy-on-Write paradigm. This means that if 'foo' changes the data it  
should return a new array descriptor that now references a newly allocated  
piece of RAM.

   char[] foo(char[] arg)
   {
      bool IsModified = false;

      for(int i = 0; i < arg.length; i++)
      {
         if (arg[i] == 'a')
         {
              if (! IsModifed)
              {
                // Allocate new ram, copy data and
                // force a new descriptor to be created
                arg = arg.dup;

                IsModified = true;
              }
              arg[i] = 'A';
         }
      }
      return arg;
   }

(Yes this is just an example and not very efficient, okay!)
Note that there is a simpler way to avoid this effect with out doing CoW  
semantics but at the cost of copying data.

    Result = foo(String).dup;

But if you want the 'foo' function to be able to change either the length  
of the array then you need to pass the array with the 'inout' qualifier.  
In that case the address of the array descriptor is passed and D will work  
with it indirectly.

So in summary, passing D arrays can be very quick and does not always  
involve data copying.

-- 
Derek Parnell
Melbourne, Australia
Jun 07 2006
parent reply Henrik Eneroth <Henrik_member pathlink.com> writes:
Many thanks for the very thorough explanation(s). As usual, D seems to exceed my
expectations. This will be easier than I thought.

On a side note, I realised that using the += operator with a dynamic array
length property didn't work. I guess the (a = a + 1) <=> (a += 1) rationale
doesn't work on arrays (since b.length = b.length + 1 does indeed work, whereas
b.length += 1 does not). Wouldn't that be neat though?

Regards,

Henrik
Jun 08 2006
next sibling parent Derek Parnell <derek psych.ward> writes:
On Thu, 8 Jun 2006 07:11:25 +0000 (UTC), Henrik Eneroth wrote:



 On a side note, I realised that using the += operator with a dynamic array
 length property didn't work. I guess the (a = a + 1) <=> (a += 1) rationale
 doesn't work on arrays (since b.length = b.length + 1 does indeed work, whereas
 b.length += 1 does not). Wouldn't that be neat though?


Yes.

I believe that to do so would add a measure of complexity to the compiler
and Walter does not want to tackle this issue just yet. But maybe for a
v2.0 release ;-)

-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
"Down with mediocrity!"
8/06/2006 5:15:19 PM
Jun 08 2006
prev sibling parent reply Deewiant <deewiant.doesnotlike.spam gmail.com> writes:
Henrik Eneroth wrote:

 On a side note, I realised that using the += operator with a dynamic array
 length property didn't work. I guess the (a = a + 1) <=> (a += 1) rationale
 doesn't work on arrays (since b.length = b.length + 1 does indeed work, whereas
 b.length += 1 does not). Wouldn't that be neat though?
 


It's not about arrays, it's about properties in general.

See, in D, a function call f(x) can also be written f = x. So "array.length =
array.length + 1" is actually equivalent to "array.length(array.length + 1)":
length is just a function. "array.length += 1" is like writing "array.length()
+= 1" which doesn't make sense to the compiler, since you can't add a value to a
function.

This syntax makes it easier to write and use properties without needing special
get/set syntax for them, but it does have the drawback of not being able to use
the rest of the assign operators.

Plus, it allows you to write some pretty strange-looking stuff, like:

writefln = "foo bar";
writefln = (toString = 42);

Fortunately, unless obfuscating on purpose, people realise to avoid writing such
code. ;-)
Jun 08 2006
parent Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
Deewiant wrote:

 
 Plus, it allows you to write some pretty strange-looking stuff, like:
 
 writefln = "foo bar";
 writefln = (toString = 42);
 
 Fortunately, unless obfuscating on purpose, people realise to avoid writing
such
 code. ;-)


Whoa, never thought about this, it's quite nasty indeed. (maybe 
something that could be improved with other getter/setter language 
semantics)

-- 
Bruno Medeiros - CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Jun 12 2006