Re: Straight Forward Arrays
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.
Re: Straight Forward Arrays
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
Re: Straight Forward Arrays
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.
Re: Straight Forward Arrays
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
Re: Straight Forward Arrays
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
Re: Straight Forward Arrays
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!
Re: Straight Forward Arrays
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
Re: Straight Forward Arrays
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.
Re: Straight Forward Arrays
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
Re: Straight Forward Arrays
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.
Re: Straight Forward Arrays
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.
Re: Straight Forward Arrays
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.
Re: Straight Forward Arrays
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.
Re: Straight Forward Arrays
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
Re: Straight Forward Arrays
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'.
Re: Straight Forward Arrays
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);
}
```
Re: Straight Forward Arrays
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);
}
```
Re: Straight Forward Arrays
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
Re: Straight Forward Arrays
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.
Straight Forward Arrays
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\. The documentation does not mention nor explain why. Can someone explain? Is there a simpler, more efficient alternative? Thanks in Advance, dhs
