www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Failed to sort range

reply "Sergei Nosov" <sergei.nosov gmail.com> writes:
Hi!

I'm trying to implement an array, which uses malloc to allocate 
memory. Also, I want to implement a random access range interface 
for it.

That went pretty well, until I tried to sort it. Sorting function 
asserted "Failed to sort range of type Array!(int)."

I've spent quite some time trying to figure out what's going on 
with no success.

The implementation can be found at:
https://gist.github.com/snosov1/5662471

I used
DMD64 D Compiler v2.062 and
LDC - the LLVM D compiler (trunk): based on DMD v2.062 and LLVM 
3.2svn
on Ubuntu. Phobos version was the one that came with the dmd 
compiler.

Does anyone have any ideas what's wrong with the code I've 
provided?
May 28 2013
next sibling parent "Sergei Nosov" <sergei.nosov gmail.com> writes:
On Tuesday, 28 May 2013 at 12:57:12 UTC, Sergei Nosov wrote:
 Hi!

 I'm trying to implement an array, which uses malloc to allocate 
 memory. Also, I want to implement a random access range 
 interface for it.

 That went pretty well, until I tried to sort it. Sorting 
 function asserted "Failed to sort range of type Array!(int)."

 I've spent quite some time trying to figure out what's going on 
 with no success.

 The implementation can be found at:
 https://gist.github.com/snosov1/5662471

 I used
 DMD64 D Compiler v2.062 and
 LDC - the LLVM D compiler (trunk): based on DMD v2.062 and LLVM 
 3.2svn
 on Ubuntu. Phobos version was the one that came with the dmd 
 compiler.

 Does anyone have any ideas what's wrong with the code I've 
 provided?
Forgot to mention, that my hand-made sorting function (simply a copy-paste of some quicksort implementation that uses array indexing syntax) works just fine void qSort(alias less, Range)(Range A, int low, int high) { int i = low; int j = high; auto x = A[(low+high)/2]; do { while(less(A[i], x)) ++i; while(less(x, A[j])) --j; if(i <= j){ auto temp = A[i]; A[i] = A[j]; A[j] = temp; i++; j--; } } while(i < j); if(low < j) qSort!less(A, low, j); if(i < high) qSort!less(A, i, high); }
May 28 2013
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Sergei Nosov:

 That went pretty well, until I tried to sort it. Sorting 
 function asserted "Failed to sort range of type Array!(int)."
If you take a look a the implementation of Phobos sort, you see there is a recently added runtime test mostly meant to catch wrongly implemented comparison functions, like q{a <= b} instead of q{a < b}. Maybe that's the one that has fired. But I don't know why. Bye, bearophile
May 28 2013
parent "Sergei Nosov" <sergei.nosov gmail.com> writes:
On Tuesday, 28 May 2013 at 13:41:19 UTC, bearophile wrote:
 Sergei Nosov:

 That went pretty well, until I tried to sort it. Sorting 
 function asserted "Failed to sort range of type Array!(int)."
If you take a look a the implementation of Phobos sort, you see there is a recently added runtime test mostly meant to catch wrongly implemented comparison functions, like q{a <= b} instead of q{a < b}. Maybe that's the one that has fired. But I don't know why. Bye, bearophile
I don't think that is the case, since I use the default comparison function for ints.
May 28 2013
prev sibling next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/28/2013 05:57 AM, Sergei Nosov wrote:
 Hi!

 I'm trying to implement an array, which uses malloc to allocate memory.
 Also, I want to implement a random access range interface for it.

 That went pretty well, until I tried to sort it. Sorting function
 asserted "Failed to sort range of type Array!(int)."

 I've spent quite some time trying to figure out what's going on with no
 success.

 The implementation can be found at:
 https://gist.github.com/snosov1/5662471

 I used
 DMD64 D Compiler v2.062 and
 LDC - the LLVM D compiler (trunk): based on DMD v2.062 and LLVM 3.2svn
 on Ubuntu. Phobos version was the one that came with the dmd compiler.

 Does anyone have any ideas what's wrong with the code I've provided?
