www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - new T[size] vs .reserve

reply "Namespace" <rswhite4 googlemail.com> writes:
Currently something like new ubyte[4]; reserves space for _at 
least_ 4 items.
But if I want to store now something, the index isn't 0, it's 4.
Let me explain that on a brief example:

[code]
import std.stdio;

void main() {
	ubyte[] arr = new ubyte[4];
	arr ~= 4; // desirable: [4, 0, 0, 0];
	writeln(arr); // prints: [0, 0, 0, 0, 4]
	
	ubyte[] arr2;
	arr2.reserve(4);
	arr2 ~= 4; // expect: [4, 0, 0, 0];
	writeln(arr2); // prints: [4] just as well
}
[/code]

So is there any reason why this behaviour is like it is?

As I looked at arr.length and arr.capacity for the first time I 
was schocked: I want only space for 4 items, but I got space for 
15.
I read in the docs that .reserve extends the space to at least 
SIZE items, but maybe more. But at that time and still yet I 
found nothing about new ubyte[SIZE]. So I ask:
wouldn't it be better, if new ubyte[4] reserves only space for 4 
items and reallocs only if I append more than 4?
Feb 02 2013
next sibling parent reply "Maxim Fomin" <maxim maxim-fomin.ru> writes:
On Saturday, 2 February 2013 at 16:36:29 UTC, Namespace wrote:

 Currently something like new ubyte[4]; reserves space for _at 
 least_ 4 items.
 But if I want to store now something, the index isn't 0, it's 4.
 Let me explain that on a brief example:

 [code]
 import std.stdio;

 void main() {
 	ubyte[] arr = new ubyte[4];


You asked for array with four zeros (T.init for ubyte is 0).


 	arr ~= 4; // desirable: [4, 0, 0, 0];
 	writeln(arr); // prints: [0, 0, 0, 0, 4]


You got it. And you appended 4 to them, so you got proper result.
  	

 	ubyte[] arr2;


You asked for empty array.


 	arr2.reserve(4);
 	arr2 ~= 4; // expect: [4, 0, 0, 0];
 	writeln(arr2); // prints: [4] just as well
 }


You appended 4 to empty array and you got [4]. By the way, note 
that the output is not [4,0,0,0] it is [4] since no one has 
pushed three zeros there.


 [/code]

 So is there any reason why this behaviour is like it is?


I found it is consistent and complying yo spec. new ubyte[4] and 
reverse(4) do different things.


 As I looked at arr.length and arr.capacity for the first time I 
 was schocked: I want only space for 4 items, but I got space 
 for 15.
 I read in the docs that .reserve extends the space to at least 
 SIZE items, but maybe more. But at that time and still yet I 
 found nothing about new ubyte[SIZE]. So I ask:
 wouldn't it be better, if new ubyte[4] reserves only space for 
 4 items and reallocs only if I append more than 4?


