www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - What's the point of static arrays ?

reply wjoe <invalid example.com> writes:
+ The size is known at compile time.

vs.

- Can neither grow nor shrink them
- Can't append elements
- Can't remove elements
- Can't slice them
- Can't range them
- Assignment copies the whole array, as in int[5] a; auto b = a;
- Size is limited by stack
- Stack overflow issues


Some of the cons could be considered a feature.
Also GC but it's possible to make a dynamic array implementation 
which avoids the GC.

I'm not considering supposed performance benefits/penalties 
because these need to be profiled.

Considering the many downsides why would I ever want to choose a 
static over a dynamic array ?
Jul 09 2020
next sibling parent Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Thursday, 9 July 2020 at 12:12:06 UTC, wjoe wrote:

 I'm not considering supposed performance benefits/penalties 
 because these need to be profiled.

 Considering the many downsides why would I ever want to choose 
 a static over a dynamic array ?


Simply put: static arrays are not dynamic arrays, and if you try 
to use one as the other you're going to be disappointed.

Usually, you use static arrays when you interface with something 
else that does it - generally a file format or a C library. For 
the most part you're right, you should probably use a dynamic 
array instead.

Now, as for your points:


 - Can neither grow nor shrink them
 - Can't append elements
 - Can't remove elements


These are the same as the first point.



 - Can't slice them
 - Can't range them


Sure you can:

unittest {
     import std.stdio;
     import std.algorithm;
     int[10] a = [1,2,3,4,5,6,7,8,9,10];

     // Note I'm slicing the static array to use in range 
algorithms:
     writeln(a[].map!(b => b+2));

     // Slicing works:
     auto b = a[3..6];
     b[] = 7;
     writeln(a);
}



 - Assignment copies the whole array, as in int[5] a; auto b = a;


This is often a factor in choosing a static array. It's not 
better or worse, just different. And sometimes it's different in 
exactly the way you need.



 - Size is limited by stack
 - Stack overflow issues


So allocate your static array on the heap if this is a problem?



 Some of the cons could be considered a feature.
 Also GC but it's possible to make a dynamic array 
 implementation which avoids the GC.


Basically none of the drawbacks you refer to are actual 
drawbacks, but instead part of what makes static arrays useful. 
Static arrays are not a poor man's dynamic arrays, they're a 
different beast, doing different things.

--
   Simen
Jul 09 2020
prev sibling next sibling parent psycha0s <box mail.com> writes:
On Thursday, 9 July 2020 at 12:12:06 UTC, wjoe wrote:

 Also GC but it's possible to make a dynamic array 
 implementation which avoids the GC.


It's easy to make a dynamic array without using the GC. Did you 
mean "implementation which avoids memory management"?


 I'm not considering supposed performance benefits/penalties 
 because these need to be profiled.

 Considering the many downsides why would I ever want to choose 
 a static over a dynamic array ?


Sometimes the amount of elements is known at compile time so you 
don't need to waste CPU cycles for memory allocation/freeing. 
This can be really important when you work on a 
performance-critical code.
Jul 09 2020
prev sibling next sibling parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 7/9/20 5:12 AM, wjoe wrote:


 Considering the many downsides why would I ever want to choose a static 
 over a dynamic array ?
 


In addition to what others said, dynamic arrays can be more expensive 
both in space and time.

Time: Dynamic array elements are accessed through an extra pointer 
compared to static arrays. Depending on the usage pattern of the data, 
that extra indirection may be slower (e.g. due to the extra load on the 
CPU's cache).

Space: Every dynamic array is represented by the pair of one pointer 
(void*) one length (size_t) e.g. 2 * 8 = 16 bytes on a 64-bit system. 
Assuming the array is just 3 floats, which is a common type used for 
RGB, 3D coordinates, etc. (3 * 4 = 12 bytes), then those 16 bytes are 
more than the data itself.

I wrote the following program (as a fun morning exercise, before coffee 
:o) ) to display bytes used by different kinds of variables:

