www.digitalmars.com         C & C++   DMDScript  

D - array length question

reply "chris jones" <flak clara.co.uk> writes:
Hi, reading the specs i see that a dynamic array is pointer/length pair. So
how does an array referance know when the array length has beend changed
elsewhere in the program? It just strikes me that this could cause problems
if the length is not tied to the array but tied to the 'pointer to the
array'. Also it seems that this would be a very ineficant way to pass
arrays/strings as parameters, many calls that would have beed suitible for
register calling conevention will now need to be stack based.

chris
Oct 02 2002
parent reply "Walter" <walter digitalmars.com> writes:
"chris jones" <flak clara.co.uk> wrote in message
news:anee9t$gnv$1 digitaldaemon.com...
 Hi, reading the specs i see that a dynamic array is pointer/length pair.

 how does an array referance know when the array length has beend changed
 elsewhere in the program? It just strikes me that this could cause

 if the length is not tied to the array but tied to the 'pointer to the
 array'. Also it seems that this would be a very ineficant way to pass
 arrays/strings as parameters, many calls that would have beed suitible for
 register calling conevention will now need to be stack based.

The length/ptr pair is passed around as one unit. Embedding the length into something the pointer points at would make slices not practical.
Oct 02 2002
parent reply "chris jones" <flak clara.co.uk> writes:
"Walter" <walter digitalmars.com> wrote in message
news:anf2jc$16pe$1 digitaldaemon.com...
 "chris jones" <flak clara.co.uk> wrote in message
 news:anee9t$gnv$1 digitaldaemon.com...
 Hi, reading the specs i see that a dynamic array is pointer/length pair.

 how does an array referance know when the array length has beend changed
 elsewhere in the program? It just strikes me that this could cause

 if the length is not tied to the array but tied to the 'pointer to the
 array'. Also it seems that this would be a very ineficant way to pass
 arrays/strings as parameters, many calls that would have beed suitible


 register calling conevention will now need to be stack based.

The length/ptr pair is passed around as one unit. Embedding the length

 something the pointer points at would make slices not practical.

I can see that it would cause problems with slicing. The thing i am having trouble with is how seperate referances to the same array keep track of its length? If for example you pass an array as a parameter to a function and that function alters the length of the array only the ptr/lgth pair in the function knows the new length, any other referances to the array will still have the old length wont they?
Oct 02 2002
parent reply "Sandor Hojtsy" <hojtsy index.hu> writes:
"chris jones" <flak clara.co.uk> wrote in message
news:ang5id$2bm5$1 digitaldaemon.com...
 Hi, reading the specs i see that a dynamic array is pointer/length



 how does an array referance know when the array length has beend



 elsewhere in the program? It just strikes me that this could cause



 if the length is not tied to the array but tied to the 'pointer to the
 array'. Also it seems that this would be a very ineficant way to pass
 arrays/strings as parameters, many calls that would have beed suitible



 register calling conevention will now need to be stack based.

The length/ptr pair is passed around as one unit. Embedding the length


 something the pointer points at would make slices not practical.

I can see that it would cause problems with slicing. The thing i am having trouble with is how seperate referances to the same array keep track of

 length? If for example you pass an array as a parameter to a function and
 that function alters the length of the array only the ptr/lgth pair in the
 function knows the new length, any other referances to the array will

 have the old length wont they?

