D - Arrays
- JamesG (3/3) Oct 03 2003 In D is there away to insert a element into a byte array.
- Walter (4/5) Oct 03 2003 Increase the length of an array by one. Then, write a loop to ripple up ...
- Ant (16/21) Oct 03 2003 to remove an element I successefuly did
- Sean L. Palmer (32/58) Oct 04 2003 I think overlapping copies should be allowed and should "do the right th...
- Matthew Wilson (5/18) Oct 04 2003 the
- Helmut Leitner (11/45) Oct 04 2003 I think that you are absolutely right.
- Sean L. Palmer (21/32) Oct 04 2003 will
- Walter (5/19) Oct 04 2003 Overlapping array operations are not allowed. The reason for this is so ...
- Sean L. Palmer (13/16) Oct 04 2003 Unfortunately this prohibition also removes much of the utility of slice
- Ant (7/34) Oct 04 2003 That's not true. They are allowed (compiles and runs)
- Walter (5/12) Oct 05 2003 There are always weaknesses in the compiler :-(
- Sean L. Palmer (9/21) Oct 05 2003 with instance sliceops(T)
- John Reimer (27/34) Oct 03 2003 Here's an example for dynamic arrays (modified from my vector template
- John Reimer (7/7) Oct 03 2003 Other examples are better. But after looking at Helmets, a correction
- Helmut Leitner (41/43) Oct 03 2003 This is an int array example based on memmove. It should be easy to adap...
- Matthew Wilson (7/50) Oct 03 2003 I don't have a problem with their being a non-template way to do this, b...
In D is there away to insert a element into a byte array. Thanks, JamesG
Oct 03 2003
"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
In article <blk7b6$41l$1 digitaldaemon.com>, Walter says..."JamesG" <JamesG_member pathlink.com> wrote in message news:blk61e$212$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; AntIn 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
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...all"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 upthe 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
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 thepointersand 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) memcpyormemfill for your particular datatypes, or calling a memcpy function liketheold 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
"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
"Helmut Leitner" <leitner hls.via.at> wrote in message news:3F7E9435.D8A6018 hls.via.at..."Sean L. Palmer" wrote:willThis is the kind of thing that if done right, once, in the compiler,thatsave countless thousands of lines of grief and pain due to forgettingorthe ranges overlap, or by trying to remember how to code a (fast) memcpythememfill for your particular datatypes, or calling a memcpy function likeRight, 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. Seanold 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.
Oct 04 2003
"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
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 sothatit's possible to use parallel operations on it. Non-overlapping arraysalsoallow more kinds of loop optimizations to be done.
Oct 04 2003
In article <blm183$2mr8$1 digitaldaemon.com>, Walter says..."Ant" <Ant_member pathlink.com> wrote in message news:blk982$6qs$1 digitaldaemon.com...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.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.Those reasons make no sense to someone trying to write a program. Ant
Oct 04 2003
"Ant" <Ant_member pathlink.com> wrote in message news:blnql0$239k$1 digitaldaemon.com...In article <blm183$2mr8$1 digitaldaemon.com>, Walter says...There are always weaknesses in the compiler :-(Overlapping array operations are not allowed.That's not true. They are allowed (compiles and runs)alsoThe reason for this is so that it's possible to use parallel operations on it. Non-overlapping arraysIt's the old array aliasing thing talked about for decades with C.allow more kinds of loop optimizations to be done.Those reasons make no sense to someone trying to write a program.
Oct 05 2003
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...There are always weaknesses in the compiler :-(Overlapping array operations are not allowed.That's not true. They are allowed (compiles and runs)alsoThe reason for this is so that it's possible to use parallel operations on it. Non-overlapping arraysIt's the old array aliasing thing talked about for decades with C.allow more kinds of loop optimizations to be done.Those reasons make no sense to someone trying to write a program.
Oct 05 2003
JamesG wrote:In D is there away to insert a element into a byte array. Thanks, JamesGHere'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
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
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
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