Since you have two tools which do different things, you can 
select that tool which does what you wanted. What's the problem 
here?
Feb 02 2013
parent reply "Namespace" <rswhite4 googlemail.com> writes:
No one said that this is a problem, or? (;
But why should I generate an array with size 4 if an append of me 
resize it to 5?

I'm asking because we have currently nothing (nice) for _fixed_ 
size arrays at runtime. That should be change. Therefore new 
T[size] would be a good.
Feb 02 2013
parent David <d dav1d.de> writes:
Am 02.02.2013 18:40, schrieb Namespace:

 No one said that this is a problem, or? (;
 But why should I generate an array with size 4 if an append of me resize
 it to 5?


That's what reserve is for.

auto bla = new ubate[4];
bla[3] = 1; // valid


ubyte[] bla;
bla.reserve(4);
bla[3] = 1; // invalid
Feb 03 2013
prev sibling next sibling parent reply FG <home fgda.pl> writes:
On 2013-02-02 17:36, Namespace wrote:

      ubyte[] arr = new ubyte[4];
      arr ~= 4; // desirable: [4, 0, 0, 0];


Why not arr[0] = 4? What is so special about having 4 elements?


 As I looked at arr.length and arr.capacity for the first time I was schocked: I
 want only space for 4 items, but I got space for 15.


I think you are out of luck with built-in dynamic arrays.
It seems that even for an array of length 1 it gives a minimum of 15 bytes
storage, so you can fit 15 bytes, 7 shorts, 3 ints, 1 long.
I'm not sure why is it 15, given alignment an all...
Feb 02 2013
parent reply "Namespace" <rswhite4 googlemail.com> writes:
On Saturday, 2 February 2013 at 17:48:14 UTC, FG wrote:

 On 2013-02-02 17:36, Namespace wrote:

     ubyte[] arr = new ubyte[4];
     arr ~= 4; // desirable: [4, 0, 0, 0];


 Why not arr[0] = 4? What is so special about having 4 elements?


Example:

struct Color {
public:
     ubyte[4] colors;
}

ubyte[] data = new ubyte[color_data.length * 4]; // enough storage
foreach (ref const Color col; color_data) {
     data ~= col.colors;
}

Currently impossible, even with self indexing absolute annoying 
and unnecessary complicated.
Sure you could do the same with .reserve but the point is that 
you does not want more storage than color_data.length * 4.
Currently I use my own struct which reserve only 
color_data.length * 4 memory and let the index at beginning to 0.
But I'm using D because it is nice and simple, so why I should 
create my own data structure, and use ugly malloc, realloc and 
free, for such needed thing if the language could and should do 
that for you?
Feb 02 2013
parent reply FG <home fgda.pl> writes:
On 2013-02-02 19:01, Namespace wrote:

 Example:

 struct Color {
 public:
      ubyte[4] colors;
 }

 ubyte[] data = new ubyte[color_data.length * 4]; // enough storage
 foreach (ref const Color col; color_data) {
      data ~= col.colors;
 }


Sorry, but what is the point of data having only 4 bytes reserved
at the beginning? What is wrong with this:

     ubyte[] data;
     data.reserve(color_data.length * 4);
     foreach (ref const Color col; color_data)
         data ~= col.colors;

Are you uncomfortable, because it may allocate twice as much space
as you need (for bigger color_data)?
Feb 02 2013
parent reply "Namespace" <rswhite4 googlemail.com> writes:
 Are you uncomfortable, because it may allocate twice as much 
 space
 as you need (for bigger color_data)?


Yes, that's the point.
Sorry, I cannot express myself very well in English.
Feb 02 2013
next sibling parent reply FG <home fgda.pl> writes:
On 2013-02-02 19:53, Namespace wrote:

 Are you uncomfortable, because it may allocate twice as much space
 as you need (for bigger color_data)?


 Yes, that's the point.
 Sorry, I cannot express myself very well in English.


You're right. It's surprising for anyone used to dealing with std::vector,
that it actually reserves more than you specify.

Another odd thing - when pushing back to a vector its capacity grows:
1, 2, 4, 8, 16, 32 ..., but with D arrays it's like 7, 15, 31, 63...
Why 2**n - 1? What secret data is hidden after the block? ;)
Feb 02 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Saturday, 2 February 2013 at 19:49:39 UTC, FG wrote:

 On 2013-02-02 19:53, Namespace wrote:

 Are you uncomfortable, because it may allocate twice as much 
 space
 as you need (for bigger color_data)?


 Yes, that's the point.
 Sorry, I cannot express myself very well in English.


 You're right. It's surprising for anyone used to dealing with 
 std::vector,
 that it actually reserves more than you specify.


FYI: std::vector will do exactly the same thing. The actual grow 
scheme may be different, but that is purelly an implementation 
detail.

Another thing to take into account: In C++, if you request 10 
bytes of allocation space, but the underlying implementation 
actually allocates a 32 byte block, you'll know nothing of it. If 
later, you want to grow those 10 bytes to 20 bytes, you'll have 
to request a new allocation.

std::vector has actually no idea how much space actually gets 
allocated. It requests a certain amount but has no idea how much 
it really gets. At best, it can tell you how much it requested.

In D, you can exploit the last drop of allocation space actually 
allocated. It is the underlying array itself that tells you how 
much space there is left.


 Another odd thing - when pushing back to a vector its capacity 
 grows:
 1, 2, 4, 8, 16, 32 ..., but with D arrays it's like 7, 15, 31, 
 63...
 Why 2**n - 1? What secret data is hidden after the block? ;)


