www.digitalmars.com         C & C++   DMDScript  

D - Arrays

reply JamesG <JamesG_member pathlink.com> writes:
In D is there away to insert a element into a byte array.

Thanks,

JamesG
Oct 03 2003
next sibling parent reply "Walter" <walter digitalmars.com> writes:
"JamesG" <JamesG_member pathlink.com> wrote in message
news:blk61e$212$1 digitaldaemon.com...
 In D is there away to insert a element into a byte array.

Increase the length of an array by one. Then, write a loop to ripple up all the elements above the insertion point, and then insert the new element.
Oct 03 2003
parent reply Ant <Ant_member pathlink.com> writes:
In article <blk7b6$41l$1 digitaldaemon.com>, Walter says...
"JamesG" <JamesG_member pathlink.com> wrote in message
news:blk61e$212$1 digitaldaemon.com...
 In D is there away to insert a element into a byte array.

Increase the length of an array by one. Then, write a loop to ripple up all the elements above the insertion point, and then insert the new element.

to remove an element I successefuly did // tested a[5..a.length-1] = a[6..a.length] a.length = a.length -1; Is that invalid? it seems to be working but the docs say: Overlapping copies are an error: s[0..2] = s[1..3]; error, overlapping copy s[1..3] = s[0..2]; error, overlapping copy can't we do the same to insert? // not tested a.length = a.length+1; a[6..a.length] = a[5..a.length-1] a[5] = newElement; Ant
Oct 03 2003
next sibling parent reply "Sean L. Palmer" <palmer.sean verizon.net> writes:
I think overlapping copies should be allowed and should "do the right thing"
meaning copy the contents unharmed, and not do a memory fill;  e.g. the
compiler should code up either a count-up or count-down loop depending on
the direction, and should choose the direction at compile time if the slice
arguments are compile-time constants, and at runtime if they're not.

If you want to do a memory fill, assign one element to a whole slice.  There
should be good code generation for that as well.

Someone should code up the "ultimate memcpy" routine as a template with
parameters of what to move and how much, alignment; that's one of those
ultra-generic things that really should only have to be done once.

This is one of those things that you might thing maybe shouldn't go into the
core language, but in a library, to keep the language small.  But if you are
going to go to all of the trouble to put dynamic arrays and slices into the
base language, you might as well specify what happens when you overlap slice
ranges.

I suppose there may be issues with aliasing and overlapping slices, but
isn't there a way to say "if at compile time the compiler can figure out
that the ranges point to different physical arrays, or do not overlap, it
can generate the fastest code possible.  Otherwise it must test the pointers
and make sure which direction it should go for the copy semantics to work,
possibly providing both loops."

This is the kind of thing that if done right, once, in the compiler, will
save countless thousands of lines of grief and pain due to forgetting that
the ranges overlap, or by trying to remember how to code a (fast) memcpy or
memfill for your particular datatypes, or calling a memcpy function like the
old days where you have to calculate the addresses and can't use the
convenient slice assignment notation.  People will get it wrong and make
bugs, or end up making a really suboptimal loop.

Sean

"Ant" <Ant_member pathlink.com> wrote in message
news:blk982$6qs$1 digitaldaemon.com...
 In article <blk7b6$41l$1 digitaldaemon.com>, Walter says...
"JamesG" <JamesG_member pathlink.com> wrote in message
news:blk61e$212$1 digitaldaemon.com...
 In D is there away to insert a element into a byte array.

Increase the length of an array by one. Then, write a loop to ripple up


the elements above the insertion point, and then insert the new element.

to remove an element I successefuly did // tested a[5..a.length-1] = a[6..a.length] a.length = a.length -1; Is that invalid? it seems to be working but the docs say: Overlapping copies are an error: s[0..2] = s[1..3]; error, overlapping copy s[1..3] = s[0..2]; error, overlapping copy can't we do the same to insert? // not tested a.length = a.length+1; a[6..a.length] = a[5..a.length-1] a[5] = newElement; Ant

