I recently put some time into updating my implementation of xinok sort for D. Major changes include support for random-access ranges and custom predicates ("a>b"). You can download the new version here:

http://sourceforge.net/projects/xinoksort/files/D%202.0/2011-10-29/xinoksort.d/download

For those that are unaware, I posted about a new sorting algorithm a few weeks ago. Xinok sort is a *stable* sorting algorithm with good performance while only requiring a small amount of constant additional memory.

The current stable sort in Phobos is broken and much slower, so I hope to contribute my algorithm to Phobos. But I'm new to this, so I'm not really sure of all what I need to do. I would appreciate if a few people could review my code and suggest any changes or improvements, as well as test for bugs.

On 10/29/2011 07:13 PM, Xinok wrote:
> I recently put some time into updating my implementation of xinok sort
> for D. Major changes include support for random-access ranges and custom
> predicates ("a>b"). You can download the new version here:
>
> http://sourceforge.net/projects/xinoksort/files/D%202.0/2011-10-29/xinoksort.d/download
>
>
> For those that are unaware, I posted about a new sorting algorithm a few
> weeks ago. Xinok sort is a *stable* sorting algorithm with good
> performance while only requiring a small amount of constant additional
> memory.
>
> The current stable sort in Phobos is broken and much slower, so I hope
> to contribute my algorithm to Phobos. But I'm new to this, so I'm not
> really sure of all what I need to do. I would appreciate if a few people
> could review my code and suggest any changes or improvements, as well as
> test for bugs.

Looks good =). Thank you. How does this implementation of your algorithm compare to the the unstable sort that is currently in Phobos, performance wise?

One comment:

while(temp is null){
	try temp.length = len;
	catch(Exception err){ // Reduce memory usage and try again
		len /= 2;
		if(len >= 8) continue;
		else throw err;
	}
}

temp.length = len cannot throw an Exception.
I think you are trying to catch an OutOfMemoryError here?

On Sat, 29 Oct 2011 20:13:10 +0300, Xinok <xinok@live.com> wrote:

> The current stable sort in Phobos is broken and much slower, so I hope to contribute my algorithm to Phobos. But I'm new to this, so I'm not really sure of all what I need to do.

The best way to contribute to Phobos is to fork the Phobos GitHub repository, integrate your algorithm into your forked version, then create a pull request. Don't forget to include appropriate unit tests.

https://github.com/D-Programming-Language/phobos

http://prowiki.org/wiki4d/wiki.cgi?PullRequest

-- 
Best regards,
 Vladimir                            mailto:vladimir@thecybershadow.net

On 10/29/2011 5:53 PM, Timon Gehr wrote:
>
> Looks good =). Thank you. How does this implementation of your algorithm
> compare to the the unstable sort that is currently in Phobos,
> performance wise?

I posted some benchmarks here. These benchmarks used the specialized code for arrays. There would likely be a larger gap when using ranges.
https://sourceforge.net/p/xinoksort/blog/2011/10/another-update--benchmarks/

> One comment:
>
> while(temp is null){
> try temp.length = len;
> catch(Exception err){ // Reduce memory usage and try again
> len /= 2;
> if(len >= 8) continue;
> else throw err;
> }
> }
>
> temp.length = len cannot throw an Exception.
> I think you are trying to catch an OutOfMemoryError here?

Yes I was. What should I do/use instead?

On 10/30/2011 12:19 AM, Xinok wrote:
> On 10/29/2011 5:53 PM, Timon Gehr wrote:
>>
>> Looks good =). Thank you. How does this implementation of your algorithm
>> compare to the the unstable sort that is currently in Phobos,
>> performance wise?
>
> I posted some benchmarks here. These benchmarks used the specialized
> code for arrays. There would likely be a larger gap when using ranges.
> https://sourceforge.net/p/xinoksort/blog/2011/10/another-update--benchmarks/
>

Ok, very nice.

>
>> One comment:
>>
>> while(temp is null){
>> try temp.length = len;
>> catch(Exception err){ // Reduce memory usage and try again
>> len /= 2;
>> if(len >= 8) continue;
>> else throw err;
>> }
>> }
>>
>> temp.length = len cannot throw an Exception.
>> I think you are trying to catch an OutOfMemoryError here?
>
> Yes I was. What should I do/use instead?