The currently used size.

In C++, set::vector is a struct that has a "size" member, and a 
pointer to a payload. In D, the "size" data is embedded straight 
into the payload. Kind of like how std::string is implemented 
actually.

This has a two-fold advantage: The actual slice object is light 
(just a fat pointer). Also, when you have two (or more) slices 
that reference the same data, they *know* if or if not they can 
safelly append, without cloberring the data of another slice.

I suggest you read this:
http://dlang.org/d-array-article.html
It is a very interesting read, especially for those of us with 
C++ background.

One very (very) important thing to realize is that std::vector is 
a container. D slices are not containers: they are ranges. They 
iterate on an underlying array object, but they are not 
containers themselves.

The underlying object, the so called "dynamic array" is actually 
a obscure and hidden object you cannot access dirrectly.

There is some ambiguity between both terms, and they are often 
used interchangedbly, but to really understand what is going on, 
you need to imagine them as two different objects interacting.
Feb 02 2013
parent FG <home fgda.pl> writes:
On 2013-02-02 22:47, monarch_dodra wrote:

 I suggest you read this:
 http://dlang.org/d-array-article.html
 It is a very interesting read, especially for those of us with C++ background.


Thank you for pointing me to that article.
I have read it months ago and forgotten the important parts.
Now it (slices & arrays) finally started making sense again. :)
Feb 02 2013
prev sibling parent reply "Namespace" <rswhite4 googlemail.com> writes:
My real question was: will we ever have fixed size arrays at 
runtime?
Feb 02 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Saturday, 2 February 2013 at 22:15:56 UTC, Namespace wrote:

 My real question was: will we ever have fixed size arrays at 
 runtime?


I see no reason why we couldn't, the only problem is a syntax 
one. If you beat the syntax (by wrapping it in a struct) then you 
can do it no problem:

//----
T[N]* makeFixed(size_t N, T)()
{
     static struct Fixed
     {
         T[N] a;
     }
     auto p = new Fixed();
     return &((*p).a);
}

void main()
{
    int[4]* p4 = makeFixed!(4, int)();
}
//----

And there, a dynamically allocated fixed size array. I know it's 
not pretty, but it proves the point.
Feb 02 2013
parent reply "Namespace" <rswhite4 googlemail.com> writes:
On Saturday, 2 February 2013 at 22:39:58 UTC, monarch_dodra wrote:

 On Saturday, 2 February 2013 at 22:15:56 UTC, Namespace wrote:

 My real question was: will we ever have fixed size arrays at 
 runtime?


 I see no reason why we couldn't, the only problem is a syntax 
 one. If you beat the syntax (by wrapping it in a struct) then 
 you can do it no problem:

 //----
 T[N]* makeFixed(size_t N, T)()
 {
     static struct Fixed
     {
         T[N] a;
     }
     auto p = new Fixed();
     return &((*p).a);
 }

 void main()
 {
    int[4]* p4 = makeFixed!(4, int)();
 }
 //----

 And there, a dynamically allocated fixed size array. I know 
 it's not pretty, but it proves the point.


Sure and as I said: something like that I'm using currently. It 
is very ugly and because of that I asked for a built in solution, 
like new ubyte[size].
C have also runtime fixed size arrays.
But as far as I can see all your are fine with the wrapped struct 
solution.
Feb 02 2013
next sibling parent "Namespace" <rswhite4 googlemail.com> writes:
 But as far as I can see all your are fine with the wrapped 
 struct solution.


