www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Straight Forward Arrays

reply dhs <dhs email.com> writes:
Hi,

Is there a straight forward Array type in D similar to C++'s 
vector class? Something along the lines of the tuple: (pointer to 
elements, length, capacity).

I tried two implementations: D's dynamic array and 
std.container.array.

When D creates a dynamic array, it returns a slice. Functions 
that add or remove elements begin by asking the memory manager 
for the dynamic array that the slice belongs to. Only then can 
they go on and add elements.

I switched to std.container.array. It is more straight forward, 
but is also reference counted. Array is basically a pointer to 
the tuple (pointer to elements, length, capacity, refCount). 
Functions that add or remove elements begin by checking that the 
Array is not null, follow the pointer to the actual tuple, then 
follow the "pointer to elements" to access the actual elements. 
In C++, this is similar to shared_ptr\<vector>. The documentation 
does not mention nor explain why. Can someone explain? Is there a 
simpler, more efficient alternative?

Thanks in Advance,
dhs
Oct 01 2023
next sibling parent reply Imperatorn <johan_forsberg_86 hotmail.com> writes:
On Sunday, 1 October 2023 at 09:01:53 UTC, dhs wrote:

 Hi,

 Is there a straight forward Array type in D similar to C++'s 
 vector class? Something along the lines of the tuple: (pointer 
 to elements, length, capacity).

 [...]


https://dlang.org/spec/simd.html
https://dlang.org/phobos/core_simd.html

Or if you want to use it, you can check out core.stdcpp.vector.
Oct 01 2023
parent dhs <dhs email.com> writes:
On Sunday, 1 October 2023 at 09:21:37 UTC, Imperatorn wrote:

 On Sunday, 1 October 2023 at 09:01:53 UTC, dhs wrote:

 Hi,

 Is there a straight forward Array type in D similar to C++'s 
 vector class? Something along the lines of the tuple: (pointer 
 to elements, length, capacity).

 [...]


 https://dlang.org/spec/simd.html
 https://dlang.org/phobos/core_simd.html

 Or if you want to use it, you can check out core.stdcpp.vector.


core.stdcpp.vector does look the dynamic array implementation I 
was looking for.

Thank you,
dhs
Oct 01 2023
prev sibling next sibling parent reply bachmeier <no spam.net> writes:
On Sunday, 1 October 2023 at 09:01:53 UTC, dhs wrote:

 Hi,

 Is there a straight forward Array type in D similar to C++'s 
 vector class? Something along the lines of the tuple: (pointer 
 to elements, length, capacity).

 I tried two implementations: D's dynamic array and 
 std.container.array.

 When D creates a dynamic array, it returns a slice. Functions 
 that add or remove elements begin by asking the memory manager 
 for the dynamic array that the slice belongs to. Only then can 
 they go on and add elements.