I see what you mean. The D array semantics seems to be rich soil for missunderstandings. From the users point of view, arrays are [should be] passed by value, by default. If you pass an array into a function, it can be thought as a copy of the original array. Any change, including the change in the length should not change the original array. If you specify the parameter to be "inout", then every change should change the original array. Lets try! void fn1(int[] a) { a.length = 4; printf("2: a.length = %d\n", a.length); } void fn2(inout int[] a) { a.length = 4; printf("4: a.length = %d\n", a.length); } int main() { int[] a; a.length = 3; printf("1: a.length = %d\n", a.length); fn1(a); printf("3: a.length = %d\n", a.length); fn2(a); printf("5: a.length = %d\n", a.length); return 0; } Output: --------------------------- 1: a.length = 3, a[0] = 0 2: a.length = 4, a[0] = 1 3: a.length = 3, a[0] = 1 // a[0] should be 0 4: a.length = 4, a[0] = 1 5: a.length = 4, a[0] = 1 --------------------------- In fn1 length changes are not incorporated into the original array, but value changes are. Even if the parameter is "in". Which is a Bad Thing! I would even say "bug". ;-) Does the possibility of slicing worth this?! A consistent self-contained array object *definitely* should not work this way. This behaviour in itself makes me want to create an own array class, which behaves in a consistent manner. If you are really want to *force* users to pass all arrays by address, then make that explicit: arrays could only be passed as "inout". Sandor
Oct 03 2002
next sibling parent reply "chris jones" <flak clara.co.uk> writes:
"Sandor Hojtsy" <hojtsy index.hu> wrote in message
news:angtef$3pt$1 digitaldaemon.com...
 I see what you mean. The D array semantics seems to be rich soil for
 missunderstandings.
 From the users point of view, arrays are [should be] passed by value, by
 default. If you pass an array into a function, it can be thought as a copy
 of the original array. Any change, including the change in the length

 not change the original array.
 If you specify the parameter to be "inout", then every change should

 the original array.

I would rather arrays are passed by referance by default. If you want pass by value you can just duplicate the array inside the function.
 In fn1 length changes are not incorporated into the original array, but
 value changes are. Even if the parameter is "in".

This is what troubles me. Arrays as parameters have diferances from all the other parameter types. They are basicly pointers with bounds checking.
 Which is a Bad Thing! I would even say "bug". ;-)
 Does the possibility of slicing worth this?!

I dont know. Slicing does have some great benefits but i just dont like arrays as they are, they seem compromised for the sake of slicing.
 A consistent self-contained array object *definitely* should not work this
 way.

I totally agree. chris.
Oct 03 2002
next sibling parent Mark Evans <Mark_member pathlink.com> writes:
In article <anigdn$1rek$1 digitaldaemon.com>, chris jones says...
I would rather arrays are passed by referance by default. If you want pass
by value you can just duplicate the array inside the function.

Hmm. Every implicit array copy shout emit a compile time warning to alert the programmer, at least. One of the worst things about STL vectors is all that hidden behind-the-scenes array copying. What about making the array's treatment as a function argument just another object property? Could that work? Mark
Oct 03 2002
prev sibling next sibling parent "Sean L. Palmer" <seanpalmer directvinternet.com> writes:
"chris jones" <flak clara.co.uk> wrote in message
news:anigdn$1rek$1 digitaldaemon.com...
 This is what troubles me. Arrays as parameters have diferances from all

 other parameter types. They are basicly pointers with bounds checking.

 I dont know. Slicing does have some great benefits but i just dont like
 arrays as they are, they seem compromised for the sake of slicing.

If that is the case maybe we should reevaluate slicing in terms of the current foreach/iteration problem that is also being worked on. It'd be nice to be able to use a slice as iterator control. But then it'd also be nice to be able to create a slice out of any two iterators. float a[10]; float[] b = a[1..9]; for (i in b) b[i] = 1; for (i in a) print a[i] ','; // prints 0111111110 ... in theory! An arbitrary slice is a base, stride, and either end or size for each dimension. It should be a language requirement that slices can not outlive their array. I would not allow them stored for sure. For instance anywhere you require an array as parameter you have to have code to account for the fact that it could be a slice and thus temporary. References to it should not be able to be stored if the callee was somehow able to outlive the array. Storing references to passed-in arrays isn't a good idea anyway; it's just asking for trouble. Sean
Oct 03 2002
prev sibling parent reply "Walter" <walter digitalmars.com> writes:
"chris jones" <flak clara.co.uk> wrote in message
news:anigdn$1rek$1 digitaldaemon.com...
 This is what troubles me. Arrays as parameters have diferances from all

 other parameter types. They are basicly pointers with bounds checking.

That is essentially correct.
 I dont know. Slicing does have some great benefits but i just dont like
 arrays as they are, they seem compromised for the sake of slicing.