->
But as far as I can see, all of you are happy with the current 
wrapped struct solution.
----
We need an 'edit' button.
Feb 02 2013
prev sibling next sibling parent "Mike Parker" <aldacron gmail.com> writes:
On Sunday, 3 February 2013 at 00:34:48 UTC, Namespace wrote:


 C have also runtime fixed size arrays.


They were added in C99 (variable length arrays, they're called). 
C++, on the other hand, still doesn't have them.
Feb 02 2013
prev sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Sunday, 3 February 2013 at 00:34:48 UTC, Namespace wrote:

 On Saturday, 2 February 2013 at 22:39:58 UTC, monarch_dodra 
 wrote:

 On Saturday, 2 February 2013 at 22:15:56 UTC, Namespace wrote:

 My real question was: will we ever have fixed size arrays at 
 runtime?


 I see no reason why we couldn't, the only problem is a syntax 
 one. If you beat the syntax (by wrapping it in a struct) then 
 you can do it no problem:

 //----
 T[N]* makeFixed(size_t N, T)()
 {
    static struct Fixed
    {
        T[N] a;
    }
    auto p = new Fixed();
    return &((*p).a);
 }

 void main()
 {
   int[4]* p4 = makeFixed!(4, int)();
 }
 //----

 And there, a dynamically allocated fixed size array. I know 
 it's not pretty, but it proves the point.


 Sure and as I said: something like that I'm using currently. It 
 is very ugly and because of that I asked for a built in 
 solution, like new ubyte[size].
 [SNIP]
 But as far as I can see all your are fine with the wrapped 
 struct solution.


I never said I was happy with this solution! The problem is that 
the old "new int[4]" syntax is already taken and means "allocate 
a dynamic array of size 4".


 C have also runtime fixed size arrays.


C has "variable length arrays". That's not exactly the same same 
thing as allocating a fixed size array at runtime (apologies if I 
was confused by your requirement).

If you want variable length arrays, you should be able to do it 
with the low level "alloca".
Feb 03 2013
parent reply "Namespace" <rswhite4 googlemail.com> writes:
Sure, but alloca has the same ugly interface as malloc. :/
Feb 03 2013
parent reply "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Sunday, 3 February 2013 at 09:11:59 UTC, Namespace wrote:

 Sure, but alloca has the same ugly interface as malloc. :/


  You mean that you have to specify how many raw bytes you want, 
then cast it to what you need? I never thought alloca or malloc 
were that ugly.
Feb 03 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Era Scarecrow:


 On Sunday, 3 February 2013 at 09:11:59 UTC, Namespace wrote:

 Sure, but alloca has the same ugly interface as malloc. :/


  You mean that you have to specify how many raw bytes you want, 
 then cast it to what you need? I never thought alloca or malloc 
 were that ugly.


The interface of alloca() is bug-prone. And it's not handy if you 
want to create a 2D or nD array on the stack :-) In bugzilla 
there is a preliminary request for better and less bug-prone VLAs 
for D.

Bye,
bearophile
Feb 03 2013
next sibling parent reply "Namespace" <rswhite4 googlemail.com> writes:
 In bugzilla there is a preliminary request for better and less 
 bug-prone VLAs for D.

 Bye,
 bearophile


Can you link it here?
Feb 03 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
Namespace:


 In bugzilla there is a preliminary request for better and less 
 bug-prone VLAs for D.
 ...


 Can you link it here?


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

Bye,
bearophile
Feb 03 2013
prev sibling next sibling parent reply "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Sunday, 3 February 2013 at 13:22:53 UTC, bearophile wrote:

 The interface of alloca() is bug-prone. And it's not handy if 
 you want to create a 2D or nD array on the stack :-) In 
 bugzilla there is a preliminary request for better and less 
 bug-prone VLAs for D.


  Maybe. I barely have ever used alloca myself, but glancing over 
