www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - The Demise of Dynamic Arrays?!

reply S <S S.com> writes:
Excuse me, because I haven't been active in the D community the last 
year due to school concerns.  However, I have been  fiddling with the 
language and on this newsgroups since 2001.

As I understand it, dynamic arrays are going away  soon in D2.0 in 
favor of an ArrayBuilder class.

I don't like it at all.  I want to stomp my feet and throw a temper 
tantrum.   As far as I am concerned, T[] has always been an 
array-builder.   Now, I'd appreciate some considering, and that you'll 
excuse my poor phrasing when it comes to terminology (I am not a 
trained computer scientist).

For the last 9 years there has been problems with dynamic arrays.   
Now, I intend to enumerate the problems I have encountered and propose 
some solutions, but let me first describe the internals of the D Arrays 
as I understand them:  (To simplify)

struct Array(T) {
	T* ptr;
	uint length;
}

So, D basically wraps this with various syntatic sugar.   Now, there 
have been a variety of probelsm with using this same type for dynamic 
arrays:

1)  It has failed as an array builder because it does not contain the 
length of the memory it references AS WELL as the actually number of 
elements stored.   Thus cannot do pre-allocation like vector<> in 
C++STL without some GC magic.   This make it slow to append.

1-Solution) So, add an additional real_length parameter to dynamic arrays.....

2) If you take a slice, it often doesn't behave as expected.   
Implement a new type T[..] that are specifically slices of other 
arrays.     This will add another parameter that references the array 
the slice came from.   Thus, appending to a slice can behave as an 
insertion into it's parent and other syntatic niceties.

2-Solution) I propose that this type Arr[..]  would be implicitely 
castable to other array types, at the expense of a dup.

3) If dynamic arrays are passed, they pass the aformentioned struct 
"by-value."  This however results in the ptr NOT being shared by the 
function and its caller.   So, if a receiving function tries to append 
to them it is possible that the sender doesn't notice the array has 
been moved by the memory manager.

