www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - runtime static arrays

reply "Namespace" <rswhite4 googlemail.com> writes:
Is there any need for 'smart' or 'compressed' arrays?

In my last projects I had some situations where I need an array, 
but only for one scope. But I could not use static arrays, 
because I didn't know the size at compile time. So I used 
'alloca'. But 'alloca' has a terrible interface and in some few 
cases I had to append x elements. So I used a dynamic array. But 
dynamic arrays live longer as the lifetime of the scope. 
Furthermore dynamic arrays costs more memory as I needed, because 
the capacity of them is n * 2 + 1, but in my cases I need only n.
So what I need was an array, which lives only for one scope 
(freed memory after leaving scope) and which hasn't more 
elements/capacity as I need.

Am I wrong and dynamic arrays are the solution? Or is there need 
for such 'compressed' arrays?
Another solution would be to improve the interface of alloca, but 
it would be still not resizable.
Nov 20 2012
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Namespace:


 Furthermore dynamic arrays costs more memory as I needed,


But maybe this doesn't happen in your case.



 Am I wrong and dynamic arrays are the solution?


Take also a look at the Array of Phobos.

Bye,
bearophile
Nov 20 2012
prev sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 11/20/2012 06:25 AM, Namespace wrote:

 Is there any need for 'smart' or 'compressed' arrays?

 In my last projects I had some situations where I need an array, but
 only for one scope. But I could not use static arrays, because I didn't
 know the size at compile time. So I used 'alloca'. But 'alloca' has a
 terrible interface and in some few cases I had to append x elements. So
 I used a dynamic array. But dynamic arrays live longer as the lifetime
 of the scope. Furthermore dynamic arrays costs more memory as I needed,
 because the capacity of them is n * 2 + 1, but in my cases I need only n.
 So what I need was an array, which lives only for one scope (freed
 memory after leaving scope) and which hasn't more elements/capacity as I
 need.

 Am I wrong and dynamic arrays are the solution? Or is there need for
 such 'compressed' arrays?
 Another solution would be to improve the interface of alloca, but it
 would be still not resizable.


The following program makes a slice from GC-allocated memory (or a 
fixed-size array as in the comment). The important part is 'buffer[0..10]'.

import std.stdio;
import core.memory;

void bar(int[] a)  // Also try: int[10] a
{
     writeln("param : ", a.ptr);
}

void foo()
{
     int *buffer = cast(int*)GC.calloc(int.sizeof * 10);
     scope (exit) GC.free(buffer);

     writeln("buffer: ", buffer);

     int[] a = buffer[0..10];  // Also try: int[10] a =

     writeln("a     : ", a.ptr);

     foreach (i; a) {
         i = 42 + i;
     }

     bar(a);
}

void main()
{
     foo();
}

Ali
Nov 20 2012
parent reply "Namespace" <rswhite4 googlemail.com> writes:
Yes, but I could also use alloca. What I mean is the shortness of 
int[4] arr or
for (int i = 0; i < 42; i += 4) {
     int[i] arr;
}

I take a look at the std.container Array.
Nov 20 2012
parent reply "Namespace" <rswhite4 googlemail.com> writes:
Something like:
scope int[8] arr;
or
scope int[i] arr;

would be cool. You get an resizeable array which capactiy is all 
the time equal to his length. And it is destroyed after the 
liftetime of the scope.

Maybe some stuff for Remus...
Nov 20 2012
next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 11/20/2012 02:46 PM, Namespace wrote:

 Something like:
 scope int[8] arr;
 or
 scope int[i] arr;

 would be cool. You get an resizeable array which capactiy is all the
 time equal to his length. And it is destroyed after the liftetime of the
 scope.

 Maybe some stuff for Remus...


This is a surprisingly promising start: :)

import std.stdio;

struct FixedArray(T, size_t N)
{
     T[N] elements;
     alias elements this;
}

void main()
{
     FixedArray!(int, 10) a;

     foreach (int i, ref e; a) {
         e = 42 + i;
     }

     writeln(a);
}

Ali
Nov 20 2012
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, November 20, 2012 14:52:56 Ali =C3=87ehreli wrote:

 On 11/20/2012 02:46 PM, Namespace wrote:

 Something like:
 scope int[8] arr;
 or
 scope int[i] arr;