import std.stdio;
import std.range;
import std.algorithm;
import std.traits;

size_t bytesUsed(T)(T var) {
   static if (isDynamicArray!T) {
     enum dynamicArrayOverhead = (void[]).sizeof;
     // Double check:
     static assert (dynamicArrayOverhead == size_t.sizeof + (void*).sizeof);

     return dynamicArrayOverhead + var.map!(element => 
bytesUsed(element)).sum;

   } else static if (isAssociativeArray!T) {
     static assert (false, "I don't know the implementation of AAs.");

   } else static if (is (T == struct)) {
     // BUG: Ignores alignment
     size_t total;
     foreach (member; var.tupleof) {
       total += bytesUsed(member);
     }
     return total;

   } else static if (is (T == class)) {
     // BUG: Ignores alignment
     size_t total;
     foreach (member; var.tupleof) {
       total += bytesUsed(member);
     }
     enum classOverhead = (void*).sizeof * 2;
     return classOverhead + total;

   } else {
     return var.sizeof;
   }

// BUG: union?
}

unittest {
   struct S {
     int[] arr;
     void* ptr;
   }
   assert(bytesUsed(S([1, 2, 3])) == size_t.sizeof + (void*).sizeof + 3 
* int.sizeof + 8);
}

void info(alias var)() {
   writefln!"'%s' is %s and uses %s bytes."(var.stringof, 
typeof(var).stringof, bytesUsed(var));
}

void main() {
   // This is an efficient data structure:
   alias Color = float[3]; // red, green, blue
   alias DayColors = Color[7];

   // Comparing it to the dynamic array equivalent:
   DayColors a;
   auto b = makeDayColors();
   info!a;
   info!b;
}

float[] makeColor() {
   // Syntax confusion alert: Return type is *not* a static array. :/
   return new float[3];
}

float[][] makeDayColors() {
   float[][] result = new float[][7];
   foreach (ref e; result) {
     e = makeColor();
   }
   return result;
}

Ali
Jul 09 2020
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Jul 09, 2020 at 12:12:06PM +0000, wjoe via Digitalmars-d-learn wrote:

 + The size is known at compile time.
 
 vs.
 
 - Can neither grow nor shrink them
 - Can't append elements
 - Can't remove elements


Consider a 3D game in which you represent vectors as static arrays of 4
elements (homogenous representation).  In this case, it's a plus to not
be able to append/remove elements, because the rest of the code expects
vectors that are exactly 4 elements long.



 - Can't slice them
 - Can't range them


Sure you can.



 - Assignment copies the whole array, as in int[5] a; auto b = a;


Sometimes this is desirable.  Consider the 3D game example.  Suppose
you're given a vector and need to perform some computation on it. If it
were a dynamic array, you'd need to allocate a new array on the heap in
order to work on it without changing the original vector. With a static
array, it's passed by value to your function, so you just do what you
need to do with it, and when you're done, either discard it (== no work
because it's allocated on the stack) or return it (== return on the
stack, no allocations).



 - Size is limited by stack
 - Stack overflow issues


You *can* allocate static arrays on the heap, in which case they become
closer to dynamic arrays.  Generally, the cases for which static arrays
are useful are when the size isn't huge; for huge arrays it makes more
sense to just use dynamic arrays.

You can also have classes that contain large static arrays: in this
case, the usefulness comes from having the array embedded in the class
object itself, rather than being a separate heap allocation + another
level of indirection.


[...]

 Considering the many downsides why would I ever want to choose a
 static over a dynamic array ?


It depends on your needs.  If you know you're always going to be trading
in vectors of a fixed size, like 4-element vectors in aforementioned 3D
game, then there's no need to put extra GC (or whatever allocator)
pressure on your code, just trade in T[4].  You also skip bounds checks
in many cases, since the length is known at compile-time.  You get
by-value semantics, which is generally much easier to reason about than
by-reference semantics.  You avoid an extra level of indirection, which
can matter in hotspots.