3-Solution)  So, since static arrays are now pass-by-value.   Make this 
true for dynamic arrays also, and provide a warning of some sort.    
This would give you the expected read-only sematics of passing values 
instead of the C one where [] == *.  Instead the proper way to pass a 
read-write dynamic array would be by reference (AKA a Handle  ... 
Computer Scientists solved this problem along time ago:  
http://en.wikipedia.org/wiki/Handle_%28computing%29 ).    Now, this 
causes some overhead in terms fo double look-ups for classes which 
might not need to change the pointer address -- maybe there is some way 
around doing this also though?


*********   Did I miss anything?   Maybe my solutions are incomplete?  
Please comment and revise this.    I think it would be a shame to get 
rid of the syntatic sugar of dynamic arrays in support of an 
ArrayBuilder class/struct.

-S.
Dec 14 2009
next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
Dynamic arrays aren't going anywhere. It's a new concept that was about to  
be introduced was dismissed.
Dec 15 2009
prev sibling next sibling parent reply "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> writes:
S wrote:
 Excuse me, because I haven't been active in the D community the last 
 year due to school concerns.  However, I have been  fiddling with the 
 language and on this newsgroups since 2001.
 
 As I understand it, dynamic arrays are going away  soon in D2.0 in favor 
 of an ArrayBuilder class.
 
 I don't like it at all.  I want to stomp my feet and throw a temper 
 tantrum.   As far as I am concerned, T[] has always been an 
 array-builder.   Now, I'd appreciate some considering, and that you'll 
 excuse my poor phrasing when it comes to terminology (I am not a trained 
 computer scientist).
 
 For the last 9 years there has been problems with dynamic arrays.   Now, 
 I intend to enumerate the problems I have encountered and propose some 
 solutions, but let me first describe the internals of the D Arrays as I 
 understand them:  (To simplify)
 
 struct Array(T) {
     T* ptr;
     uint length;
 }
 
 So, D basically wraps this with various syntatic sugar.   Now, there 
 have been a variety of probelsm with using this same type for dynamic 
 arrays:
 
 1)  It has failed as an array builder because it does not contain the 
 length of the memory it references AS WELL as the actually number of 
 elements stored.   Thus cannot do pre-allocation like vector<> in C++STL 
 without some GC magic.   This make it slow to append.
 
 1-Solution) So, add an additional real_length parameter to dynamic 
 arrays.....
 
 2) If you take a slice, it often doesn't behave as expected.   Implement 
 a new type T[..] that are specifically slices of other arrays.     This 
 will add another parameter that references the array the slice came 
 from.   Thus, appending to a slice can behave as an insertion into it's 
 parent and other syntatic niceties.
 
 2-Solution) I propose that this type Arr[..]  would be implicitely 
 castable to other array types, at the expense of a dup.
 
 3) If dynamic arrays are passed, they pass the aformentioned struct 
 "by-value."  This however results in the ptr NOT being shared by the 
 function and its caller.   So, if a receiving function tries to append 
 to them it is possible that the sender doesn't notice the array has been 
 moved by the memory manager.
 
 3-Solution)  So, since static arrays are now pass-by-value.   Make this 
 true for dynamic arrays also, and provide a warning of some sort.    
 This would give you the expected read-only sematics of passing values 
 instead of the C one where [] == *.  Instead the proper way to pass a 
 read-write dynamic array would be by reference (AKA a Handle  ... 
 Computer Scientists solved this problem along time ago:  
 http://en.wikipedia.org/wiki/Handle_%28computing%29 ).    Now, this 
 causes some overhead in terms fo double look-ups for classes which might 
 not need to change the pointer address -- maybe there is some way around 
 doing this also though?
 
 
 *********   Did I miss anything?   Maybe my solutions are incomplete?  
 Please comment and revise this.    I think it would be a shame to get 
 rid of the syntatic sugar of dynamic arrays in support of an 
 ArrayBuilder class/struct.
 
 -S.

This page describes the current future plans for D2 and Phobos, and is actually pretty much up-to-date: http://www.prowiki.org/wiki4d/wiki.cgi?LanguageDevel The section "Probably no longer required" near the bottom contains some links to the array discussions. -Lars
Dec 15 2009
parent S <S S.com> writes:
On 2009-12-15 00:15:17 -0800, "Lars T. Kyllingstad" 
<public kyllingen.NOSPAMnet> said:

 S wrote:
 Excuse me, because I haven't been active in the D community the last 
 year due to school concerns.  However, I have been  fiddling with the 
 language and on this newsgroups since 2001.
 
 As I understand it, dynamic arrays are going away  soon in D2.0 in 
 favor of an ArrayBuilder class.
 
 I don't like it at all.  I want to stomp my feet and throw a temper 
 tantrum.   As far as I am concerned, T[] has always been an 
 array-builder.   Now, I'd appreciate some considering, and that you'll 
 excuse my poor phrasing when it comes to terminology (I am not a 
 trained computer scientist).
 
 For the last 9 years there has been problems with dynamic arrays.   
 Now, I intend to enumerate the problems I have encountered and propose 
 some solutions, but let me first describe the internals of the D Arrays 
 as I understand them:  (To simplify)
 
 struct Array(T) {
     T* ptr;
     uint length;
 }
 
 So, D basically wraps this with various syntatic sugar.   Now, there 
 have been a variety of probelsm with using this same type for dynamic 
 arrays:
 
 1)  It has failed as an array builder because it does not contain the 
 length of the memory it references AS WELL as the actually number of 
 elements stored.   Thus cannot do pre-allocation like vector<> in 
 C++STL without some GC magic.   This make it slow to append.
 
 1-Solution) So, add an additional real_length parameter to dynamic arrays.....
 
 2) If you take a slice, it often doesn't behave as expected.   
 Implement a new type T[..] that are specifically slices of other 
 arrays.     This will add another parameter that references the array 
 the slice came from.   Thus, appending to a slice can behave as an 
 insertion into it's parent and other syntatic niceties.
 
 2-Solution) I propose that this type Arr[..]  would be implicitely 
 castable to other array types, at the expense of a dup.
 
 3) If dynamic arrays are passed, they pass the aformentioned struct 
 "by-value."  This however results in the ptr NOT being shared by the 
 function and its caller.   So, if a receiving function tries to append 
 to them it is possible that the sender doesn't notice the array has 
 been moved by the memory manager.
 
 3-Solution)  So, since static arrays are now pass-by-value.   Make this 
 true for dynamic arrays also, and provide a warning of some sort.    
 This would give you the expected read-only sematics of passing values 
 instead of the C one where [] == *.  Instead the proper way to pass a 
 read-write dynamic array would be by reference (AKA a Handle  ... 
 Computer Scientists solved this problem along time ago:  
 http://en.wikipedia.org/wiki/Handle_%28computing%29 ).    Now, this 
 causes some overhead in terms fo double look-ups for classes which 
 might not need to change the pointer address -- maybe there is some way 
 around doing this also though?
 
 
 *********   Did I miss anything?   Maybe my solutions are incomplete?  
 Please comment and revise this.    I think it would be a shame to get 
 rid of the syntatic sugar of dynamic arrays in support of an 
 ArrayBuilder class/struct.
 
 -S.

This page describes the current future plans for D2 and Phobos, and is actually pretty much up-to-date: http://www.prowiki.org/wiki4d/wiki.cgi?LanguageDevel The section "Probably no longer required" near the bottom contains some links to the array discussions. -Lars

Me reading that section was the motivation for this post. I don't see how any of the proposed solutions obviate the 3 main problems with arrays in D that I listed above? Even the current one with thread-local-caching doesn't fix the misbehaviorof slices and arrays having psuedo-reference semantics. -S.
Dec 15 2009
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 15 Dec 2009 02:25:11 -0500, S <S s.com> wrote:

 Excuse me, because I haven't been active in the D community the last  
 year due to school concerns.  However, I have been  fiddling with the  
 language and on this newsgroups since 2001.

 As I understand it, dynamic arrays are going away  soon in D2.0 in favor  
 of an ArrayBuilder class.

 I don't like it at all.  I want to stomp my feet and throw a temper  
 tantrum.   As far as I am concerned, T[] has always been an  
 array-builder.   Now, I'd appreciate some considering, and that you'll  
 excuse my poor phrasing when it comes to terminology (I am not a trained  
 computer scientist).

It's not going away. The plan as I understand it(*) is to fix dynamic array stomping problems, and make thread-local dynamic arrays append efficiently without using the GC lock where possible. -Steve (*) I am not Walter Bright/Andrei Alexandrescu and so I do not have any final word on what makes it into D2 or not, these are just speculations from communications I've been involved in.
Dec 15 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
retard wrote:
 Tue, 15 Dec 2009 09:42:26 -0500, Steven Schveighoffer wrote:
 
 On Tue, 15 Dec 2009 02:25:11 -0500, S <S s.com> wrote:

 Excuse me, because I haven't been active in the D community the last
 year due to school concerns.  However, I have been  fiddling with the
 language and on this newsgroups since 2001.

 As I understand it, dynamic arrays are going away  soon in D2.0 in
 favor of an ArrayBuilder class.

 I don't like it at all.  I want to stomp my feet and throw a temper
 tantrum.   As far as I am concerned, T[] has always been an
 array-builder.   Now, I'd appreciate some considering, and that you'll
 excuse my poor phrasing when it comes to terminology (I am not a
 trained computer scientist).

array stomping problems, and make thread-local dynamic arrays append efficiently without using the GC lock where possible. -Steve (*) I am not Walter Bright/Andrei Alexandrescu and so I do not have any final word on what makes it into D2 or not, these are just speculations from communications I've been involved in.

Most likely Walter won't even tell what kind of arrays D2 will have. Anything can happen. The final word is the undocumented executable you can download when the book hits stores.

That's a bit of an oxymoron isn't it :o). The book _is_ the documentation, and the chapter dedicated to arrays has been public for a while. http://erdani.com/d/thermopylae.pdf Andrei
Dec 15 2009
next sibling parent Don <nospam nospam.com> writes:
retard wrote:
 Tue, 15 Dec 2009 10:21:04 -0800, Andrei Alexandrescu wrote:
 
 retard wrote:
 Tue, 15 Dec 2009 09:42:26 -0500, Steven Schveighoffer wrote:

 On Tue, 15 Dec 2009 02:25:11 -0500, S <S s.com> wrote:

 Excuse me, because I haven't been active in the D community the last
 year due to school concerns.  However, I have been  fiddling with the
 language and on this newsgroups since 2001.

 As I understand it, dynamic arrays are going away  soon in D2.0 in
 favor of an ArrayBuilder class.

 I don't like it at all.  I want to stomp my feet and throw a temper
 tantrum.   As far as I am concerned, T[] has always been an
 array-builder.   Now, I'd appreciate some considering, and that
 you'll excuse my poor phrasing when it comes to terminology (I am not
 a trained computer scientist).

