www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Array start index

reply "DLearner" <bmqazwsx123 gmail.com> writes:
Does the D language set in stone that the first element of an 
array _has_ to be index zero?
Wouldn't starting array elements at one avoid the common 
'off-by-one' logic error, it does
seem more natural to begin a count at 1.

Actually, maybe even better to allow array definitions of form
int foo[x:y];
(y >= x) creating integer variables foo[x], foo[x+1],...,foo[y].

I think the (very old) IBM PL/I language was like this.
Aug 01 2015
next sibling parent Rikki Cattermole <alphaglosined gmail.com> writes:
On 1/08/2015 9:35 p.m., DLearner wrote:
 Does the D language set in stone that the first element of an array
 _has_ to be index zero?
 Wouldn't starting array elements at one avoid the common 'off-by-one'
 logic error, it does
 seem more natural to begin a count at 1.

 Actually, maybe even better to allow array definitions of form
 int foo[x:y];
 (y >= x) creating integer variables foo[x], foo[x+1],...,foo[y].

 I think the (very old) IBM PL/I language was like this.
In c style languages (like D) the index actually defines the offset in memory. Not actually the index. So while in some languages 1 is used instead of 0, 0 maps better to the hardware. Think of this byte array: ubyte* myptr = [ |---|-------| | i | value | |---|-------| | 0 | 1 | | 1 | 255 | ]; For 0 start of index: size_t i = 0; assert(myptr[i] == 1); For 1 start of index: size_t i = 1; assert(i != 0); assert(myptr[i-1] == 1); While this is not the complete reason why 0 is chosen, it is something to think about.
Aug 01 2015
prev sibling next sibling parent "bachmeier" <no spam.net> writes:
On Saturday, 1 August 2015 at 09:35:53 UTC, DLearner wrote:
 Does the D language set in stone that the first element of an 
 array _has_ to be index zero?
 Wouldn't starting array elements at one avoid the common 
 'off-by-one' logic error, it does
 seem more natural to begin a count at 1.

 Actually, maybe even better to allow array definitions of form
 int foo[x:y];
 (y >= x) creating integer variables foo[x], foo[x+1],...,foo[y].

 I think the (very old) IBM PL/I language was like this.
Seems you could easily wrap an array in a struct, define opIndex and opSlice appropriately, and use alias this to keep the other properties of the array. The problem you'll run into is interacting with other code that assumes zero-based indexing. I thought about setting the first index at 1 for my library that embeds D inside R, since that's how it's done in R, but very quickly realized how confusing it would be.
Aug 01 2015
prev sibling next sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Saturday, 1 August 2015 at 09:35:53 UTC, DLearner wrote:
 Does the D language set in stone that the first element of an 
 array _has_ to be index zero?
For the builtin slice types? Yes, set in stone.
 Wouldn't starting array elements at one avoid the common 
 'off-by-one' logic error, it does
 seem more natural to begin a count at 1.

 Actually, maybe even better to allow array definitions of form
 int foo[x:y];
 (y >= x) creating integer variables foo[x], foo[x+1],...,foo[y].

 I think the (very old) IBM PL/I language was like this.
See https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html As other commenters have/will point out, you can easily define a custom type in D that behaves as you describe, and - Dijkstra notwithstanding - there are valid uses for such things.
Aug 01 2015
parent reply "DLearner" <bmqazwsx123 gmail.com> writes:
On Saturday, 1 August 2015 at 17:55:06 UTC, John Colvin wrote:
 On Saturday, 1 August 2015 at 09:35:53 UTC, DLearner wrote:
 Does the D language set in stone that the first element of an 
 array _has_ to be index zero?
For the builtin slice types? Yes, set in stone.
 Wouldn't starting array elements at one avoid the common 
 'off-by-one' logic error, it does
 seem more natural to begin a count at 1.

 Actually, maybe even better to allow array definitions of form
 int foo[x:y];
 (y >= x) creating integer variables foo[x], 
 foo[x+1],...,foo[y].

 I think the (very old) IBM PL/I language was like this.
