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.

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.

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 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.

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

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 :)

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 :)

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...

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

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.