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?

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);
}

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

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.

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

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.

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

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

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.

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.)