See https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html As other commenters have/will point out, you can easily define a custom type in D that behaves as you describe, and - Dijkstra notwithstanding - there are valid uses for such things.
D is a C derivative, so it seems a shame not to identify causes of bugs in C, and design them out in D. For example, in C difficult to write non-trivial commercial programs without using pointers. Pointer manipulation has a terrible reputation for bugs. But in D, easy to write commercial programs without using pointers. Problem has been designed away. Similarly, off-by-one array bugs are commonplace in C. We should seek to eliminate the source of those bugs, which basically reduces to the issue that programmers find it unnatural to start a count at zero. Whether they _should_ find a zero start unnatural is irrelevant - they just do as an observed fact, so let's change the language so the issue is avoided (designed away). Suggestion: if the codebase for D is considered so large that zero-basing cannot now be changed, why not extend the language to allow for array definitions like 'int[x:y] foo'? And then have a rule that 'int[:y] bar' defines a 1-based array of y elements?
Aug 01 2015
parent reply Andrej Mitrovic via Digitalmars-d-learn writes:
On 8/1/15, DLearner via Digitalmars-d-learn
<digitalmars-d-learn puremagic.com> wrote:
 D is a C derivative, so it seems a shame not to identify causes
 of bugs in C,
 and design them out in D.
This has already been done! D defines an array to be a struct with a pointer and a length. See this article: http://www.drdobbs.com/architecture-and-design/cs-biggest-mistake/228701625 I would argue it's not "off-by-one" that's causing most issues when dealing with C "arrays", but instead it's in general out-of-bounds issues (whether it's off bye one or off by 50..) since you often don't have the length or could easily use the wrong variable as the length. Think about how much D code would actually have subtle off-by-one errors if D didn't use 0-based indexing like the majority of popular languages use. Any time you would interface with other languages you would have to double, triple-check all your uses of arrays. FWIW at the very beginning I also found it odd that languages use 0-based indexing, but that was before I had any significant programming experience under my belt. By now it's second nature to me to use 0-based indexing.
Aug 01 2015
parent reply "bachmeier" <no spam.net> writes:
On Saturday, 1 August 2015 at 19:04:10 UTC, Andrej Mitrovic wrote:
 On 8/1/15, DLearner via Digitalmars-d-learn 
 <digitalmars-d-learn puremagic.com> wrote:
 D is a C derivative, so it seems a shame not to identify causes
 of bugs in C,
 and design them out in D.
This has already been done! D defines an array to be a struct with a pointer and a length. See this article: http://www.drdobbs.com/architecture-and-design/cs-biggest-mistake/228701625 I would argue it's not "off-by-one" that's causing most issues when dealing with C "arrays", but instead it's in general out-of-bounds issues (whether it's off bye one or off by 50..) since you often don't have the length or could easily use the wrong variable as the length. Think about how much D code would actually have subtle off-by-one errors if D didn't use 0-based indexing like the majority of popular languages use. Any time you would interface with other languages you would have to double, triple-check all your uses of arrays. FWIW at the very beginning I also found it odd that languages use 0-based indexing, but that was before I had any significant programming experience under my belt. By now it's second nature to me to use 0-based indexing.
But what type of programming are you doing? Even after decades of programming and trying out dozens of languages, zero-based indexing still gets me at times when the arrays I work with represent vectors and matrices. Especially when porting code from other languages that use one-based indexing. One of the nice things about D is that it gives you the tools to easily make the change if you want.
Aug 01 2015
parent reply "QAston" <qastonx gmail.com> writes:
On Saturday, 1 August 2015 at 23:02:51 UTC, bachmeier wrote:
 But what type of programming are you doing? Even after decades 
 of programming and trying out dozens of languages, zero-based 
 indexing still gets me at times when the arrays I work with 
 represent vectors and matrices. Especially when porting code 
 from other languages that use one-based indexing. One of the 
 nice things about D is that it gives you the tools to easily 
 make the change if you want.
Adding 1-indexed arrays to the language fixes nothing. Just write your 1-indexed array type and if you enjoy using it, publish it as a library. Who knows, if demand is high it may even end up in phobos.
Aug 02 2015
parent reply "bachmeier" <no spam.com> writes:
On Sunday, 2 August 2015 at 21:58:48 UTC, QAston wrote:

 Adding 1-indexed arrays to the language fixes nothing. Just 
 write your 1-indexed array type and if you enjoy using it, 
 publish it as a library. Who knows, if demand is high it may 
 even end up in phobos.
