Dear JoshyFun ,

(A)

An "algorithm" ( http://en.wikipedia.org/wiki/Algorithm ) and its "implementation" are different concepts , at least in the sense that , for an algorithm there may be many distinct implementations of it .

(B)

"RPSORT" program itself is written in 16-bit 8086 assembler but its bit size is not related to the file size it sorts .

(C)
Personally , I am not writing assembler programs , and I do not know 32-bit assembly programming .
Therefore , I am not able to convert it to a 32-bit assembly program .
I think a programmer fluent in assembly language programming can do it . I am not able to evaluate its difficultyness but it is my opinion that many statements may be converted by replace operations .

After this it may be used as embedded into a Pascal procedure or may be used as a spawned process to sort a file .

(D)
To make a proper reply to your question I prepared a simple program compiled with FPC
to demonstrate its sorting speed as follows :

Program Numbers ;
Var T : Text ;
Var M : LongInt ;
Var i : LongInt ;
Var p : Int64 ;
Var q : Int64 ;
Begin
M := 0 ;
Writeln ( 'Give number of values to generate :' ) ;
Readln ( M ) ;

If ( M > 0 )
Then

    Begin

Assign ( T , 'RNumbers.TXT' ) ;
ReWrite ( T ) ;
p := 9223372036854775807 ;
For i := 1 to M
Do
  Begin
  q := Random ( p )  ;
  Writeln ( T , q : 20 ) ;
  End ;
Close ( T ) ;
    End
Else
    Begin
    Writeln ( 'Given value : ' , M , ' is NOT greater than zero .' ) ;
    End ;

End .

Times are obtained in a PC
with Intel Pentium 4 CPU 3.00 GHz
2 GB Memeory
and Windows XP Home Edition .

(E)

For each value of M as number of records ,
the following command has been applied :

rpsort < rnumbers.txt > snumbers.txt

The RPSORT.COM is reporting the time used for sorting which I checked by an actual clock and I have found them to be correct .

The results are as follows :

Number of records File size Time required for sorting as given for M as MegaBytes as Hour : Minute : Second . ------------------ ------------- ---------------------------

10 000 0.214 00 : 00 : 00.11 ( + Six program working )
100 000 2.2 00 : 00 : 01.43 ( + Six program working )
1 000 000 22.0 00 : 00 : 17.19 ( + Six program working )
5 000 000 110.0 00 : 01 : 36.61 ( + Six program working )
10 000 000 220.0 00 : 03 : 21.41 ( + Six program working )

only + Command Prompt working :

5 000 000 110.0 00 : 01 : 11.24 10 000 000 220.0 00 : 02 : 28.41 25 000 000 550.0 00 : 06 : 29.47 100 000 000 2200.0 Locked :

I think file size should be less than 2147.0
MegaBytes ,
because of 32-bit MaxInt size ( 2 147 ... ... ) .
It is locked after 2053 MegaBytes of its
temporary file
left behind after its locking .

90 000 000 1980.0 01 : 32 : 45.98

When M = 10 000 000 :

snumbers.txt which is already sorted
is sorted as

rpsort < snumbers.txt > tnumbers.txt

in time 00 : 01 : 50.84 .

snumbers.txt which is already sorted in ascending order is sorted in descending order as

rpsort /R < snumbers.txt > tnumbers.txt

in time 00 : 01 : 50.35 .

(F)
It is possible to generate multiple column files and test it for multiple sort keys .
Details may be found in its documentation .

Thank you very much ,

Mehmet Erol Sanliturk

If you really need the speed you should learn assembler programming. It is not that hard (at least for small programs like this sort).

Assembler is not portable. So you need a different implementation for every plattform that fpc supports. If you just need x86 support then the sort programm should be part of your project and not of fpc in general. IMHO there is not much gain by including an assembly code sort in fpc.

Hello Mehmet,

Tuesday, August 26, 2008, 7:35:00 AM, you wrote:

MES> (A)
MES> An "algorithm" ( http://en.wikipedia.org/wiki/Algorithm ) MES> and its "implementation" are different concepts , at least MES> in the sense that , for an algorithm there may be many MES> distinct implementations of it .

Yes, you are right, but a good implementation of the same algorithm does not provide a big bunch of gain usually. Different algorithms are great for different sort tasks and QuickSort is, maybe, the best for the general case.

MES> (B)
MES> "RPSORT" program itself is written in 16-bit 8086 assembler MES> but its bit size is not related to the file size it sorts .

Yes, but it matters in how it handle the data, as it can not deal with more than 64 KB in each bunch, also you should not mix 16 bit and 32 bit assembler if possible. Anyway porting it to 32 bits (the algorithm implementation, not the full code) should be quite easy.

MES> (C)
MES> Personally , I am not writing assembler programs , and MES> I do not know 32-bit assembly programming .
MES> Therefore , I am not able to convert it to a 32-bit MES> assembly program .
MES> I think a programmer fluent in assembly language programming MES> can do it . I am not able to evaluate its difficultyness but MES> it is my opinion that many statements may be converted by replace MES> operations .
MES> After this it may be used as embedded into a Pascal procedure or MES> may be used as a spawned process to sort a file .

The problem is that assembler is not portable. Also a 32 bit pure Pascal implementation should be even faster than RPSRT.

MES> (D)
MES> To make a proper reply to your question I prepared a simple program MES> compiled with FPC
MES> to demonstrate its sorting speed as follows :

Great, as both have the same computer ;) except that I have 1 GB. So I wrote a routine to sort it (the 10 000 000 lines file) with Lazarus using the already provided primitives, nothing special programmed. I had used your program to generate the test file.

After 4 runs the average time to sort the file:

Number of records File size Temporal Time required for as given for M as MegaBytes disk space sorting HH:MMM:SS ------------------ ------------- ---------- ----------------- 10 000 000 220.0 0.00 00:03:18 5 000 000 110.0 0.00 00:01:23

--------------------------------------------------
procedure TForm1.Button1Click(Sender: TObject);
var
  L: TStringList;
  StartTime: TDateTime;
begin
  StartTime:=Now;
  L:=TStringList.Create;
  L.LoadFromFile('G:\RNumbers.txt');
  L.Sort;
  L.SaveToFile('G:\sorted.txt');
  L.Free;
  self.Caption:=TimeToStr(Now-StartTime);
end;
--------------------------------------------------

It does not beat RPSRT, so I decided to optimize it a bit, preparing the TStringList to receive 20 million lines at least, which preallocate 20 million pointer positions, and not freeing the memory as the OS will do it in one step.

Number of records File size Temporal Time required for as given for M as MegaBytes disk space sorting HH:MMM:SS ------------------ ------------- ---------- ----------------- 10 000 000 220.0 0.00 00:02:53 5 000 000 110.0 0.00 00:01:18

--------------------------------------------------
procedure TForm1.Button1Click(Sender: TObject);
var
  L: TStringList;
  StartTime: TDateTime;
begin
  StartTime:=Now;
  L:=TStringList.Create;
  L.Capacity:=20000000;
  L.LoadFromFile('G:\RNumbers.txt');
  Beep;
  L.Sort;
  Beep;
  L.SaveToFile('G:\sorted.txt');
  Beep;
  self.Caption:=TimeToStr(Now-StartTime);
  L.Free; //Free time is not counted as RPSRT will not free 20 million pointers.
end;
--------------------------------------------------

Also disk write is not optimized in any way, so it could mean (not checked in the code) 5/10 million writes to disk.

This code quite sure will explode with 2 Gigabytes file, and will take ages to complete

MES> Number of records File size Time required for sorting MES> as given for M as MegaBytes as Hour : Minute : Second . MES> ------------------ ------------- --------------------------- MES> only + Command Prompt working :
MES> 5 000 000 110.0 00 : 01 : 11.24 MES> 10 000 000 220.0 00 : 02 : 28.41 MES> 25 000 000 550.0 00 : 06 : 29.47

MES> 100 000 000 2200.0 Locked : MES> I think file size should be less than 2147.0 MES> MegaBytes ,
MES> because of 32-bit MaxInt size ( 2 147 ... ... ) . MES> It is locked after 2053 MegaBytes of its MES> temporary file
MES> left behind after its locking . MES> 90 000 000 1980.0 01 : 32 : 45.98

Yes, 2 gigabytes will be a serious problem to RPSRT due file access routines, remember it is a DOS program.

I'll perform the tests for 90 and 100 millions this night, I do not want to spend near 2 hours looking to the screen :)

MES> (F)
MES> It is possible to generate multiple column files and MES> test it for multiple sort keys .
MES> Details may be found in its documentation .

The multiple keys for sorting is defined in the implementation of the "checkorder" of QS function, it is mostly "trivial" to add them to a quicksort implementation in a hardcoded function. Writting the function in a dynamic definition way is a bit more complex, but the penalty for both Lazarus and RPSRT would be almost the same.

MES> Thank you very much ,

Thank you.