www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - Xinok Sort - December 2011

reply Xinok <xinok live.com> writes:
I've released a few updates for my sorting algorithm in the past month.

https://sourceforge.net/projects/xinoksort/

Major changes:
* Added concurrency using taskPool
* Use any callable type as predicate (functions, delegates)
* Unittests
* Documentation
* Minor optimizations


I have a few more things I'd like to address before I do a pull request:

* Should I use the global 'taskPool', or a unique TaskPool object for 
concurrency?

* Is it possible to overload opDollar / __dollar at the moment? 
Otherwise, I'll replace the dollars with *.length instead.

* I can't figure out all the requirements to satisfy the condition, 
isRandomAccessRange!(). I've read through the documentation a few times 
but I'm still missing something. I've successfully tested the code for 
ranges on arrays, but not any class type.

class N(T){
	T[] arr;
	this(T[] other){ arr = other.save; }
	ref T opIndex(size_t i){ return arr[i]; }
	size_t length(){ return arr.length; }
	ref T front(){ return arr.front; }
	ref T back(){ return arr.back; }
	ref T popFront(){ arr.popFront(); }
	ref T popBack(){ arr.popBack(); }
	bool empty(){ return arr.empty; }
	N save(){ return new N(arr); }
}
static assert(isRandomAccessRange!(N!uint));
Nov 30 2011
next sibling parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
Add  property to front/back/popFront/popBack/empty/save.

Also popFront/popBack need to be void return type.
Nov 30 2011
next sibling parent Xinok <xinok live.com> writes:
On 11/30/2011 8:45 PM, Andrej Mitrovic wrote:

 Add  property to front/back/popFront/popBack/empty/save.

 Also popFront/popBack need to be void return type.


Thanks. I was missing  property, the void return type was a mistake.

After fixing some bugs, the code is working but the benchmarks are 
terrible. >.< This is the benchmark compared to Phobos unstable sort:

phobUSortArray: 256939
phobUSortRange: 664792
xinokSortArray: 323069
xinokSortRange: 2401659


Also a new problem, this is the primary code for concurrent sorting. It 
compiles just fine in release builds, but it doesn't compile in debug 
builds:

// Start threading
auto th = task!(findRunsT)(arr[0..mid], temp[0..temp.length/2]);
taskPool.put(th);
findRunsT(arr[mid..arr.length], temp[temp.length/2..temp.length]);
th.workForce();
// End threading

The compiler prints lots of errors stating several members are not 
accessible, for example:

C:\D\dmd2\windows\bin\..\..\src\phobos\std\parallelism.d(491): Error: 
class std.parallelism.TaskPool member tryDeleteExecute is not accessible
Nov 30 2011
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 30 Nov 2011 20:45:19 -0500, Andrej Mitrovic  
<andrej.mitrovich gmail.com> wrote:


 Add  property to front/back/popFront/popBack/empty/save.

 Also popFront/popBack need to be void return type.


popFront/popBack need not be  property.

-Steve
Dec 01 2011
parent =?UTF-8?B?QWxleCBSw7hubmUgUGV0ZXJzZW4=?= <xtzgzorex gmail.com> writes:
On 01-12-2011 14:26, Steven Schveighoffer wrote:

 On Wed, 30 Nov 2011 20:45:19 -0500, Andrej Mitrovic
 <andrej.mitrovich gmail.com> wrote:


 Add  property to front/back/popFront/popBack/empty/save.

 Also popFront/popBack need to be void return type.


 popFront/popBack need not be  property.

 -Steve


Anything that mutates the state of an object or does something that's 
significantly more expensive than retrieving a field should not be a 
property. This is something I still have gripes with in the language 
itself (see array.dup). I think it's completely broken that such design 
is encouraged.

- Alex
Dec 01 2011
prev sibling parent Xinok <xinok live.com> writes:
On 11/30/2011 8:23 PM, Xinok wrote:

 I've released a few updates for my sorting algorithm in the past month.

 https://sourceforge.net/projects/xinoksort/

 Major changes:
 * Added concurrency using taskPool
 * Use any callable type as predicate (functions, delegates)
 * Unittests
 * Documentation
 * Minor optimizations


Update (2011-12-02)

* Fix: Several bugs and other issues related to sorting ranges
* Fix: Use taskPool for release builds, Thread for debug builds
* Added unittest for ranges
* Merged all unittests into one unittest statement
* makeTemp now takes size_t rather than Range

The performance of ranges isn't as good as I hoped, but it's still 
significantly faster than Phobos stable sort. Now I'll work on 
implementing my code in std.algorithm and do a pull request when it's ready.

Benchmark on array of 16777216 uints
xinokSortArray: 6180865
xinokSortRange: 11515011
phobUSortArray: 4880857
phobUSortRange: 4514736 <- Why is sorting a range faster than an array?
phobSSortArray: 104081737
phobSSortRange: Failed to compile (many functions under std.algorithm 
use $ when slicing)
Dec 01 2011