array stomping problems, and make thread-local dynamic arrays append efficiently without using the GC lock where possible. -Steve (*) I am not Walter Bright/Andrei Alexandrescu and so I do not have any final word on what makes it into D2 or not, these are just speculations from communications I've been involved in.

Anything can happen. The final word is the undocumented executable you can download when the book hits stores.

documentation, and the chapter dedicated to arrays has been public for a while. http://erdani.com/d/thermopylae.pdf

I guess the book would be The Documentation (tm) in a perfect world :) However, if Walter doesn't say anything, that can as well mean that he didn't like the contemporary compromise. Many things in D have changed so many times that I cannot really tell when the decision is final.

Yes, but the book is different. You change the spec on the website with 10 minutes notice, but you can't change the text in printed books. <g>
 Sometimes articulating even bad design decisions is better than staying 
 quiet. People widely acknowledge that some features in some language are 
 really bad, but since their authors have decided not to change those 
 anymore, the language users can rely on it, and some form of trust is 
 established.

Dec 15 2009
prev sibling next sibling parent reply S <S S.com> writes:
On 2009-12-15 10:21:04 -0800, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:

 retard wrote:
 Tue, 15 Dec 2009 09:42:26 -0500, Steven Schveighoffer wrote:
 
 On Tue, 15 Dec 2009 02:25:11 -0500, S <S s.com> wrote:
 
 Excuse me, because I haven't been active in the D community the last
 year due to school concerns.  However, I have been  fiddling with the
 language and on this newsgroups since 2001.
 
 As I understand it, dynamic arrays are going away  soon in D2.0 in
 favor of an ArrayBuilder class.
 
 I don't like it at all.  I want to stomp my feet and throw a temper
 tantrum.   As far as I am concerned, T[] has always been an
 array-builder.   Now, I'd appreciate some considering, and that you'll
 excuse my poor phrasing when it comes to terminology (I am not a
 trained computer scientist).