If your arrays are going to change in length, then static arrays aren't
what you need; just use dynamic arrays. They serve different purposes.


T

-- 
All men are mortal. Socrates is mortal. Therefore all men are Socrates.
Jul 09 2020
prev sibling next sibling parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Thursday, July 9, 2020 10:21:41 AM MDT H. S. Teoh via Digitalmars-d-learn 
wrote:

 - Assignment copies the whole array, as in int[5] a; auto b = a;


 Sometimes this is desirable.  Consider the 3D game example.  Suppose
 you're given a vector and need to perform some computation on it. If it
 were a dynamic array, you'd need to allocate a new array on the heap in
 order to work on it without changing the original vector. With a static
 array, it's passed by value to your function, so you just do what you
 need to do with it, and when you're done, either discard it (== no work
 because it's allocated on the stack) or return it (== return on the
 stack, no allocations).


I recall that at one point, I wrote brute-force sudoku solver, and
initially, I'd used dynamic arrays to represent the board. When I switched
them to static arrays, it was _way_ faster - presumably, because all of
those heap allocations were gone. And of course, since the sudoku board is
always the same size, the ability to resize the array was unnecessary.

In most programs that I've written, it hasn't made sense to use static
arrays anywhere, but sometimes, they're exactly what you need.

- Jonathan M Davis
Jul 09 2020
parent wjoe <invalid example.com> writes:
On Thursday, 9 July 2020 at 17:15:26 UTC, Jonathan M Davis wrote:

 On Thursday, July 9, 2020 10:21:41 AM MDT H. S. Teoh via 
 Digitalmars-d-learn wrote:

 - Assignment copies the whole array, as in int[5] a; auto b 
 = a;


 Sometimes this is desirable.  Consider the 3D game example.  
 Suppose you're given a vector and need to perform some 
 computation on it. If it were a dynamic array, you'd need to 
 allocate a new array on the heap in order to work on it 
 without changing the original vector. With a static array, 
 it's passed by value to your function, so you just do what you 
 need to do with it, and when you're done, either discard it 
 (== no work because it's allocated on the stack) or return it 
 (== return on the stack, no allocations).


 I recall that at one point, I wrote brute-force sudoku solver, 
 and initially, I'd used dynamic arrays to represent the board. 
 When I switched them to static arrays, it was _way_ faster - 
 presumably, because all of those heap allocations were gone. 
 And of course, since the sudoku board is always the same size, 
 the ability to resize the array was unnecessary.

 In most programs that I've written, it hasn't made sense to use 
 static arrays anywhere, but sometimes, they're exactly what you 
 need.

 - Jonathan M Davis


Even though dynamic arrays can be resized, they don't need to be 
if the need doesn't arise  - did you measure performance with 
pre-allocated dynamic arrays and disabled bounds checks, too ?

I wouldn't expect that big of a performance difference in that 
scenario, but what you expect and what you get can be vastly 
different. I'm really curious to know.
Jul 10 2020
prev sibling next sibling parent reply IGotD- <nise nise.com> writes:
On Thursday, 9 July 2020 at 12:12:06 UTC, wjoe wrote:

 ...


Static arrays are great because as already mentioned, they are 
allocated on the stack (unless it is global variable something, 
then it ends up in the data segment or TLS area).

As C/C++ now allows dynamically sized static arrays (for stack 
only), shouldn't D allow this as well.

Now you have to do.

import core.stdc.stdlib;

void myFunc(size_t arraySize)
{
     void *ptr = alloca(arraySize);
     ubyte[] arr = cast(ubyte[])ptr[0..arraySize];

}

it would be nice if we could just write

ubyte[arraySize] just like in C.

Now this operation is not safe, but could be allowed in  system 
code.

Is this the reason that ubyte[arraySize] doesn't create a dynamic 
array with size arraySize?

Now you need to do.

ubyte[] arr;
arr.length = arraySize;

Like ubyte[arraySize] is reserved for the same usage as in C.
Jul 09 2020
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Jul 09, 2020 at 06:02:02PM +0000, IGotD- via Digitalmars-d-learn wrote:
[...]

 Is this the reason that ubyte[arraySize] doesn't create a dynamic
 array with size arraySize?
 
 Now you need to do.
 
 ubyte[] arr;
 arr.length = arraySize;


Nah, just do this:

	arr = new ubyte[arraySize];

Mission accomplished. ;-)