=20
 would be cool. You get an resizeable array which capactiy is all th=




e

 time equal to his length. And it is destroyed after the liftetime o=




f the

 scope.
=20
 Maybe some stuff for Remus...


=20
 This is a surprisingly promising start: :)
=20
 import std.stdio;
=20
 struct FixedArray(T, size_t N)
 {
      T[N] elements;
      alias elements this;
 }
=20
 void main()
 {
      FixedArray!(int, 10) a;
=20
      foreach (int i, ref e; a) {
          e =3D 42 + i;
      }
=20
      writeln(a);
 }


How is that any different from just using a static array? All you've do=
ne is=20
wrap it. You still can't set its size at runtime. Isn't what the OP is=20=

essentially looking for is a static array whose length can be set at ru=
ntime?=20
This doesn't solve that. For that, you need something which is going to=
=20
allocate on the heap at runtime but deterministically free that that me=
mory=20
when it's done.

- Jonathan M Davis
Nov 20 2012
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 11/20/2012 02:59 PM, Jonathan M Davis wrote:

 On Tuesday, November 20, 2012 14:52:56 Ali Çehreli wrote:



 This is a surprisingly promising start: :)





 How is that any different from just using a static array?


I know, I know... That surprising start surprised me too. :p

Ali
Nov 20 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Namespace:


 scope int[8] arr;
 or
 scope int[i] arr;


See also:
http://d.puremagic.com/issues/show_bug.cgi?id=5348

Bye,
bearophile
Nov 20 2012
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, November 20, 2012 23:46:39 Namespace wrote:

 Something like:
 scope int[8] arr;
 or
 scope int[i] arr;
 
 would be cool. You get an resizeable array which capactiy is all
 the time equal to his length. And it is destroyed after the
 liftetime of the scope.
 
 Maybe some stuff for Remus...


It's pretty trivial to create a struct which uses malloc and free to create a 
dynamic array of the exact size that you want with deterministic destruction, 
and you can easily overload the indexing and slicing operators - though 
clearly, as if with static arrays, you'd have to be careful with slices being 
passed around, since they're not owned by the GC. And I'm not sure what would 
happen if you were foolish enough to try and append to them.

Personally though, I wish that the length of static arrays could be set at 
runtime and don't really understand why you can't (aside from the fact that 
you can't in standard C - gcc will let you though).

- Jonathan M Davis
Nov 20 2012
next sibling parent reply "Namespace" <rswhite4 googlemail.com> writes:
 It's pretty trivial to create a struct which uses malloc and 
 free to create a
 dynamic array of the exact size that you want with 
 deterministic destruction,
 and you can easily overload the indexing and slicing operators 
 - though
 clearly, as if with static arrays, you'd have to be careful 
 with slices being
 passed around, since they're not owned by the GC. And I'm not 
 sure what would
 happen if you were foolish enough to try and append to them.

 Personally though, I wish that the length of static arrays 
 could be set at
 runtime and don't really understand why you can't (aside from 
 the fact that
 you can't in standard C - gcc will let you though).

 - Jonathan M Davis


Yeah, but it's inconvenient to use a struct instead of a built in 
solution. ;)
Nov 20 2012
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, November 21, 2012 00:30:16 Namespace wrote:

 Yeah, but it's inconvenient to use a struct instead of a built in
 solution. ;)


But if the built-in solution doesn't do what you want, then that's what you 
have to do. And the only built-in solutions are to either have a static array 
where you know its length at compile time or to use dynamic arrays, whose 
memory would be managed by the GC and which would allocate extra memory beyond 
the end of the array in order to make appending efficient. If either of those 
are fine, then there you go. But if they're not fine, then you need to find 
another solution. std.container.Array is closer to what you seem to want, but 
it would also allocate extra memory (it should have deterministic destruction 
though, since it uses malloc and free internally). To do exactly what you want 
would require creating your own type.

