Re: Xinok Sort Update
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.
Re: Xinok Sort Update
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.
Re: Xinok Sort Update
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.
Re: Xinok Sort Update
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?
Re: Xinok Sort Update
On 10/29/2011 7:19 PM, Vladimir Panteleev wrote: On Sun, 30 Oct 2011 01:56:23 +0300, Timon Gehr 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.
Re: Xinok Sort Update
On Sun, 30 Oct 2011 01:56:23 +0300, Timon Gehr 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, Vladimirmailto:vladi...@thecybershadow.net
Re: Xinok Sort Update
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.
Re: Xinok Sort Update
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?
Re: Xinok Sort Update
On Sat, 29 Oct 2011 20:13:10 +0300, Xinok 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, Vladimirmailto:vladi...@thecybershadow.net
Re: Xinok Sort Update
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?