T

-- 
I am Ohm of Borg. Resistance is voltage over current.
Jul 09 2020
prev sibling parent reply Paul Backus <snarwin gmail.com> writes:
On Thursday, 9 July 2020 at 18:02:02 UTC, IGotD- wrote:

 Static arrays are great because as already mentioned, they are 
 allocated on the stack (unless it is global variable something, 
 then it ends up in the data segment or TLS area).

 As C/C++ now allows dynamically sized static arrays (for stack 
 only), shouldn't D allow this as well.

 Now you have to do.

 import core.stdc.stdlib;

 void myFunc(size_t arraySize)
 {
     void *ptr = alloca(arraySize);
     ubyte[] arr = cast(ubyte[])ptr[0..arraySize];

 }

 it would be nice if we could just write

 ubyte[arraySize] just like in C.


Note that using VLAs in C is widely considered to be bad 
practice, and that they were made optional in the C11 standard.

If you want to allocate an array on the stack, the best way is to 
use a static array for size below a predetermined limit, and fall 
back to heap allocation if that limit is exceeded. An easy way to 
do this in D is with 
`std.experimental.allocator.showcase.StackFront`.
Jul 09 2020
parent IGotD- <nise nise.com> writes:
On Thursday, 9 July 2020 at 18:51:47 UTC, Paul Backus wrote:

 Note that using VLAs in C is widely considered to be bad 
 practice, and that they were made optional in the C11 standard.

 If you want to allocate an array on the stack, the best way is 
 to use a static array for size below a predetermined limit, and 
 fall back to heap allocation if that limit is exceeded. An easy 
 way to do this in D is with 
 `std.experimental.allocator.showcase.StackFront`.


I know but I at least really like them because they solve a few 
obstacles for me. If you have a maximum allowed size, then they 
should be alright but opinions differ here.

I do not recommend allocating a 'max' static size if you don't 
use just a fraction of it. The reason is that will possibly break 
out more stack pages than necessary leading to unnecessary memory 
consumption, especially if you initialize the entire array. This 
is another reason I like VLAs.
Jul 09 2020
prev sibling parent reply wjoe <invalid example.com> writes:
So many awesome answers, thank you very much everyone!

Less overhead,
Using/needing it to interface with something else, and
Efficiency are very good points.

However stack memory needs to be allocated at program start. I 
don't see a huge benefit in allocation speed vs. heap 
pre-allocation, or is there?
I mean 1 allocation vs 2 isn't going to noticeably improve 
overall performance.


On Thursday, 9 July 2020 at 12:48:26 UTC, Simen Kjærås wrote:

 [...]

 - Can't slice them
 - Can't range them


 Sure you can:

 unittest {
     import std.stdio;
     import std.algorithm;
     int[10] a = [1,2,3,4,5,6,7,8,9,10];

     // Note I'm slicing the static array to use in range 
 algorithms:
     writeln(a[].map!(b => b+2));

 [...]


Cool.

     a[]


What happens here exactly ?

I read the chapters in Ali's book (thank you very much for such a 
great book, Ali) on arrays and slicing prior to asking this 
question and I came to the following conclusion:

Because a static array is pre-allocated on the stack,
doesn't have a pointer/length pair,
is addressed via the stack pointer, and
due to the fact that a slice is a pointer/length pair
   and because a slice is technically the meta data of a dynamic 
