How to swap pointers?

Question

How can I efficiently swap pointers in Delphi? I am trying to exchange pointers for integer type. The following example works however I2 is 0 when compiled with 64 bit.

program Project11;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils;

procedure Swap(const P1, P2);
asm
{$if defined(CPUX86)}
  xchg ecx, [eax]
  xchg ecx, [edx]
  xchg [eax], ecx
{$else}
  xchg rcx, [rax]
  xchg rcx, [rdx]
  xchg [rax], rcx
{$endif}
end;

var
  I1, I2: Integer;

begin
  I1 := 19;
  I2 := 564;

  WriteLn('Swapping..');

  WriteLn('I1: '+I1.ToString());
  WriteLn('I2: '+I2.ToString());

  Swap(I1, I2);

  WriteLn('I1: '+I1.ToString());
  WriteLn('I2: '+I2.ToString());

  ReadLn;
end.

Ibex

Implementing a swap routine in asm won't give any noticeable performance boost over just using a locale temp variable. And if you want thread safety you can use TInterlocked.Exchange. – Tmesis

@StefanGlienke Actually I would use LOCK XCHG – Ibex

Which is what TInterlocked.Exchange does ... but it also works on other platforms. – Tmesis

Answer 1

I do it like this:

type
  TGeneric = class
  public
    class procedure Swap<T>(var Left, Right: T); static;
  end;

class procedure TGeneric.Swap<T>(var Left, Right: T);
var
  temp: T;
begin
  temp := Left;
  Left := Right;
  Right := temp;
end;

This can be used to swap values of any type. A capability that will make any Java programmers weep! ;-)

The compiler produces pretty efficient code in my opinion. I don't think you need to worry about the compiler's ability to produce effective code to perform assignments.

For 32 bit with T = Pointer we have:

push ebx
mov ecx,[eax]
mov ebx,[edx]
mov [eax],ebx
mov [edx],ecx
pop ebx
ret 

For 64 bit with T = Pointer we have:

mov rax,[rcx]
mov r8,[rdx]
mov [rcx],r8
mov [rdx],rax
ret

FWIW, I'm not keen on your versions use of const parameters. The code in the question should use var. But the type safety of this generic version is of course preferable.

Clardy

That would work but it's not type safe. So I would avoid that. It's better to let the compiler find your errors where it can. – Clardy

Uhm. I don't call that efficient code. The ASM version would run around this. MOV is slower than XCHG. – Ibex

@Ibex What are your timings for that? – Clardy

4x MOV + 2x POP vs 3x XCHG do the math. :) – Ibex

Do you have timings? Counting ops doesn't measure actual runtime. I'd imagine that the bottle neck is the in reading of the memory. – Clardy

Besides MOV does a copy XCHG simply exchanges the pointers. – Ibex

@user xchg ecx, [eax] Notice the [eax]. That's a memory read and write. If you care about performance, time the code. Don't count op codes. – Clardy

In your xchg asm version I count 3 reads of main memory, and 3 writes to main memory. In the mov based version produced by the compiler, I count 2 reads and 2 writes. I do suggest that you do some benchmarking before you draw any conclusions. – Clardy

You can also use 1x XCHG + 2 MOV – Ibex

Did you do that timing experiment yet? – Clardy

I will time a quick sort with default and asm. Ill post it here. – Ibex

My very quick first benchmark shows the code in my answer to be around 5 times faster than the asm in the question. I'm swapping the values in arrays of length 5000. I do that 100000 times to get reasonable runtimes. If I can teach you anything it is that optimisation without benchmarking is not optimisation. If you optimise like that then do not be surprised if you find your optimised code slower than the original! – Clardy

Ah yes, pastebin.com/xk3fYV4e is faster than SwapPas. Consistently by about 300-500 ms. On 32 bit atleast. – Ibex

I'm swapping 32 bit integers in my test. I don't see the relevance of your pastebin. It will compile to the same code as my SwapPas. Bottom line is that I hope I've got across the message that timing and benchmarking is crucial. – Clardy

You were too fast with your assumption. This one is 20-50% faster on my Q6600 pastebin.com/75A756j4 – Ibex

I did not make any assumptions at all. All I said was that it was essential to profile. It seems that you've got the message which means I've done my job! That said, it seems odd for memory to be faster than registers. I trust you are building release build? – Clardy

Yes. Its faster in both builds. Obviously more in debug. – Ibex

That does surprise me but it's a perfect illustration of the point I am making – Clardy

Why using a class ? – Leatheroid

@Marus so that we can use a generic method – Clardy

Answer 2

David's answer is entirely the most sensible approach to solving the problem.

To explore why your code doesn't work however, note two things

• Integer is a 32-bit type for both x86 and x64
• In x64, arguments are passed (in order) to RCX, RDX, R8 and R9

When compiling for x86 your code works. When compiling for X64 you are assuming that arguments are being passed to RAX and RDX, (like x86's EAX, EDX) which is wrong. So your code should look like

  xchg rax, [rcx]
  xchg rax, [rdx]
  xchg [rcx], rax

You'll note that without changes this also fails - now both I1 and I2 are zero. This is because you've assumed that Integer is a 64-bit type, which, unlike pointers, it is not (and you are not doing any type checking whatsoever - see again the benefit's of David's solution). If you redefine :

var
  {$if defined(CPUX86)}
    I1, I2: Integer;
  {$else}
    I1, I2: Int64;    
  {$ifend}

Then suddenly everything works as expected. By now, it should also be clear why this is not the most elegant approach.

Preoccupy

I guess something along the lines of xchg eax, [rcx] xchg eax, [rdx] would do a 32 bit swap xchg [rcx], eax – Clardy

Would be better to use NativeInt. – Ibex

@Ibex Would be better to use something type safe. – Preoccupy

@DavidHeffernan Yes, but I assume OP wants to swap pointers (as the question indicates). The confusing part is the selection of a value type (Integer) to demonstrate the method rather than a reference type or a pointer (both of which are at least guaranteed to be NativeInt size for the given target platform). – Preoccupy

I guess instead of proposing Int64 we just switch to pointers and can do away with conditional code. Yes, choice of integer is weird. – Clardy