Saturday, June 25, 2011

Sleep Sort in OTL

I found Sleep Sort so ingenious (in the mad genius way) that I just had to implement it using the OmniThreadLibrary framework.

The code is now shorter than Serg’s original implementation and it’s … wait for it, wait for it … even faster! Twice as fast as the original, actually! Now that I call an improvement!

The code below carries not copyright nor copyleft and can be used in any occasion as long as you don’t blame me for getting fired or any other problems in your personal or professional life it may cause.

Winking smile

program OTLSleepSort;

{$APPTYPE CONSOLE}

uses
SysUtils,
OtlSync, OtlTask, OtlTaskControl;

const
ArrLen = 16;


var

A : array[0..ArrLen - 1] of Integer;
I : Integer;
lock : IOmniCriticalSection;
sortGroup: IOmniTaskGroup;

begin
for I:= 0 to ArrLen - 1 do begin
A[I]:= Random(15);
Write(A[I]:3);
end;
Writeln;

sortGroup := CreateTaskGroup;
lock := CreateOmniCriticalSection;
for I:= 0 to ArrLen - 1 do
CreateTask(
procedure (const task: IOmniTask)
begin
Sleep(task.Param[0].AsInteger * 500);
task.Lock.Acquire;
Write(task.Param[0].AsInteger:3);
task.Lock.Release;
end
).SetParameter(A[I]).Join(sortGroup).WithLock(lock);
sortGroup.RunAll.WaitForAll;
Writeln;

Write('> ');
Readln;
end.

I know that using low-level OTL tools is not for everybody so I’ve also created a high-level version which is not only shorter but outputs elements in the main thread, as it should be, not in the worker threads as my first version and Serg’s implementation do (bleuch!). To run it successfully, you’ll need fresh OTL from the SVN (and I’m not kidding now) because I found a bug in Parallel.NumTasks while testing the sleep sort implementation below.

program OTLSleepSort2;

{$APPTYPE CONSOLE}

uses
SysUtils,
OtlCommon, OtlParallel, OtlCollections;

const
ArrLen = 16;
var
A : array[0..ArrLen - 1] of Integer;
I : Integer;
sorted : IOmniBlockingCollection;
sortedEl : TOmniValue;

begin
for I:= 0 to ArrLen - 1 do begin
A[I]:= Random(15);
Write(A[I]:3);
end;
Writeln;

sorted := TOmniBlockingCollection.Create;
Parallel.ForEach(0, ArrLen - 1).NumTasks(ArrLen).NoWait.Into(sorted).Execute(
procedure (const idx: integer; var result: TOmniValue)
begin
Sleep(A[idx] * 500);
result := A[idx];
end
);
for sortedEl in sorted do
Write(sortedEl.AsInteger:3);
Writeln;

Write('> ');
Readln;
end.

3 comments:

  1. Cool. I should say that though my implementation is twice as slow, it is more reliable (by the same time-based reason). ;)

    ReplyDelete
  2. Anonymous19:26

    Interestingly enough, with the latest SVN version the sorting is far from perfect if you change the line
    Sleep(A[idx] * 500);
    into
    Sleep(A[idx] * 50);
    Still more bugs?

    ReplyDelete
  3. And it breaks completely if you change sleep factor from 50 to 1. Which is not really surprising if you take a little time and think about how the sleep sort is working at all.

    ReplyDelete