View mode: basic / threaded / horizontal-split · Log in · Help
November 07, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
On Tuesday, 6 November 2012 at 09:10:08 UTC, bearophile wrote:
> Malte Skarupke:
>
>> I will most certainly never use dynamic arrays or slices again 
>> for anything that needs to grow or shrink dynamically.
>
> And doing so you will miss an important and handy part of D :-/
>
> Bye,
> bearophile

I implemented my own DynamicArray struct which behaves more like 
I want it to and is still giving me all of the benefits that I 
want from dynamic arrays.

Having no clear ownership for the array is not something I am 
willing to accept. Same thing for the non-deterministic copying 
and destruction behavior for the elements. That's the kind of 
thing which looks convenient at first, but will create many small 
performance problems. Once those add up to a big problem, it's 
incredibly frustrating to fix because your slow downs are from 
all over the place.

I don't anticipate that I will ever run into a situation where I 
want to append to a range without caring about whether it 
allocates and copies or not. If I want to append to a range, I 
will write the extra line to create a copy manually.
Because of that I don't need the syntactic ambiguity of treating 
a range the same as an array.
November 07, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
On Wednesday, November 07, 2012 04:45:04 Malte Skarupke wrote:
> I don't anticipate that I will ever run into a situation where I
> want to append to a range without caring about whether it
> allocates and copies or not. If I want to append to a range, I
> will write the extra line to create a copy manually.
> Because of that I don't need the syntactic ambiguity of treating
> a range the same as an array.

In general, you can't append to ranges. You can chain ranges together with 
std.range.chain, but appending is not one of the operations that ranges 
support. That's the sort of thing that you'd do to a container, not a range. 
Granted, it doesn't help that arrays are containers of sorts in addition to 
being ranges, but that's abnormal. Normally ranges have no control over 
whatever is actually holding their data.

- Jonathan M Davis
November 07, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
On Wednesday, 7 November 2012 at 06:44:11 UTC, Jonathan M Davis 
wrote:
> On Wednesday, November 07, 2012 04:45:04 Malte Skarupke wrote:
>> I don't anticipate that I will ever run into a situation where 
>> I want to append to a range without caring about whether it
>> allocates and copies or not. If I want to append to a range, I
>> will write the extra line to create a copy manually.
>> Because of that I don't need the syntactic ambiguity of 
>> treating
>> a range the same as an array.
>
> In general, you can't append to ranges.

I assume Malte really meant slices, not ranges.
November 07, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
On Wednesday, November 07, 2012 10:19:06 thedeemon wrote:
> On Wednesday, 7 November 2012 at 06:44:11 UTC, Jonathan M Davis
> 
> wrote:
> > On Wednesday, November 07, 2012 04:45:04 Malte Skarupke wrote:
> >> I don't anticipate that I will ever run into a situation where
> >> I want to append to a range without caring about whether it
> >> allocates and copies or not. If I want to append to a range, I
> >> will write the extra line to create a copy manually.
> >> Because of that I don't need the syntactic ambiguity of
> >> treating
> >> a range the same as an array.
> > 
> > In general, you can't append to ranges.
> 
> I assume Malte really meant slices, not ranges.

Well, there's no difference between a slice of an array and an array. There's 
no point in distinguishing them, and it's just going to cause confusion if you 
try and think of them as being any different from one another. Similarly, 
thinking of a dynamic array as a container is a bit mistaken, because dynamic 
arrays don't own or manage their own memory. The runtime does.