Oct 04 2003
next sibling parent "Matthew Wilson" <matthew stlsoft.org> writes:
 I suppose there may be issues with aliasing and overlapping slices, but
 isn't there a way to say "if at compile time the compiler can figure out
 that the ranges point to different physical arrays, or do not overlap, it
 can generate the fastest code possible.  Otherwise it must test the

 and make sure which direction it should go for the copy semantics to work,
 possibly providing both loops."

 This is the kind of thing that if done right, once, in the compiler, will
 save countless thousands of lines of grief and pain due to forgetting that
 the ranges overlap, or by trying to remember how to code a (fast) memcpy

 memfill for your particular datatypes, or calling a memcpy function like

 old days where you have to calculate the addresses and can't use the
 convenient slice assignment notation.  People will get it wrong and make
 bugs, or end up making a really suboptimal loop.

I'm sold. Let's do it. Walter?
Oct 04 2003
prev sibling parent reply Helmut Leitner <leitner hls.via.at> writes:
"Sean L. Palmer" wrote:
 
 I think overlapping copies should be allowed and should "do the right thing"
 meaning copy the contents unharmed, and not do a memory fill;  e.g. the
 compiler should code up either a count-up or count-down loop depending on
 the direction, and should choose the direction at compile time if the slice
 arguments are compile-time constants, and at runtime if they're not.
 
 If you want to do a memory fill, assign one element to a whole slice.  There
 should be good code generation for that as well.
 
 Someone should code up the "ultimate memcpy" routine as a template with
 parameters of what to move and how much, alignment; that's one of those
 ultra-generic things that really should only have to be done once.
 
 This is one of those things that you might thing maybe shouldn't go into the
 core language, but in a library, to keep the language small.  But if you are
 going to go to all of the trouble to put dynamic arrays and slices into the
 base language, you might as well specify what happens when you overlap slice
 ranges.
 
 I suppose there may be issues with aliasing and overlapping slices, but
 isn't there a way to say "if at compile time the compiler can figure out
 that the ranges point to different physical arrays, or do not overlap, it
 can generate the fastest code possible.  Otherwise it must test the pointers
 and make sure which direction it should go for the copy semantics to work,
 possibly providing both loops."
 
 This is the kind of thing that if done right, once, in the compiler, will
 save countless thousands of lines of grief and pain due to forgetting that
 the ranges overlap, or by trying to remember how to code a (fast) memcpy or
 memfill for your particular datatypes, or calling a memcpy function like the
 old days where you have to calculate the addresses and can't use the
 convenient slice assignment notation.  People will get it wrong and make
 bugs, or end up making a really suboptimal loop.

I think that you are absolutely right. When - years ago - I looked into Java 1.2 array handling, I found 200+ places in the standard library where low-level array copying and resizing was handled. A real redundant bloated mess. But while I'd like the compiler to do the best it can, I'd also like to be able to write generic functions that basically can do the same. There are many similar low level access tasks that won't be handled be the compiler. -- Helmut Leitner leitner hls.via.at Graz, Austria www.hls-software.com
Oct 04 2003
parent "Sean L. Palmer" <palmer.sean verizon.net> writes:
"Helmut Leitner" <leitner hls.via.at> wrote in message
news:3F7E9435.D8A6018 hls.via.at...
 "Sean L. Palmer" wrote:
 This is the kind of thing that if done right, once, in the compiler,


 save countless thousands of lines of grief and pain due to forgetting


 the ranges overlap, or by trying to remember how to code a (fast) memcpy


 memfill for your particular datatypes, or calling a memcpy function like


 old days where you have to calculate the addresses and can't use the
 convenient slice assignment notation.  People will get it wrong and make
 bugs, or end up making a really suboptimal loop.

But while I'd like the compiler to do the best it can, I'd also like to be able to write generic functions that basically can do the same. There are many similar low level access tasks that won't be handled be the compiler.

Right, but have a good, useful semantics for slice copies wouldn't prohibit you from making something as good (especially now that you can overload slicing). It's just like memcpy though... there's not much point in every program making its own; it's something fundamental enough that it should be built in. Gives compiler writers an opportunity to make it an intrinsic, and lets the compilers shine in benchmarks if they put work into it. Then everybody benefits: the user gets clean semantics, doesn't have to worry about overlapping anymore. If they want the ultimate performance, they shouldn't be doing overlapping copies anyway, or they should find a way to let the compiler know that the ranges couldn't possibly overlap. I find the current D behavior similar to a language that doesn't have range checking on arrays. Sure, it's faster *not* to check, but I'd rather have it check, with some option to turn the check off if I'm sure the program is debugged and I really need the speed. Sean
Oct 04 2003
prev sibling parent reply "Walter" <walter digitalmars.com> writes:
"Ant" <Ant_member pathlink.com> wrote in message
news:blk982$6qs$1 digitaldaemon.com...
 to remove an element I successefuly did

 // tested
 a[5..a.length-1] = a[6..a.length]
 a.length = a.length -1;

 Is that invalid? it seems to be working

 but the docs say:

 Overlapping copies are an error:
 s[0..2] = s[1..3]; error, overlapping copy
 s[1..3] = s[0..2]; error, overlapping copy


 can't we do the same to insert?

 // not tested
 a.length = a.length+1;
 a[6..a.length] = a[5..a.length-1]
 a[5] = newElement;