array, a view into (part) of a dynamic array,
that it's not possible to slice a static array because the slice 
would technically be akin to a dynamic array and hence be 
incompatible.


As for `can't range them` Ali's chapter on ranges emphatically 
stresses the fact that ranges are lazy.
But due to the fact that static arrays are copied, I couldn't see 
how to satisfy the lazy property.

Consider this:

struct SuperSpecializedArray(T, size_t S) if (S > 0)
{
    T[S] elements;

    struct SuperSpecializedArrayRange
    {
       typeof(elements) e;

       this(SuperSpecializedArray a)
       {
          e = a.elements; // copies
       }

       // ...
    }
}

Upon creation of a SuperSpecializedArrayRange, the array is 
copied, but more importantly, data which may not ever be needed 
is copied and that's supposed to be a big selling point for 
ranges - only ever touching the data when it's requested - am I 
wrong ?

But considering Simen's answer I now know that a slice of 
elements can be used so that's that.
Jul 10 2020
next sibling parent reply psycha0s <box mail.com> writes:
On Friday, 10 July 2020 at 10:13:23 UTC, wjoe wrote:

 However stack memory needs to be allocated at program start. I 
 don't see a huge benefit in allocation speed vs. heap 
 pre-allocation, or is there?
 I mean 1 allocation vs 2 isn't going to noticeably improve 
 overall performance.


Allocation on the stack is basically just a single processor 
instruction that moves the stack pointer (well, ofc you also need 
to initialize array elements). Meanwhile, allocation on the heap 
involves much more complex logic of the memory allocator. 
Moreover, in D dynamic arrays use GC, thus the memory allocation 
may involve the trash collection step.
Jul 10 2020
parent reply wjoe <invalid example.com> writes:
On Friday, 10 July 2020 at 10:47:49 UTC, psycha0s wrote:

 On Friday, 10 July 2020 at 10:13:23 UTC, wjoe wrote:

 However stack memory needs to be allocated at program start. I 
 don't see a huge benefit in allocation speed vs. heap 
 pre-allocation, or is there?
 I mean 1 allocation vs 2 isn't going to noticeably improve 
 overall performance.


 Allocation on the stack is basically just a single processor 
 instruction that moves the stack pointer (well, ofc you also 
 need to initialize array elements). Meanwhile, allocation on 
 the heap involves much more complex logic of the memory 
 allocator. Moreover, in D dynamic arrays use GC, thus the 
 memory allocation may involve the trash collection step.


On Friday, 10 July 2020 at 11:20:17 UTC, Simen Kjærås wrote:

 You seem to still be thinking of static arrays as the same kind 
 of "thing" as a dynamic array. They're (usually) more like ints 
 or structs than containers: they're generally small, they're 
 often parts of other structures or classes, and they're fairly 
 often the element type of a larger dynamic array. For instance, 
 a bitmap image could be a byte[4][][], with dynamic dimensions 
 3840x2160. If instead of byte[4] we used byte[], not only would 
 things grind to a halt immediately, we'd also be using 
 massively more memory.


No, not quite. My idea of the stack is like a pre-allocated 
amount of memory in computer RAM which is pointed to by the stack 
pointer.
And further that at program start,whn the process is created, 
this memory needs to be allocated by the OS, just like any other 
memory allocation in protected mode, but only once for the entire 
run time of the process.
(And since there is an allocation when a process/thread is 
created, the act of creating a thread is considered slow.)
A static array resides in this memory (with a fixed length, so a 
length needn't be stored because bounds can be checked at compile 
time) if declared as a variable and is accessed via stack pointer 
and offset.