You could use catch(Error err) or catch(OutOfMemoryError err) or not catch the Error at all.

On Sun, 30 Oct 2011 01:56:23 +0300, Timon Gehr <timon.gehr@gmx.ch> wrote:

> You could use catch(Error err) or catch(OutOfMemoryError err) or not catch the Error at all.

Note that (IIRC) an OutOfMemoryError will be thrown only when:
1) There is no space on the managed heap
2) A garbage collection cycle failed to free enough memory for the requested allocation
3) The operating system could not allocate any more memory, even from swap.

Some operating systems (Windows) will even expand the swap file automatically when it nears being full.

I don't think that there's any point in doing anything sensible in an OutOfMemory handler.

-- 
Best regards,
 Vladimir                            mailto:vladimir@thecybershadow.net

On 10/29/2011 7:19 PM, Vladimir Panteleev wrote:
> On Sun, 30 Oct 2011 01:56:23 +0300, Timon Gehr <timon.gehr@gmx.ch> wrote:
>
>> You could use catch(Error err) or catch(OutOfMemoryError err) or not
>> catch the Error at all.

I'll use OutOfMemoryError. If any other error occurs, it's probably best to let the function fail.

> Note that (IIRC) an OutOfMemoryError will be thrown only when:
> 1) There is no space on the managed heap
> 2) A garbage collection cycle failed to free enough memory for the
> requested allocation
> 3) The operating system could not allocate any more memory, even from swap.
>
> Some operating systems (Windows) will even expand the swap file
> automatically when it nears being full.
>
> I don't think that there's any point in doing anything sensible in an
> OutOfMemory handler.
>

32-bit processes on Windows can only have up to 2GiB of addressable memory. Even if there's enough "available" memory, there may not be a large enough area of contiguous free space. I've gotten out of memory errors when working in D.

I handle the error because I can. My algorithm doesn't require any minimum amount of memory to be allocated, so I can reduce the memory usage for a small loss in performance.

Hey there.

Thanks for your good work.

I decided to test your xinok sort in my implementation of the A* algorithm; since the list of open nodes will always be partially sorted, it should give better performance than the phobos sort.

/Max

On 10/30/2011 12:19 AM, Xinok wrote:
> On 10/29/2011 5:53 PM, Timon Gehr wrote:
>>
>> Looks good =). Thank you. How does this implementation of your algorithm
>> compare to the the unstable sort that is currently in Phobos,
>> performance wise?
>
> I posted some benchmarks here. These benchmarks used the specialized
> code for arrays. There would likely be a larger gap when using ranges.
> https://sourceforge.net/p/xinoksort/blog/2011/10/another-update--benchmarks/
>
>
>> One comment:
>>
>> while(temp is null){
>> try temp.length = len;
>> catch(Exception err){ // Reduce memory usage and try again
>> len /= 2;
>> if(len >= 8) continue;
>> else throw err;
>> }
>> }
>>
>> temp.length = len cannot throw an Exception.
>> I think you are trying to catch an OutOfMemoryError here?
>
> Yes I was. What should I do/use instead?

On 10/30/2011 09:52 AM, Max Wolter wrote:
> Hey there.
>
> Thanks for your good work.
>
> I decided to test your xinok sort in my implementation of the A*
> algorithm; since the list of open nodes will always be partially sorted,
> it should give better performance than the phobos sort.
>
> /Max
>

You might want to consider using a heap to maintain the list of open nodes instead.

On 10/29/2011 1:13 PM, Xinok wrote:
> I recently put some time into updating my implementation of xinok sort
> for D. Major changes include support for random-access ranges and custom
> predicates ("a>b"). You can download the new version here:
>
> http://sourceforge.net/projects/xinoksort/files/D%202.0/2011-10-29/xinoksort.d/download

I'm working on adapting the code to work at compile time. I found out about the variable, __ctfe, so I can bypass the try / catch statement. But it can't be used in a compile-time specific manner, such as in a static if.

The implementation for ranges works just fine at compile time, but the implementation for arrays doesn't (it makes heavy use of pointers). I'm not sure how I could rewrite it to use only ranges at compile time.