pmcgee

Just wondering if anyone knows a ballpark figure for the "size" of (any of) the Delphi compilers?

On 8/24/2020 at 8:08 PM, Stefan Glienke said:

Leave implementing generic collections to people experienced with it (which I in no way claim to have monopoly on)

To be fair, there's a Catch-22 in that idea.   ie don't implement Generics until you have experience implementing Generics.

(and the same would apply for trying to use a c++ like move feature)

If someone publishes open source ... not part of a (reasonably big) commercial product like RAD ... and it is useful to maybe 80% of people, then sure it's valuable to point out edge cases - but it doesn't mean it should be discouraged.  We need *more* Delphi out there.  And more understanding of these elements that weren't even part of Delphi in say 2005.

On 12/1/2020 at 1:52 AM, Kas Ob. said:

 the fact you are using it on only AnsiStrings will reduce its usability a lot.

...

12! and waiting 15second is long time, shorter test bed will be nice

Sure ... byte / ansichar is a simple case ... but you need to start with simple and solve it the best you can before tackling a bigger / harder problem.

The testing is made faster by just using a shorter string.  The increase in time is about x10 at the 12 mark ... so 11 is quicker, and 10 is almost immediate.

8 hours ago, Kas Ob. said:

 if you already have Delphi code, then at least share the implementation, along with tests for correctness, and one or two benchmarks, many here can spot inefficient code or just suggest things that we all can benefit from.

I'm a little confused.  First post *is* the Delphi code.

I've been learning about C++ for a couple years, alongside 20 with Delphi, and the ideas from both are interesting to me.
Naively, it seems like a Delphi version should be able to produce about the same performance.  Teasing that out should be educational.

The calling code from c++ :

