www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - Xinok Sort Update

reply Xinok <xinok live.com> writes:
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.
Oct 29 2011
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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?
Oct 29 2011
next sibling parent reply Xinok <xinok live.com> writes:
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?
Oct 29 2011
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
Oct 29 2011
parent Xinok <xinok live.com> writes:
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.
Oct 29 2011
prev sibling parent reply Max Wolter <awishformore gmail.com> writes:
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?
Oct 30 2011
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
Oct 30 2011
parent Peter Alexander <peter.alexander.au gmail.com> writes:
On 30/10/11 10:36 AM, Timon Gehr wrote:

 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.



+1, you shouldn't ever need a sorting algorithm in an A* implementation.
Nov 20 2011
prev sibling parent "Vladimir Panteleev" <vladimir thecybershadow.net> writes:
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
Oct 29 2011
prev sibling next sibling parent "Vladimir Panteleev" <vladimir thecybershadow.net> writes:
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
Oct 29 2011
prev sibling parent Xinok <xinok live.com> writes:
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.
Oct 30 2011