Hi,

In my tests, FPC 2.4.4 has much slower CompareMem than FPC 2.4.2, at least for some cases:

# with fpc 2.4.4
$ time ./compare_mem_test 100000000
real 0m7.795s
user 0m7.764s
sys 0m0.008s
# with fpc 2.4.2
$ time ./compare_mem_test 100000000
real 0m1.218s
user 0m1.216s
sys 0m0.000s

This uses CompareMem to compare vectors 3 x Single (12 bytes). As you can see, FPC 2.4.2 is > 6 times faster, so it's a noticeable slowdown (especially if this is a bottleneck of your algorithm :). This is on Linux, i386 (32 bit).

I'm attaching the sample compare_mem_test.lpr, just compile by "fpc compare_mem_test.lpr".

I did some tests. In FPC 2.4.4 CompareMem equals to CompareByte. I tried using CompareWord, which is ~2 times faster, and CompareDWord, which is even better, but still --- even the best (CompareDWord) on FPC 2.4.4 is ~3 times slower than CompareMem on FPC 2.4.2.

Funny thing is, the fastest approach turned out to be the simplest one: compare by "(V1[0] = V2[0]) and (V1[1] = V2[1]) and (V1[2] = V2[2])". This is *much* faster than every other approach. (And yes, I tested that it wasn't optimized out :)

Any thoughts? Maybe something can be improved?

1. Why CompareMem got slower in FPC 2.4.4? Maybe something can be fixed?

2. The simple comparison "(V1[0] = V2[0]) and..." is much faster than any CompareXxx. Any chance of improving it? In this case, size is known at compile time, so maybe CompareXxx could be "magic" and (for reasonably small sizes) the compiler could just generate a proper code to compare them just like "=" operator? Just an idea of course, I don't know how easy it would be to actually implement.

Michalis

Michalis Kamburelis wrote

Any thoughts? Maybe something can be improved? 1. Why CompareMem got slower in FPC 2.4.4? Maybe something can be fixed?

Let's see...

CompareMem in 2.4.2:

=== source begin ===

function CompareMem(P1, P2: Pointer; Length: cardinal): Boolean;
var
   i: cardinal;
begin
   Result:=True;
   I:=0;
   If (P1)(P2) then
     While Result and (i<Length) do
       begin
       Result:=PByte(P1)^=PByte(P2)^;
       Inc(I);
       Inc(pchar(P1));
       Inc(pchar(P2));
       end;
end;

=== source end ===

CompareMem in 2.4.4:

=== source begin ===

function CompareMem(P1, P2: Pointer; Length: cardinal): Boolean;
begin
   Result:=CompareByte(P1^,P2^,Length)=0;
end;

=== source end ===

This at least explains why CompareMem behaves similar to CompareByte in your test :D

The CompareMem function is in unit SysUtils and I don't think it is a good idea to "magicalize" that unit.

Maybe it's better if you or someone else would try to improve the performance of the i386 assembler code that makes up the Compare(Byte/Word/DWord) functions (it's located in rtl/i386/i386.inc btw).

Regards,
Sven

02.06.2011 19:49, Sven Barth пишет:

Maybe it's better if you or someone else would try to improve the performance of the i386 assembler code that makes up the Compare(Byte/Word/DWord) functions (it's located in rtl/i386/i386.inc btw).

I tend to agree. The string instructions used there (rep cmpsb, etc.) are known to be not the fastest solution on modern x86 CPUs.

Sergei

Hello FPC,

Wednesday, June 1, 2011, 10:07:18 PM, you wrote:

MK> In my tests, FPC 2.4.4 has much slower CompareMem than FPC 2.4.2, at MK> least for some cases:

The difference is that CompareMem takes the same time to check a memory block if the elements are equal or different, while the pascal code aborts inmediatly after first difference.

I had performed a fast test filling 2 megabytes of memory, the first with value "1" and the second with value "2". Performing the test 10 millions times takes 610 milliseconds. In the second test fill both arrays with same value, and CompareMem takes 610 milliseconds.

After some tests (not very professional) CompareMem takes much more advantage if the amount of bytes to be compared are more than 32-38, so the best performance I get is using this function:

function XCompareByte(const p1,p2,Length: sizeInt): SizeInt;
var
  j: SizeInt;
  PB1: PBYTE absolute p1;
  PB2: PBYTE absolute p2;
begin
  if Length<=38 then begin
    for j := 0 to Length-1 do begin
      if pb1[j]PB2[j] then begin
        Result:=BYTE(PB1[j]-PB2[j]);
        exit;
      end;
    end;
    Result:=0;
  end else begin
    Result:=CompareByte(p1,p2,Length);
  end;
end;