As for dynamic arrays, that's an allocated amount 
(length/capacity) of memory in computer RAM which is not part of 
the stack (the heap).
Whichever creation process is chosen (malloc, GC, Pool that 
doesn't allocate but just returns a pointer/length, etc.) you end 
up with a pointer to the allocated memory in computer RAM and a 
length variable.

But when the static array is part of a data structure which 
itself is stored in a dynamic array, this memory is accessed 
through the pointer of the dynamic array.

Is that not correct ?


Thanks for the answers :)
Jul 10 2020
parent wjoe <invalid example.com> writes:
On Friday, 10 July 2020 at 14:20:15 UTC, wjoe wrote:

 On Friday, 10 July 2020 at 10:47:49 UTC, psycha0s wrote:

 On Friday, 10 July 2020 at 10:13:23 UTC, wjoe wrote:


 A static array resides in this memory (with a fixed length, so 
 a length needn't be stored because bounds can be checked at 
 compile time) if declared as a variable and is accessed via 
 stack pointer and offset.


resides is the wrong word again, sorry.

A static array is mapped into stack memory...
Jul 10 2020
prev sibling next sibling parent reply Stanislav Blinov <stanislav.blinov gmail.com> writes:
On Friday, 10 July 2020 at 10:13:23 UTC, wjoe wrote:

 So many awesome answers, thank you very much everyone!

 Less overhead,
 Using/needing it to interface with something else, and
 Efficiency are very good points.

 However stack memory needs to be allocated at program start. I 
 don't see a huge benefit in allocation speed vs. heap 
 pre-allocation, or is there?


Stack is allocated by the OS for the process when it's started. 
Reserving space for stack variables, including arrays, is 
effectively free, since the compiler assigns offsets statically 
at compile time.


 I mean 1 allocation vs 2 isn't going to noticeably improve 
 overall performance.


A GC allocation is way more complex than a mere bump-the-pointer. 
If your program is trivial enough you may actually find that one 
extra GC allocation is significant in its runtime. Of course, if 
you only ever allocate once and your program runs for ages, you 
won't really notice that allocation.


     a[]


 What happens here exactly ?


This:

int[10] a;
int[] slice = a[];
assert(slice.ptr == &a[0]);
assert(slice.length == 10);
assert(a.sizeof == 10 * int.sizeof);    // 40
assert(slice.sizeof == (int[]).sizeof); // 16 on 64 bit


 I read the chapters in Ali's book (thank you very much for such 
 a great book, Ali) on arrays and slicing prior to asking this 
 question and I came to the following conclusion:

 Because a static array is pre-allocated on the stack,
 doesn't have a pointer/length pair,
 is addressed via the stack pointer, and
 due to the fact that a slice is a pointer/length pair
   and because a slice is technically the meta data of a dynamic 
 array, a view into (part) of a dynamic array,


No. A slice is just a pointer/length pair - a contiguous view 
into *some* memory, regardless of where that memory came from:

void takeASlice(scope void[] data) // can take any slice since 
any slice converts to void[]
{
     import std.stdio;
     writefln("%x %d", data.ptr, data.length);
}

int[10] a;
takeASlice(a); // a[]
takeASlice(a[1 .. $-1]); // a[1 .. 9]

struct S
{
     float x, y, z;
     float dx, dy, dz;
}

S s;
takeASlice((&s)[0 .. 1]); // Slicing a pointer, not  safe but can 
be done.
takeASlice(new int[10]); // Array, GC allocation
takeASlice([1, 2, 3, 4]); // Array literal, may or may not be 
GC-allocated

`takeASlice` has no knowledge of where the memory came from.

Dynamic arrays only ever come into the picture if you try to 
manipulate the slice itself: resize it, append to it, etc.


 that it's not possible to slice a static array because the 
 slice would technically be akin to a dynamic array and hence be 
 incompatible.


Incompatible to what?

int[10] a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
a[0 .. 2] = a[2 .. 4];
assert(a[0] == 3);
assert(a[1] == 4);
int[10] b = void;
b[] = a[];
assert(b == [3, 4, 3, 4, 5, 6, 7, 8, 9, 10]);


 struct SuperSpecializedArray(T, size_t S) if (S > 0)
 {
    T[S] elements;

    struct SuperSpecializedArrayRange
    {
       typeof(elements) e;

       this(SuperSpecializedArray a)
       {
          e = a.elements; // copies
       }

       // ...
    }
 }

 Upon creation of a SuperSpecializedArrayRange, the array is 
 copied, but more importantly, data which may not ever be needed 
 is copied and that's supposed to be a big selling point for 
 ranges - only ever touching the data when it's requested - am I 
 wrong ?