Oh, I don't think that's a good idea. It's too confusing to have more than one method of indexing within the same language. You just have to do a thorough job of testing, as the possibility of errors is something you'll have to live with, given the different design choices of different languages.
Aug 03 2015
parent reply "DLearner" <bmqazwsx123 gmail.com> writes:
On Monday, 3 August 2015 at 13:45:01 UTC, bachmeier wrote:
 On Sunday, 2 August 2015 at 21:58:48 UTC, QAston wrote:

 Adding 1-indexed arrays to the language fixes nothing. Just 
 write your 1-indexed array type and if you enjoy using it, 
 publish it as a library. Who knows, if demand is high it may 
 even end up in phobos.
Oh, I don't think that's a good idea. It's too confusing to have more than one method of indexing within the same language. You just have to do a thorough job of testing, as the possibility of errors is something you'll have to live with, given the different design choices of different languages.
Looks like 0-base is fixed, to avoid problems with existing code. But nothing stops _adding_ to the language by allowing int[x:y] foo to mean valid symbols are foo[x], foo[x+1],..., foo[y]. Plus rule that int[:y] means valid symbols are foo[1], foo[2],..., foo[y]. That way, 1-start achieved, with no conflict with existing code?
Aug 03 2015
next sibling parent Jonathan M Davis via Digitalmars-d-learn writes:
On Monday, August 03, 2015 21:32:03 DLearner via Digitalmars-d-learn wrote:
 On Monday, 3 August 2015 at 13:45:01 UTC, bachmeier wrote:
 On Sunday, 2 August 2015 at 21:58:48 UTC, QAston wrote:

 Adding 1-indexed arrays to the language fixes nothing. Just
 write your 1-indexed array type and if you enjoy using it,
 publish it as a library. Who knows, if demand is high it may
 even end up in phobos.
Oh, I don't think that's a good idea. It's too confusing to have more than one method of indexing within the same language. You just have to do a thorough job of testing, as the possibility of errors is something you'll have to live with, given the different design choices of different languages.
Looks like 0-base is fixed, to avoid problems with existing code. But nothing stops _adding_ to the language by allowing int[x:y] foo to mean valid symbols are foo[x], foo[x+1],..., foo[y]. Plus rule that int[:y] means valid symbols are foo[1], foo[2],..., foo[y]. That way, 1-start achieved, with no conflict with existing code?
Almost all programming languages in heavy use at this point in time start indexing at 0. It would be highly confusing to almost all programmers out there to have 1-based indexing. In addition, having 0-based indexing actually makes checking against the end of arrays and other random-access ranges easier. You can just check against length without having to do any math. In general, I would expect 1-based indexing to _increase_ the number of off by one errors in code - both because 0-based indexing helps avoid such problems when dealing with the end of the array and more importantly, because almost everyone expects 0-based indexing. You're really barking up the wrong tree if you're trying to get any support for 1-based indexing in D. I doubt that you will see much of anyone who thinks that it's even vaguely a good idea, and there's no way that Walter or Andrei (or probably anyone in the main dev team) who is going to agree that it's even worth considering. I think that the reality of the matter is that if you're going to do much programming - especially if you're going to be professional programmer - you just need to get used to the idea that array indices start at 0. There are a few languages out there where they don't, but they are far from the norm. - Jonathan M Davis
Aug 03 2015
prev sibling parent "QAston" <qaston gmail.com> writes:
On Monday, 3 August 2015 at 21:32:05 UTC, DLearner wrote:
 Looks like 0-base is fixed, to avoid problems with existing 
 code.

 But nothing stops _adding_ to the language by allowing
 int[x:y] foo to mean valid symbols are foo[x], foo[x+1],..., 
 foo[y].
 Plus rule that int[:y] means valid symbols are foo[1], 
 foo[2],..., foo[y].

 That way, 1-start achieved, with no conflict with existing code?