- Jonathan M Davis
Nov 20 2012
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Jonathan M Davis:


 Personally though, I wish that the length of static arrays 
 could be set at
 runtime and don't really understand why you can't (aside from 
 the fact that
 you can't in standard C - gcc will let you though).


Variable Length Arrays are part of the standard in C since C99, 
and they are in C11 still.

D doesn't have VLAs, I have asked for them since lot of time. I 
don't know why Walter doesn't like them. After using Ada language 
a little, I believe that stack allocation is very useful when you 
want to write fast code.

VLAs are a little unsafe in D because they are not on the heap, 
but a good type system is able to make them safe (some kind of 
static region analysis, done by the Rust language compiler, not 
present in D).

Beside the problem of memory ownership, and problems with stack 
overflows, there are other problems with VLAs, like how the D 
type system has to denote them, and how to move them around. How 
do you return them? Some considerations:


void foo(int n) {
     int[](n) data; // D VLA syntax?
     static assert(sizeof(data) = sizeof(size_t)); // 1 word?
     static assert(is(typeof(data) == int()));
     bar(data); // OK, decays to dynamic array
     bar(data.dup); // OK, dup turns it on a heap allocated 
dynamic array
     spam(data); // probably not allowed.
}
void bar(int[] a) {}
void spam(int[10] b) {}
void baz(int() c) {} // not allowed syntax.


Here I have used a different syntax because I think there is a 
problem with using the normal syntax: D performs CTFE when you 
call a function in a context that asks for a compile-time result 
value. Currently static array definitions require a compile-time 
value, so they induce CTFE. If D gains VLAs stack arrays can be 
created with a run-time size too, so how does the compiler knows 
if you want CTFE and to create a fixed array or you want to call 
the function at runtime and create a VLA? A different syntax 
avoids this problem.

VLAs are meant only for automatic variables, you can't put one of 
them in structs or class instances, or in global scope. Also a 
VLA decades in a dynamic array with dup or to fixed size whem 
given to a function with fixed sized argument, so you can't pass 
VLA around.

One advantage of VLA is a less bug-prone syntax compared to 
alloca(), expecially when you want 2D, 3D, etc VLA array.

C++11 has not introduced VLA for unclear reasons, but probably 
one reason was to not add more complexities. In the D type system 
there are dynamic arrays, so the situation is better.

Maybe some kind of VLAs will be present in C++14, according to 
what the C++ committee says.

Bye,
bearophile
Nov 20 2012
parent reply "Namespace" <rswhite4 googlemail.com> writes:
Is there an official statement why Walter dislike them?
Nov 20 2012
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Namespace:


 Is there an official statement why Walter dislike them?


In the last years I remember no comments from him about this 
topic. But he has not closed my enhancement request.

Bye,
bearophile
Nov 20 2012
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, November 21, 2012 02:26:35 bearophile wrote:

 Namespace:

 Is there an official statement why Walter dislike them?


 
 In the last years I remember no comments from him about this
 topic. But he has not closed my enhancement request.


One serious problem posed by them is that the size then can't be part of the 
type, meaning that you can't possibly pass them around. If you did, you'd just 
be passing dynamic arrays around. You'd have the same problem with them with 
templates - everything instantiated with them would have to be instantiated as 
a dynamic array, which could cause problems.

So, while in principle, I like the idea of being able to have the size of a 
static array determined when it's created, there are definitely problems with 
doing that once you start getting into the details of what that would mean.

- Jonathan M Davis
Nov 20 2012
parent "bearophile" <bearophileHUGS lycos.com> writes:
Jonathan M Davis:


 One serious problem posed by them is that the size then can't 
 be part of the
 type, meaning that you can't possibly pass them around. If you 
 did, you'd just
 be passing dynamic arrays around.


Take a look at my code, few posts above. When a VLA is passed to 
a function, it "decays" to a dynamic array.



 You'd have the same problem with them with
 templates - everything instantiated with them would have to be 
 instantiated as
 a dynamic array, which could cause problems.


Templates will support arrays, they already do partially.

Kind of arrays and templates are two orthogonal things. What 
matters for templates is the a value is known at compile time or 
not. So I think this is not a problem.



 there are definitely problems with
 doing that once you start getting into the details of what that 
 would mean.


I agree there are some problems. But I think they aren't hard 
problems to solve.

Bye,
bearophile
Nov 20 2012
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 11/20/2012 11:56 PM, Jonathan M Davis wrote:

 ...
 clearly, as if with static arrays, you'd have to be careful with slices being
 passed around, since they're not owned by the GC. And I'm not sure what would
 happen if you were foolish enough to try and append to them.
 ...


It works as expected. A new GC-managed slice is created.
Nov 21 2012