Overlapping array operations are not allowed. The reason for this is so that it's possible to use parallel operations on it. Non-overlapping arrays also allow more kinds of loop optimizations to be done.
Oct 04 2003
next sibling parent "Sean L. Palmer" <palmer.sean verizon.net> writes:
Unfortunately this prohibition also removes much of the utility of slice
copies.

It is possible to allow overlapping ranges during copies, and the only
sacrifice would be (if the compiler can't figure it out for sure at compile
time)

(A) generating code for both the forward and backward copy
(B) an extra runtime check to choose between them

But wouldn't the semantics be nice for the user?

Sean

"Walter" <walter digitalmars.com> wrote in message
news:blm183$2mr8$1 digitaldaemon.com...
 Overlapping array operations are not allowed. The reason for this is so

 it's possible to use parallel operations on it. Non-overlapping arrays

 allow more kinds of loop optimizations to be done.

Oct 04 2003
prev sibling parent reply Ant <Ant_member pathlink.com> writes:
In article <blm183$2mr8$1 digitaldaemon.com>, Walter says...
"Ant" <Ant_member pathlink.com> wrote in message
news:blk982$6qs$1 digitaldaemon.com...
 to remove an element I successefuly did

 // tested
 a[5..a.length-1] = a[6..a.length]
 a.length = a.length -1;

 Is that invalid? it seems to be working

 but the docs say:

 Overlapping copies are an error:
 s[0..2] = s[1..3]; error, overlapping copy
 s[1..3] = s[0..2]; error, overlapping copy


 can't we do the same to insert?

 // not tested
 a.length = a.length+1;
 a[6..a.length] = a[5..a.length-1]
 a[5] = newElement;

Overlapping array operations are not allowed.

That's not true. They are allowed (compiles and runs) just don't get the result I'm expecting. maybe an exception should be thrown but probably they should work properly.
 The reason for this is so that
it's possible to use parallel operations on it. Non-overlapping arrays also
allow more kinds of loop optimizations to be done.

Those reasons make no sense to someone trying to write a program. Ant
Oct 04 2003
parent reply "Walter" <walter digitalmars.com> writes:
"Ant" <Ant_member pathlink.com> wrote in message
news:blnql0$239k$1 digitaldaemon.com...
 In article <blm183$2mr8$1 digitaldaemon.com>, Walter says...
Overlapping array operations are not allowed.