I too initially shared your reluctance for the idea. In a sense the semantics are oriented towards slicing, I know of no other language that does slicing like D does. I think experience will show, however, that once people get used to slicing, they'll find it a huge convenience and performance boost. For example, in most tokenizers I write I build symbols by copying characters from the source into an array, and terminate it with 0. All ordinary C practice. In D, I just slice the source buffer. You can see the same technique in the regular expression compiler, the wc word counting program, etc. Think about routine tasks like picking off path names from a fully qualified filespec. Reorienting the approach from string copying to string slicing is more natural and much more efficient in string processing code.
Oct 12 2002
next sibling parent reply Mark Evans <Mark_member pathlink.com> writes:
 I dont know. Slicing does have some great benefits but i just dont like
 arrays as they are, they seem compromised for the sake of slicing.

I too initially shared your reluctance for the idea. ...once people get used to slicing, they'll find it a huge convenience and performance boost.

Right on, Walter. If Chris wants C arrays let him use C! Mark
Oct 12 2002
parent "chris jones" <flak clara.co.uk> writes:
"Mark Evans" <Mark_member pathlink.com> wrote in message
news:aoa357$1vcr$1 digitaldaemon.com...
 I dont know. Slicing does have some great benefits but i just dont like
 arrays as they are, they seem compromised for the sake of slicing.

I too initially shared your reluctance for the idea. ...once people get used to slicing, they'll find it a huge convenience and performance boost.

Right on, Walter. If Chris wants C arrays let him use C!

I wasnt arguing for C like arrays. More the oposite. chris
Oct 13 2002
prev sibling parent reply Patrick Down <pat codemoon.com> writes:
"Walter" <walter digitalmars.com> wrote in
news:ao9lh9$1gta$1 digitaldaemon.com: 

 
 "chris jones" <flak clara.co.uk> wrote in message
 news:anigdn$1rek$1 digitaldaemon.com...
 This is what troubles me. Arrays as parameters have diferances from
 all 

 other parameter types. They are basicly pointers with bounds
 checking. 

That is essentially correct.
 I dont know. Slicing does have some great benefits but i just dont
 like arrays as they are, they seem compromised for the sake of
 slicing. 

I too initially shared your reluctance for the idea.

When one first reads the D documentation the initial reaction is, "Cool two of the most used high level container types, resizable arrays and maps (assoc array), are implemented in the language." However arrays in D arrays aren't really the high level contain construct that people associate with the STL vector template. Array and slice semantics are going to be the most confusing thing to understand for a new person learning D. I think that you are trying to accomplish two different goals with arrays in D and I think these goals are incompatible. One of the these goals is creating a safe bound checked pointer and the other goal is to use arrays as a container type. You are absolutely correct, slices are very useful constructs for a lot of tasks. However as a container type arrays in D are not as functional as one might desire. As a container arrays should have the object reference semantics. Modify an object one place and all the other references see the change. Right now if you change the array length you run the risk that other array references now don't refer to the same array. I believe you should really separate the concepts of the slice and array. Create two different types. Let the slice play the role of the safe bounds checked pointer and expand arrays to have suitable container semantics for the type.
Oct 12 2002
next sibling parent "Sean L. Palmer" <seanpalmer directvinternet.com> writes:
Yes... slices and arrays are really two different things.  The array is the
actual container and a slice is a reduced functionality subset that's more
like a boundschecked pointer.

I think most of the time when you take an array parameter you should
actually take a slice instead, unless you want a reference to the actual
array.

Sean

"Patrick Down" <pat codemoon.com> wrote in message
news:Xns92A5AF708AFD0patcodemooncom 63.105.9.61...
 "Walter" <walter digitalmars.com> wrote in
 news:ao9lh9$1gta$1 digitaldaemon.com:

 When one first reads the D documentation the initial reaction
 is, "Cool two of the most used high level container types,
 resizable arrays and maps (assoc array), are implemented in
 the language."  However arrays in D arrays aren't really
 the high level contain construct that people associate with
 the STL vector template.  Array and slice semantics are going
 to be the most confusing thing to understand for a new person
 learning D.

 I think that you are trying to accomplish two different goals
 with arrays in D and I think these goals are incompatible.
 One of the these goals is creating a safe bound checked pointer
 and the other goal is to use arrays as a container type.

 You are absolutely correct, slices are very useful constructs
 for a lot of tasks.  However as a container type arrays in D
 are not as functional as one might desire.  As a container
 arrays should have the object reference semantics.  Modify an
 object one place and all the other references see the change.
 Right now if you change the array length you run the risk that
 other array references now don't refer to the same array.

 I believe you should really separate the concepts of the slice
 and array.  Create two different types.  Let the slice play
 the role of the safe bounds checked pointer and expand arrays
 to have suitable container semantics for the type.

