digitalmars.D - The Demise of Dynamic Arrays?!
- S (53/53) Dec 14 2009 Excuse me, because I haven't been active in the D community the last
- Denis Koroskin (2/2) Dec 15 2009 Dynamic arrays aren't going anywhere. It's a new concept that was about ...
- Lars T. Kyllingstad (7/75) Dec 15 2009 This page describes the current future plans for D2 and Phobos, and is
- S (8/86) Dec 15 2009 Me reading that section was the motivation for this post. I don't see
- Steven Schveighoffer (8/18) Dec 15 2009 It's not going away. The plan as I understand it(*) is to fix dynamic
- retard (5/29) Dec 15 2009 Most likely Walter won't even tell what kind of arrays D2 will have.
- Andrei Alexandrescu (6/35) Dec 15 2009 That's a bit of an oxymoron isn't it :o). The book _is_ the
- retard (10/47) Dec 15 2009 I guess the book would be The Documentation (tm) in a perfect world :)
- Don (3/50) Dec 15 2009 Yes, but the book is different. You change the spec on the website with
- Andrei Alexandrescu (8/55) Dec 15 2009 There are only few design decisions that I can think of as patently bad....
- S (17/56) Dec 15 2009 Alright Andrei,
- Andrei Alexandrescu (9/71) Dec 15 2009 Thank you, but I think you are overrating my expertise. I can't claim I
- grauzone (4/16) Dec 16 2009 So the book _is_ the documentation?
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
"Denis Koroskin" <2korden gmail.com> Dynamic arrays aren't going anywhere. It's a new concept that was about to be introduced was dismissed.
Dec 15 2009
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
On 2009-12-15 00:15:17 -0800, "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> said:S wrote: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.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
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
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: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.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
retard wrote:Tue, 15 Dec 2009 09:42:26 -0500, Steven Schveighoffer wrote: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 AndreiOn Tue, 15 Dec 2009 02:25:11 -0500, S <S s.com> 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.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
Tue, 15 Dec 2009 10:21:04 -0800, Andrei Alexandrescu wrote:retard wrote: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.Tue, 15 Dec 2009 09:42:26 -0500, Steven Schveighoffer wrote: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.pdfOn Tue, 15 Dec 2009 02:25:11 -0500, S <S s.com> 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.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
retard wrote:Tue, 15 Dec 2009 10:21:04 -0800, Andrei Alexandrescu wrote: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>retard wrote: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.Tue, 15 Dec 2009 09:42:26 -0500, Steven Schveighoffer wrote: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.pdfOn Tue, 15 Dec 2009 02:25:11 -0500, S <S s.com> 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.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.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
retard wrote:Tue, 15 Dec 2009 10:21:04 -0800, Andrei Alexandrescu wrote:Walter and I keep 100% in agreement regarding the contents of TDPL.retard wrote: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.Tue, 15 Dec 2009 09:42:26 -0500, Steven Schveighoffer wrote: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.pdfOn Tue, 15 Dec 2009 02:25:11 -0500, S <S s.com> 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.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.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
On 2009-12-15 10:21:04 -0800, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:retard wrote: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?Tue, 15 Dec 2009 09:42:26 -0500, Steven Schveighoffer wrote: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 AndreiOn Tue, 15 Dec 2009 02:25:11 -0500, S <S s.com> 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.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
S wrote:On 2009-12-15 10:21:04 -0800, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:Thank you, but I think you are overrating my expertise. I can't claim I am a programming language designer.retard wrote:Alright Andrei, I respect your expertise. I'm going to go read this chapter and then give you a piece of my mind.Tue, 15 Dec 2009 09:42:26 -0500, Steven Schveighoffer wrote: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 AndreiOn Tue, 15 Dec 2009 02:25:11 -0500, S <S s.com> 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.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.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
Andrei Alexandrescu wrote:retard wrote:So the book _is_ the documentation? I suddenly found the reason why D's documentation/specification is do damn bad!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 16 2009