Have you read [this 
article](https://dlang.org/articles/d-array-article.html)? I'm 
not sure what you mean with your reference to the memory manager, 
but consider this program:

```
import std;

void main() {
     int[] x;
     x.length = 100;
     foreach(ii; 0..100) {
         x.ptr[ii] = ii;
     }
     x.length = 100;
     writeln(x);
}
```
Oct 01 2023
parent reply bachmeier <no spam.net> writes:
On Sunday, 1 October 2023 at 11:39:11 UTC, bachmeier wrote:

 On Sunday, 1 October 2023 at 09:01:53 UTC, dhs wrote:

 Hi,

 Is there a straight forward Array type in D similar to C++'s 
 vector class? Something along the lines of the tuple: (pointer 
 to elements, length, capacity).

 I tried two implementations: D's dynamic array and 
 std.container.array.

 When D creates a dynamic array, it returns a slice. Functions 
 that add or remove elements begin by asking the memory manager 
 for the dynamic array that the slice belongs to. Only then can 
 they go on and add elements.


 Have you read [this 
 article](https://dlang.org/articles/d-array-article.html)? I'm 
 not sure what you mean with your reference to the memory 
 manager, but consider this program:

 ```
 import std;

 void main() {
     int[] x;
     x.length = 100;
     foreach(ii; 0..100) {
         x.ptr[ii] = ii;
     }
     x.length = 100;
     writeln(x);
 }
 ```


Or if you want a safer version:

```
import std;

void main() {
     int[] x;
     x.length = 100;
     foreach(ii; 0..150) {
         if (ii < x.length) {
         	x.ptr[ii] = ii;
         }
     }
     writeln(x);
}
```
Oct 01 2023
parent dhs <dhs email.com> writes:
On Sunday, 1 October 2023 at 11:43:17 UTC, bachmeier wrote:

 On Sunday, 1 October 2023 at 11:39:11 UTC, bachmeier wrote:

 On Sunday, 1 October 2023 at 09:01:53 UTC, dhs wrote:

 Hi,

 Is there a straight forward Array type in D similar to C++'s 
 vector class? Something along the lines of the tuple: 
 (pointer to elements, length, capacity).

 I tried two implementations: D's dynamic array and 
 std.container.array.

 When D creates a dynamic array, it returns a slice. Functions 
 that add or remove elements begin by asking the memory 
 manager for the dynamic array that the slice belongs to. Only 
 then can they go on and add elements.


 Have you read [this 
 article](https://dlang.org/articles/d-array-article.html)? I'm 
 not sure what you mean with your reference to the memory 
 manager, but consider this program:

 ```
 import std;

 void main() {
     int[] x;
     x.length = 100;
     foreach(ii; 0..100) {
         x.ptr[ii] = ii;
     }
     x.length = 100;
     writeln(x);
 }
 ```


 Or if you want a safer version:

 ```
 import std;

 void main() {
     int[] x;
     x.length = 100;
     foreach(ii; 0..150) {
         if (ii < x.length) {
         	x.ptr[ii] = ii;
         }
     }
     writeln(x);
 }
 ```


Thanks for the article.

When you write x.length = 100, the code looks at x.capacity to 
see if the allocated memory is big enough for 100 elements. Since 
'capacity' is not part of x, the code calculates it by asking the 
Garbage Collected how much memory was allocated. This is my 
understanding of the code and what I meant by "asking the memory 
manager".

std.container.array uses a 'capacity' field, but is reference 
counted. This is not documented and means an additional 
indirection, which in my case is unnecessary.

User 'Imperatorn' suggested using core.stdcpp.vector. 
Unfortunately, it compile for me (neither using DMD nor LDC). In 
addition, it looks like it depends on the C++ runtime for 'new' 
and 'delete'.

So I am still in search of a straightforward dynamic array 
similar to C++ 'vector'.
Oct 01 2023
prev sibling next sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On Sunday, 1 October 2023 at 09:01:53 UTC, dhs wrote:

 Hi,

 Is there a straight forward Array type in D similar to C++'s 
 vector class? Something along the lines of the tuple: (pointer 
 to elements, length, capacity).

 [...]


Std::vector uses value semantics. D does not have anything like 
that. It could be done someone just has to do it.

-Steve
Oct 01 2023
parent reply dhs <dhs email.com> writes:
On Sunday, 1 October 2023 at 13:05:12 UTC, Steven Schveighoffer 
wrote:

 On Sunday, 1 October 2023 at 09:01:53 UTC, dhs wrote:

 Hi,

 Is there a straight forward Array type in D similar to C++'s 
 vector class? Something along the lines of the tuple: (pointer 
 to elements, length, capacity).

 [...]


 Std::vector uses value semantics. D does not have anything like 
 that. It could be done someone just has to do it.

 -Steve


Yes, and therein lies the problem: writing a dynamic array is not 
a very difficult task for an old developer like me. I looked at 
the D runtime and at the Phobos implementation for reference. The 
code is so extremely difficult to understand and uses so many 
advanced D features, that I doubt that I am up to the task. For 
me, the point of switching to D was to use a language that is 
simpler to read and maintain.
Oct 01 2023
next sibling parent reply Imperatorn <johan_forsberg_86 hotmail.com> writes:
On Sunday, 1 October 2023 at 13:24:27 UTC, dhs wrote:

 On Sunday, 1 October 2023 at 13:05:12 UTC, Steven Schveighoffer 
 wrote:

 On Sunday, 1 October 2023 at 09:01:53 UTC, dhs wrote:

 Hi,

 Is there a straight forward Array type in D similar to C++'s 
 vector class? Something along the lines of the tuple: 
 (pointer to elements, length, capacity).

 [...]


 Std::vector uses value semantics. D does not have anything 
 like that. It could be done someone just has to do it.

 -Steve


 Yes, and therein lies the problem: writing a dynamic array is 
 not a very difficult task for an old developer like me. I 
 looked at the D runtime and at the Phobos implementation for 
 reference. The code is so extremely difficult to understand and 
 uses so many advanced D features, that I doubt that I am up to 
 the task. For me, the point of switching to D was to use a 
 language that is simpler to read and maintain.


D can be very readable and maintainable, but since all the 
advanced features exist, we are tempted to use them, which can 
cause otherwise normal code to become a bit obfuscated.
Oct 01 2023
parent dhs <dhs email.com> writes:
On Sunday, 1 October 2023 at 13:51:35 UTC, Imperatorn wrote:

 D can be very readable and maintainable, but since all the 
 advanced features exist, we are tempted to use them, which can 
 cause otherwise normal code to become a bit obfuscated.


OK in any case the forum seems to be very helpful. Thanks to all 
for your help.
Oct 01 2023
prev sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On Sunday, 1 October 2023 at 13:24:27 UTC, dhs wrote:

 On Sunday, 1 October 2023 at 13:05:12 UTC, Steven Schveighoffer 
 wrote:

 On Sunday, 1 October 2023 at 09:01:53 UTC, dhs wrote:

 [...]


 Std::vector uses value semantics. D does not have anything 
 like that. It could be done someone just has to do it.


 Yes, and therein lies the problem: writing a dynamic array is 
 not a very difficult task for an old developer like me. I 
 looked at the D runtime and at the Phobos implementation for 
 reference. The code is so extremely difficult to understand and 
 uses so many advanced D features, that I doubt that I am up to 
 the task. For me, the point of switching to D was to use a 
 language that is simpler to read and maintain.


The complexity is from the way d does operator overloading and 
indexing.

It should be pretty straightforward. I’ll see if I can post a 
simple wrapper.

-Steve
Oct 01 2023
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 10/1/23 10:34 AM, Steven Schveighoffer wrote:


 
 The complexity is from the way d does operator overloading and indexing.
 
 It should be pretty straightforward. I’ll see if I can post a simple 
 wrapper.


I didn't tackle any attribute or memory safety issues, or many operator 
overloads, but this is going to be reasonably close. It should make a 
copy of the data when copied.

Note this still uses the GC for storage, and when expanding, uses the GC 
to fetch the capacity (this could be done in one call, but meh).

Some niceties of builtin arrays may not work, but this is somewhat of 
the cost you pay for trying to make a custom type.

```d
struct VTArray(T)
{
     private T[] _storage;
     private size_t _length;

     const size_t length() => _length;

     void length(size_t newLen) {
         if(newLen <= _storage.length)
             _length = newLen;
         else
         {
             _storage.length = newLen;
             _storage.length = _storage.capacity;
         }
     }

     inout this(ref inout(VTArray) other)
     {
         this(other[]);
     }

     inout this(inout(T)[] buf)
     {
         auto x = buf.dup;
         x.length = x.capacity;
         _length = buf.length;
         _storage = cast(inout)x;
     }

     ref inout(T) opIndex(size_t idx) inout {
         assert(idx < length);
         return _storage[idx];
     }

     void opOpAssign(string s : "~", V)(auto ref V other) {
         static if(is(V == T[]))
         {
             immutable avail = _storage.length - length;
             if(avail < other.length)
             {
                 _storage[length .. $] = other[0 .. avail];
                 _storage ~= other[avail .. $];
                 _storage.length = _storage.capacity; // expand to capacity;
             }
             else
             {
                 _storage[length .. length + other.length] = other;
             }
             _length += other.length;
         }
         else static if(is(V == T))
         {
             if(length == _storage.length)
             {
                 _storage.length += 1;
                 _storage.length = _storage.capacity;
             }
             _storage[_length++] = other;
         }
         else static if(is(V == VTArray))
         {
             this ~= other[];
         }
     }

     void opAssign(T[] arr)
     {
         _storage = arr.dup;
         _storage.length = _storage.capacity;
         _length = arr.length;
     }

     void opAssign(VTArray vtarr)
     {
         this = vtarr._storage[0 .. vtarr.length];
     }

     inout(T)[] opIndex() inout => _storage[0 .. _length];

     void toString(Out)(auto ref Out output)
     {
         import std.format;
         formattedWrite(output, "%s", this[]);
     }
}

void main()
{
     auto arr = VTArray!int.init;
     arr ~= 1;
     arr ~= [2,3,4,5];
     import std.stdio;
     writeln(arr);
     auto arr2 = arr;
     arr2[0] = 5;
     writeln(arr);
     writeln(arr2);
     arr2 ~= arr;
     writeln(arr2);
}
```

This should give you a reasonable head-start.

-Steve
Oct 01 2023
parent dhs <dhs email.com> writes:
On Sunday, 1 October 2023 at 17:21:32 UTC, Steven Schveighoffer 
wrote:

 On 10/1/23 10:34 AM, Steven Schveighoffer wrote:

 This should give you a reasonable head-start.

 -Steve


It does. Many thanks!
Oct 01 2023
prev sibling parent reply Adam D Ruppe <destructionator gmail.com> writes:
On Sunday, 1 October 2023 at 09:01:53 UTC, dhs wrote:

 When D creates a dynamic array, it returns a slice. Functions 
 that add or remove elements begin by asking the memory manager 
 for the dynamic array that the slice belongs to. Only then can 
 they go on and add elements.


Why is this a problem? It is convenient and usually works fine.

I use the built in arrays very very often for a lot of things.
Oct 01 2023
parent reply dhs <dhs email.com> writes:
On Sunday, 1 October 2023 at 13:27:37 UTC, Adam D Ruppe wrote:

 On Sunday, 1 October 2023 at 09:01:53 UTC, dhs wrote:

 When D creates a dynamic array, it returns a slice. Functions 
 that add or remove elements begin by asking the memory manager 
 for the dynamic array that the slice belongs to. Only then can 
 they go on and add elements.


 Why is this a problem? It is convenient and usually works fine.

 I use the built in arrays very very often for a lot of things.


It may not be a problem in practice. My concern was performance, 
because each time we add an element to the array, the garbage 
collector has to map the slice to the allocation it belongs to.
Oct 01 2023
next sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Sunday, October 1, 2023 11:13:43 AM MDT dhs via Digitalmars-d-learn wrote:

 On Sunday, 1 October 2023 at 13:27:37 UTC, Adam D Ruppe wrote:

 On Sunday, 1 October 2023 at 09:01:53 UTC, dhs wrote:

 When D creates a dynamic array, it returns a slice. Functions
 that add or remove elements begin by asking the memory manager
 for the dynamic array that the slice belongs to. Only then can
 they go on and add elements.


 Why is this a problem? It is convenient and usually works fine.

 I use the built in arrays very very often for a lot of things.


 It may not be a problem in practice. My concern was performance,
 because each time we add an element to the array, the garbage
 collector has to map the slice to the allocation it belongs to.


In general, this is a non-issue. Usually, the only time that you might need
to worry about it is when you're building an array with a bunch of elements,
in which case, std.array.Appender gives you a wrapper which avoids a lot of
that overhead (since it keeps track of the capacity separately):

https://dlang.org/phobos/std_array.html#appender

However, most code ends up using arrays without appending, and appending to
an array here and there doesn't really impact performance. In addition,
because D's dynamic arrays are slices of memory rather than owning their
memory, passing them around is extremely cheap in comparison to std::vector.
You're basically just passing around

DynamicArray(T)
{
    size_t length;
    T* ptr;
}

so you don't end up with a bunch of unnecessary copies, whereas in C++, you
have to be careful about passing by reference or const reference (or
worrying about move constructors) in order to avoid copying when you don't
actually want a copy.

So, unless you're doing a _lot_ of appending to dynamic arrays in D, and
you're doing it a lot outside of when a dynamic array is first created, the
way that D's arrays work will easily beat out how std::vector works in terms
of performance.

Of course, the exact performance characteristics are going to depend on what
you're doing in your program, and whether the approach of D's dynamic arrays
or C++'s std::vector is better depends on what your code is doing, but for
most code, D's approach works extremely well. It just tends to take some
getting used to, because the way that D's arrays work work is kind of
unique.

- Jonathan M Davis
Oct 01 2023
prev sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 10/1/23 1:13 PM, dhs wrote:


 It may not be a problem in practice. My concern was performance, because 
 each time we add an element to the array, the garbage collector has to 
 map the slice to the allocation it belongs to.


FWIW, there is a cache that makes this decently fast, so it doesn't have 
to go all the way into the GC to get all the information for every append.

But it *most definitely* not going to be as fast as reading a local 
"capacity" variable.

-Steve
Oct 01 2023
parent reply dhs <dhs email.com> writes:
On Monday, 2 October 2023 at 02:56:33 UTC, Steven Schveighoffer 
wrote:

 FWIW, there is a cache that makes this decently fast, so it 
 doesn't have to go all the way into the GC to get all the 
 information for every append.

 But it *most definitely* not going to be as fast as reading a 
 local "capacity" variable.

 -Steve


Sure, I saw that, it obviously works pretty good.

I think it's worth mentioning that D slices are similar in 
concept to Go slices.

In Python, lists are reference types too but slicing creates a 
copy (so, 'b = a' shares, while 'b = a[:]' copies.) JavaScript 
arrays are similar to Python in this sense.
C++ and Rust use distinct types for the resizable array and its 
view, and the view must not outlive the array.

D and Go slices have advantages but can be confusing. I don't 
have a solution, but if anyone is interested, the relevant 
discussions about slice confusion in the Go community apply to D 
slices as well.
Oct 04 2023
parent reply Jesse Phillips <Jesse.K.Phillips+D gmail.com> writes:
On Wednesday, 4 October 2023 at 10:51:46 UTC, dhs wrote:

 D and Go slices have advantages but can be confusing. I don't 
 have a solution, but if anyone is interested, the relevant 
 discussions about slice confusion in the Go community apply to 
 D slices as well.


I don't believe slice confusion in D is the same as God.

https://he-the-great.livejournal.com/48672.html

D manages to avoid stomping, while Go provides no clear ownership 
when slices are at play.


And here is the slices explained
https://dlang.org/articles/d-array-article.html
Oct 05 2023
parent dhs <dhs email.com> writes:
On Thursday, 5 October 2023 at 16:57:00 UTC, Jesse Phillips wrote:

 On Wednesday, 4 October 2023 at 10:51:46 UTC, dhs wrote:

 D and Go slices have advantages but can be confusing. I don't 
 have a solution, but if anyone is interested, the relevant 
 discussions about slice confusion in the Go community apply to 
 D slices as well.


 I don't believe slice confusion in D is the same as God.

 https://he-the-great.livejournal.com/48672.html

 D manages to avoid stomping, while Go provides no clear 
 ownership when slices are at play.


 And here is the slices explained
 https://dlang.org/articles/d-array-article.html


Thanks for the link. It actually demonstrates my point: he gets 
the same results from D and Go until he appends elements to the 
slice. It is then that things get confusing.

Obviously, the implementations are not exactly the same: for 
example, in Go 'capacity' is a field whereas in D it is a 
calculated property. But they are *similar*.

Here are some quotes from Go users:

"the issue of Go's slices is that they act as both a dynamic 
array and a slice viewing a portion of one. The two uses conflict 
with one another, and the interactions are full of traps. "

https://news.ycombinator.com/item?id=28344938

"the behaviour is logical based on how Go works. The criticism is 
instead that it works this way in the first place. The reason 
it's like this is that slices were attempting to address two 
separate use cases — growable arrays and subarrays"

https://www.reddit.com/r/golang/comments/6qizjq/fucking_go_slices/

Quote: "Welcome to go! This is one of the language quirks."

https://www.reddit.com/r/golang/comments/10b4ofx/confused_about_array_and_slices/

Others pointed out that slices work well. My points is: if you're 
thinking about a change it's worth reading the Go discussions, 
because their slices are similar in concept.
Oct 06 2023