There're quite a few things stopping this from being added to the language. 1. People will have to learn this new feature and it's interaction with gazillion of other D features. 2. There would be a redundancy - core language will have 2 array types while one of them can be easily implemented using the other. 3. Devs will have to maintain it - as if they don't have enough things to fix atm. Really, this is so simple to do as a library - just use opIndex, opSlice with a template struct. As a general rule - start asking for language features only when things can't be done without them.
Aug 04 2015
prev sibling next sibling parent "jmh530" <john.michael.hall gmail.com> writes:
On Saturday, 1 August 2015 at 09:35:53 UTC, DLearner wrote:
 Does the D language set in stone that the first element of an 
 array _has_ to be index zero?
 Wouldn't starting array elements at one avoid the common 
 'off-by-one' logic error, it does
 seem more natural to begin a count at 1.

 Actually, maybe even better to allow array definitions of form
 int foo[x:y];
 (y >= x) creating integer variables foo[x], foo[x+1],...,foo[y].

 I think the (very old) IBM PL/I language was like this.
I come from matlab and R which start matrices at 1. I used to think it was more natural. However after I started using numpy I now think 0 index is better. Also see http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html Give it a try. You might find you like it.
Aug 03 2015
prev sibling next sibling parent "Observer" <spurious.address yahoo.com> writes:
On Saturday, 1 August 2015 at 09:35:53 UTC, DLearner wrote:
 Does the D language set in stone that the first element of an 
 array _has_ to be index zero?
 Wouldn't starting array elements at one avoid the common 
 'off-by-one' logic error, it does
 seem more natural to begin a count at 1.

 Actually, maybe even better to allow array definitions of form
 int foo[x:y];
 (y >= x) creating integer variables foo[x], foo[x+1],...,foo[y].