array stomping problems, and make thread-local dynamic arrays append efficiently without using the GC lock where possible. -Steve (*) I am not Walter Bright/Andrei Alexandrescu and so I do not have any final word on what makes it into D2 or not, these are just speculations from communications I've been involved in.

Most likely Walter won't even tell what kind of arrays D2 will have. Anything can happen. The final word is the undocumented executable you can download when the book hits stores.

That's a bit of an oxymoron isn't it :o). The book _is_ the documentation, and the chapter dedicated to arrays has been public for a while. http://erdani.com/d/thermopylae.pdf Andrei

Alright Andrei, I respect your expertise. I'm going to go read this chapter and then give you a piece of my mind. But I will say this -- I hope the solutoin is good :) Pretty much all the arrays in D are messed up, and have been that way for the last 10 years since they "sort of behave" like Python, and "sort of behave" like C. This code is listed as nonfunctioning: int[] a = [0, 10, 20, 30, 40, 50, 60, 70]; auto b = a[4 .. $]; a=a[0..4]; // At this point a and b are adjacent a ~= [0, 0, 0, 0]; assert(b == [40, 50, 60, 70]); // passes; a got reallocated But how is it ever supposed to work. Does the GC look at more than start block addresses?
Dec 15 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
S wrote:
 On 2009-12-15 10:21:04 -0800, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org> said:
 
 retard wrote:
 Tue, 15 Dec 2009 09:42:26 -0500, Steven Schveighoffer wrote:

 On Tue, 15 Dec 2009 02:25:11 -0500, S <S s.com> wrote:

 Excuse me, because I haven't been active in the D community the last
 year due to school concerns.  However, I have been  fiddling with the
 language and on this newsgroups since 2001.

 As I understand it, dynamic arrays are going away  soon in D2.0 in
 favor of an ArrayBuilder class.

 I don't like it at all.  I want to stomp my feet and throw a temper
 tantrum.   As far as I am concerned, T[] has always been an
 array-builder.   Now, I'd appreciate some considering, and that you'll
 excuse my poor phrasing when it comes to terminology (I am not a
 trained computer scientist).

