www.digitalmars.com         C & C++   DMDScript  

D - Is array efficient?

reply Ben Y <Ben_member pathlink.com> writes:
Hi, I just saw the D language yesterday from comp.lang.c++.moderated.

I feel that it is a very cool language.

After reading part of the spec, I found that I'm most curious about the built-in
array.

It seems that slicing does not create new array but simply just aliases existent
arrays. 
Does it do it by adjusting the internal pointers to the middle of the original
buffer? If true, wouldn't the fact that a pointer may be pointing to the middle
of an object affect garbage collection?

Also, If array is allowed to be overlapped (by slicing), D cannot make the
advantage of non-aliased assumption that fortran and C resitrict pointer can
make. Does that affect performance for array copying?


Thanks.
Oct 23 2003
parent reply "Walter" <walter digitalmars.com> writes:
"Ben Y" <Ben_member pathlink.com> wrote in message
news:bn9fv1$1u8i$1 digitaldaemon.com...
 Hi, I just saw the D language yesterday from comp.lang.c++.moderated.

 I feel that it is a very cool language.
Thanks!
 After reading part of the spec, I found that I'm most curious about the
built-in
 array.

 It seems that slicing does not create new array but simply just aliases
existent
 arrays.
 Does it do it by adjusting the internal pointers to the middle of the
original
 buffer?
Yes.
 If true, wouldn't the fact that a pointer may be pointing to the middle
 of an object affect garbage collection?
The garbage collector will account for that.
 Also, If array is allowed to be overlapped (by slicing), D cannot make the
 advantage of non-aliased assumption that fortran and C resitrict pointer
can
 make. Does that affect performance for array copying?
It shouldn't.
Oct 23 2003
next sibling parent reply Ben Y <Ben_member pathlink.com> writes:
 If true, wouldn't the fact that a pointer may be pointing to the middle
 of an object affect garbage collection?
The garbage collector will account for that.
It's amazing to hear that. Nice work!
 Also, If array is allowed to be overlapped (by slicing), D cannot make the
 advantage of non-aliased assumption that fortran and C resitrict pointer
can
 make. Does that affect performance for array copying?
It shouldn't.
Please bear with me if I sound dumb. But I don't get it. If two int[] can be overlapped, then the optimizer will not be able to take advantage of the CPU vector processing instructions safely. Isn't that the whole point of C restricted pointer? How possible that you can get around it? You don't have to check the overlapping at runtime? Or you just take that overhead as insignificant compared to the time for array copying?

Oct 23 2003
parent reply "Walter" <walter digitalmars.com> writes:
"Ben Y" <Ben_member pathlink.com> wrote in message
news:bn9q4c$2c5k$1 digitaldaemon.com...
 If true, wouldn't the fact that a pointer may be pointing to the middle
 of an object affect garbage collection?
The garbage collector will account for that.
It's amazing to hear that. Nice work!
 Also, If array is allowed to be overlapped (by slicing), D cannot make
the
 advantage of non-aliased assumption that fortran and C resitrict
pointer
can
 make. Does that affect performance for array copying?
It shouldn't.
Please bear with me if I sound dumb. But I don't get it. If two int[] can be overlapped, then the optimizer
will not
 be able to take advantage of the CPU vector processing instructions
safely.
 Isn't that the whole point of C restricted pointer? How possible that you
can
 get around it? You don't have to check the overlapping at runtime? Or you
just
 take that overhead as insignificant compared to the time for array
copying? The vector operations don't add anything for copying. They do add value for things like summing.
Oct 23 2003
parent reply "Sean L. Palmer" <palmer.sean verizon.net> writes:
"Walter" <walter digitalmars.com> wrote in message
news:bnaf21$71c$1 digitaldaemon.com...
 But I don't get it. If two int[] can be overlapped, then the optimizer
will not
 be able to take advantage of the CPU vector processing instructions
safely.
 Isn't that the whole point of C restricted pointer? How possible that
you
 can
 get around it? You don't have to check the overlapping at runtime? Or
you
 just
 take that overhead as insignificant compared to the time for array
copying?
It doesn't check for overlap at runtime, it's undefined behavior to copy a slice with source overlapping destination. Not sure about pointers though. It wouldn't be hard to check for overlap at runtime though.
 The vector operations don't add anything for copying. They do add value
for
 things like summing.