This experiment has already been run. Perl used to support a $[ variable to set the array base. After experience with the confusion and problems that causes, it was finally deprecated and effectively removed from the language. See the end paragraphs of http://perldoc.perl.org/perlvar.html and also http://search.cpan.org/~wolfsage/perl/ext/arybase/arybase.pm for more info.
Aug 03 2015
prev sibling next sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Saturday, 1 August 2015 at 09:35:53 UTC, DLearner wrote:
 Does the D language set in stone that the first element of an 
 array _has_ to be index zero?
 Wouldn't starting array elements at one avoid the common 
 'off-by-one' logic error, it does
 seem more natural to begin a count at 1.
I, too, don't think this is a good idea in general, but I can see a few use-cases where 1-based indices may be more natural. It's easy to define a wrapper: struct OneBasedArray(T) { T[] _payload; alias _payload this; T opIndex(size_t index) { assert(index > 0); return _payload[index-1]; } void opIndexAssign(U : T)(size_t index, auto ref U value) { assert(index > 0); _payload[index-1] = value; } } unittest { OneBasedArray!int arr; arr = [1,2,3]; arr ~= 4; assert(arr.length == 4); assert(arr[1] == 1); assert(arr[2] == 2); assert(arr[3] == 3); assert(arr[4] == 4); } Test with: rdmd -main -unittest xx.d This can of course be easily extended to support other bases than one.
Aug 04 2015
next sibling parent reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Tuesday, 4 August 2015 at 08:18:50 UTC, Marc Schütz wrote:
         void opIndexAssign(U : T)(size_t index, auto ref U 
 value) {
Careful here, you've got the arguments reversed. The unit test didn't detect this because it was ambiguous. This one isn't: unittest { OneBasedArray!int arr; arr = [1,2,3]; arr ~= 14; assert(arr.length == 4); assert(arr[1] == 1); assert(arr[2] == 2); assert(arr[3] == 3); assert(arr[4] == 14); }
Feb 06 2017
parent reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Monday, 6 February 2017 at 14:26:35 UTC, Bastiaan Veelo wrote:
 The unit test didn't detect this because it was ambiguous.
Sorry for that misinformation. I should have said that opIndexAssign wasn't tested. Here is a better test. unittest { OneBasedArray!int arr; arr = [1,2,3]; arr ~= 4; arr[4] = 14; assert(arr.length == 4); assert(arr[1] == 1); assert(arr[2] == 2); assert(arr[3] == 3); assert(arr[4] == 14); }
Feb 06 2017
parent reply pineapple <meapineapple gmail.com> writes:
One reason for zero-based indexes that isn't "it's what we're all 
used to" is that if you used one-based indexes, you would be able 
to represent one fewer index than zero-based, since one of the 
representable values - zero - could no longer be used to 
represent any index.

Also, it's what we're all used to, and it makes perfect sense to 
a lot of us, and the only times in recent memory I've ever made 
off-by-one errors were when I was trying to use Lua and its 
one-based indexing.
Feb 06 2017
next sibling parent Nemanja Boric <4burgos gmail.com> writes:
On Monday, 6 February 2017 at 18:55:19 UTC, pineapple wrote:
 One reason for zero-based indexes that isn't "it's what we're 
 all used to" is that if you used one-based indexes, you would 
 be able to represent one fewer index than zero-based, since one 
 of the representable values - zero - could no longer be used to 
 represent any index.

 Also, it's what we're all used to, and it makes perfect sense 
 to a lot of us, and the only times in recent memory I've ever 
 made off-by-one errors were when I was trying to use Lua and 
 its one-based indexing.
Related: https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html
Feb 06 2017
prev sibling parent bachmeier <no spam.net> writes:
On Monday, 6 February 2017 at 18:55:19 UTC, pineapple wrote:
 One reason for zero-based indexes that isn't "it's what we're 
 all used to" is that if you used one-based indexes, you would 
 be able to represent one fewer index than zero-based, since one 
 of the representable values - zero - could no longer be used to 
 represent any index.

 Also, it's what we're all used to, and it makes perfect sense 
 to a lot of us, and the only times in recent memory I've ever 
 made off-by-one errors were when I was trying to use Lua and 
 its one-based indexing.
In the scientific programming community, languages like Matlab, Fortran, and R use one-based indexing for a very good reason. Zero-based indexing is a computer science thing that makes no sense to someone working with equations.
Feb 06 2017
prev sibling parent reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
(There is an honest question in the end, please read on.)

All good reasons set aside, both in favour and against 0-based 
arrays, the only reason that is relevant to me right now is that 
we are seriously looking into translating close to a million 
lines of foreign code to D, from a language that supports arrays 
over arbitrary ranges of indices (positive and negative). 
Adapting this much program logic to a different array base is out 
of the question; this is an engineering application and lives are 
at stake. So let's not bring the base-arguments back into this 
sub-thread but focus on a performant solution.

Expanding on Marc's outset, I now have:

/*****************
  * A fixed-length array with an index that runs from $(D_PARAM 
first)
  * to $(D_PARAM last) inclusive.
  *
  * Indices are converted, which involves a small overhead.
  */
struct StaticArray(T, ptrdiff_t first, ptrdiff_t last) {
     T[last - first + 1] _payload;

     alias _payload this;

     // Support e = arr[5];
     ref T opIndex(ptrdiff_t index) {
         assert(index >= first);
         assert(index <= last);
         return _payload[index - first];
     }

     // Support arr[5] = e;
     void opIndexAssign(U : T)(auto ref U value, ptrdiff_t index) {
         assert(index >= first);
         assert(index <= last);
         _payload[index - first] = value;
     }

     // Support foreach(e; arr).
     int opApply(scope int delegate(ref T) dg)
     {
         int result = 0;

         for (int i = 0; i < _payload.length; i++)
         {
             result = dg(_payload[i]);
             if (result)
                 break;
         }
         return result;
     }

     // Support foreach(i, e; arr).
     int opApply(scope int delegate(ptrdiff_t index, ref T) dg)
     {
         int result = 0;

         for (int i = 0; i < _payload.length; i++)
         {
             result = dg(i + first, _payload[i]);
             if (result)
                 break;
         }
         return result;
     }

     // Write to binary file.
     void toFile(string fileName)
     {
         import std.stdio;
         auto f = File(fileName, "wb");
         if (f.tryLock)
         {
             f.rawWrite(_payload);
         }
     }
}

unittest {
     StaticArray!(int, -10, 10) arr;
     assert(arr.length == 21);

     foreach (ref e; arr)
         e = 42;
     assert(arr[-10] == 42);
     assert(arr[0]   == 42);
     assert(arr[10]  == 42);

     foreach (i, ref e; arr)
         e = i;
     assert(arr[-10] == -10);
     assert(arr[0]   ==   0);
     assert(arr[5]   ==   5);
     assert(arr[10]  ==  10);

     arr[5] = 15;
     assert(arr[5]   == 15);
}

//////////////

(The first and last indices probably don't need to be template 
arguments, they could possibly be immutable members of the 
struct; But that is not what worries me now.)
The thing is that a small overhead is paid in opIndex() and 
opIndexAssign() (the other member functions are fine). I'd like 
to get rid of that overhead.

In "Numerical Recipes in C", section 1.2, Press et al. propose an 
easy solution using an offset pointer:

float b[4], *bb;
bb = b - 1;

Thus bb[1] through bb[4] all exist, no space is wasted nor is 
there a run-time overhead.

I have tried to adapt the internals of my struct to Press' 
approach, but it seems to me it is not that easy in D -- or I'm 
just not proficient enough. Can someone here show me how that 
could be done?

Thanks!
Feb 06 2017
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 02/06/2017 03:00 PM, Bastiaan Veelo wrote:

 In "Numerical Recipes in C", section 1.2, Press et al. propose an easy
 solution using an offset pointer:

 float b[4], *bb;
 bb = b - 1;

 Thus bb[1] through bb[4] all exist, no space is wasted nor is there a
 run-time overhead.

 I have tried to adapt the internals of my struct to Press' approach, but
 it seems to me it is not that easy in D -- or I'm just not proficient
 enough. Can someone here show me how that could be done?
struct StaticArray(T, ptrdiff_t first, ptrdiff_t last) { T[last - first + 1] _payload; If the static array has to be a member like that (as opposed to a dynamic one), you need an extra member: T* _ptr; Because structs cannot have default constructors, you need an init() function to establish the invariant: void init() { this._ptr = _payload.ptr - first; } Of course, that relies on the fact that _payload.ptr - first is a valid address to hold in a pointer. [OT]: // Commented-out as it seems dangerous because _payload does not // have the same semantics as StaticArray. // // alias _payload this; Which means, you would implement length() yourself: size_t length() { return _payload.length; } Then you use _ptr when indexing: // Support e = arr[5]; ref T opIndex(ptrdiff_t index) { assert(index >= first); assert(index <= last); return *(_ptr + index); } Ali
Feb 06 2017
parent reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Monday, 6 February 2017 at 23:42:55 UTC, Ali Çehreli wrote:
 Then you use _ptr when indexing:

     // Support e = arr[5];
     ref T opIndex(ptrdiff_t index) {
         assert(index >= first);
         assert(index <= last);
         return *(_ptr + index);
     }

 Ali
Thank you very much for your time. Sadly this gives me an access violation. The traceback doesn't seem right though, as it seems to jump to opIndexAssign from where opIndex is used. If I'm not mistaken, I have confirmed that _ptr is a valid address, see below. We do not need to take measures against the GC? - Bastiaan. On Windows: rdmd -main -unittest -debug -g source\epcompat\array.d object.Error (0): Access Violation ---------------- 0x00402057 in void epcompat.array.__unittestL81_1() at C:\SARC\Pascal2017\D\epcompat\source\epcompat\array.d(88) 0x0040465C in void epcompat.array.__modtest() at C:\SARC\Pascal2017\D\epcompat\source\epcompat\array.d(39) 0x0040A455 in int core.runtime.runModuleUnitTests().__foreachbody1(object.ModuleInfo*) 0x0040C007 in int object.ModuleInfo.opApply(scope int delegate(object.ModuleInfo*)).__lambda2(immutable(object.ModuleInfo*)) 0x00406808 in _d_run_main 0x004046D4 in main at C:\SARC\Pascal2017\D\epcompat\source\epcompat\array.d(7) 0x004225DD in mainCRTStartup 0x779C62C4 in BaseThreadInitThunk 0x77B50FD9 in RtlSubscribeWnfStateChangeNotification 0x77B50FA4 in RtlSubscribeWnfStateChangeNotification The complete source: module epcompat.array; // Test with rdmd -main -unittest -debug -g source\epcompat\array.d alias StaticArray_offset StaticArray; /***************** * A fixed-length array with an index that runs from $(D_PARAM first) * to $(D_PARAM last) inclusive. * * Implemented by means of an offset pointer. */ struct StaticArray_offset(T, ptrdiff_t first, ptrdiff_t last) { T[last - first + 1] _payload; T* _ptr; void init() { assert( first < cast(size_t)_payload.ptr); // Address space underrun. assert(-first < size_t.max - cast(size_t)_payload.ptr); // Address space overrun. this._ptr = _payload.ptr - first; } size_t length() { return _payload.length; } // Support e = arr[5]; ref T opIndex(ptrdiff_t index) { assert(index >= first); assert(index <= last); return *(_ptr + index); } // Support arr[5] = e; void opIndexAssign(U : T)(auto ref U value, ptrdiff_t index) { assert(index >= first); assert(index <= last); *(_ptr + index) = value; } // Line 39 // Support foreach(e; arr). int opApply(scope int delegate(ref T) dg) { int result = 0; for (int i = 0; i < _payload.length; i++) { result = dg(_payload[i]); if (result) break; } return result; } // Support foreach(i, e; arr). int opApply(scope int delegate(ptrdiff_t index, ref T) dg) { int result = 0; for (int i = first; i <= last; i++) { result = dg(i, *(_ptr + i)); if (result) break; } return result; } // Write to binary file. void toFile(string fileName) { import std.stdio; auto f = File(fileName, "wb"); if (f.tryLock) { f.rawWrite(_payload); } } } unittest { StaticArray!(int, -10, 10) arr; assert(arr.length == 21); foreach (ref e; arr) e = 42; assert(arr[-10] == 42); // Line 88 assert(arr[0] == 42); assert(arr[10] == 42); foreach (i, ref e; arr) e = i; assert(arr[-10] == -10); assert(arr[0] == 0); assert(arr[5] == 5); assert(arr[10] == 10); arr[5] = 15; assert(arr[5] == 15); }
Feb 07 2017
next sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 02/07/2017 02:11 AM, Bastiaan Veelo wrote:

     void init() {
         assert( first < cast(size_t)_payload.ptr);              //
 Address space underrun.
         assert(-first < size_t.max - cast(size_t)_payload.ptr); //
 Address space overrun.
         this._ptr = _payload.ptr - first;
     }
You forgot to call that most important function. ;) 1) I don't understand the first assert there, which does not pass for me, so I commented it out. 2) May bad: init() is not a good name for a struct member, so it should be renamed: void initialize() { // assert( first < cast(size_t)_payload.ptr); // Address space underrun. assert(-first < size_t.max - cast(size_t)_payload.ptr); // Address space overrun. this._ptr = _payload.ptr - first; } 3) Instead of having to remember to call it, let's introduce a function that does it for us: auto makeStaticArray(T, ptrdiff_t first, ptrdiff_t last)() { auto s = StaticArray!(T, first, last)(); s.initialize(); return s; } unittest { // StaticArray!(int, -10, 10) arr; auto arr = makeStaticArray!(int, -10, 10);
     foreach (i, ref e; arr)
         e = i;
Unrelated: That line passes because you're building 32-bits. Here is the error I got: Error: cannot implicitly convert expression (i) of type long to int You can cast it: e = cast(int)i; or by import std.conv : to; e = i.to!int; Ali
Feb 07 2017
parent Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Tuesday, 7 February 2017 at 20:28:30 UTC, Ali Çehreli wrote:
 You forgot to call that most important function. ;)
Hah of course. I assumed the name would give it some special meaning, like postblit.
 1) I don't understand the first assert there, which does not 
 pass for me, so I commented it out.