the VLA's it seems iffy. If there's just one it's easy to 
implement, however if there's several then the data would point 
to a slice on the stack. I can see how it works in my head, but 
with dynamic arrays, malloc & scope you can get a similar affect. 
Hmmm... Maybe a possible use for a template instead?
Feb 03 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
Era Scarecrow:


 I barely have ever used alloca myself,


I have used alloca less than 10 times in D with DMD, but the 
performance improvement was well visible.



 Maybe a possible use for a template instead?


I don't know.

Bye,
bearophile
Feb 03 2013
prev sibling parent reply Nick Treleaven <ntrel-public yahoo.co.uk> writes:
On 03/02/2013 13:22, bearophile wrote:

 Era Scarecrow:


 On Sunday, 3 February 2013 at 09:11:59 UTC, Namespace wrote:

 Sure, but alloca has the same ugly interface as malloc. :/


  You mean that you have to specify how many raw bytes you want, then
 cast it to what you need? I never thought alloca or malloc were that
 ugly.


 The interface of alloca() is bug-prone. And it's not handy if you want
 to create a 2D or nD array on the stack :-) In bugzilla there is a
 preliminary request for better and less bug-prone VLAs for D.


^ I know you're aware of this, but maybe others might not know the 
default-argument alloca wrapping trick:

import std.stdio;
import core.stdc.stdlib:alloca;

T *stack(T)(void* m = alloca(T.sizeof))
{
     return cast(T*)m;
}

void main(string[] args)
{
     auto i = stack!int();
     *i = 5;
     writeln(*i);
     writeln(i);
     int j;
     writeln(&j);
}

More advanced behaviour e.g. switching to heap allocation for large 
sizes of T may be possible.
Feb 05 2013
next sibling parent reply Nick Treleaven <ntrel-public yahoo.co.uk> writes:
On 05/02/2013 16:17, Nick Treleaven wrote:

 On 03/02/2013 13:22, bearophile wrote:

 Era Scarecrow:


 On Sunday, 3 February 2013 at 09:11:59 UTC, Namespace wrote:

 Sure, but alloca has the same ugly interface as malloc. :/


  You mean that you have to specify how many raw bytes you want, then
 cast it to what you need? I never thought alloca or malloc were that
 ugly.


 The interface of alloca() is bug-prone. And it's not handy if you want
 to create a 2D or nD array on the stack :-) In bugzilla there is a
 preliminary request for better and less bug-prone VLAs for D.


 ^ I know you're aware of this, but maybe others might not know the
 default-argument alloca wrapping trick:


I've just realized this doesn't work for variable-length allocation:

T[] stack(T)(size_t N, void* m = alloca(T.sizeof * N))

Error: undefined identifier N, did you mean alias T?

N is not visible in the caller's scope.
Feb 05 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 5 February 2013 at 16:37:41 UTC, Nick Treleaven wrote:

 On 05/02/2013 16:17, Nick Treleaven wrote:

 On 03/02/2013 13:22, bearophile wrote:

 Era Scarecrow:


 On Sunday, 3 February 2013 at 09:11:59 UTC, Namespace wrote:

 Sure, but alloca has the same ugly interface as malloc. :/


 You mean that you have to specify how many raw bytes you 
 want, then
 cast it to what you need? I never thought alloca or malloc 
 were that
 ugly.


 The interface of alloca() is bug-prone. And it's not handy if 
 you want
 to create a 2D or nD array on the stack :-) In bugzilla there 
 is a
 preliminary request for better and less bug-prone VLAs for D.


 ^ I know you're aware of this, but maybe others might not know 
 the
 default-argument alloca wrapping trick:


 I've just realized this doesn't work for variable-length 
 allocation:

 T[] stack(T)(size_t N, void* m = alloca(T.sizeof * N))

 Error: undefined identifier N, did you mean alias T?

 N is not visible in the caller's scope.