If you want an array that is never sliced, you have to make sure of that 
yourself (probably by wrapping it in class - even wrapping it in a struct 
wouldn't work, since it would be sliced when the struct was copied), and if 
you want to avoid reallocating when appending in the face of removing elements 
from the array, you'll have to manage that yourself as well. But if you're 
going that far to manage your own arrays, and you're wrapping them in another 
type, it might make the most sense to just not use arrays but rather allocate 
the memory yourself with malloc, and then have the wrapper manage its length. 
You lose concatenation and whatnot, but it's probably more efficient that way, 
and you avoid the problem of potentially screwing up and ending up with 
reallocations that you didn't expect. Dynamic arrays are meant to be 
sliceable, and trying to avoid letting them be sliced or otherwise letting the 
runtime manage them is likely more trouble than it's worth.

- Jonathan M Davis
November 07, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
On Wednesday, 7 November 2012 at 03:45:06 UTC, Malte Skarupke 
wrote:
> Having no clear ownership for the array is not something I am 
> willing to accept.

"Strong ownership" puts you back into C++'s boat of "bordering 
psychotic duplication on every pass by value". In a GC language, 
and in particular, D, that favors pass by value, this might not 
be the best approach.

I'll re-iterate that you may consider looking into 
std.container.Array. It behaves much like would std::vector 
(reserve, etc)... You can extract an actual range from Array, but 
there is a clear "container" - "range" distinction.

An added bonus is that it uses "implicit reference" semantics. 
This means that when you write "a = b", then afterwards, you have 
"a is b", and they are basically alias. This is a good thing, as 
it avoids payload duplication without your explicit consent. The 
implicit means that it will lazily initialize if you haven't done 
so yet.

You claim you want "explicit ownership": Array gives you that, 
but not in the classic RAII sense. If you need to duplicate an 
Array, you call "dup" manually.

--------
Also, Array uses a deterministic memory model, just like vector, 
that releases content as soon as it goes out of scope. I could 
have done without that, personally, but to each their own.
November 07, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
On Wednesday, November 07, 2012 10:45:46 monarch_dodra wrote:
> Also, Array uses a deterministic memory model, just like vector,
> that releases content as soon as it goes out of scope. I could
> have done without that, personally, but to each their own.

Yes. The built-in arrays work extremely well as they are designed, but they 
are _not_ meant for cases where you need the array to have specific ownership.

It appears that Array is using malloc and free internally (including telling 
the GC about it so that it's scanned for references/pointers as appropriate), 
so it doesn't even have to worry about stuff like assumeSafeAppend. It's very 
much in line with std::vector and what should be used if you want something 
similar to std::vector.

By the way, monarch_dodra, since you've been messing around with Array 
recently, I would point out that it looks like setting the length doesn't work 
properly if you set it greater than the current length, let alone greater than 
the current capacity.  _capacity is not adjusted if newLength is greater than 
it, and no calls to GC.removeRange or GC.addRange are made, so it doesn't look 
like newly allocated memory is being tracked by the GC like it should if 
length is allocating it. And I find the whole length vs capacity bit in Array 
highly confusing, because it looks like the length of the payload is used for 
length, when I would have expected the length of the payload to be the 
capacity and for there to be a separate length for the actual number of 
elements. So, I really don't know what's going on with std.array.Array's 
implementation without studying it a lot more - hopefully you do. But at 
minimimu, I'd advise verifying that the GC.addRange and GC.removeRange calls 
are being correctly done, because regardless of what the deal is with capacity 
vs length, it seems seriously off to me that no GC functions are called when a 
realloc is made.

- Jonathan M Davis
November 07, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
On Wednesday, 7 November 2012 at 10:18:51 UTC, Jonathan M Davis 
wrote:
> And I find the whole length vs capacity bit in Array
> highly confusing, because it looks like the length of the 
> payload is used for
> length, when I would have expected the length of the payload to 
> be the
> capacity and for there to be a separate length for the actual 
> number of
> elements.

I was confused the first time too, but the payload's "slice" in 
only as big as the elements it is holding, and it "knows" there 
is more room after the slice, up to _capacity.

This keeps things relatively simpler for most of Array's 
implementation, and keeps all the complexity inside the Payload 
structure.

So yeah, their semantic is what you'd expect actually.

On Wednesday, 7 November 2012 at 10:18:51 UTC, Jonathan M Davis 
wrote:
> By the way, monarch_dodra, since you've been messing around 
> with Array
> recently, I would point out that it looks like setting the 
> length doesn't work
> properly if you set it greater than the current length, let 
> alone greater than
> the current capacity.  _capacity is not adjusted if newLength 
> is greater than
> it, and no calls to GC.removeRange or GC.addRange are made, so 
> it doesn't look
> like newly allocated memory is being tracked by the GC like it 
> should if
> length is allocating it.

I kind of wanted to stay out of that part of the code, but good 
catch. This creates an assertion error:
--------
    auto a = Array!int();
    a.length = 5;
    a.insertBack(1);
--------
Because at the point of insert back, length > capacity...

I'll correct the issues anyways. Good point about the 
GC.removeRange a,d GC.addRange too.
November 08, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
11/7/2012 2:44 PM, monarch_dodra пишет:
> On Wednesday, 7 November 2012 at 10:18:51 UTC, Jonathan M Davis wrote:
>> By the way, monarch_dodra, since you've been messing around with Array
>> recently, I would point out that it looks like setting the length
>> doesn't work
>> properly if you set it greater than the current length, let alone
>> greater than
>> the current capacity.  _capacity is not adjusted if newLength is
>> greater than
>> it, and no calls to GC.removeRange or GC.addRange are made, so it
>> doesn't look
>> like newly allocated memory is being tracked by the GC like it should if
>> length is allocating it.
>
> I kind of wanted to stay out of that part of the code, but good catch.
> This creates an assertion error:
> --------
>      auto a = Array!int();
>      a.length = 5;
>      a.insertBack(1);
> --------
> Because at the point of insert back, length > capacity...
>
> I'll correct the issues anyways. Good point about the GC.removeRange a,d
> GC.addRange too.

The ugly truth is that std.container even the most primitive collections 
are not tested well enough.

The stuff should have obligatory notes about it being *experimental* 
somewhere prominent so that people don't get tied strongly to its 
current behavior prematurely and don't get appalled because of the 
amount of bugs lurking inside.

That and it being quite novel in general (sealed containers, only range 
iteration/insertion/removal etc.) more then justifies the *experimental* 
status.


-- 
Dmitry Olshansky
November 08, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
On Thursday, November 08, 2012 21:39:53 Dmitry Olshansky wrote:
> The ugly truth is that std.container even the most primitive collections
> are not tested well enough.
> 
> The stuff should have obligatory notes about it being *experimental*
> somewhere prominent so that people don't get tied strongly to its
> current behavior prematurely and don't get appalled because of the
> amount of bugs lurking inside.
> 
> That and it being quite novel in general (sealed containers, only range
> iteration/insertion/removal etc.) more then justifies the *experimental*
> status.

I agree. And it's in definite need of an overhaul. It's a good start, but in 
particular, all of the range stuff in it is completely new, and it definitely 
needs work even just from an API standpoint. I expect that in some cases, 
we're going to either have to break people's code or create std.container2 to 
sort it out, and that's not even taking the custom allocators into account 
(though depending, they may be able to be added without actually breaking any 
code).

- Jonathan M Davis
November 09, 2012
Re: How do you remove/insert elements in a dynamic array without allocating?
On Wednesday, 7 November 2012 at 09:45:48 UTC, monarch_dodra 
wrote:
> On Wednesday, 7 November 2012 at 03:45:06 UTC, Malte Skarupke 
> wrote:
>> Having no clear ownership for the array is not something I am 
>> willing to accept.
>
> "Strong ownership" puts you back into C++'s boat of "bordering 
> psychotic duplication on every pass by value". In a GC 
> language, and in particular, D, that favors pass by value, this 
> might not be the best approach.
>
> I'll re-iterate that you may consider looking into 
> std.container.Array. It behaves much like would std::vector 
> (reserve, etc)... You can extract an actual range from Array, 
> but there is a clear "container" - "range" distinction.
>
> An added bonus is that it uses "implicit reference" semantics. 
> This means that when you write "a = b", then afterwards, you 
> have "a is b", and they are basically alias. This is a good 
> thing, as it avoids payload duplication without your explicit 
> consent. The implicit means that it will lazily initialize if 
> you haven't done so yet.
>
> You claim you want "explicit ownership": Array gives you that, 
> but not in the classic RAII sense. If you need to duplicate an 
> Array, you call "dup" manually.
>
> --------
> Also, Array uses a deterministic memory model, just like 
> vector, that releases content as soon as it goes out of scope. 
> I could have done without that, personally, but to each their 
> own.

I think we have just had different experiences. In my experience 
a shared_ptr is usually not what you want. Instead I prefer a 
unique_ptr in many cases. Just because multiple things are 
referencing your data, that doesn't mean that they should all 
share ownership of it.

For me well defined ownership is just good coding practice, 
similar to the const keyword. I've seen it prevent bugs and 
therefore I use it for all cases that I can. I prefer to have 
those exceptions where I can not have clear ownership stand out, 
rather than them being the norm.
Next ›   Last »
1 2
Top | Discussion index | About this forum | D home