int main()
{
	const std::string Test = "abcdefghijkl";
	int i = 0;
	std::string v = Test;

	Timer timer;   
	timer.start();
	do    { ++i; }
	while ( std::next_permutation( v.begin(), v.end() ) );
	timer.stop();
          
	std::cout << "C++     " << i << "\n";
	std::cout << "Seconds: " << timer.elapsedSeconds() << std::endl;

	AnsiString s = Test.c_str();
	int len      = s.Length()+1;
	i = 0;

	Timer timer2;  
	timer2.start();
	do    { ++i; }
	while ( D_next_permutation(s, 1, len ) );
	timer2.stop();

	std::cout << "Delphi  " << i << "\n";
	std::cout << "Seconds: " << timer2.elapsedSeconds() << std::endl;

	getchar();
	return 0;

@Kas Ob.  posted this in the original thread :

procedure reverse2(var s: AnsiString; const a, x: word); inline;
var
  i, j: word;
  tmpChar: Byte;
  SBytes: pByte absolute s;
begin
  if a = x - 1 then
    exit;
  j := (x - a) shr 1;     //  trunc((x-a)/2);
  for i := 1 to j do
  begin
    tmpChar := SBytes[a - 1 + i];
    SBytes[a - 1 + i] := SBytes[x - i];
    SBytes[x - i] := tmpChar;
  end;
end;

var
  st: AnsiString;
  i: Integer;
  D: Uint64;

begin
  st := '1234567890ab';
  Writeln(st);
  d := GetTickCount;
  for i := 1 to 479001600 do           // 12!
    reverse(st, 1, 12);
  D := GetTickCount - D;
  Writeln(d);

  st := '1234567890ab';
  Writeln(st);
  d := GetTickCount;
  for i := 1 to 479001600 do
    reverse2(st, 1, 12);
  D := GetTickCount - D;
  Writeln(d);

  Readln;
end.

With these results ... (32 bit?  64 bit? compile)
1234567890ab
14125
1234567890ab
4891

I didn't recall correctly.  This was a significant speed up : 

procedure swapByte( a:Pbyte ; b:Pbyte );    inline;
begin
    if a <> b then begin
       a^ := a^ + b^;
       b^ := a^ - b^;
       a^ := a^ - b^ ;
    end;
end;

swapByte( @s[a-1+i] , @s[x_-i] );

A bit of a challenge ... to produce Delphi code equaling the performance of C++'s next_permutation.

Hopefully more readable in Delphi ... 

unit D_Next_perm_string;

interface

procedure             swapCh(var a:Ansichar; var b:Ansichar);
procedure            reverse(var s:AnsiString; const a,x:word);
function  D_next_permutation(var s:AnsiString; const first, end_:word) : boolean;

implementation
//uses System.Diagnostics;

procedure swapCh( var a : Ansichar; var b : Ansichar );   inline;
var c :  Ansichar;
begin
    if a<>b then begin
       c := a; a := b; b := c;
    end;
end;


procedure reverse(var s:AnsiString; const a,x:word);  inline;
var
    i,j : word;
    //t   : string;
begin                          //  x is one past the end of string
   if  a  = x-1 then exit;
   j     := ( x-a ) shr 1;     //trunc((x-a)/2);
   for i := 1 to j do
            swapCh( s[a-1+i] , s[x-i] );
end;


function  D_next_permutation(var s : AnsiString; const first, end_ : word) : boolean;   inline;
var
	i, ii, j : word;
begin
	if first  = end_  then begin result := false; exit; end;
	    i    := first + 1;
	if  i     = end_  then begin result := false; exit; end;
	    i    := end_  - 1;

	while true do begin
	     ii := i;  dec(i);

	     if s[i] < s[ii] then begin
	          j := end_;
	          repeat dec(j); until     s[i] < s[j];

	          swapCh( s[i] , s[j] );
	          reverse(s, ii, end_);
	          result := true;
	          exit;
	     end;

	     if i = first then begin
	          reverse(s, first, end_);
	          result := false;
	          exit;
	     end;
	end;
end;

end.

Ballpark, we're looking at about 6s vs 2s for s = "abcdefghijkl" (12 bytes).   Increases by about a factor of 10 per character beyond that.

Note the c++ end() iterator is **one past the end of string**, so ... D_next_permutation(s,1,13)

Maybe this is OT for this thread. I'll look up where to start a new one, and add a link.

8 hours ago, Kas Ob. said:

@pmcgee Thank you for sharing.

 

I tried this

{$APPTYPE CONSOLE}

end.

The result

What am i missing here ?

5 minutes ago, Kas Ob. said:

@pmcgee That swapCh caught my eye and signaled something wrong, would you care to share its implementation ?

 

I think it can be faster but that depends on that swapChar, s is var string and the compiler in many cases will introduce an overhead for handling it and passing it further.

While you care about the speed of 12! permutations operation, then can you check if this is faster

   for i := 1 to j do
     begin
       tmpChar := SBytes[a - 1 + i];
       SBytes[a - 1 + i] := SBytes[x - i];
       SBytes[x - i] := tmpChar;      
       //swapCh( s[a-1+i] , s[x-i] );
     end;

 

I had tried a couple things there ... this was a small improvement.  I haven't pulled apart the assembly code yet.  It's just an ongoing interest.    It'll be fun to try it with char/byte array.
 

procedure swapByte( a:Pbyte ; b:Pbyte );    inline;
begin
    if a <> b then begin
       a^ := a^ + b^;
       b^ := a^ - b^;
       a^ := a^ - b^ ;
    end;
end;

procedure swapChar( var a : Ansichar; var b : Ansichar );   inline;
var c :  Ansichar;
begin
    if a<>b then begin
       c := a; a := b; b := c;
    end;
end;

Just checking ... You can characterise one edge by one TPoint?  or one edge by 4 TPoints?  or does Fedges describe a parallelogram?

Is ok. "GEORect". I get it. (I'm not sure 'edges' is the best name) ... (also ... can't see how to delete posts.)

On 11/26/2020 at 7:08 PM, A.M. Hoornweg said:

The problem of having local variables of managed data types such as strings is that Delphi needs to guarantee that no memory leaks occur.  So there's always a hidden Try/Finally block in such methods that will "finalize" the managed variables and release any allocated heap space. That takes time to execute, even if there's no further "code" in the method.

 

I came across this trying to duplicate C++'s std::next_permutation using Delphi.  I went through various modifications, and had left a string declaration in where it was no longer needed:

procedure reverse(var s:AnsiString; const a,x:word);  inline;
var
    i,j : word;
    //t   : string;
begin                          //  x is one past the end of string
   if  a  = x-1 then exit;
   j     := ( x-a ) shr 1;     //  trunc((x-a)/2);
   for i := 1 to j do
            swapCh( s[a-1+i] , s[x-i] );
end;

All permutations of 12 chars = 479,001,600.  C++ = 2s.  Commenting out the string reduced the Delphi code from 9s to 6s.  (I haven't been back to it since then.)