array stomping problems, and make thread-local dynamic arrays append efficiently without using the GC lock where possible. -Steve (*) I am not Walter Bright/Andrei Alexandrescu and so I do not have any final word on what makes it into D2 or not, these are just speculations from communications I've been involved in.

Most likely Walter won't even tell what kind of arrays D2 will have. Anything can happen. The final word is the undocumented executable you can download when the book hits stores.

That's a bit of an oxymoron isn't it :o). The book _is_ the documentation, and the chapter dedicated to arrays has been public for a while. http://erdani.com/d/thermopylae.pdf Andrei

Alright Andrei, I respect your expertise. I'm going to go read this chapter and then give you a piece of my mind.

Thank you, but I think you are overrating my expertise. I can't claim I am a programming language designer.
 But I will say this -- I hope the solutoin is good :)  Pretty much all 
 the arrays in D are messed up, and have been that way for the last 10 
 years since they "sort of behave" like Python, and "sort of behave" like C.
 
 This code is listed as nonfunctioning:
 
 int[] a = [0, 10, 20, 30, 40, 50, 60, 70];
 auto b = a[4 .. $];
 a=a[0..4]; // At this point a and b are adjacent
 a ~= [0, 0, 0, 0];
 assert(b == [40, 50, 60, 70]); // passes; a got reallocated
 
 But how is it ever supposed to work.   Does the GC look at more than 
 start block addresses?
 

There was a long thread regarding this matter, entitled "LRU cache for ~=". You may want to look it up. The thread title is due to me and has a mistake, it should have been "MRU" = most recently used. "LRU" is the negation of that, reflecting the eviction policy (least recently used entry is evicted). Andrei
Dec 15 2009
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
retard wrote:
 Tue, 15 Dec 2009 10:21:04 -0800, Andrei Alexandrescu wrote:
 
 retard wrote:
 Tue, 15 Dec 2009 09:42:26 -0500, Steven Schveighoffer wrote:

 On Tue, 15 Dec 2009 02:25:11 -0500, S <S s.com> wrote:

 Excuse me, because I haven't been active in the D community the last
 year due to school concerns.  However, I have been  fiddling with the
 language and on this newsgroups since 2001.

 As I understand it, dynamic arrays are going away  soon in D2.0 in
 favor of an ArrayBuilder class.

 I don't like it at all.  I want to stomp my feet and throw a temper
 tantrum.   As far as I am concerned, T[] has always been an
 array-builder.   Now, I'd appreciate some considering, and that
 you'll excuse my poor phrasing when it comes to terminology (I am not
 a trained computer scientist).

array stomping problems, and make thread-local dynamic arrays append efficiently without using the GC lock where possible. -Steve (*) I am not Walter Bright/Andrei Alexandrescu and so I do not have any final word on what makes it into D2 or not, these are just speculations from communications I've been involved in.

Anything can happen. The final word is the undocumented executable you can download when the book hits stores.

documentation, and the chapter dedicated to arrays has been public for a while. http://erdani.com/d/thermopylae.pdf

I guess the book would be The Documentation (tm) in a perfect world :) However, if Walter doesn't say anything, that can as well mean that he didn't like the contemporary compromise. Many things in D have changed so many times that I cannot really tell when the decision is final.

Walter and I keep 100% in agreement regarding the contents of TDPL.
 Sometimes articulating even bad design decisions is better than staying 
 quiet. People widely acknowledge that some features in some language are 
 really bad, but since their authors have decided not to change those 
 anymore, the language users can rely on it, and some form of trust is 
 established.