It does, just alias it.

//----
import std.stdio;
import core.stdc.stdlib:alloca;

T* stack(T)(void* m = alloca(T.sizeof))
{
     return cast(T*)m;
}
T[] stack(T, alias N)(void* m = alloca(T.sizeof * N))
{
     return (cast(T*)m)[0 .. N];
}

void main(string[] args)
{
     int*  p   = stack!int();
     int[] arr = stack!(int, 5)();
     *p = 2;
     arr[0] = 5;
     writeln(*p);
     writeln(arr);
}
//----
Feb 05 2013
next sibling parent "Namespace" <rswhite4 googlemail.com> writes:
Why not:
[code]
T[] stack(T, const size_t N)(void* m = alloca(T.sizeof * N))
{
     return (cast(T*)m)[0 .. N];
}
[/code]
?
Feb 05 2013
prev sibling parent reply Nick Treleaven <ntrel-public yahoo.co.uk> writes:
On 05/02/2013 16:47, monarch_dodra wrote:

 On Tuesday, 5 February 2013 at 16:37:41 UTC, Nick Treleaven wrote:

 I've just realized this doesn't work for variable-length allocation:

 T[] stack(T)(size_t N, void* m = alloca(T.sizeof * N))

 Error: undefined identifier N, did you mean alias T?

 N is not visible in the caller's scope.


 It does, just alias it.

 //----
 import std.stdio;
 import core.stdc.stdlib:alloca;

 T* stack(T)(void* m = alloca(T.sizeof))
 {
      return cast(T*)m;
 }
 T[] stack(T, alias N)(void* m = alloca(T.sizeof * N))
 {
      return (cast(T*)m)[0 .. N];
 }


This works if you know N at compile-time. But there doesn't seem to be a 
way to wrap alloca to accept a runtime-only value, e.g.:

// allocate as many ints as command-line parameters
int[] arr = stack!int(args.length);
Feb 05 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 5 February 2013 at 20:47:46 UTC, Nick Treleaven wrote:

 On 05/02/2013 16:47, monarch_dodra wrote:

 On Tuesday, 5 February 2013 at 16:37:41 UTC, Nick Treleaven 
 wrote:

 I've just realized this doesn't work for variable-length 
 allocation:

 T[] stack(T)(size_t N, void* m = alloca(T.sizeof * N))

 Error: undefined identifier N, did you mean alias T?

 N is not visible in the caller's scope.


 It does, just alias it.

 //----
 import std.stdio;
 import core.stdc.stdlib:alloca;

 T* stack(T)(void* m = alloca(T.sizeof))
 {
     return cast(T*)m;
 }
 T[] stack(T, alias N)(void* m = alloca(T.sizeof * N))
 {
     return (cast(T*)m)[0 .. N];
 }


 This works if you know N at compile-time. But there doesn't 
 seem to be a way to wrap alloca to accept a runtime-only value, 
 e.g.:

 // allocate as many ints as command-line parameters
 int[] arr = stack!int(args.length);


I don't have access to my compiler, but that *should*work. Did 
you try it? BTW, the syntax would be:

int[] arr = stack!(int, args.length)();
Feb 05 2013
parent reply Nick Treleaven <ntrel-public yahoo.co.uk> writes:
On 05/02/2013 21:02, monarch_dodra wrote:

 On Tuesday, 5 February 2013 at 20:47:46 UTC, Nick Treleaven wrote:

 On 05/02/2013 16:47, monarch_dodra wrote:

 T[] stack(T, alias N)(void* m = alloca(T.sizeof * N))
 {
     return (cast(T*)m)[0 .. N];
 }


 This works if you know N at compile-time. But there doesn't seem to be
 a way to wrap alloca to accept a runtime-only value, e.g.:

 // allocate as many ints as command-line parameters
 int[] arr = stack!int(args.length);


 I don't have access to my compiler, but that *should*work. Did you try
 it? BTW, the syntax would be:

 int[] arr = stack!(int, args.length)();