1) First, an observation: This Array design conflates the concepts of container and range. If there are actual elements that are being stored (as opposed to elements being generated), it is better tha a range merely provides access to those elements. popFront should consume the range, not the container. (Unless it is some special type of range with the responsibility of removing elements from the container.) 2) As a minor comment, "back" usually means the last element but your back_ has the meaning of one-past-the-last element. 3) You have to rethink the indexing as well. opIndex indexes directly on vec_: ref T opIndex(size_t idx) { return vec_[idx]; } However, we may be on a slice which has already been sliced before (as is the case in quick sort, which SwapStrategy.unstable uses). So, I think opIndex should add front_ to idx: ref T opIndex(size_t idx) { return vec_[front_ + idx]; } It is a start but still not the solution. Sorry... :/ Ali
May 28 2013
parent reply "Sergei Nosov" <sergei.nosov gmail.com> writes:
Thx, Ali!

 1) First, an observation: This Array design conflates the 
 concepts of container and range. If there are actual elements 
 that are being stored (as opposed to elements being generated), 
 it is better tha a range merely provides access to those 
 elements. popFront should consume the range, not the container. 
 (Unless it is some special type of range with the 
 responsibility of removing elements from the container.)
I'm not sure I understand this correctly. Do you mean it's a good idea to separate storage and access (via range) to the container? Like std.container's containers (heh) have nested Range struct?
 2) As a minor comment, "back" usually means the last element 
 but your back_ has the meaning of one-past-the-last element.
Yeah, that's probably a not-so-good name.
 3) You have to rethink the indexing as well. opIndex indexes 
 directly on vec_:

     ref T opIndex(size_t idx) {
         return vec_[idx];
     }

 However, we may be on a slice which has already been sliced 
 before (as is the case in quick sort, which 
 SwapStrategy.unstable uses). So, I think opIndex should add 
 front_ to idx:

     ref T opIndex(size_t idx) {
         return vec_[front_ + idx];
     }

 It is a start but still not the solution. Sorry... :/
That's obviously a bug, thanks. But, yeah, not the last one =) I updated the gist. And also, replaced the malloc call with new. The behavior is the same.
May 28 2013
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/28/2013 11:19 AM, Sergei Nosov wrote:

 Do you mean it's a good idea
 to separate storage and access (via range) to the container? Like
 std.container's containers (heh) have nested Range struct?
Yes, that is generally the right approach. Note that built-in arrays have a similar design which may not be obvious: The storage is in an array that is owned by the D runtime. (The exception is fixed-length arrays where the entire array may be on the stack.) Then, the elements are accessed by slices, which are ranges. Consuming the slice does not invalidate the consumed elements (as long as there are other accesses to those elements.)
     ref T opIndex(size_t idx) {
         return vec_[front_ + idx];
     }

 It is a start but still not the solution. Sorry... :/