They do add value for copying. The compiler can know unambiguously that you intend to copy the entire array or slice. With manual copying (for loop) it has to infer this, figure out what you mean, in order to optimize it. With memcpy, you lose type safety and the compiler usually has to figure out alignment. You should see the SIMD classes this guy at work is making. Pretty nice stuff. Our current approach is to convert source like this: int[24] a, b, c, d; int e = 7; for (int i = 0; i < 24; ++i) a[i] = b[i] * c[i] * d[i] + e; into something like this: int[6][4] a, b, c, d; int[4] e = 7; for (int i = 0; i < 6; ++i) a[i][] = b[i][] * c[i][] * d[i][] + e[]; But we have to do it manually. The compiler should be able to do this automatically for the most part, not really any more complicated than unrolling the loop 4x. Also we don't do this: struct point { float x,y,z }; point[12] pts; float[12] lens; for (int i = 0; i < 12; ++i) lens[i] = sqrt(pts[i].x*pts[i].x + pts[i].y*pts[i].y + pts[i].z*pts[i].z); We do this instead: struct fourpoints { float[4] x,y,z; }; fourpoints[3] pts; float[3][4] lens; for (int i = 0; i < 3; ++i) lens[i] = psqrt(pts[i].x[]*pts[i].x[] + pts[i].y[]*pts[i].y[] + pts[i].z[]*pts[i].z[]); If you don't care about maybe thrashing the cache (will only happen if arrays are big) or cache locality then you can do it this way: struct allpoints { float[3][4] x,y,z; }; allpoints pts; float[3][4] lens; for (int i = 0; i < 3; ++i) lens[i] = psqrt(pts.x[i][]*pts.x[i][] + pts.y[i][]*pts.y[i][] + pts.z[i][]*pts.z[i][]); But this is how I'd like to be able to write the above in D: struct allpoints { float[12] x,y,z; }; allpoints pts; float[12] lens; lens[] = sqrt(pts.x[]*pts.x[] + pts.y[]*pts.y[] + pts.z[]*pts.z[]); Unfortunately, A) array ops aren't currently implemented, and B) DMD doesn't try to use any SIMD operations yet. Sean
Oct 24 2003
parent reply Ben Y <Ben_member pathlink.com> writes:
It doesn't check for overlap at runtime, it's undefined behavior to copy a
slice with source overlapping destination.  Not sure about pointers though.
It wouldn't be hard to check for overlap at runtime though.
Thanks a lot. So it's the programmers responsibility to ensure no overlapping? And in case of overlapping, programmer should write code explicitly to copy elements one by one?
Oct 24 2003
parent "Sean L. Palmer" <palmer.sean verizon.net> writes:
Right.

Sean

"Ben Y" <Ben_member pathlink.com> wrote in message
news:bnbhd8$222h$1 digitaldaemon.com...
It doesn't check for overlap at runtime, it's undefined behavior to copy
a
slice with source overlapping destination.  Not sure about pointers
though.
It wouldn't be hard to check for overlap at runtime though.
Thanks a lot. So it's the programmers responsibility to ensure no overlapping? And in case of overlapping, programmer should write code explicitly to
copy
 elements one by one?
Oct 24 2003
prev sibling parent reply "Sean L. Palmer" <palmer.sean verizon.net> writes:
"Walter" <walter digitalmars.com> wrote in message
news:bn9ju9$23md$1 digitaldaemon.com...
 Also, If array is allowed to be overlapped (by slicing), D cannot make
the
 advantage of non-aliased assumption that fortran and C resitrict pointer
can
 make. Does that affect performance for array copying?
It shouldn't.
So what are the semantics of aliasing in D? Does it allow pointer aliasing, ignore it, or fight an uphill battle trying to account for it at the expense of the ability to keep things in registers? Sean
Oct 24 2003
parent "Walter" <walter digitalmars.com> writes:
"Sean L. Palmer" <palmer.sean verizon.net> wrote in message
news:bnal3l$o4j$1 digitaldaemon.com...
 "Walter" <walter digitalmars.com> wrote in message
 news:bn9ju9$23md$1 digitaldaemon.com...
 Also, If array is allowed to be overlapped (by slicing), D cannot make
the
 advantage of non-aliased assumption that fortran and C resitrict
pointer
 can
 make. Does that affect performance for array copying?
It shouldn't.
So what are the semantics of aliasing in D? Does it allow pointer
aliasing,
 ignore it, or fight an uphill battle trying to account for it at the
expense
 of the ability to keep things in registers?
For copying, they can be aliased. For other vector operations, they cannot be.
Oct 24 2003