There are only few design decisions that I can think of as patently bad. I think by and large D does considerably better than average in terms of warts it needs to live with. Many design awkwardnesses are simply because we didn't know how to do better. Some others are the best we could choose to satisfy an intricate web of compromises. Andrei
Dec 15 2009
prev sibling parent grauzone <none example.net> writes:
Andrei Alexandrescu wrote:
 retard wrote:
 Most likely Walter won't even tell what kind of arrays D2 will have. 
 Anything can happen. The final word is the undocumented executable you 
 can download when the book hits stores.

That's a bit of an oxymoron isn't it :o). The book _is_ the documentation, and the chapter dedicated to arrays has been public for a while.

So the book _is_ the documentation? I suddenly found the reason why D's documentation/specification is do damn bad!
 http://erdani.com/d/thermopylae.pdf
 
 
 Andrei

Dec 16 2009
prev sibling next sibling parent retard <re tard.com.invalid> writes:
Tue, 15 Dec 2009 09:42:26 -0500, Steven Schveighoffer wrote:

 On Tue, 15 Dec 2009 02:25:11 -0500, S <S s.com> wrote:
 
 Excuse me, because I haven't been active in the D community the last
 year due to school concerns.  However, I have been  fiddling with the
 language and on this newsgroups since 2001.

 As I understand it, dynamic arrays are going away  soon in D2.0 in
 favor of an ArrayBuilder class.

 I don't like it at all.  I want to stomp my feet and throw a temper
 tantrum.   As far as I am concerned, T[] has always been an
 array-builder.   Now, I'd appreciate some considering, and that you'll
 excuse my poor phrasing when it comes to terminology (I am not a
 trained computer scientist).

It's not going away. The plan as I understand it(*) is to fix dynamic array stomping problems, and make thread-local dynamic arrays append efficiently without using the GC lock where possible. -Steve (*) I am not Walter Bright/Andrei Alexandrescu and so I do not have any final word on what makes it into D2 or not, these are just speculations from communications I've been involved in.

Most likely Walter won't even tell what kind of arrays D2 will have. Anything can happen. The final word is the undocumented executable you can download when the book hits stores. Even then dmd's behavior isn't the final word, it might as well be a bug.
Dec 15 2009
prev sibling parent retard <re tard.com.invalid> writes:
Tue, 15 Dec 2009 10:21:04 -0800, Andrei Alexandrescu wrote:

 retard wrote:
 Tue, 15 Dec 2009 09:42:26 -0500, Steven Schveighoffer wrote:
 
 On Tue, 15 Dec 2009 02:25:11 -0500, S <S s.com> wrote:

 Excuse me, because I haven't been active in the D community the last
 year due to school concerns.  However, I have been  fiddling with the
 language and on this newsgroups since 2001.

 As I understand it, dynamic arrays are going away  soon in D2.0 in
 favor of an ArrayBuilder class.

 I don't like it at all.  I want to stomp my feet and throw a temper
 tantrum.   As far as I am concerned, T[] has always been an
 array-builder.   Now, I'd appreciate some considering, and that
 you'll excuse my poor phrasing when it comes to terminology (I am not
 a trained computer scientist).

array stomping problems, and make thread-local dynamic arrays append efficiently without using the GC lock where possible. -Steve (*) I am not Walter Bright/Andrei Alexandrescu and so I do not have any final word on what makes it into D2 or not, these are just speculations from communications I've been involved in.

Most likely Walter won't even tell what kind of arrays D2 will have. Anything can happen. The final word is the undocumented executable you can download when the book hits stores.

That's a bit of an oxymoron isn't it :o). The book _is_ the documentation, and the chapter dedicated to arrays has been public for a while. http://erdani.com/d/thermopylae.pdf

I guess the book would be The Documentation (tm) in a perfect world :) However, if Walter doesn't say anything, that can as well mean that he didn't like the contemporary compromise. Many things in D have changed so many times that I cannot really tell when the decision is final. Sometimes articulating even bad design decisions is better than staying quiet. People widely acknowledge that some features in some language are really bad, but since their authors have decided not to change those anymore, the language users can rely on it, and some form of trust is established.
Dec 15 2009