Ranges need not be lazy. They can be, and most of them should be 
indeed, but they need not be. And, as you yourself point out, in 
your case `e` can just be a slice, and your range becomes lazy.
Jul 10 2020
parent reply wjoe <invalid example.com> writes:
On Friday, 10 July 2020 at 11:13:51 UTC, Stanislav Blinov wrote:

 On Friday, 10 July 2020 at 10:13:23 UTC, wjoe wrote:

 So many awesome answers, thank you very much everyone!

 Less overhead,
 Using/needing it to interface with something else, and
 Efficiency are very good points.

 However stack memory needs to be allocated at program start. I 
 don't see a huge benefit in allocation speed vs. heap 
 pre-allocation, or is there?


 Stack is allocated by the OS for the process when it's started. 
 Reserving space for stack variables, including arrays, is 
 effectively free, since the compiler assigns offsets statically 
 at compile time.


 I mean 1 allocation vs 2 isn't going to noticeably improve 
 overall performance.


 A GC allocation is way more complex than a mere 
 bump-the-pointer. If your program is trivial enough you may 
 actually find that one extra GC allocation is significant in 
 its runtime. Of course, if you only ever allocate once and your 
 program runs for ages, you won't really notice that allocation.


I think that memory for the program must be allocated when the 
process is created, this includes the stack, etc. but it is an 
allocation in computer RAM nonetheless.

A pre-allocated amount of memory for a dynamic array once is one 
additional allocation throughout the entire run time of the 
program.
Now I can't make any guess about how this allocation takes place 
- it might be allocated via malloc, a pool, new, etc. - but it is 
one additional allocation.
What I'm saying is even if this allocation is slow let's say 5ms, 
but it only happens once, that wouldn't matter to overall 
performance at all.

But performance isn't the focus of this question.


 No. A slice is just a pointer/length pair - a contiguous view 
 into *some* memory, regardless of where that memory came from:


Metadata is data that describes other data - a pointer/length 
pair, which describs a continuous view into memory, is matching 
that criteria, doesn't it ?
An array is, by definition, a length of the same kind of element 
mapped into continuous memory, no ?

A dynamic array is a pointer/length pair, a slice is a 
pointer/length pair, too.
Can a function, which is passed both, a dynamic array and a 
slice, tell the two apart, as in distinguish between the two ?
Also, can this function distinguish a slice of a dynamic array 
from a slice of a static array ?


 void takeASlice(scope void[] data) // can take any slice since 
 any slice converts to void[]
 {
     import std.stdio;
     writefln("%x %d", data.ptr, data.length);
 }

 int[10] a;
 takeASlice(a); // a[]
 takeASlice(a[1 .. $-1]); // a[1 .. 9]

 struct S
 {
     float x, y, z;
     float dx, dy, dz;
 }

 S s;
 takeASlice((&s)[0 .. 1]); // Slicing a pointer, not  safe but 
 can be done.
 takeASlice(new int[10]); // Array, GC allocation
 takeASlice([1, 2, 3, 4]); // Array literal, may or may not be 
 GC-allocated

 `takeASlice` has no knowledge of where the memory came from.

 Dynamic arrays only ever come into the picture if you try to 
 manipulate the slice itself: resize it, append to it, etc.


 that it's not possible to slice a static array because the 
 slice would technically be akin to a dynamic array and hence 
 be incompatible.


 Incompatible to what?


void foo(int[4] a){}

int[4] x;
auto slice = x[];
foo(slice); // that's incompatible, isn't it?