The intention is to check that (_payload.ptr - first) is larger than 0.
 2) May bad: init() is not a good name for a struct member, so 
 it should be renamed:

     void initialize() {
         // assert( first < cast(size_t)_payload.ptr);
    // Address space underrun.
         assert(-first < size_t.max - cast(size_t)_payload.ptr); 
 // Address space overrun.
         this._ptr = _payload.ptr - first;
     }

 3) Instead of having to remember to call it, let's introduce a 
 function that does it for us:

 auto makeStaticArray(T, ptrdiff_t first, ptrdiff_t last)() {
     auto s = StaticArray!(T, first, last)();
     s.initialize();
     return s;
 }
OK good.
 unittest {
     // StaticArray!(int, -10, 10) arr;
     auto arr = makeStaticArray!(int, -10, 10);

     foreach (i, ref e; arr)
         e = i;
Unrelated: That line passes because you're building 32-bits. Here is the error I got: Error: cannot implicitly convert expression (i) of type long to int You can cast it: e = cast(int)i; or by import std.conv : to; e = i.to!int;
Thanks a lot for your illustrative answers, including the next one! Bastiaan.
Feb 07 2017
prev sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
Pressed send too soon, before considering your GC question.

On 02/07/2017 02:11 AM, Bastiaan Veelo wrote:

 We do not need to take measures against the GC?
Of course we have to and the struct that I wrote is illegal because it is self-referencing through the _ptr member. (D has the right to move structs around, making my _ptr potentially pointing to an illegal address.) This optimization cannot work if the array is a static array inside the same struct. It would work with a dynamic array but then it would probably be slower than applying the *(ptr+index) technique. Ali
Feb 07 2017
parent reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Tuesday, 7 February 2017 at 20:33:35 UTC, Ali Çehreli wrote:
 On 02/07/2017 02:11 AM, Bastiaan Veelo wrote:

 We do not need to take measures against the GC?
Of course we have to and the struct that I wrote is illegal because it is self-referencing through the _ptr member. (D has the right to move structs around, making my _ptr potentially pointing to an illegal address.)
Gosh am I glad I brought that up, and for people like you hanging out in the learn group. Thanks for pointing this out!
 This optimization cannot work if the array is a static array 
 inside the same struct. It would work with a dynamic array but 
 then it would probably be slower than applying the *(ptr+index) 
 technique.
You mean slower than the _payload[index - first] technique? Is that because of heap memory versus stack memory? Am I correct that the reason that a dynamic array would work is because it is allocated independently from the struct, meaning that its address stays the same even if the struct is moved? We could .reserve a dynamic array in initialize() to prevent it being resized. Thanks again. Bastiaan.
Feb 07 2017
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 02/07/2017 02:04 PM, Bastiaan Veelo wrote:

 This optimization cannot work if the array is a static array inside
 the same struct. It would work with a dynamic array but then it would
 probably be slower than applying the *(ptr+index) technique.
You mean slower than the _payload[index - first] technique? Is that because of heap memory versus stack memory?
Mandatory disclaimer: We can't be sure without testing. Not exactly because stack versus heap because the whole object might be sitting in heap memory anyway: alias S = StaticArray!(/* ... */); S[] objects; objects ~= S(/* ... */); So, all of those are on the heap. It's more about having everything at hand, near each other, close in memory. If the member is a static array, then when we have an S[], all members are there to be operated on. If the array in dynamic, then an S[] has indirections, reaching out to the heap, which may involve long-latency memory reads. foreach (s; objects) { s[42]; // May have a cache miss and read from memory } In the static array case, the entire body of s is already on the cache. On the other hand, when the objects are large, then few of those can fit in the cache. etc. One needs to profile to see what works better.
 Am I correct that the reason that a dynamic array would work is because
 it is allocated independently from the struct, meaning that its address
 stays the same even if the struct is moved?
Yes, that would be a requirement to prevent the self-reference.
 We could .reserve a dynamic
 array in initialize() to prevent it being resized.
Makes sense. Another solution that came to my mind: You can keep the self-referencing solution but make sure that the objects are not moved after initialize(): S[] objects; objects.reserve(100); objects.each!(o => o.initialize()); // The objects will not move if you're careful
 Thanks again.
 Bastiaan.
Ali
Feb 07 2017
parent Bastiaan Veelo <Bastiaan Veelo.net> writes:
Wrapup: I am going to go for the original approach of index 
conversion, and leaving the offset-pointer approach for what it 
is.

Reasons:
1) uncertain efficiency gain/loss,
2) theoretically it may fail,
3) .sizeof does not include the payload,
4) analysis of the assembler generated by our reference compiler 
(Prospero) shows that it also uses index conversion. 
(Interestingly, it does so at compile time, when possible).

Thanks for many interesting insights.

Bastiaan.
Feb 08 2017
prev sibling parent WhatMeForget <kheaser gmail.com> writes:
On Saturday, 1 August 2015 at 09:35:53 UTC, DLearner wrote:
 Does the D language set in stone that the first element of an 
 array _has_ to be index zero?
 Wouldn't starting array elements at one avoid the common 
 'off-by-one' logic error, it does
 seem more natural to begin a count at 1.

 Actually, maybe even better to allow array definitions of form
 int foo[x:y];
 (y >= x) creating integer variables foo[x], foo[x+1],...,foo[y].

 I think the (very old) IBM PL/I language was like this.
There is a good metaphor in multi-story buildings. Americans number the first or ground floor of a high rise as floor #1. In the UK, their first floor is what Americans would call the 2nd floor. But then how can you trust a group of people who drive on the wrong side of the road :)
Feb 06 2017