There are always weaknesses in the compiler :-(
 The reason for this is so that
it's possible to use parallel operations on it. Non-overlapping arrays


allow more kinds of loop optimizations to be done.


It's the old array aliasing thing talked about for decades with C.
Oct 05 2003
parent "Sean L. Palmer" <palmer.sean verizon.net> writes:
with instance sliceops(T)
    if (source_pointer > dest_pointer)
        copy_range_lo_to_hi(dest_pointer, source_pointer, count);
    else
        copy_range_hi_to_lo(dest_pointer, source_pointer,count);

The fix is dropdead simple.

Sean

"Walter" <walter digitalmars.com> wrote in message
news:blpnav$1hks$1 digitaldaemon.com...
 "Ant" <Ant_member pathlink.com> wrote in message
 news:blnql0$239k$1 digitaldaemon.com...
 In article <blm183$2mr8$1 digitaldaemon.com>, Walter says...
Overlapping array operations are not allowed.


There are always weaknesses in the compiler :-(
 The reason for this is so that
it's possible to use parallel operations on it. Non-overlapping arrays


allow more kinds of loop optimizations to be done.


It's the old array aliasing thing talked about for decades with C.

Oct 05 2003
prev sibling next sibling parent reply John Reimer <jjreimer telus.net> writes:
JamesG wrote:
 In D is there away to insert a element into a byte array.
 
 Thanks,
 
 JamesG
 
 

Here's an example for dynamic arrays (modified from my vector template code): NOTE: inserts are expensive in non-linked lists! // previously declared byte [] tmpArray; byte [] byteArray; // array we want to insert into //==================== void insert(in int index, in byte T) { if (index >= byteArray.length-1) byteArray ~= T; else { // Make a copy of the array and store it in tmpArray // so we don't point to the same array space. tmpArray = byteArray.dup; // Chop and store the section of array before index byteArray = byteArray[0 .. index]; // Store the byte next at index byteArray ~= T; // Store the remaining portion of the array. byteArray ~= tmpArray[index .. tmpArray.length]; } }
Oct 03 2003
parent John Reimer <jjreimer telus.net> writes:
Other examples are better.  But after looking at Helmets, a correction 
on mine:

if (index >= byteArray.length-1) ... // Oops!

should be:

if (index >= byteArray.length)

Later,
John
Oct 03 2003
prev sibling parent reply Helmut Leitner <helmut.leitner chello.at> writes:
JamesG wrote:
 
 In D is there away to insert a element into a byte array.

This is an int array example based on memmove. It should be easy to adapt: import string; alias char [] String; int [] itab= [1,12,7,14,11]; void IntArrayPrint(String s,int [] ar) { printf("%.*s [",s); foreach(int i; ar) { printf(" %d",i); } printf(" ]\n"); } void IntArrayIndInsElement(inout int [] ar,uint ind,int el) { if(ind>=ar.length) { ar ~= el; } else { int size=(ar.length-ind)*el.size; ar.length=ar.length+1; memmove(&ar[ind+1],&ar[ind],size); ar[ind]=el; } } int main (String [] args) { IntArrayPrint("itab before insert: ",itab); IntArrayIndInsElement(itab,3,6); IntArrayPrint("itab after insert ind=3 el=6: ",itab); IntArrayIndInsElement(itab,100,33); IntArrayPrint("itab after insert ind=100 el=33: ",itab); IntArrayIndInsElement(itab,0,-1); IntArrayPrint("itab after insert ind=0 el=-1: ",itab); return 0; } Output: itab before insert: [ 1 12 7 14 11 ] itab after insert ind=3 el=6: [ 1 12 7 6 14 11 ] itab after insert ind=100 el=33: [ 1 12 7 6 14 11 33 ] itab after insert ind=0 el=-1: [ -1 1 12 7 6 14 11 33 ] -- Helmut Leitner leitner hls.via.at Graz, Austria www.hls-software.com
Oct 03 2003
parent "Matthew Wilson" <matthew stlsoft.org> writes:
I don't have a problem with their being a non-template way to do this, but I
would hope that when the D template library eventuates, it will generalise
(and specialise, for performance, where needed) this operation

Just my two-pen'th

Matthew

"Helmut Leitner" <helmut.leitner chello.at> wrote in message
news:3F7DCE65.B19FD3AE chello.at...
 JamesG wrote:
 In D is there away to insert a element into a byte array.

This is an int array example based on memmove. It should be easy to adapt: import string; alias char [] String; int [] itab= [1,12,7,14,11]; void IntArrayPrint(String s,int [] ar) { printf("%.*s [",s); foreach(int i; ar) { printf(" %d",i); } printf(" ]\n"); } void IntArrayIndInsElement(inout int [] ar,uint ind,int el) { if(ind>=ar.length) { ar ~= el; } else { int size=(ar.length-ind)*el.size; ar.length=ar.length+1; memmove(&ar[ind+1],&ar[ind],size); ar[ind]=el; } } int main (String [] args) { IntArrayPrint("itab before insert: ",itab); IntArrayIndInsElement(itab,3,6); IntArrayPrint("itab after insert ind=3 el=6: ",itab); IntArrayIndInsElement(itab,100,33); IntArrayPrint("itab after insert ind=100 el=33: ",itab); IntArrayIndInsElement(itab,0,-1); IntArrayPrint("itab after insert ind=0 el=-1: ",itab); return 0; } Output: itab before insert: [ 1 12 7 14 11 ] itab after insert ind=3 el=6: [ 1 12 7 6 14 11 ] itab after insert ind=100 el=33: [ 1 12 7 6 14 11 33 ] itab after insert ind=0 el=-1: [ -1 1 12 7 6 14 11 33 ] -- Helmut Leitner leitner hls.via.at Graz, Austria www.hls-software.com

Oct 03 2003