Thank you for your explanations :)
Jul 10 2020
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 7/10/20 8:03 AM, wjoe wrote:


 What I'm saying is even if this allocation is slow let's say 5ms, but it
 only happens once, that wouldn't matter to overall performance at all.


Yes, you are correct and there are dynamic arrays that are allocated 
once in many programs.

I haven't read the rest of your post but you've said elsewhere that a 
static array is on the stack. Yes, there are such static arrays but the 
issue is not that simple.

struct S {
   float[3] rgb;  // Can be on the stack or dynamic memory
}

The member of that struct can be anywhere:

void foo() {
   S s;                // On the stack
   auto arr = [ S() ]; // On dynamically allocated memory
}

Additionally, as is common and understandable in D, we are conflating 
dynamic arrays and slices. The way I see it is dynamic array is owned by 
the D runtime. Although a slice is an interface to such dynamic arrays, 
a slice can start its life with non-dynamic arrays and may or may not 
move to accessing dynamic arrays.

struct S {
   float[] arr;  // A slice can use dynamic or static memory
}

void foo() {
   float[10] storage;
   auto a = S(storage[1..7]);  // Slice is referring to the stack space
   auto b = S();
   b.arr ~= 1.5;               // Slice is referring to dynamic memory
}

What is important is overhead:

1) Allocation: Only sometimes an issue.

2) Cost of the slice object (1 pointer and 1 size_t): The cost of this 
may be enormous. (Compare the 12-byte rgb above to a 16-byte slice 
overhead.)

3) Cost of accessing the elements: The access through that extra level 
of indirection may be a cost but the CPU can alleviate it by 
pre-fetching or caching but only for some access patterns.

4) Bounds checking: Some bounds checks for static arrays can be elided 
at run time.

So, there are cases where a dynamic array is better (or must), there are 
cases there is no winner and there are cases where a static array is a 
huge win.

Ali
Jul 10 2020
parent wjoe <invalid example.com> writes:
On Friday, 10 July 2020 at 21:24:08 UTC, Ali Çehreli wrote:

 What is important is overhead:


That's the major point I took from all this.
Thanks for your effort.

And thanks everybody else, too, I really appreciate it.
Jul 13 2020
prev sibling parent Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Friday, 10 July 2020 at 10:13:23 UTC, wjoe wrote:

 However stack memory needs to be allocated at program start. I 
 don't see a huge benefit in allocation speed vs. heap 
 pre-allocation, or is there?
 I mean 1 allocation vs 2 isn't going to noticeably improve 
 overall performance.


You seem to still be thinking of static arrays as the same kind 
of "thing" as a dynamic array. They're (usually) more like ints 
or structs than containers: they're generally small, they're 
often parts of other structures or classes, and they're fairly 
often the element type of a larger dynamic array. For instance, a 
bitmap image could be a byte[4][][], with dynamic dimensions 
3840x2160. If instead of byte[4] we used byte[], not only would 
things grind to a halt immediately, we'd also be using massively 
more memory.

When you're using a static array on the stack, it's usually just 
because it's more convenient to say `int[16] buffer;` than `auto 
buffer = new int[16];`. The fact it may be faster is mostly a 
side benefit. Also, even if you did preallocate such a buffer, 
there's the overhead of remembering how to get to it, the work of 
setting it up, probably a function call on use, etc. The 
alternative is terser, built-in, more obvious to maintainers, 
pretty unlikely to overflow the stack, and very unlikely to be 
slower. Allocating a multi-MiB static array on the stack is a 
sign that you're using your screwdriver as a hammer, and there 
are probably better ways to do what you're trying to do.



     a[]


 What happens here exactly ?


It creates a dynamic array that points to the data in the static 
array. It's just shorthand for a[0..$]:

unittest {
     int[4] a = [1,2,3,4];

     auto b = a[];
     assert(b.length == 4);
     assert(b.ptr == &a[0]);

     auto c = a[0..$];
     assert(b is c);
}

--
   Simen
Jul 10 2020