I've just tried it with dmd 2.059 (haven't upgraded yet). I got:

Error: variable args cannot be read at compile time

void main(string[] args)
{
     int[] arr = stack!(int, args.length)();
}
Feb 05 2013
parent reply Nick Treleaven <ntrel-public yahoo.co.uk> writes:
On 05/02/2013 21:13, Nick Treleaven wrote:

 I've just tried it with dmd 2.059 (haven't upgraded yet)


sorry, 2.060
Feb 05 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 5 February 2013 at 21:14:32 UTC, Nick Treleaven wrote:

 On 05/02/2013 21:13, Nick Treleaven wrote:

 I've just tried it with dmd 2.059 (haven't upgraded yet)


 sorry, 2.060


Right, it's "alias" being finicky, because "args.length" isn't an 
actual variable (it's a property). The problem is not so much 
that it can't be "read" at compile time, that the compiler 
doesn't know what to alias to.

I'll file a bug report to try and see if we can't get a better 
message.

Use a named variable, or use a manifest constant:

//----
import std.stdio;
import core.stdc.stdlib:alloca;

T* stack(T)(void* m = alloca(T.sizeof))
{
     return cast(T*)m;
}
T[] stack(T, alias N)(void* m = alloca(T.sizeof * N))
{
     return (cast(T*)m)[0 .. N];
}

void main(string[] args)
{
     auto n = args.length;
     int[] arr = stack!(int, n)();
}
//----
Feb 05 2013
parent Nick Treleaven <ntrel-public yahoo.co.uk> writes:
On 05/02/2013 22:15, monarch_dodra wrote:

 On Tuesday, 5 February 2013 at 21:14:32 UTC, Nick Treleaven wrote:

 On 05/02/2013 21:13, Nick Treleaven wrote:

 I've just tried it with dmd 2.059 (haven't upgraded yet)


 sorry, 2.060


 Right, it's "alias" being finicky, because "args.length" isn't an actual
 variable (it's a property). The problem is not so much that it can't be
 "read" at compile time, that the compiler doesn't know what to alias to.

 I'll file a bug report to try and see if we can't get a better message.


OK, please post the link if/when you file it.


 Use a named variable, or use a manifest constant:


This works, thanks.


 //----
 import std.stdio;
 import core.stdc.stdlib:alloca;

 T* stack(T)(void* m = alloca(T.sizeof))
 {
      return cast(T*)m;
 }
 T[] stack(T, alias N)(void* m = alloca(T.sizeof * N))
 {
      return (cast(T*)m)[0 .. N];
 }

 void main(string[] args)
 {
      auto n = args.length;
      int[] arr = stack!(int, n)();
 }
 //----
Feb 06 2013
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Nick Treleaven:


 ^ I know you're aware of this, but maybe others might not know 
 the default-argument alloca wrapping trick:


For some usages it's an improvement over raw usage of alloca.
I did see this in past, but sometimes I forget.

Bye,
bearophile
Feb 05 2013
parent Nick Treleaven <ntrel-public yahoo.co.uk> writes:
On 05/02/2013 16:39, bearophile wrote:

 Nick Treleaven:


 ^ I know you're aware of this, but maybe others might not know the
 default-argument alloca wrapping trick:


 For some usages it's an improvement over raw usage of alloca.
 I did see this in past, but sometimes I forget.


Sorry if I sounded critical, I didn't mean to ;-)
Feb 06 2013
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 02 Feb 2013 11:36:28 -0500, Namespace <rswhite4 googlemail.com>  
wrote:


 Currently something like new ubyte[4]; reserves space for _at least_ 4  
 items.
 But if I want to store now something, the index isn't 0, it's 4.
 Let me explain that on a brief example:

 [code]
 import std.stdio;

 void main() {
 	ubyte[] arr = new ubyte[4];
 	arr ~= 4; // desirable: [4, 0, 0, 0];
 	writeln(arr); // prints: [0, 0, 0, 0, 4]
 	
 	ubyte[] arr2;
 	arr2.reserve(4);
 	arr2 ~= 4; // expect: [4, 0, 0, 0];
 	writeln(arr2); // prints: [4] just as well
 }
 [/code]

 So is there any reason why this behaviour is like it is?

 As I looked at arr.length and arr.capacity for the first time I was  
 schocked: I want only space for 4 items, but I got space for 15.
 I read in the docs that .reserve extends the space to at least SIZE  
 items, but maybe more. But at that time and still yet I found nothing  
 about new ubyte[SIZE]. So I ask:
 wouldn't it be better, if new ubyte[4] reserves only space for 4 items  
 and reallocs only if I append more than 4?


Heap block sizes start at 16.  One byte overhead is used to store the  
array length, so the minimum size of ANY array allocation is 15 bytes.

Then it doubles to 32, then to 64, then to 128, 256, 512, etc. until you  
get to a page size (4096).  Then it scales linearly by pages.

I think you misunderstand what reserve and append do.  You should read  
this article to understand arrays and appending better:  
http://dlang.org/d-array-article.html

-Steve
Feb 02 2013
parent reply FG <home fgda.pl> writes:
On 2013-02-02 22:33, Steven Schveighoffer wrote:

 Heap block sizes start at 16.  One byte overhead is used to store the array
 length, so the minimum size of ANY array allocation is 15 bytes.


How is the length stored because I see only strange numbers in that byte.

     foreach (end; 2..31) {
         ubyte[] x;
         foreach (i; 0..end) {
             x ~= cast(ubyte)i;
         }
         writeln(x.length, " ", x.capacity, " ", x.ptr[end]);
     }

That code outputs following length/capacity/extra_byte:

2 15 69
3 15 0
4 15 100
5 15 26
6 15 36
7 15 0
8 15 0
9 15 0
10 15 0
11 15 0
12 15 0
13 15 0
14 15 0
15 15 15
16 31 0
17 31 0
18 31 0
19 31 0
20 31 0
21 31 0
22 31 0
23 31 0
24 31 0
25 31 0
26 31 0
27 31 0
28 31 0
29 31 0
30 31 0

Last byte's value for length == 2 is quite random on each execution.
In a smaller way also for length == 6. Other values seem constant.
Feb 02 2013
parent FG <home fgda.pl> writes:
On 2013-02-02 22:57, FG wrote:

 On 2013-02-02 22:33, Steven Schveighoffer wrote:

 Heap block sizes start at 16.  One byte overhead is used to store the array
 length, so the minimum size of ANY array allocation is 15 bytes.


 How is the length stored because I see only strange numbers in that byte.

      foreach (end; 2..31) {
          ubyte[] x;
          foreach (i; 0..end) {
              x ~= cast(ubyte)i;
          }
          writeln(x.length, " ", x.capacity, " ", x.ptr[end]);
      }


Ah, sorry. Silly me.
I have figured out that the length byte would have to be aligned to the end
of the block, so that is where I should look. The updated code:

     // size_t ends = [1,2,7,15,31]; // crashes DMD
     foreach (end; 2..31) {
         ubyte[] x;
         foreach (i; 0..end) {
             x ~= cast(ubyte)i;
         }
         writeln(x.length, " ", x.capacity, " ", x.ptr[x.capacity]);
     }
     return;

shows that indeed, there's length written at the end. :)
Output:

2 15 2
3 15 3
4 15 4
5 15 5
6 15 6
7 15 7
8 15 8
9 15 9
10 15 10
11 15 11
12 15 12
13 15 13
14 15 14
15 15 15
16 31 16
17 31 17
18 31 18
19 31 19
20 31 20
21 31 21
22 31 22
23 31 23
24 31 24
25 31 25
26 31 26
27 31 27
28 31 28
29 31 29
30 31 30
Feb 02 2013