In my computer Intel 9300 QCore WindowsXP this function get the best of the two worlds, fast comparison escape for different memory blocks, fast compare for small blocks and the "rep cmpsl" for larger blocks, performance that can not be achieved with the pascal loop. The comparison penalty if rapidly payed with the fast escape in case of differeces in the very first bytes.

I'm quite sure the magic number is 32 not 38, but in my case I get better performance with 38.

Simple test code:

procedure Comparememtest;
const
  COMPARELENGTH=1000;
var
  p1,p2: PBYTE;
  j: integer;
  ST,ET: TTimeStamp;
begin
  GetMem(p1,1000000);
  for j := 0 to 1000000-1 do begin
    p1[j]:=0;
  end;
  GetMem(p2,1000000);
  for j := 0 to 1000000-1 do begin
    p2[j]:=0;
  end;
  ST:=DateTimeToTimeStamp(Now);
  for j := 0 to 10000000 do begin
    XCompareByte(SizeInt(p1),SizeInt(p2),COMPARELENGTH);
  end;
  ET:=DateTimeToTimeStamp(Now);
  self.Caption:=inttostr(ET.Time-ST.Time);
  FreeMem(p1);
  FreeMem(p2);
end;

Times table:
PlainCompare CompareByte XCompareByte
------------ ----------- ------------
Equal arrays 1000 elements 16250 ms 625 ms 656 ms Diff. arrays 1000 elements 62 ms 640 ms 656 ms

Equal arrays 32 elements 547 ms 625 ms 547 ms Diff. arrays 32 elements 62 ms 640 ms 62 ms

I improved the original CompareByte, please tell me how it works for you.

Hello FPC,

Wednesday, June 1, 2011, 10:07:18 PM, you wrote:

MK> In my tests, FPC 2.4.4 has much slower CompareMem than FPC 2.4.2, at MK> least for some cases:

Please take care with my last email, it has a bug that result in wrong speed tests, anyway after fixing the bug, the "magic" number for plain compare is around 28-32, so for blocks of 28-32 or less bytes, a plain compare is much faster than CompareMem even when the memory blocks are identical.

Hello FPC,

Thursday, June 2, 2011, 7:03:10 PM, you wrote:

FK> Am 02.06.2011 18:45, schrieb José Mejuto:

FK> I improved the original CompareByte, please tell me how it works for you.

Much better now when arrays are identical it scales well...

Identical arrays
----------------
Comparemem 4 : 203
XCompareMem 4 : 109
CompareMemNew 4 : 94

Comparemem 32 : 453
XCompareMem 32 : 547
CompareMemNew 32 : 438

Comparemem 200 : 1125
XCompareMem 200 : 1156
CompareMemNew 200: 1125

Different arrays at first position
----------------------------------
Comparemem 4 : 293
XCompareMem 4 : 51
CompareMemNew 4 : 59

Comparemem 32 : 596
XCompareMem 32 : 51
CompareMemNew 32 : 59

Comparemem 200 : 593
XCompareMem 200 : 625
CompareMemNew 200: 609

Hello FPC,

FK> I improved the original CompareByte, please tell me how it works for you.

After a brief test, the same happends with FillByte for blocks of 24 bytes or less, probably 32 when coded in ASM.

FillByte
--------
FillByte 4 : 371
XFillByte 4 : 68

FillByte 16 : 235
XFillByte 16 : 172

FillByte 24 : 235
XFillByte 24 : 228

FillByte 32 : 235
XFillByte 32 : 292

Michalis Kamburelis wrote

Hi, In my tests, FPC 2.4.4 has much slower CompareMem than FPC 2.4.2, at least for some cases:

I've commited an improved version in r17642

That's great :) I just tested with fpc from SVN (rev 17644), and can confirm that CompareMem is much faster now. It beats CompareMem from both FPC 2.4.4 and FPC 2.4.2:

FPC 2.4.2: 2.635s
FPC 2.4.4: 16.803s
FPC trunk: 1.931s

Although it's still slightly slower than comparing directly with "(V1[0] = V2[0]) and ...", which is ~1.2s for all 3 FPC versions mentioned above. I guess there has to be some price for CompareMem being more general, and checking everyone,
Michalis

I improved CompareDWord as well, for your application it should be even better.

Florian Klämpfl wrote

I improved CompareDWord as well, for your application it should be even better.

Ha, I hesitated earlier to mention that CompareWord and CompareDWord are ~4 times slower than equivalent (on the same number of bytes) CompareMem/CompareByte calls :) Cool, times with latest FPC (rev 17651):

CompareMem: 1.928s
CompareWord: 1.270s
CompareDWord: 1.108s

These times directly help in my algorithm (I use it to aggressively search for pairs of matching edges for shadow volumes). Great!

Thanks,
Michalis

Is this merged in 2.4.5 ?

zeljko