Oct 12 2002
prev sibling next sibling parent reply "Walter" <walter digitalmars.com> writes:
"Patrick Down" <pat codemoon.com> wrote in message
news:Xns92A5AF708AFD0patcodemooncom 63.105.9.61...
 When one first reads the D documentation the initial reaction
 is, "Cool two of the most used high level container types,
 resizable arrays and maps (assoc array), are implemented in
 the language."  However arrays in D arrays aren't really
 the high level contain construct that people associate with
 the STL vector template.  Array and slice semantics are going
 to be the most confusing thing to understand for a new person
 learning D.

Perhaps. They are their own animal. Once they are looked at on their own terms, rather than C, STL, Java, or Javascript style arrays, then they make sense.
 I think that you are trying to accomplish two different goals
 with arrays in D and I think these goals are incompatible.
 One of the these goals is creating a safe bound checked pointer
 and the other goal is to use arrays as a container type.

 You are absolutely correct, slices are very useful constructs
 for a lot of tasks.  However as a container type arrays in D
 are not as functional as one might desire.  As a container
 arrays should have the object reference semantics.  Modify an
 object one place and all the other references see the change.
 Right now if you change the array length you run the risk that
 other array references now don't refer to the same array.

 I believe you should really separate the concepts of the slice
 and array.  Create two different types.  Let the slice play
 the role of the safe bounds checked pointer and expand arrays
 to have suitable container semantics for the type.

Separating slices and arrays into different types won't change the resize problem. BTW, I should mention that Jan Knepper provided much early inspiration and motivation for me to do the slices.
Oct 13 2002
next sibling parent reply Burton Radons <loth users.sourceforge.net> writes:
Walter wrote:
 "Patrick Down" <pat codemoon.com> wrote in message
 news:Xns92A5AF708AFD0patcodemooncom 63.105.9.61...
 
When one first reads the D documentation the initial reaction
is, "Cool two of the most used high level container types,
resizable arrays and maps (assoc array), are implemented in
the language."  However arrays in D arrays aren't really
the high level contain construct that people associate with
the STL vector template.  Array and slice semantics are going
to be the most confusing thing to understand for a new person
learning D.

Perhaps. They are their own animal. Once they are looked at on their own terms, rather than C, STL, Java, or Javascript style arrays, then they make sense.

Agreed vehemently. It's the proper tool for the software environment, and I've never found it hard-to-deal-with in D code. In fact, D has taken over Python for me in the ease of use department, which only has the advantage in string methods, being able to run as a script, and a far better library. That's not a theoretical "D looks better than Python if I ever got around to using it"; it is.
I think that you are trying to accomplish two different goals
with arrays in D and I think these goals are incompatible.
One of the these goals is creating a safe bound checked pointer
and the other goal is to use arrays as a container type.

You are absolutely correct, slices are very useful constructs
for a lot of tasks.  However as a container type arrays in D
are not as functional as one might desire.  As a container
arrays should have the object reference semantics.  Modify an
object one place and all the other references see the change.
Right now if you change the array length you run the risk that
other array references now don't refer to the same array.

I believe you should really separate the concepts of the slice
and array.  Create two different types.  Let the slice play
the role of the safe bounds checked pointer and expand arrays
to have suitable container semantics for the type.

Separating slices and arrays into different types won't change the resize problem.