That's obviously a bug, thanks. But, yeah, not the last one =)
property Array!T opSlice(size_t i, size_t j) { // ... ret.front_ = i; I feel like the initialization of front_ above is not right either. Imagine quick sort where we are slicing the right-hand side of a range as [0..10], which has already been sliced before. Setting front_ to 0 would be wrong because then opIndex would still be counting from the beginning of the original elements. Ali
May 28 2013
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/28/2013 11:31 AM, Ali Çehreli wrote:

       property Array!T opSlice(size_t i, size_t j) {
          // ...
          ret.front_ = i;

 I feel like the initialization of front_ above is not right either.
 Imagine quick sort where we are slicing the right-hand side of a range
 as [0..10], which has already been sliced before. Setting front_ to 0
 would be wrong because then opIndex would still be counting from the
 beginning of the original elements.
My explanation is wrong but I think there is still a bug. Imagine we are in the right-hand range that has been sliced as [10..$]. Now front_ is 10 and all is good: s[0] provides the arr[10] of the original array. Now imagine our slice again by [5..$]. s_further[0] should provide arr[15] of the original array but your setting front_ to 5 would unfortunately provide arr[5]. Ali
May 28 2013
parent "Sergei Nosov" <sergei.nosov gmail.com> writes:
On Tuesday, 28 May 2013 at 18:38:01 UTC, Ali Çehreli wrote:
 On 05/28/2013 11:31 AM, Ali Çehreli wrote:

       property Array!T opSlice(size_t i, size_t j) {
          // ...
          ret.front_ = i;

 I feel like the initialization of front_ above is not right
either.
 Imagine quick sort where we are slicing the right-hand side
of a range
 as [0..10], which has already been sliced before. Setting
front_ to 0
 would be wrong because then opIndex would still be counting
from the
 beginning of the original elements.
My explanation is wrong but I think there is still a bug. Imagine we are in the right-hand range that has been sliced as [10..$]. Now front_ is 10 and all is good: s[0] provides the arr[10] of the original array. Now imagine our slice again by [5..$]. s_further[0] should provide arr[15] of the original array but your setting front_ to 5 would unfortunately provide arr[5]. Ali
Yes, exactly. I believe, the same fix should be applied here: front_ + i, front_ + j. It passes the sorting test. Thank you so much, Ali. Feels like to be back in school again.
May 28 2013
prev sibling parent reply "Anthony Goins" <neontotem gmail.com> writes:
On Tuesday, 28 May 2013 at 12:57:12 UTC, Sergei Nosov wrote:
 Hi!

 I'm trying to implement an array, which uses malloc to allocate 
 memory. Also, I want to implement a random access range 
 interface for it.

 That went pretty well, until I tried to sort it. Sorting 
 function asserted "Failed to sort range of type Array!(int)."

 I've spent quite some time trying to figure out what's going on 
 with no success.

 The implementation can be found at:
 https://gist.github.com/snosov1/5662471

 I used
 DMD64 D Compiler v2.062 and
 LDC - the LLVM D compiler (trunk): based on DMD v2.062 and LLVM 
 3.2svn
 on Ubuntu. Phobos version was the one that came with the dmd 
 compiler.

 Does anyone have any ideas what's wrong with the code I've 
 provided?
sort!("a<b", SwapStrategy.stable)(arr); This worked for me with the code at your link. Of course it does not answer your real question. But it is a place to start looking. (assuming you aren't miles ahead of me already.)
May 28 2013
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/28/2013 12:47 PM, Anthony Goins wrote:

 sort!("a<b", SwapStrategy.stable)(arr);

 This worked for me with the code at your link.
I've noticed that too. The reason that works is because in that case it uses Tim Sort. Apparently, the Tim Sort algorithm does not expose the bugs that were in the code. Ali
May 28 2013
parent "Sergei Nosov" <sergei.nosov gmail.com> writes:
On Tuesday, 28 May 2013 at 20:43:32 UTC, Ali Çehreli wrote:
 On 05/28/2013 12:47 PM, Anthony Goins wrote:

 sort!("a<b", SwapStrategy.stable)(arr);

 This worked for me with the code at your link.
I've noticed that too. The reason that works is because in that case it uses Tim Sort. Apparently, the Tim Sort algorithm does not expose the bugs that were in the code. Ali
I believe the issues with opIndex and opSlice caused the bug. Now, those are fixed, and I guess it's safe to say that range interface is correct. Although, I remember a discussion in the NG about somewhat "standardized" testing facilities for ranges ( http://forum.dlang.org/thread/20130321130858.00003ef4 unknown ). Precisely the semantic/runtime behavior, to supplement isSomeRange templates family. Do you, guys know, was there any activities on it?
May 28 2013