The ownership bit separates them AND distinguishes between an array and an array copy. If I understand your method correctly (and I don't, as you never explained what your mysterious changes allowed): char [] array = "cheese_".dup; char [] copy = array; copy ~= "foo"; array ~= "gee"; In this case, copy may be "cheese_gee" if the second append fit in the allocation, right? That doesn't happen in DLI - copy doesn't own the array, hence must allocate. The only thing the ownership bit changes from non-overallocating is whether append results in a new pointer or not.
Oct 13 2002
parent "Walter" <walter digitalmars.com> writes:
"Burton Radons" <loth users.sourceforge.net> wrote in message
news:aoc5bl$sae$1 digitaldaemon.com...
 Walter wrote:
 Perhaps. They are their own animal. Once they are looked at on their own
 terms, rather than C, STL, Java, or Javascript style arrays, then they


 sense.

and I've never found it hard-to-deal-with in D code. In fact, D has taken over Python for me in the ease of use department, which only has the advantage in string methods, being able to run as a script, and a far better library. That's not a theoretical "D looks better than Python if I ever got around to using it"; it is.

I'm using D now for new code, and it sure beats everything else.
 The ownership bit separates them AND distinguishes between an array and
 an array copy.  If I understand your method correctly (and I don't, as
 you never explained what your mysterious changes allowed):

      char [] array = "cheese_".dup;
      char [] copy = array;

      copy ~= "foo";
      array ~= "gee";

 In this case, copy may be "cheese_gee" if the second append fit in the
 allocation, right?  That doesn't happen in DLI - copy doesn't own the
 array, hence must allocate.  The only thing the ownership bit changes
 from non-overallocating is whether append results in a new pointer or not.

What my method (!) is is to have the garbage collector find the allocation block for the array being resized. If it is outside the gc pool, or not at the start of the block, it allocates a new one. Otherwise, it resizes in place if the resize will fit.
Oct 16 2002
prev sibling parent Patrick Down <pat codemoon.com> writes:
"Walter" <walter digitalmars.com> wrote in
news:aob6o5$31ao$1 digitaldaemon.com: 

 Separating slices and arrays into different types won't change the
 resize problem.

Not in their present form. Separating the types would allow arrays to have a different implementation.
Oct 13 2002
prev sibling parent reply "Sandor Hojtsy" <hojtsy index.hu> writes:
"Patrick Down" <pat codemoon.com> wrote in message
news:Xns92A5AF708AFD0patcodemooncom 63.105.9.61...
 "Walter" <walter digitalmars.com> wrote in
 news:ao9lh9$1gta$1 digitaldaemon.com:

 "chris jones" <flak clara.co.uk> wrote in message
 news:anigdn$1rek$1 digitaldaemon.com...
 This is what troubles me. Arrays as parameters have diferances from
 all

 other parameter types. They are basicly pointers with bounds
 checking.

That is essentially correct.
 I dont know. Slicing does have some great benefits but i just dont
 like arrays as they are, they seem compromised for the sake of
 slicing.

I too initially shared your reluctance for the idea.

When one first reads the D documentation the initial reaction is, "Cool two of the most used high level container types, resizable arrays and maps (assoc array), are implemented in the language." However arrays in D arrays aren't really the high level contain construct that people associate with the STL vector template. Array and slice semantics are going to be the most confusing thing to understand for a new person learning D.

I agree. Basically: void fn(in int[] a) is the same as void fn(int *a, int len) Effectively you cannot resize the array inside the function. If you only used C, that will be quite easy. But this concept of arrays is quite ... deprecated. Nowadays arrays are thought of as self-encapsulated objects. The length and the contents are both immutable or both changeable. The "inout" guarantees that both of them is changeable. void fn(inout int[] a) in D is same as void fn(vector<int> &a) in C++. In both languages, one more level of indirection is needed to access the items, so they will be slower, than the previous case. So you can choose: Speed or logical concept. Also see my post in the thread "Re: passing arrays as "in" parameter with suprising results". Sandor
Oct 14 2002
parent reply "Walter" <walter digitalmars.com> writes:
"Sandor Hojtsy" <hojtsy index.hu> wrote in message
news:aoe332$2qji$1 digitaldaemon.com...
 But this concept of arrays is quite ... deprecated. Nowadays arrays are
 thought of as self-encapsulated objects.

True, but none of the languages that do so can match the array handling performance of D.
Oct 16 2002
parent reply "Sandor Hojtsy" <hojtsy index.hu> writes:
"Walter" <walter digitalmars.com> wrote in message
news:aol69i$12j2$1 digitaldaemon.com...
 "Sandor Hojtsy" <hojtsy index.hu> wrote in message
 news:aoe332$2qji$1 digitaldaemon.com...
 But this concept of arrays is quite ... deprecated. Nowadays arrays are
 thought of as self-encapsulated objects.

True, but none of the languages that do so can match the array handling performance of D.

Ok, so you now have a fast array type, which is a good thing in some situations. Now we have to think about creating a separate full-featured array *class*, possibly in the standard library, with [] operator overload and self-encapsulation, and ... well ... poorer performance than the built-in array. Sandor
Oct 16 2002
parent reply "Walter" <walter digitalmars.com> writes:
"Sandor Hojtsy" <hojtsy index.hu> wrote in message
news:aolk6c$1g2q$1 digitaldaemon.com...
 Ok, so you now have a fast array type, which is a good thing in some
 situations.
 Now we have to think about creating a separate full-featured array

 possibly in the standard library, with [] operator overload and
 self-encapsulation, and ... well ... poorer performance than the built-in
 array.

I have thought about enabling operator [] overload for classes, that way you can create your own 'array' semantics.
Oct 24 2002
parent "Mike Wynn" <mike.wynn l8night.co.uk> writes:
 I have thought about enabling operator [] overload for classes, that way

 can create your own 'array' semantics.

and more flexable.
Oct 24 2002
prev sibling parent "Sandor Hojtsy" <hojtsy index.hu> writes:
"Sandor Hojtsy" <hojtsy index.hu> wrote in message
news:angtef$3pt$1 digitaldaemon.com...
 "chris jones" <flak clara.co.uk> wrote in message
 news:ang5id$2bm5$1 digitaldaemon.com...
 Hi, reading the specs i see that a dynamic array is pointer/length



 how does an array referance know when the array length has beend



 elsewhere in the program? It just strikes me that this could cause



 if the length is not tied to the array but tied to the 'pointer to




 array'. Also it seems that this would be a very ineficant way to




 arrays/strings as parameters, many calls that would have beed




 for
 register calling conevention will now need to be stack based.

The length/ptr pair is passed around as one unit. Embedding the length


 something the pointer points at would make slices not practical.

I can see that it would cause problems with slicing. The thing i am


 trouble with is how seperate referances to the same array keep track of

 length? If for example you pass an array as a parameter to a function


 that function alters the length of the array only the ptr/lgth pair in


 function knows the new length, any other referances to the array will

 have the old length wont they?

I see what you mean. The D array semantics seems to be rich soil for missunderstandings. From the users point of view, arrays are [should be] passed by value, by default. If you pass an array into a function, it can be thought as a copy of the original array. Any change, including the change in the length

 not change the original array.
 If you specify the parameter to be "inout", then every change should

 the original array.

 Lets try!

 void fn1(int[] a)
 {
   a.length = 4;
   printf("2: a.length = %d\n", a.length);
 }

 void fn2(inout int[] a)
 {
   a.length = 4;
   printf("4: a.length = %d\n", a.length);
 }

 int main()
 {
   int[] a;
   a.length = 3;
   printf("1: a.length = %d\n", a.length);
   fn1(a);
   printf("3: a.length = %d\n", a.length);
   fn2(a);
   printf("5: a.length = %d\n", a.length);
   return 0;
 }

 Output:
 ---------------------------
 1: a.length = 3, a[0] = 0
 2: a.length = 4, a[0] = 1
 3: a.length = 3, a[0] = 1  // a[0] should be 0
 4: a.length = 4, a[0] = 1
 5: a.length = 4, a[0] = 1
 ---------------------------

 In fn1 length changes are not incorporated into the original array, but
 value changes are. Even if the parameter is "in".
 Which is a Bad Thing! I would even say "bug". ;-)
 Does the possibility of slicing worth this?!
 A consistent self-contained array object *definitely* should not work this
 way.
 This behaviour in itself makes me want to create an own array class, which
 behaves in a consistent manner.
 If you are really want to *force* users to pass all arrays by address,

 make that explicit: arrays could only be passed as "inout".

 Sandor

Sorry the example is buggy, the correct one was: void fn1(int[] a) { a.length = 4; a[0] = 1; printf("2: a.length = %d, a[0] = %d\n", a.length, a[0]); } void fn2(inout int[] a) { a.length = 4; a[0] = 1; printf("4: a.length = %d, a[0] = %d\n", a.length, a[0]); } int main() { int[] a; a.length = 3; a[0] = 0; printf("1: a.length = %d, a[0] = %d\n", a.length, a[0]); fn1(a); printf("3: a.length = %d, a[0] = %d\n", a.length, a[0]); fn2(a); printf("5: a.length = %d, a[0] = %d\n", a.length, a[0]); return 0; }
Oct 07 2002